Minimize a black-box convex function

A pricing service exposes a cost curve F(x) only through an expensive API call: each evaluation takes seconds. All you know is that F is convex on [a, b] (the chord between any two points on the curve lies on or above the curve). You need to find where the minimum is, while spending as few calls as possible.

Write minimize(evaluate, a: float, b: float, eps: float) -> float that returns a point x in [a, b] within eps of a minimiser of F:

• evaluate(x) returns F(x) for any a <= x <= b. Calling it outside [a, b] is an error.
• A convex function may be flat at the bottom, so it can have a whole interval [L, R] of minimisers (a single point is the case L == R). Your answer x must satisfy L - eps <= x <= R + eps, and also a <= x <= b.
• The minimum may sit at an end of the interval (for a function that only goes down or only goes up).
• Budget: you may call evaluate at most ceil(log_phi((b - a) / eps)) + 2 times, where phi = (1 + sqrt(5)) / 2 ≈ 1.618. If b - a <= 2 * eps the budget is 0: return the midpoint (a + b) / 2 without calling evaluate at all. The tests count.

minimize(lambda x: (x - 3) ** 2, 0.0, 10.0, 1e-6)            # about 3.0
minimize(lambda x: abs(x + 2) + abs(x - 2), -5.0, 5.0, 1e-6)  # anything in [-2, 2]
minimize(lambda x: 2 * x, -1.0, 1.0, 1e-6)                    # about -1.0 (the left end)

Constraints: a <= b, b - a <= 10^6, eps >= 1e-6, and F's values are well-conditioned for comparing (no precision tricks).

A method that spends two new calls per round to cut the interval to 2/3 keeps about 0.82 of it per call, which blows the budget.