An augmentation read in the smallest eigenvalue

Where the augmentation puts the cost measured the augmented Lagrangian preconditioner across ten decades of its one parameter and found that γ has an optimum rather than a direction. Adding $\gamma A^{\mathsf T}A$ to the Hessian block makes the Schur complement tend to $I/\gamma$, so the cheapest approximation of it becomes the right one and MINRES needs fewer outer steps; the augmented block $H + \gamma A^{\mathsf T}A$ becomes worse conditioned, so each inner solve with it needs more conjugate gradient steps. On three systems the least product of the two counts sat at γ = 1, $10^4$ and 1. The essay noticed that two of those three optima sat where the smallest generalised eigenvalue of the augmented pair was about 0.06, and proposed a rule written in that eigenvalue rather than in γ, with the caveat that three systems are not enough to call it one.

The eigenvalue is a natural thing to try. The preconditioned spectrum is known in closed form: with $s$ the eigenvalues of the Schur complement $S = AH^{-1}A^{\mathsf T}$, the augmented pair has generalised eigenvalues

$$\nu = \frac{\gamma s}{1 + \gamma s},$$

and the preconditioned matrix’s eigenvalues are one and $(1 \pm \sqrt{1 + 4\nu})/2$. When the smallest ν is near one, the spectrum has gathered at the golden-ratio pair and MINRES needs a handful of steps; when it is near zero, one pair of eigenvalues sits near zero and one near one and MINRES pays for the gap. A γ is a number with units — it multiplies $A^{\mathsf T}A$ and has to be compared with H to mean anything — while ν is dimensionless and says directly what the outer iteration sees. If the least work has a place in the spectrum, ν is where to look for it.

Twenty-four systems, all of the same size #

The systems are the saddle-point matrices the golden-ratio essays used, twelve unknowns and five constraints, built with a prescribed condition number for the Hessian and for the constraint: κ(A) of 10, 100, 1,000 and 10,000, κ(H) of 10, 100 and 10,000, and two seeds of each, twenty-four in all. Every one has $\|H\| = 1$ and $\|A\| = 1$. That detail matters later. For each, γ runs over a quarter-decade grid from 0.01 to $10^8$; at each γ MINRES is run to a relative residual of $10^{-14}$ with the block-diagonal preconditioner, each application of $(H + \gamma A^{\mathsf T}A)^{-1}$ is counted as the conjugate gradient steps it needs to reach $10^{-10}$, and the product of the two counts is the work. The forward error of each answer is measured against the exact rational solution.

The work curves all have the same shape and none has a sharp minimum. On the six systems with κ(A) = 1,000 the product starts between 1.6 and 1.9 times its least at γ = 0.01, falls into a floor two to three decades wide where it wanders within a few tens of per cent of its least, and rises again as the inner solve’s conditioning takes over. The least sits at γ = 1,000 or 1,778 on four of the six and at 100 and 56 on the two with the worst-conditioned Hessian. Turn the dial and the floor moves: near γ = 1 at κ(A) = 10, near 50 at 100, near $10^3$ at 1,000, near $10^5$ at 10,000. It moves by decades, and it moves by about two decades for every decade of the constraint’s conditioning.

Seven decades, and nothing in the norms #

Collected, the optima run from $\gamma = 0.032$ to $3.2 \cdot 10^5$ — seven decades — and they sort by the constraint’s conditioning first and the Hessian’s second. The four groups sit at 0.032 to 1.8, 0.56 to 100, 56 to 1,800 and 5,600 to $3.2 \cdot 10^5$. Within each group the systems with the worst-conditioned Hessian sit lowest, by up to two decades.

This is where the unit norms matter. A common recommendation is to choose γ so that the added term balances the Hessian — $\gamma \approx \|H\|/\|A\|^2$ — and every such rule reads only norms. On this family every norm is one, so every norm-based rule chooses the same γ for all twenty-four systems, and the best any single γ can do is the whole of what such rules can do. Scored against each system’s own least work over every γ on the grid, the best single choice is $\gamma = 31.6$: its median system pays 1.36 times its least work and its worst 1.61. That is better than no augmentation — γ = 0.01 costs between 1.33 and 2.28 times the least — and it is the ceiling for any rule that cannot see past the norms.

