A cut that gets sharper as the map gets lazier

A map that shrinks everything proved Banach’s theorem. A map of the plane that brings every two points closer by at least a fixed factor $\lambda < 1$ has exactly one fixed point, and iterating the map from anywhere converges to it. What it costs to find the point that stays put priced that convergence. Each iteration brings the current point a factor $\lambda$ closer, so reaching accuracy $\varepsilon$ costs about $\ln(1/\varepsilon)/\ln(1/\lambda)$ readings of the map. That grows like $1/(1 - \lambda)$ as the map approaches one that does not shrink at all. It closed by asking whether a method that uses each reading more cleverly could do better.

It can, and by an amount that is not a constant factor. A map that shrinks distances gives away more with each reading than iteration uses. Read it at a point $c$, and the image $f(c)$ is closer to the fixed point than $c$ is. The fixed point must lie on $f(c)$'s side of the perpendicular bisector of $c$ and $f(c)$. Every reading halves the plane, and a method that keeps only the half known to contain the answer — a cutting method — needs a number of readings that does not grow as $\lambda$ approaches one. It actually falls.

Half the plane from one reading #

The cut rests on one inequality. If $x^*$ is the fixed point and the map shrinks distances by $\lambda$, then $|f(c) - x^*| = |f(c) - f(x^*)| \le \lambda |c - x^*| < |c - x^*|$. The points closer to $f(c)$ than to $c$ form a half-plane, bounded by the line through the midpoint of $c$ and $f(c)$ perpendicular to the segment between them. The fixed point is in that half-plane. Nothing about the map beyond this one reading is needed, and in particular the value of $\lambda$ is never used.

The method keeps a convex region known to contain the fixed point, starting from the whole square. It reads the map at the region’s centre, cuts the region along the bisector, and repeats. The regions shrink around the fixed point, and the method stops when the region is smaller than the accuracy wanted.

The map in the hero figure shrinks distances by only $0.999$ and turns them as it does, more sharply the further out a point lies, so that its images spiral slowly in towards the fixed point. Iterating it from the corner of the square takes 7,215 steps to come within a thousandth. Four cuts take the region to that size, and the fixed point is inside it.

On a line, the cut is bisection #

In one dimension the method is already familiar. A map of an interval to itself has a fixed point by the intermediate value theorem, the argument something always stays put began with. The function $g(x) = f(x) - x$ is positive at the left end and negative at the right, so it changes sign somewhere in between. Read it at the midpoint. Its sign says which half contains a crossing, and the other half can be thrown away. That is bisection. It gains one binary digit of accuracy per reading, for every continuous map of an interval, whether it shrinks or not.

The plane is harder because a sign is not enough. A map of the square has a displacement that is an arrow, not a number, and an arrow at one point says nothing in general about where the fixed point is — which is why Brouwer’s search needed winding numbers and corridors. Shrinking restores what the plane lost. The arrow from $c$ to $f(c)$ points towards the fixed point’s half-plane, and the bisector plays the role of the midpoint. The cutting method is bisection carried into two dimensions, and the price of carrying it there is the assumption that the map never stretches.

In one dimension the bisector of $c$ and $f(c)$ is a single point, their midpoint, and the cut keeps the side towards $f(c)$. When $\lambda$ is small, $f(c)$ lands close to the fixed point and the midpoint is about halfway there, so the cut is deeper than bisection’s. When $\lambda$ is near one, $f(c)$ is close to $c$, the midpoint is too, and the cut is plain bisection. The planar advantage near $\lambda = 1$ has no counterpart on a line. It comes from the bisector being a line that passes close to the fixed point, and in one dimension a “line” through the fixed point is the fixed point itself, which no single reading can find.

Iterating and cutting, side by side #

The comparison is starkest as $\lambda$ approaches one.

At $\lambda = \tfrac12$ the two methods cost about the same: 21 readings to iterate and 24 to cut, because each iteration halves the distance and each cut roughly halves the region. From there they part. Iteration grows in proportion to $1/(1 - \lambda)$, reaching 1,406 readings at $\lambda = 0.99$ and 141,254 at $0.9999$. Cutting goes the other way, 15 readings at $0.9$, 10 at $0.99$, 6 at $0.9999$. The two methods are hurt by opposite things, and only one of them badly. Iteration suffers when the map barely shrinks, because each step gains little. The cut suffers, mildly, when the map shrinks a lot, for a reason the last figure explains.

