The search that reuses a point

The rectangle that eats itself said the golden ratio has one property and every other property follows from it: cut a square off a golden rectangle and what is left is a golden rectangle again. That essay also warned that most of what is claimed for the number — in shells, in faces, in the proportions of buildings — is wrong. This essay is about a place where the golden ratio genuinely is the answer, not as an aesthetic preference but as the only solution to an engineering problem, and where the self-reproducing cut is exactly the thing that makes it work.

The problem is a search. A function rises to a single peak and then falls, and its formula is unknown or expensive: each value costs an experiment, a simulation, a measurement. Where is the peak? Every evaluation narrows the region where it can be, and the question is how to place the evaluations so that the region shrinks as fast as possible. The best answer, for a search that runs as long as needed, divides each bracket in the golden ratio; for a search with a fixed budget, it uses the Fibonacci numbers; and nothing does better, which Jack Kiefer proved in 1953.

Two points, and a part to throw away #

One evaluation says nothing about where a peak is; a single value cannot be compared with anything. Two evaluations inside the bracket can. If the function rises and then falls, and its value at $x_1$ is greater than at $x_2$ with $x_1 < x_2$, then the peak cannot be to the right of $x_2$: past the peak the function only falls, so if the peak were beyond $x_2$ the function would be rising all the way from $x_1$ to $x_2$, contradicting $f(x_1) > f(x_2)$. So everything beyond $x_2$ can be discarded. If the comparison goes the other way, everything before $x_1$ goes. Either way the bracket shrinks to the part between an endpoint and the farther interior point, and one interior point survives inside it, with its value already known.

That surviving point is the whole subject. The next step needs two interior points to compare, and one of them is already available for free. If the next bracket’s interior points can be chosen so that one of them is the survivor, every step after the first costs exactly one new evaluation. The hero does this with a function on $[0, 1]$ whose peak is at $0.3747$: nine evaluations, and in every row after the first one of the two dots is black, inherited from the row above, and only one is blue and new. The brackets shrink in a perfectly regular way, each $0.618$ times as wide as the last, and after nine evaluations the bracket is $0.0344$ wide and still contains the peak.

The regularity is not chosen; it is forced, and the reason is a single equation.

Why only one ratio works #

Put the bracket at $[0, 1]$ and the two interior points symmetrically, at $1 - c$ and $c$ with $c > \tfrac12$, so that the outcome does not depend on which side the peak is. Suppose the comparison drops the part beyond $c$. The new bracket is $[0, c]$, of length $c$, and the surviving point is $1 - c$. For the search to continue in the same pattern, the new bracket’s points must sit at the same fractions of its length, $1 - c$ and $c$ of $c$, and the survivor must be one of them — the larger, since $1 - c$ is the right-hand of the two in the old bracket’s left part. That requires $1 - c = c \cdot c$:

$$c^2 + c - 1 = 0, \qquad c = \frac{\sqrt 5 - 1}{2} = 0.6180\ldots = \frac1\varphi.$$

There is no other solution in $(0, 1)$. The figure tries five values of $c$ near it: at $c = 0.55$ the kept point lands at $0.818$ of the new bracket where it is needed at $0.55$, off by $0.268$; at $c = 0.65$ it is off by $0.112$; only at $c = 0.618$ does it land where it is needed.

The same self-reproduction shows in every row of the hero: the two ends and two interior points always cut the bracket into three gaps in the proportions $c^2 : c^3 : c^2$, the same at every scale, which is the one-dimensional cousin of the evenness three gaps and no more found for points placed round a circle by the golden angle. The equation is the rectangle’s equation. A golden rectangle of sides 1 and $\varphi$ with a square removed leaves sides $\varphi - 1$ and 1, in the same ratio, because $\varphi^2 = \varphi + 1$; the bracket with its outer piece removed leaves a bracket whose interior points are in the same positions, because $c^2 = 1 - c$. The search is the self-reproducing cut applied to a line instead of a rectangle, and the old interior point plays the part of the square’s edge; the tiles that never repeat used the same equation in two dimensions, where Penrose’s rhombs are cut into smaller copies scaled by exactly $1/\varphi$. The diagonal no unit measures found the same equation in the pentagon, as the ratio that subtracting a side from a diagonal reproduces; here it is the ratio that throwing away a piece of a bracket reproduces.

A game against an adversary #

Golden section is the best way to search indefinitely, shrinking by the same factor for ever. With a fixed budget it can be beaten slightly, and finding by how much is a different kind of problem: the worst case over every function, against the best strategy. The cleanest version is discrete. A row of $L$ unknown values rises to a single peak and then falls; each evaluation reveals one value; how long can the row be, if $n$ evaluations must always be enough to say exactly where the peak is?