ν at the optimum is not one number #

The proposal was that the optimum sits at one ν. It does not. At each system’s least work the smallest ν ranges from 0.0020 to 0.059, a factor of thirty. The two optima the earlier essay saw near 0.06 are at the top of that range, not its centre, and the systems with the worst-conditioned constraint have their optima at ν of a few thousandths — where the preconditioned spectrum still has a pair of eigenvalues within a few thousandths of zero and one, and MINRES is paying for them — because on those systems moving ν higher costs inner steps faster than it saves outer ones.

So the reading “the least work sits at ν ≈ 0.06” is false as stated. What the figure shows instead is a compression. The optimum in γ spans seven decades; in ν it spans one and a half. The quantity that absorbed the five and a half decades is the Schur complement’s smallest eigenvalue. For ν well below one, $\nu \approx \gamma s_{\min}$, so a target in ν is a γ proportional to $1/s_{\min}$, and with unit norms $s_{\min}$ falls like $1/\kappa(A)^2$ — two decades of γ for every decade of κ(A), the slope the dial showed. The Hessian’s conditioning enters $s_{\min}$ too, which is why the worst-conditioned Hessians sit apart from the others within each group; the section below measures how.

Where each floor begins #

The floors have an edge, and the edge is not in ν. It is in the outer count. Twelve unknowns and five constraints give a preconditioned matrix with at most $2m + 1 = 11$ distinct eigenvalues — one, and a pair for each generalised eigenvalue — so MINRES in exact arithmetic terminates in eleven steps whatever γ is. At a tolerance of $10^{-14}$ it takes more wherever one of those eigenvalues sits so near zero that rounding costs steps: 19 outer steps at γ = 0.01 on the gentlest system, 45 on the worst. As γ grows the eigenvalue nearest zero, $(1 - \sqrt{1 + 4\nu_{\min}})/2 \approx -\nu_{\min}$, moves away from it, and at some γ the count falls to eleven or twelve.

On nineteen of the twenty-four systems the least work is exactly at the first γ on the grid where that happens, and on all twenty-four it is within 11 per cent of it. Before that γ, the outer count falls faster than the inner count rises. After it, the outer count falls only slowly — from twelve to between six and ten by $\gamma = 10^8$, as the spectrum gathers towards the golden-ratio pair — while the inner count keeps rising, at the rate the rate the condition number predicts allows for a block whose condition number grows like γ, and the product turns. The least work is where MINRES stops paying for rounding.

That is why ν at the optimum is not one number. How close to zero an eigenvalue can sit before rounding costs a step depends on the rest of the spectrum — on how the other ten eigenvalues are spread, which is set by the Schur complement’s other eigenvalues — so the ν at which the count reaches eleven varies from system to system, by the factor of thirty the figure showed. A target of 0.03 works because it sits in the middle of that range: on most systems it lands on or just past the γ where the count terminates, and on the rest a quarter-decade or two away, on the floor.

A rule that still travels #

A target that is not where the optimum sits can still be a good rule, because the work curves have floors. The rule is: take the smallest γ on the grid at which the smallest ν reaches c.

At $c = 0.03$ the median system pays 1.07 times its least work and the worst pays 1.29. At 0.01 the median is 1.10 and the worst 1.55; at 0.06, 1.15 and 1.35; at 0.3, 1.27 and 1.60; at 0.003, 1.31 and 1.91. The curve of the worst case has a clear minimum at 0.03, and every target from 0.01 to 0.1 beats the best fixed γ on both the median and the worst system. The six dots in the dialled figure are the rule at 0.03 on the κ(A) = 1,000 systems: between 1.05 and 1.20 times the least work, on γ values from $10^3$ to $10^4$ that no single choice of γ would have reached for all six.