Readings per digit #

Both costs grow with the accuracy wanted, and in the same way: in proportion to the number of digits.

Iterating at $\lambda = 0.999$ costs about 2,300 readings for each additional digit of accuracy, since each digit means shrinking the distance tenfold and each step shrinks it by only a thousandth. At $\lambda = 0.9$ it is about 22 per digit. Cutting costs about two readings per digit at $\lambda = 0.9$ and about one at $0.999$. A reading tells the cut on which side of a line the answer lies, a bit of information about where it is, while it moves the iteration only a factor $\lambda$ closer. The comparison is between a method that uses the reading’s location and one that uses only its direction of travel.

The guarantee: five-ninths #

The cut along the bisector is fast in practice, but its worst case is not easy to bound, because the bisector can pass anywhere relative to the region. A safer variant cuts through the region’s centre instead, along the line through $c$ parallel to the bisector. The fixed point is still on the kept side, since the bisector lies entirely within the kept half. This version comes with a guarantee.

Branko Grünbaum proved in 1960 that any line through the centroid of a convex region in the plane leaves at least four-ninths of the area on each side. The bound is attained by a triangle cut parallel to a side. So each centroid cut keeps at most five-ninths of the area, and after $k$ cuts the area is at most $(5/9)^k$ of the square’s — a decrease at a fixed rate, independent of the map. Over 1,200 cuts the largest share kept is exactly $5/9$, from a triangle, and the average is half. In $d$ dimensions the same theorem says a cut through the centroid keeps at most $1 - (d/(d+1))^d$ of the volume, which is never more than $1 - 1/e$. That is the reason the centre-of-gravity method, and its practical cousin the ellipsoid method, converge at a rate independent of everything but the dimension.

The guarantee is about area, not width. A long thin sliver can have tiny area and still be wide. In practice the cuts arrive from varied directions and the region shrinks in every direction together. The bisector cut, which runs further into the region than the centroid cut, shrinks it faster still.

Where the cut is safe #

The cut needs only that $f(c)$ is no further from the fixed point than $c$ is. That holds for every map that never stretches distances, and fails for one that does.

For a rotation, $f(c)$ and $c$ are at exactly the same distance from the fixed point, which therefore lies on every bisector. The closed half-plane still contains it, and two bisectors in different directions cross exactly at it. Three cuts reach a millionth. For a map that stretches, $f(c)$ is further from the fixed point than $c$, the fixed point is on the wrong side, and the very first cut throws it away.

That boundary is the boundary of what it costs to find the point that stays put. For a general continuous map of the square — which may stretch anywhere — Brouwer’s theorem still guarantees a fixed point. Finding one needs the corridor and winding-number searches of that essay, at a cost that grows with the accuracy far faster than a logarithm. Michael Hirsch, Christos Papadimitriou and Stephen Vavasis proved in 1989 that this cost is unavoidable. Not stretching is exactly what turns that search into a sequence of cuts.

Why a lazy map is easy #

The falling cost as $\lambda \to 1$ has a geometric explanation, and it can be measured directly.

The fixed point lies on the bisector exactly when $f(c)$ and $c$ are equally far from it, which for a map that shrinks they are not. But a map that barely shrinks makes them nearly equal. The distance from the fixed point to the bisector works out to

$$\frac{|c - x^*|^2 - |f(c) - x^*|^2}{2\,|f(c) - c|} = \frac{\rho^2 (1 - \lambda^2)}{2\,|f(c) - c|},$$

where $\rho = |c - x^*|$. For a map that also turns, $|f(c) - c|$ is a fixed multiple of $\rho$, so the fixed point’s distance from the bisector is a fixed multiple of $(1 - \lambda)\rho$. The figure measures it at $0.58\,(1 - \lambda)$ of $\rho$ for a turning angle of 2.1 radians, matching the formula. As $\lambda$ approaches one, every bisector passes almost exactly through the fixed point, so two readings in different directions nearly pin it down. The property that makes iteration slow — that the map barely moves points towards the answer — is the same property that puts the answer on every bisector.

