Find minimum of unknown convex function

You are provided with an unknown univariate convex function $f(x)$ whose domain is a closed interval $[L, R]$ on the real line.

• The analytical expression for $f(x)$ is hidden from you.
• You may evaluate the function at any point $x \in [L, R]$ and receive the value $f(x)$.
• You are also told that $f(x)$ is convex and has a unique global minimum inside $[L, R]$.
• Your budget is limited to at most $K$ function evaluations, and the goal is to locate the minimum as accurately as possible. Tasks:

1. Describe an algorithm that relies only on function evaluations (no gradient information) to find the point at which $f(x)$ reaches its minimum on $[L, R]$, assuming convexity.
2. Explain why gradient descent cannot be applied directly when gradients or subgradients are unavailable, and why the algorithm you propose is appropriate.
3. Analyze the time complexity, expressed as the number of function evaluations required to reduce the uncertainty interval containing the minimum to length at most $\varepsilon$.
4. Discuss how noisy function evaluations (that is, observing $f(x) + \epsilon$ where $\epsilon$ is small random noise) would affect your method, and what modifications, if any, you would introduce. Clearly explain the intuition, the step-by-step procedure (including how the search interval is shrunk in each iteration), and provide pseudocode. Overview: This question tests a candidate's grasp of convex optimization and zeroth-order (query-based) algorithm design, including reasoning about sample complexity, interval-reduction strategies, and robustness to noisy function evaluations.