The rule needs one number the norm rules do not, $s_{\min}$, the smallest eigenvalue of $AH^{-1}A^{\mathsf T}$. It is not free: each product with S is a solve with H, so a few Lanczos steps on S cost a few solves with the unaugmented Hessian — which is cheaper to solve with than the augmented block the whole method will use, and is solved once rather than once per outer step. At the rule’s γ the MINRES run takes eleven or twelve outer steps on every system, each with one augmented solve of twelve to twenty-nine conjugate gradient steps, so an estimate of $s_{\min}$ to a factor of two would be a small fraction of the whole. That estimate’s accuracy is not measured here: the rule is scored with the exact $s_{\min}$, and a factor of two error in it moves γ by a factor of two along a floor that is two decades wide.

The digits the rule gives up #

The earlier essay’s other finding was that the answer’s accuracy has its own optimum, and that it sits elsewhere: at γ = 0.01, 100 and 1 where the work’s sat at 1, $10^4$ and 1. That is true of the twenty-four as well, and it is what a rule tuned for work pays. At the rule’s γ the median system’s forward error is 11.6 times the best the grid offers, and the worst’s is 4,561 times — $4.4 \cdot 10^{-10}$ on the system with both condition numbers at $10^4$, whose best is $9.6 \cdot 10^{-14}$ at γ = 0.18. Every dot lies on or above the diagonal, and the spread grows with the error: the systems whose best forward error is already $10^{-13}$, the ones with the worst constraints, are the ones the rule takes furthest from it.

The mechanism is the one the condition number is an amplifier names and the earlier essay measured: the forward error tracks $\kappa(H + \gamma A^{\mathsf T}A)$, and the γ that balances the outer and inner counts is a γ at which that condition number is already large. A system whose constraint is badly conditioned needs a large γ before the outer count falls, and a large γ is exactly what makes the augmented block ill-conditioned. The least work and the most digits are therefore at different γ for the same reason on every system, and further apart the worse the constraint is.

What the two optima are for #

The measurement separates two questions that the phrase “choosing γ” runs together.

If the work is the concern, a target in the smallest eigenvalue is a rule, and a good one: it absorbs the dependence on the constraint’s conditioning that makes a fixed γ wrong by seven decades, and it leaves the median system within 7 per cent of its least work. What it cannot absorb — the factor of thirty in ν at the optimum — costs at most 29 per cent, because the floors are broad. One eigenvalue and two steps found the triangular variant of this preconditioner halving the outer count; whether its floors sit at the same ν is a question for the same sweep.

If the answer’s digits are the concern, no rule in ν helps, because ν says only what the outer iteration sees. The digits’ optimum sits at or below the work’s on seventeen of the twenty-four systems, by up to five and a half decades on the systems with the worst-conditioned Hessian, and the constraint’s conditioning, which pushed the work optimum up, pushes the digits’ optimum up far less. Two ways to remove a constraint measured the same constraint conditioning costing digits in the eliminations that inherit it, before any augmentation is added; here it is what sets how far apart the two optima sit. A constraint is a weight at infinity found the method of weighting losing digits for the same reason at large weights, a condition number sent to infinity found it in the interior-point method’s barrier, and the regularisation that legalises every order found the same shape of trade in quasi-definite factorisation: a parameter that makes one part of a computation cheap by making another part ill-conditioned.

The earlier essay’s closing suggestion was that the digits are the part that transfers between implementations, and that is the reading this sweep supports. A production augmented Lagrangian code uses an inner solver designed for the augmented block, which changes the inner count and moves the work floors. It does not change $\kappa(H + \gamma A^{\mathsf T}A)$. A ν-target tuned to one inner solver’s floors would have to be re-measured for another; the digits’ cost of a large γ would not.

What the smallest eigenvalue carries from each block #