For a map that shrinks strongly, $\lambda = \tfrac12$ say, the bisector misses the fixed point by a good fraction of the distance, the cut throws away less, and more readings are needed. That is the mild cost the cutting curve shows at small $\lambda$, where iterating is cheap anyway. The formula also says what can go wrong for a lazy map. If the map barely turns as well as barely shrinking, $|f(c) - c|$ is itself of order $(1 - \lambda)\rho$, the ratio is no longer small, and the bisector can miss the fixed point by a large share of the distance. For a map that moves points almost straight towards the answer, slowly, the bisector runs close to $c$, square to the direction of the answer, and the cut is an ordinary halving through the region. That is still a cost that grows only with the number of digits wanted, but without the near-exact pinning. The maps in these figures all turn, and the turning is what makes their bisectors pass so close to the answer.

Where cutting came from #

Cutting methods were invented for optimisation, not for fixed points. To minimise a convex function over a convex region, read its gradient at a point. The minimum lies in the half-space the gradient points away from, so the region can be cut through the point and the search continued. Anatoly Levin and Donald Newman independently proposed cutting through the centre of gravity in 1965, which Grünbaum’s theorem makes converge at a fixed rate. Centres of gravity of high-dimensional bodies are hard to compute, so Naum Shor, David Yudin and Arkadi Nemirovski replaced the region in the 1970s by an ellipsoid enclosing it, which is easy to update after each cut.

The ellipsoid method became famous in 1979, when Leonid Khachiyan used it to prove that linear programming — the problem the lines the optimum lies under studied through duality — can be solved in a time bounded by a polynomial in the size of the input. It was the first such proof. The simplex method, which walks from corner to corner, is fast in practice and exponential in the worst case, while the ellipsoid method is slow in practice and polynomial in the worst case.

The same idea applies to fixed points with almost no change. The gradient’s half-space is replaced by the bisector’s, and convexity of the function by the map’s refusal to stretch. Whether an equilibrium or a fixed point can be found quickly therefore turns on whether the problem supplies a cut. Contractions and convex functions do. General continuous maps, and the games whose equilibria they describe, do not, which is why finding those is the hard problem where the fixed point escapes and its successors kept meeting.

What the experiments do and do not show #

The maps in the figures are rotations scaled towards a fixed point, some with a turning angle that varies with distance. The cutting argument needs only that each reading’s image is no further from the fixed point than the reading. The experiments therefore show its behaviour on one natural family, and the argument carries over to every map with that property. What the experiments do not establish is a worst case. A map designed to make the bisector cuts as uninformative as possible could do worse than these, though never worse than the centroid cut’s guaranteed five-ninths per reading.

They also say nothing about dimension. In three or more dimensions the cut is a half-space, the centroid of a convex body is expensive to compute, and practical methods use ellipsoids or other simple shapes. Their cost grows with the dimension, and how the best achievable cost depends on dimension and on $\lambda$ together is the question what it costs to find the point that stays put left open. Krzysztof Sikorski and coauthors gave cutting methods for contractions in any dimension whose cost depends on the dimension and the logarithm of the accuracy rather than on $1/(1 - \lambda)$. The exact trade-off, and where it meets Brouwer’s much higher cost as $\lambda$ passes one, is still being studied.

Still open: the price of the last factor #

For contractions in the plane, the cutting method’s cost is a small multiple of the number of digits of accuracy, whatever $\lambda$ is. In $d$ dimensions the best methods known cost a number of readings growing like a power of $d$ times the number of digits. Lower bounds — how many readings any method must use, against an adversarial map — match only in the order of the accuracy and not in the power of $d$. As $\lambda$ crosses one, the problem changes character entirely, from logarithmic cost to cost exponential in the number of digits for general continuous maps. How the cost interpolates between those regimes for maps that stretch only slightly, or only in some directions, is not known.

There is also the question a map that offers a choice raised for equilibria. When the map is not a black box to be read but a formula that can be inspected, can its fixed point be found faster than any reading-based method allows? For contractions given by explicit formulas, it is not known how much inspection can help.

Reading the answer from the direction it must lie #

Iterating a contraction uses each reading to move a little closer. Cutting uses it to rule out half of everything that is left. For a map that shrinks strongly the two are comparable. For a map that barely shrinks, iteration needs a number of readings proportional to $1/(1 - \lambda)$, while cutting needs a handful, fewer the lazier the map. Laziness is what makes the bisectors pass so close to the answer. The boundary of the method is equally sharp: any map that never stretches can be cut down this way, and a map that stretches cannot. That boundary separates Banach’s iteration from Brouwer’s search.