0

Minimize a black-box convex function

by Frontier Interview· 1 day ago· ⑂ 0 remixes

Question: Minimize a black-box convex function

Companies: Uber

Difficulty: Medium

Problem statement

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.

Approach

The only tool is evaluate(x). There are no derivatives and no formula. Convexity on [a, b] is the property that makes search possible: for any two probes x1 < x2 inside the bracket, comparing F(x1) with F(x2) tells us which side of the bracket can be thrown away.

Why one comparison is enough. Let x1 < x2.

  • If F(x1) < F(x2), then F has already started rising by x2. A convex function never falls again after it rises, so no point in (x2, b] beats F(x1). Some minimizer is in [a, x2].
  • If F(x1) > F(x2), the mirror argument puts a minimizer in [x1, b].
  • If they are equal, a minimizer is in [x1, x2], so either cut is safe. We treat ties like the first case.

Invariant: the current bracket [lo, hi] always contains at least one minimizer of F on the original interval. When hi - lo <= 2 * eps, the midpoint is within eps of that minimizer. The answer is then correct. If F is flat at the bottom (a whole interval of minimizers), the midpoint is within eps of a minimizer, which is the only sensible reading of the spec.

Brute force. Sample a grid of step eps and take the best point. That costs (b - a) / eps evaluations, which is 2·10^7 for [-10, 10] with eps = 1e-6. Too many when each call is expensive (a model training run, a simulation, a remote service).

Ternary search. Probe at the 1/3 and 2/3 points and drop one third. Each step makes 2 calls and keeps 2/3 of the bracket. That is about 2 · log_{1.5}(W / 2eps) calls, or 80 for the example above.

Golden-section search (optimal answer). Place the probes at hi - 0.618·W and lo + 0.618·W. After we cut one side, the surviving probe lands exactly where the next step needs one of its two probes, because 0.618² = 1 - 0.618. So every step after the first costs one call and keeps 0.618 of the bracket. Total is about log_{1.618}(W / 2eps) + 2 calls, or 36 for the same example: less than half of ternary. When the black box is expensive, this is the point of the question.

Practical points worth saying out loud:

  • Wrap evaluate so you can count calls and enforce a budget.
  • Stop on bracket width, never on how much F changed. A flat-bottomed function can change very little while x is still far from the minimum.
  • Floating point: with eps near machine precision relative to |a|, |b|, the bracket stops shrinking. Clamp eps to something like 1e-12 · max(1, |a|, |b|) in production code.

Code

import math
from typing import Callable, Optional


class BudgetExceeded(Exception):
    pass


class CountingOracle:
    """Wraps the black box so we can count (and cap) evaluations."""

    def __init__(self, f: Callable[[float], float], budget: Optional[int] = None) -> None:
        self.f = f
        self.budget = budget
        self.calls = 0

    def __call__(self, x: float) -> float:
        if self.budget is not None and self.calls >= self.budget:
            raise BudgetExceeded(f"more than {self.budget} evaluations")
        self.calls += 1
        return self.f(x)


def ternary_search(evaluate: Callable[[float], float], a: float, b: float, eps: float) -> float:
    """Baseline: two fresh evaluations per step, bracket shrinks to 2/3."""
    if a > b:
        a, b = b, a
    while b - a > 2 * eps:
        m1 = a + (b - a) / 3
        m2 = b - (b - a) / 3
        if evaluate(m1) <= evaluate(m2):
            b = m2          # a minimizer lies in [a, m2]
        else:
            a = m1          # a minimizer lies in [m1, b]
    return (a + b) / 2


INV_PHI = (math.sqrt(5) - 1) / 2  # 0.618...


def golden_section(evaluate: Callable[[float], float], a: float, b: float, eps: float) -> float:
    """One new evaluation per step, bracket shrinks to 0.618.

    Invariant: some minimizer of F on the original [a, b] lies in the current [a, b].
    Returns the bracket midpoint once the bracket width is <= 2 * eps, so the answer
    is within eps of that minimizer.
    """
    if eps <= 0:
        raise ValueError("eps must be positive")
    if a > b:
        a, b = b, a
    if b - a <= 2 * eps:
        return (a + b) / 2

    c = b - INV_PHI * (b - a)
    d = a + INV_PHI * (b - a)
    fc, fd = evaluate(c), evaluate(d)
    while b - a > 2 * eps:
        if fc <= fd:
            # Convexity: F(c) <= F(d) means F does not decrease after d, so drop (d, b].
            b, d, fd = d, c, fc
            c = b - INV_PHI * (b - a)
            fc = evaluate(c)
        else:
            a, c, fc = c, d, fd
            d = a + INV_PHI * (b - a)
            fd = evaluate(d)
    return (a + b) / 2


