Minimize a black-box convex function

You are given a black-box function F that is convex on a closed interval [a, b]. You cannot see its formula or its derivative. The only way to learn about it is to call evaluate(x), which returns F(x) for any x in [a, b]. Each call is expensive, so use as few as you can.

Implement:

def minimize(evaluate: Callable[[float], float], a: float, b: float, eps: float) -> float

Return a point x* in [a, b] with |x* - x_min| <= eps, where x_min is a point at which F attains its minimum on [a, b]. If F is constant along a whole stretch at the bottom, being within eps of any minimizer is enough.

Constraints

• F is convex on [a, b]. It may not be differentiable (for example |x - c|), and its minimum may be at an endpoint.
• eps > 0. The bounds may be given in either order, and a may equal b.
• Report how many times your solution calls evaluate. Expect follow-ups about an evaluation budget.

Example 1

F(x) = (x - 4)^2 + 1 on [0, 10] with eps = 0.001 → any value in [3.999, 4.001].

Example 2

F(x) = 3x + 7 on [-2, 6] with eps = 0.01 → any value in [-2, -1.99]. F is increasing, so the minimum is at the left endpoint.