The figure solves it as a game. The searcher chooses which value to reveal; an adversary, who has not committed to any particular row, answers each comparison in whichever way leaves the searcher worse off, subject only to staying consistent with a single peak. The searcher wins if, whatever the adversary does, the peak’s position is known when the evaluations run out. Every strategy for every row of up to 160 values is examined, by recursion over the bracket that remains and the position of the one value already known inside it. The answers, for one to ten evaluations, are

$$1,\ 2,\ 4,\ 7,\ 12,\ 20,\ 33,\ 54,\ 88,\ 143,$$

each one less than a Fibonacci number: $F_{n+2} - 1$. The longest searchable row grows by a factor tending to $\varphi$ with each evaluation, which is golden section again, and the exact numbers are Fibonacci’s.

The optimal strategy is Fibonacci search: in a row of $F_{n+2} - 1$ values, put the first two evaluations at positions $F_n$ and $F_{n+1}$, so that whichever part is thrown away, the remaining row has $F_{n+1} - 1$ values with the survivor exactly where the next stage of the strategy needs it. Each step drops down one Fibonacci number, and at the end one value is left. Kiefer proved the continuous version — with $n$ evaluations, no strategy can guarantee a final bracket smaller than $1/F_{n+1}$ of the original, and Fibonacci search achieves it — and the game in the figure is that theorem done by exhaustion on small cases.

Golden section against the obvious choice #

The obvious strategy is not golden section. It is to put the two points as close to the middle as possible, a hair either side, so that whichever half is dropped, the bracket is nearly halved. That halves the bracket every two evaluations, a factor of $1/\sqrt 2 = 0.707$ per evaluation. Putting the points at the thirds keeps two thirds every two evaluations, $0.816$ per evaluation. Golden section keeps $0.618$ per evaluation, and the figure shows what the difference compounds to: after forty evaluations golden section has narrowed the bracket by a factor of a hundred million, the middle pair by a factor of a million, and the thirds by a few thousand.

The middle pair loses because it never reuses anything. Each step’s two points are spent on one comparison and then both discarded, since the survivor sits at the middle of the new bracket, not where the next pair is needed. Golden section spends one evaluation per step and gets a full comparison out of each, because the other half of the comparison is the point it kept. Root-finding has the same choice: bisection, which how fast the staircase arrives found to gain one binary digit per evaluation, halves its bracket with a single sign test and has nothing to reuse, because a sign is a comparison with nought rather than with another value. That is a general lesson about search: what matters is not how much one step shrinks the bracket but how much it shrinks it per unit of cost, and a step that looks smaller can be better if it leaves something reusable behind. Newton’s method without a derivative made the same trade for roots, and found the same number: the secant method reuses its previous evaluation and gains a factor of $\varphi$ in digits per evaluation.

Where floating point stops the search #

A search that compares values can only be as precise as the values. The figure runs golden section on $2 - (x - \tfrac13)^2$, whose peak is at $\tfrac13$, in ordinary double-precision arithmetic for eighty evaluations. The bracket’s nominal width keeps shrinking by $0.618$ at every step, down past $10^{-16}$. The distance from the bracket’s centre to the true peak follows it down to about $10^{-8}$ and then stops, wandering at that level for the rest of the run.

The floor is the square root of the machine precision. Near a smooth peak the function differs from its maximum by the square of the distance, so two points within about $10^{-8}$ of the peak have values differing by about $10^{-16}$, which is the relative precision of a double. Below that, the comparison $f(x_1) > f(x_2)$ is decided by rounding rather than by the function, and the search discards parts of the bracket at random. Richard Brent made this the standard warning in his 1973 book on minimisation without derivatives: a search that uses only function values can locate a smooth optimum to about $\sqrt\varepsilon$ and no better, however long it runs. To do better needs the derivative, whose sign changes cleanly at the peak, or a higher-precision evaluation of the function — the same distinction the orbit a computer draws drew between what an algorithm computes and what its arithmetic allows.

The worst functions, and what “always” costs #

The game’s adversary deserves a closer look, because it explains why the guarantee is about worst cases and not about luck. Golden section and Fibonacci search shrink the bracket by the same factor whatever the function is; they never get lucky, and they never get unlucky. A strategy that guessed — that put a point exactly at the peak on the first try — would sometimes finish at once. But any such strategy has an adversary that answers every comparison so that the peak is in the larger remaining part, and against that adversary the guess wastes an evaluation. The Fibonacci numbers are what remains when every evaluation is forced to pay for itself in the worst case.