def minimize(
    evaluate: Callable[[float], float],
    a: float,
    b: float,
    eps: float,
    budget: Optional[int] = None,
) -> float:
    """Public entry point: golden-section search with an optional evaluation cap."""
    oracle = CountingOracle(evaluate, budget)
    return golden_section(oracle, a, b, eps)


def evaluations_needed(a: float, b: float, eps: float) -> int:
    """Upper bound on golden-section evaluations to reach width 2*eps."""
    width = abs(b - a)
    if width <= 2 * eps:
        return 0
    steps = math.ceil(math.log(2 * eps / width) / math.log(INV_PHI))
    return steps + 2  # two initial probes, then one per step (last step's probe is spare)

Usage:

x = minimize(lambda x: (x - 2) ** 2, -10, 10, 1e-6)   # ~2.0, 36 evaluations

Complexity

Let W = b - a.

  • Golden-section: O(log(W / eps)) time, about log_{1.618}(W / 2eps) + 2 evaluations (36 for W = 20, eps = 1e-6). O(1) extra space.
  • Ternary search: also O(log(W / eps)), but about 2 · log_{1.5}(W / 2eps) evaluations (80 for the same input). O(1) space.
  • Grid brute force: O(W / eps) evaluations.
  • evaluations_needed is O(1). It lets the caller check a budget before spending anything.

Time is dominated by the cost of evaluate, so the number of evaluations is the metric that matters.

Test cases

  • F(x) = (x - 2)^2 on [-10, 10], eps = 1e-6 → about 2.0. Golden-section uses 36 calls, ternary uses 80.
  • F(x) = |x + 3| on [-10, 10] → about -3.0. The kink has no derivative, and the search still works.
  • F(x) = x on [0, 5] (increasing) → about 0.0. The minimum is at the left endpoint.
  • F(x) = -x on [0, 5] (decreasing) → about 5.0. The minimum is at the right endpoint.
  • F(x) = e^x - 2x on [-5, 5] → about ln 2 ≈ 0.693147.
  • F(x) = max(0, |x - 2| - 1) on [-10, 10] (flat bottom on [1, 3]) → any value in [1 - eps, 3 + eps].
  • a == b == 4 → 4 with zero evaluations.
  • a = 5, b = -5 (reversed) for (x - 1)^2 → about 1.0. The bounds are swapped first.
  • eps <= 0 → ValueError.
  • budget = 10 with eps = 1e-6 on [-10, 10] → BudgetExceeded, because 36 calls are needed.

Follow-ups

  1. Fixed evaluation budget instead of eps. "You get k calls; return the best estimate." Run golden-section for k - 2 steps and return the midpoint, or the best point seen so far. With the same budget, its final bracket is smaller than ternary's (0.618^(k-2) against 0.816^k). Fibonacci search is the exact optimum for a fixed k.
  2. Integer domain (for example, the best batch size in [1, 10^9]). Binary search on the sign of F(m + 1) - F(m): find the first m where F(m) <= F(m + 1). That takes about 2 log W calls. Golden-section on integers also works with rounding, but the endpoint handling is fiddly, so check the last 3 points by brute force.
  3. Noisy evaluations (F(x) + noise). A single comparison can point the wrong way. Average repeated samples at each probe, with enough repeats that the confidence interval is narrower than the difference, or stop shrinking once the bracket is down to the noise level. Mention that Bayesian optimization is the usual tool when calls are noisy and expensive.
  4. Unknown interval (F convex on all of ℝ). First find a bracket: step out from x0 with doubling steps until F rises on both sides, which costs O(log |x_min - x0|) calls. Then run golden-section.
  5. Expensive or parallel calls, or several dimensions. With p parallel workers, evaluate p evenly spaced points per round and keep the two cells next to the best point. For d dimensions, coordinate descent with a 1D line search works on convex functions. Mention that subgradient methods or Nelder–Mead are the next step up.

Interviewer expectations

Mid-level (L4)

  • Uses convexity to explain why comparing two interior points lets you discard a third of the interval.
  • Writes a correct ternary search with a width-based stopping rule and returns a point within eps.
  • Tests endpoint minima and a non-smooth function such as |x|.

Senior (L5)

  • States the bracket invariant precisely, including ties and flat-bottomed functions.
  • Notices that each step evaluates two points and moves to golden-section search to reuse one. Quantifies the saving (about 36 calls against 80).
  • Counts evaluations behind a wrapper, enforces a budget, and checks inputs (reversed bounds, eps <= 0, a == b).

Staff (L6+)

  • Frames the cost model: evaluations are the expensive resource. Can derive the evaluation count for a given eps before running, and knows Fibonacci search is optimal for a fixed budget.
  • Discusses the limits of floating-point precision, noisy oracles, an unknown bracket, and the integer variant without being prompted.
  • Connects the problem to real uses at Uber scale (tuning a pricing or dispatch parameter against an expensive simulator) and knows when to switch to Bayesian optimization or parallel grid refinement.

Sign in to comment, vote or remix.