Find minimum of unknown convex function

You are given access to an unknown univariate convex function $f(x)$ defined on a closed interval $[L, R]$ on the real line.

• You cannot see the analytical form of $f(x)$ .
• You are allowed to query the function at any point $x \in [L, R]$ and obtain the value $f(x)$ .
• You are told that $f(x)$ is convex and has a unique global minimum within $[L, R]$ .
• You have a strict budget of at most $K$ function evaluations (queries) and want to find the location of the minimum as accurately as possible.

Tasks:

1. Describe an algorithm that uses only function evaluations (no gradient information) to find the point where $f(x)$ attains its minimum on $[L, R]$ , under the convexity assumption.
2. Explain why gradient descent is not directly applicable when gradients or subgradients are not available, and why your proposed algorithm is suitable.
3. Analyze the time complexity in terms of the number of function evaluations needed to achieve an interval of uncertainty of length at most $\varepsilon$ containing the minimum.
4. Discuss how noise in the function evaluations (i.e., you observe $f(x) + \epsilon$ where $\epsilon$ is small random noise) would affect your method and what modifications, if any, you would make.

Clearly explain the intuition, the step-by-step procedure (including how you shrink the search interval each iteration), and provide pseudocode.