Convex functions and ternary search

Many optimization problems ask you to choose a value from a large range. A naive answer checks every possibility and takes too long. But if the cost function has a special shape, you can find the minimum much faster.

Imagine you are organizing a community event and need to decide where to hold it on a street numbered from 0 to 1000. Your budget depends on where you choose. The cost of travel for people coming from location $x$ to location $c$ is the absolute distance $|x - c|$. If ten people are at known locations, the total cost of a location $c$ is the sum of all distances they must travel.

What location minimizes the total cost? You could check all 1001 positions, but with a larger range or more people, checking every position becomes impractical. This cost function has a special shape: it decreases as you move in one direction and increases as you move in the other. It has exactly one minimum.

Convex functions and their shape

A function is convex if the line segment connecting any two points on the graph lies entirely above the graph. This means the function curves upward: if you move away from the minimum in either direction, the cost increases, and the rate of increase keeps growing.

A piecewise-linear function is made of straight-line segments joined at specific points. If such a function is also convex, each segment has a slope that increases (or stays the same) as you move to the right.

The travel-cost example above is piecewise-linear and convex. Each person at position $x$ contributes $|x - c|$ to the cost. As $c$ increases, these contributions change linearly. The total cost is a sum of absolute-value functions, which creates a piecewise-linear shape with a single minimum somewhere in the middle.

Ternary search

Ternary search finds the minimum of a convex function over a continuous range. The idea is to narrow down the search space by testing two points inside the current interval.

Consider an interval from lo to hi. Pick two points m1 and m2 inside the interval, with m1 closer to lo and m2 closer to hi. Evaluate the function at both points.

• If the function value at m1 is smaller, the minimum cannot be on the right side of m2, so move hi down to m2.
• If the value at m2 is smaller, the minimum cannot be on the left side of m1, so move lo up to m1.
• If they are equal (unlikely with real numbers), the minimum is between them.

Each iteration narrows the range to two-thirds of its previous size. After about $\log_{3/2}(R)$ iterations, where $R$ is the initial range, the interval is small enough to check or to round to an integer.

1def cost(c, targets):2    """Total distance from location c to all targets."""3    return sum(abs(x - c) for x in targets)4
5
6def ternary_search(targets, lo, hi):7    """Find the location that minimizes cost using ternary search."""8    epsilon = 1e-69    while hi - lo > epsilon:10        m1 = lo + (hi - lo) / 311        m2 = hi - (hi - lo) / 312        if cost(m1, targets) > cost(m2, targets):13            lo = m114        else:15            hi = m216    return (lo + hi) / 217
18
19targets = [10, 40, 50, 100]20best_loc = ternary_search(targets, 0, 1000)21best_cost = cost(best_loc, targets)22
23print(f"Best location: {best_loc:.2f}")24print(f"Minimum cost: {best_cost:.2f}")

Best location: 40.00
Minimum cost: 100.00

This example defines a simple cost function (sum of absolute distances to target points) and finds its minimum over the range 0 to 1000. The algorithm converges quickly without needing to check every integer value.

Binary search on the slope

Another way to find the minimum of a piecewise-linear convex function is to binary search on the slope.

For a piecewise-linear function, the slope is constant within each segment. The minimum occurs at a breakpoint where the slope changes from negative to positive. You can binary search for this breakpoint by checking the slope at candidate points.

If the slope at point $c$ is negative, the minimum is to the right. If it is positive, the minimum is to the left. This reduces the problem to checking slopes, which you can compute directly from the problem data.

The slope-sweep algorithm

When you have many breakpoints, computing the slope at each point becomes expensive. The slope-sweep algorithm processes the breakpoints in sorted order and updates the slope incrementally.

Imagine the function is a sum of terms, each of the form $|x - p_i| \cdot w_i$ for some position $p_i$ and weight $w_i$. As $x$ increases from left to right, each term's contribution to the slope changes at the point $p_i$.

Sort all positions $p_i$. Initialize the slope as if $x$ is far to the left (all terms contribute negatively). Then sweep from left to right. At each position, some terms flip from negative to positive, so the slope increases by twice the sum of their weights.

1def slope_sweep(positions, weights):2    """Find location c that minimizes sum of |c - p_i| * w_i."""3    total_weight = sum(weights)4    events = sorted(zip(positions, weights))5
6    # At c = -infinity, all terms contribute negatively7    slope = -total_weight8    left_weight = 09    best_cost = float('inf')10    best_loc = events[0][0]11
12    # Cost at the first position13    current_loc = events[0][0]14    current_cost = sum(abs(current_loc - p) * w for p, w in zip(positions, weights))15
16    for pos, w in events:17        # Move from current_loc to pos18        if pos > current_loc:19            current_cost += slope * (pos - current_loc)20            current_loc = pos21
22        if current_cost < best_cost:23            best_cost = current_cost24            best_loc = current_loc25
26        # At this breakpoint, slope changes27        left_weight += w28        right_weight = total_weight - left_weight29        slope = left_weight - right_weight30
31    return best_loc, best_cost32
33
34positions = [10, 40, 50, 100]35weights = [1, 2, 1, 3]36best_loc, best_cost = slope_sweep(positions, weights)37
38print(f"Best location: {best_loc}")39print(f"Minimum cost: {best_cost}")

Best location: 50
Minimum cost: 210

The sweep processes breakpoints once, updating the slope in constant time at each. This runs in $O(N \log N)$ due to sorting, much faster than checking $O(N)$ candidate points.

Common mistakes

• Assuming the minimum is at a data point: The minimum of a convex function might lie between data points. Use ternary search on real numbers and round if needed.
• Forgetting that slope sign flips: As you move right, negative contributions become positive. Track how many terms sit to your left, and how many sit to your right.
• Integer overflow on weighted sums: If positions and weights are large, the slope or cost can overflow. Use 64-bit integers.
• Off-by-one in slope updates: When you cross a breakpoint, update the slope by exactly the weight at that point, not more or less.

Recap

A piecewise-linear convex function has a single minimum that you can find without checking every possible value. Ternary search narrows the range by a constant factor each iteration. For many breakpoints, slope sweep processes them in sorted order and updates the slope incrementally, achieving $O(N \log N)$ time instead of $O(N^2)$ brute force.