One-Dimensional Search Methods

A one-dimensional search — or line search — is the problem of minimising a function of a single variable, \(\min_{x} f(x)\). It matters far beyond one dimension: almost every method for minimising a multivariable function \(F(\mathbf{x})\) works by repeatedly choosing a search direction \(\mathbf{d}_k\) at the current point \(\mathbf{x}_k\) and then asking how far to move along it. That step-length question is itself a one-variable minimisation.

Restricting \(F\) to the line through \(\mathbf{x}_k\) in direction \(\mathbf{d}_k\) collapses a hard multivariable problem into a scalar one in \(\alpha\). Because this subproblem is solved thousands of times inside a larger algorithm, it must be cheap — the whole subject of this chapter is how to find (or approximate) the minimising \(\alpha\) using as few evaluations of \(f\) as possible.

The elimination methods rest on one assumption: the function is unimodal on the interval of interest. A function \(f\) is unimodal on \([a,b]\) if it has a single minimum there and is strictly decreasing before it and strictly increasing after it. Unimodality is what lets us throw away part of the interval: comparing two interior evaluations tells us which side the minimum cannot be on.

Before shrinking, we must first bracket the minimum — find an interval \([a,b]\) that is guaranteed to contain it. A simple bracketing scheme steps outward from a starting point with a growing step until the function stops decreasing and starts to rise; the last three points then straddle the minimum.

All region-elimination (or interval-reduction) methods follow the same loop: place two points inside the current bracket \([a,b]\), evaluate \(f\) there, compare, and keep the sub-interval on the side of the smaller value. They differ only in where the points go and how many fresh evaluations each step costs.

The prize is reusing points. Halving spends two evaluations per step; the smarter methods place their points so that one of the two survives into the next, smaller interval and can be reused, costing only one new evaluation each iteration. That single idea is what makes Fibonacci and golden-section search so efficient.

Fibonacci search is the provably optimal region-elimination method for a fixed budget of \(n\) function evaluations: no other method guarantees a smaller final interval for the same number of evaluations. It uses the Fibonacci numbers \(F_0 = F_1 = 1,\ F_k = F_{k-1} + F_{k-2}\), giving \(1,1,2,3,5,8,13,21,34,\dots\)

At each step the two interior points are placed symmetrically using ratios of consecutive Fibonacci numbers, so one point is always reused in the next interval. The catch is that \(n\) must be chosen in advance to set the spacing — you decide how many evaluations you can afford, then the method squeezes the interval by the factor \(1/F_n\). To guarantee a final interval no longer than a tolerance \(\varepsilon\) starting from length \(L_0\), pick the smallest \(n\) with \(F_n \ge L_0/\varepsilon\).

Fibonacci search is optimal but awkward: it needs \(n\) fixed ahead of time and a changing ratio at every step. The golden-section method sacrifices a hair of optimality for a constant, self-similar ratio that needs no advance planning. It comes from letting \(n \to \infty\) in the Fibonacci ratios, which converge to the golden ratio:

On the current interval \([a,b]\) of length \(L = b - a\), place two symmetric points:

Compare \(f(x_1)\) and \(f(x_2)\). If \(f(x_1) < f(x_2)\), the minimum lies in \([a, x_2]\); otherwise it lies in \([x_1, b]\). The golden ratio is chosen precisely so the surviving interior point is already positioned correctly for the next interval — only one new evaluation is needed per iteration, and the interval shrinks by a constant factor.

Elimination methods use only comparisons of function values and make no assumption of smoothness. When \(f\) is smooth, interpolation methods exploit its shape to converge much faster. The idea: fit a simple model — a parabola or a cubic — through a few sampled points, jump to the model's minimum, and repeat.

Quadratic interpolation fits a parabola through three points \((x_1,f_1), (x_2,f_2), (x_3,f_3)\) and takes its vertex as the next estimate of the minimum:

When derivatives are available, Newton's method for line search converges even faster by using curvature directly. Applying Newton's root-finding to \(f'(x) = 0\) gives:

Newton's method converges quadratically near a minimum and lands on the exact minimum of any quadratic in a single step — but it needs both derivatives and can diverge if \(f''\) is negative or the start is poor. Interpolation is powerful when \(f\) is smooth and well-behaved; elimination is the safe fallback when it is not.

Inside a larger optimiser, solving the step-length subproblem exactly is wasteful — a rough but sufficient step is enough to keep the outer method converging. An inexact line search accepts any \(\alpha\) that makes "enough" progress, judged by two conditions on \(\phi(\alpha) = F(\mathbf{x}_k + \alpha\,\mathbf{d}_k)\).

The Armijo condition demands that the actual decrease be at least a fraction \(c_1\) (often \(10^{-4}\)) of the decrease the slope predicts — it rules out steps that are too long. On its own it can be satisfied by tiny useless steps, so it is paired with the curvature condition, which rules out steps that are too short:

Together these are the Wolfe conditions. The simplest way to satisfy Armijo is backtracking: start from a full step \(\alpha = 1\) and repeatedly shrink \(\alpha \leftarrow \rho\,\alpha\) (say \(\rho = 0.5\)) until sufficient decrease holds. Backtracking with the Armijo test is the line search buried inside most practical gradient and quasi-Newton solvers.

For each, state the interval, apply the method step by step, and track how the bracket shrinks. Difficulty rises down the list.