That is also why the search is a statement about one hump. With two peaks, a comparison of two values says nothing reliable about where either is, and no strategy can guarantee anything; the unimodality assumption is what turns a comparison into a reason to throw something away. Real functions often have one hump only near their optimum, and in practice golden section is run after a coarser search has bracketed a single peak, or alongside a faster method that it can fall back on. Brent’s method for minimisation interleaves golden-section steps with parabolic interpolation, which fits a parabola through three points and jumps to its vertex, converging much faster on smooth functions; the golden steps are there to guarantee progress when the parabolas misbehave.

Fibonacci in the bracket, φ in the limit #

The relation between the two optimal strategies is the relation between Fibonacci numbers and the golden ratio, and it is worth seeing in the positions. Fibonacci search on a row of $F_{n+2} - 1$ values starts its points at the fractions $F_n/F_{n+2}$ and $F_{n+1}/F_{n+2}$ of the row; for ten evaluations, $55/144$ and $89/144$, which are $0.3819$ and $0.6181$. Golden section starts at $1 - 1/\varphi = 0.3820$ and $1/\varphi = 0.6180$. The ratios of consecutive Fibonacci numbers are the best approximations to $\varphi$ by fractions — the numbers that come after the golden ratio found that $\varphi$ is the number worst approximated by fractions, so these approximations are only as good as approximations can be forced to be — and Fibonacci search is golden section with the irrational ratio replaced by its best rational stand-in at each stage, adjusted so that the last stage comes out to a whole number of values.

The one place Fibonacci search beats golden section is the end. With a fixed budget, golden section finishes with a bracket of width $c^{n-1}$; Fibonacci search finishes with $1/F_{n+1}$, smaller by a factor tending to $\varphi^2/\sqrt5 \approx 1.17$. The saving is a sixth of the final bracket, bought by knowing the budget in advance. For a search that might be stopped at any time, golden section is the right choice, since every intermediate bracket is as good as any strategy could have made it with that many evaluations.

Optimal with a budget, not without one, and not with noise #

The brackets in the hero are computed in double precision for a function with a single peak; the shrinking factor is checked at every step and the final bracket is checked to contain the true peak, found separately by a long ternary search. The game is exact: for every number of evaluations up to ten and every row up to 160 values, every strategy is tried against every consistent adversary, so the lengths in the figure are the true optima of the discrete problem, and the Fibonacci pattern is checked rather than assumed. The floating-point floor is a single run, and its level depends on the function’s curvature at the peak and on where the peak falls among representable numbers; that it sits near $\sqrt\varepsilon$ is the general rule, not a measurement of every case.

The figures do not show that golden section is optimal among all strategies that run without a budget; that is a further theorem, about strategies required to be good at every intermediate stage at once. Nor do they consider noisy evaluations, where each value carries random error and comparisons can be wrong. For that problem the right strategies sample repeatedly near the current points, the shrinking slows to a rate set by the noise, and the golden ratio plays no special role.

Still open: searching in more than one dimension #

On a line the problem is solved: Fibonacci search for a fixed budget, golden section without one, and Kiefer’s theorem that nothing does better. In two dimensions nothing comparable is known. A function with a single peak in a square can be searched by golden section along lines, one coordinate at a time, but that is far from optimal, and the minimax problem — the fewest evaluations that can guarantee locating the peak of any unimodal function on a square to a given accuracy — has no known exact solution even for simple notions of unimodality. Part of the difficulty is that “unimodal” has several inequivalent meanings in the plane, and comparisons of two values no longer let a whole region be discarded, only a half-plane on one side of a line.

There are also open questions about the discrete game with different rules. If the adversary may lie about a bounded number of comparisons, or if evaluations come in batches of two or three at a time, chosen in parallel, the optimal strategies are known only in special cases, and the numbers that replace the Fibonacci numbers are not always known to grow at any recognisable rate.

A cut that leaves something behind #

To narrow a bracket around a single peak, compare two interior values and throw away the part beyond the lower one; placing the points so that the survivor is reused forces $c^2 + c = 1$, so each evaluation shrinks the bracket to $0.618$ of its width. Solved as a game against an adversary, the longest row of values whose peak $n$ evaluations can always find is $1, 2, 4, 7, 12, 20, 33, 54, 88, 143$ — one less than the Fibonacci numbers — which is Kiefer’s theorem by exhaustion, with golden section as its limit. Against a pair of points near the middle, which reuses nothing, golden section is a hundred times faster after forty evaluations; and in double precision it stops near $10^{-8}$, where the values themselves can no longer tell which side the peak is on.