It is worth checking the compression against the closed form rather than taking it from the figure. With $\|H\| = 1$ and $\|A\| = 1$ the Schur complement’s smallest eigenvalue is at least $\sigma_{\min}(A)^2/\|H\| = 1/\kappa(A)^2$, and that lower bound is where the constraint enters: every decade of κ(A) lowers $s_{\min}$ by two, and the rule raises γ by two to compensate — the slope the dial showed. The measured $s_{\min}$ sits above the bound by a factor that belongs to the Hessian: $s_{\min}\kappa(A)^2$ is 2.2 to 2.9 on the six systems with κ(H) = 10, 5.9 to 9.4 with κ(H) = 100, and 66 to 128 with κ(H) = $10^4$, the same at every κ(A). The reason is $H^{-1}$ inside S. A Hessian with small eigenvalues has an inverse with large ones, and wherever the constraint’s weak direction sees any of H’s weak end, S is lifted there.

So the rule reads both blocks through one number, and reads them in the right direction. The systems with the worst-conditioned Hessian have the largest $s_{\min}$, and the rule gives them the smallest γ — which is where their optima are, one and a half to two decades below the rest of their group. A rule written in κ(A) alone, $\gamma = c\,\kappa(A)^2$, would have put them where the others are and paid for it.

The same argument says when the rule would fail. The lift comes from $H^{-1}$, but the inner solve is with $H + \gamma A^{\mathsf T}A$, which is ill-conditioned wherever H is weak outside the constraint’s range. On a problem whose Hessian is weak mostly outside that range, $s_{\min}$ would not be lifted, the rule would ask for a large γ, and the inner solve would pay for H’s weakness and the augmentation’s at once. None of the twenty-four systems is built that way, and a preconditioner that need not know the constraint is the alternative for such problems.

What the family leaves out #

Twenty-four systems of one size, twelve unknowns and five constraints, with random orthogonal factors and prescribed condition numbers. The inner solve is unpreconditioned conjugate gradients, the outer tolerance is $10^{-14}$ and the inner $10^{-10}$, and the work is a product of step counts rather than a time. Each of those choices shapes the floors, and the claim that a ν target finds them is a claim about this family. At twelve unknowns the outer count is capped by the number of distinct eigenvalues, which flattens it at small γ — in exact arithmetic it could not exceed eleven, one step for each distinct eigenvalue, and at a tolerance of $10^{-14}$ it reaches about twenty only because of rounding. On larger systems the outer count at small γ would be larger and the floors would sit further right.

The digits are measured as the earlier essay measured them: the preconditioner’s augmented solves are done by a Cholesky factorisation of $H + \gamma A^{\mathsf T}A$, so no inner tolerance is to blame, and the answer is compared with the exact rational solution. The conjugate gradient counts price the inner solve an iterative code would do; they do not produce the answer whose error is reported. A code that solved its inner systems to $10^{-10}$ would add an error of its own, which is not measured.

Still open: an estimated eigenvalue, and a rule for both currencies #

The rule with an estimated $s_{\min}$. Everything above uses the exact smallest eigenvalue of the Schur complement. A few Lanczos steps on S — each a solve with H — give an estimate from above, and an estimate from above gives a γ that is too small, which is the safe side for the digits and the unsafe side for the work. How many steps put the rule’s worst case within a tenth of its exact-eigenvalue value is one sweep, and the prediction with a sign is that three or four suffice, because the floor is two decades wide.

A rule for both currencies. The work wants $\nu_{\min} \approx 0.03$ and the digits want γ small. A rule that took the smaller of the ν target’s γ and the γ at which $\kappa(H + \gamma A^{\mathsf T}A)$ reaches a stated multiple of $\kappa(H)$ would state its digits in advance. What such a cap costs in work on the systems with badly conditioned constraints — where the two optima are furthest apart — is the trade this essay measured only at its two ends.

A larger system. At twelve unknowns the outer count is capped by finite termination. The same sweep at a hundred unknowns, where MINRES converges geometrically at small γ, would say whether the floors stay two decades wide or narrow, and with them how much the factor of thirty in ν at the optimum costs.