A shift that certifies a saddle

A minimum the Hessian cannot see found the second-order test for a constrained minimum inside one factorisation. A Hessian with four negative eigenvalues can sit at a constrained minimum, because the negative curvature points in directions the constraint forbids, and the signs of the pivots of the saddle-point matrix say so: ten positive and four negative means the reduced Hessian ZᵀHZ is positive definite, whatever H is, without a basis Z ever being formed. The essay ended on a question it could not answer from where it stood. Sparse codes perturb the two blocks of that matrix in opposite directions so that every ordering is legal, which changes the matrix whose signs are being counted. How far can that perturbation go before the count stops meaning what the test needs it to mean?

The perturbation that does the work found the answer’s first half without looking for it. On a positive definite H the whole of the quasi-definite guarantee is bought by the zero block’s perturbation γ, and the perturbation of H is almost free. On an indefinite H that stops being true. The theorem needs positive definiteness of H + δI, so δ has to pass the most negative eigenvalue of H, and on a Lagrangian’s Hessian that is not a small number.

At that δ the count certifies nothing about the problem that was posed. It certifies the problem with δ added to the curvature, and every saddle shallower than δ becomes a minimum. What survives the regularisation is not the count but the refinement run beside it, whose rate of convergence turns out to be the second-order test in another form.

Two problems on one constraint #

The construction is the saddle-point essay’s. The constraint matrix A has four rows and ten columns and a condition number of 10. H is built in an orthonormal basis split into the range of $A^{\mathsf T}$ and the null space of A: in the range of $A^{\mathsf T}$ it has four negative curvatures between −3 and 0, in the null space it has the reduced Hessian’s eigenvalues, and a random block couples the two.

For the minimum, the reduced Hessian’s eigenvalues are 0.1, 1, 2, 3, 4 and 5 — positive, so the point is a constrained minimum — and H has four negative eigenvalues, the most negative −4.67. For the saddle, one reduced eigenvalue is −1 instead of 1, so there is a feasible direction of descent, and the most negative eigenvalue of H is −5.08. The saddle-point matrix of the minimum has ten positive and four negative eigenvalues; the saddle’s has nine and five. Those are the counts the test is for.

Both matrices are unmistakably not quasi-definite at δ = 0. And the first finding is that, in floating point, that does not matter for whether they factorise.

With the zero block perturbed by 10⁻⁸ and H left indefinite, all three hundred orderings factorise. No theorem promises it, and the reason it happens is the one the perturbation that does the work found: an unpivoted factorisation fails on an exactly zero pivot, and it is the zero block that supplies exact zeros. Remove them and a matrix with generic entries meets a zero pivot with probability zero. What it meets instead are small ones, and the worst of three hundred grows by 1.1·10⁷ with a residual of 3.6·10⁻³. The guarantee δ would buy is a guarantee against coincidence, not against the orderings a sample finds, and its price is what the rest of this essay measures.

The count reads the shifted curvature #

The saddle-point essay’s count rests on a theorem of Gould’s: the inertia of K is the inertia of the reduced Hessian plus m positive and m negative eigenvalues. Adding δ times the identity to H adds δ to every eigenvalue of ZᵀHZ, so the regularised matrix’s pivots count the inertia of ZᵀHZ + δI.

The hero figure is that sentence drawn. The minimum’s reduced curvatures are all positive, adding δ keeps them positive, and its count reads ten at every δ from 0 to 7. The saddle’s negative curvature is −1, and shifted by δ it sits at δ − 1 in ZᵀHZ + δI: negative below δ = 1, positive above. Its count reads nine at every δ up to 0.95 and ten from 1.05 on. From that point the factorisation reports the inertia of a minimum, on a problem with a direction of descent, and nothing in the factorisation’s residual, growth or pivots distinguishes it from the genuine minimum’s.

The δ the quasi-definite guarantee needs is past the most negative eigenvalue of H: 4.67 for the minimum and 5.08 for the saddle. At any such δ the count certifies every saddle whose negative reduced curvature is shallower than δ, which on this construction is every saddle it can build. The regularisation that makes the ordering free has made the second-order test into a test of a different problem.

That is not an accident of this construction but the arithmetic of where the negative curvature lives. A Lagrangian’s Hessian at a constrained minimum is indefinite precisely in the directions the constraint forbids, and those directions can have curvature of any size. The most negative eigenvalue of H — the number δ has to pass — is a fact about those forbidden directions. The negative curvature a saddle needs to be caught — the number δ must not pass — is a fact about the allowed ones. Nothing links the two, and on this construction the first is five times the second.

What an inertia-correcting loop does with the same count #

Codes that minimise with a constraint already use this arithmetic on purpose. An inertia-correcting loop factorises K, reads the count, and if it is not n positive and m negative adds a multiple of the identity to H and factorises again, until it is. On the minimum the loop stops at δ = 0. On the saddle it stops at the first δ past 1, and the step it then computes is a step for a convexified problem, which is exactly what the loop exists to produce: a direction of descent from a point that is not a minimum.

The loop reads the count as a question — is this point a minimum? — and adds δ only when the answer is no. Quasi-definite regularisation adds δ before asking, for a different reason, and at a δ five times larger than any saddle here needs to hide. The two uses of one perturbation give opposite readings of the same pivot signs, and a code that does both has to keep the count from before the regularisation if it wants the test.

The regularised answer is not usable either. At δ = 5 the solve of the minimum’s regularised system in the natural order is wrong by 111 per cent: a perturbation of H by more than the size of H’s own eigenvalues moves the solution by more than the solution. Refinement is where the answer, and the test, come back.

Refinement contracts on the minimum #

Refinement against K forms the residual with the unregularised matrix and solves the correction with the regularised factorisation. The perturbation that does the work found that on a positive definite H its error is multiplied each step by δ/(μ + δ), with μ the reduced Hessian’s smallest eigenvalue. On an indefinite H the same algebra holds eigenvalue by eigenvalue, and the factor is |δ/(μ + δ)| for every reduced curvature μ. When every μ is positive, every factor is below one, however large δ is.

On the minimum at δ = 5 the error falls by 0.9804 a step, and 5/(0.1 + 5) is 0.9804. At δ = 2 it falls by 0.952, and 2/2.1 is 0.952. The rate is slow — three hundred steps take the error from 111 per cent to 0.2 per cent — because the slowest direction has curvature 0.1 against a shift of 5, and a refinement that removes a large regularisation is a proximal-point iteration taking small steps. It converges, at a rate set entirely by the smallest positive reduced curvature, and that rate is itself a statement that the smallest curvature is positive.

And diverges on the saddle #

On the saddle the same algebra gives a factor of |δ/(δ − 1)| along the negative direction, which is above one for every δ past a half.

At δ = 5 the saddle’s refinement error grows by 1.2500 a step, and 5/(5 − 1) is 1.25. At δ = 2 it grows by 2.000, which is 2/(2 − 1). The factorisation behind both runs reports a minimum. The refinement run beside it reports a direction along which the regularised solve overshoots the true one by a growing factor, and that direction exists because ZᵀHZ has a negative eigenvalue.

So the second-order test has moved from the pivots to the iteration. The count was an integer read once and blinded by δ. The refinement rate is a real number read over steps, and δ shifts it without hiding its sign: below one when every reduced curvature is positive, above one when one is negative and δ has passed half its size.

The band where refinement warns before the count goes wrong #

Between δ = |μ|/2 and δ = |μ| the two readings disagree in the other direction: the count is still right and refinement is already diverging.

At δ = 0.45 the factor along the saddle’s direction is |0.45/(0.45 − 1)| = 0.818, and the refinement error falls by exactly that, to 6.2·10⁻⁶ in sixty steps, with the count reading nine. At δ = 0.55 the factor is 1.22: the count still reads nine and the refinement error has grown to 4.3·10⁴ after sixty steps. At δ = 0.75 it is 3, and the error is 2.6·10²⁸. At δ = 1.05 the count flips to ten and the factor is 21.

The band is not a curiosity. An inertia-correcting loop that overshoots the curvature it is correcting by less than a factor of two lands in it: its count is right, and a refinement run to recover the unregularised step diverges. Reading the two together says more than either: a divergent refinement with a correct count means a saddle whose curvature lies between δ and 2δ, and a divergent refinement with a count reading minimum means one shallower than δ.

Every saddle diverges, and the shallow ones slowly #

The remaining question is how reliable a warning that arrives as a rate can be, and it depends on how deep the saddle is.

At δ = 7 every one of the seven saddles is certified a minimum, and every one diverges under refinement at |μ|/(7 − |μ|) above one: 1.0014 a step at μ = −0.01, 1.014 at −0.1, 1.17 at −1, 1.75 at −3 and 2.8 at −4.5, each measured between steps 200 and 400 and matching its prediction to three places. The deep saddles give themselves away in a handful of steps. The shallowest takes 485 steps for its error to double, while the minimum at the same δ contracts by 0.9859 a step — and at those rates, over the first hundred steps, the two histories look alike.

That is the honest limit of the test. A saddle whose negative curvature is a hundredth of the regularisation is detected only by a refinement run long enough to see a growth rate of 1.0014 separate from a contraction of 0.986, and that is hundreds of steps of a solve that was supposed to be a correction. The count, for all its blindness, was one factorisation. What the regularisation has done is convert a sign read once into a rate read over time, and the rate’s resolution is worst exactly where the curvature is smallest — which is where a minimum the Hessian cannot see found the count’s own floating-point blind band as well.

What the regularisation changes about the second-order test #

Set beside the unregularised count, the quasi-definite regularisation of an indefinite problem changes three things.

The count answers a shifted question. Its pivots count ZᵀHZ + δI, and the δ the guarantee needs is set by the most negative eigenvalue of H, which is a fact about forbidden directions. A saddle is hidden whenever its allowed negative curvature is shallower than that, and nothing prevents that being every saddle.

The guarantee was not what made the orderings legal. With γ = 10⁻⁸ and δ = 0 every one of three hundred orderings factorised. The guarantee protects against an exactly zero pivot arising by coincidence, and it costs the test.

The test survives as a rate. Refinement against K contracts at δ/(μ + δ) on every positive curvature and grows at |δ/(μ + δ)| on a negative one once δ is past half of it, measured to three and four figures here. It is slower and less decisive than a count, and it is still a test.

Two readings of one shift #

The count and the refinement rate look like two different tests. They are two functions of the same shifted curvatures, and that is why they disagree exactly where they do and why, between them, they miss nothing.

The count reads the sign of μ + δ for each reduced curvature μ. An eigenvalue count that cannot be slightly wrong made the case for reading signs: an integer from a factorisation is right or wrong, never nearly right. Shifting every curvature by δ keeps the integer exact and changes the question it answers, and nothing about its exactness warns that the question has changed. It is wrong for every saddle whose curvature lies between −δ and 0.

The refinement rate reads |δ/(μ + δ)|, which exceeds one for every curvature between −2δ and 0. So it catches every saddle the count misses, and more: it also diverges for curvatures between −2δ and −δ, where the count is still right, which is the band measured above. Below −2δ it converges, and there the count is right. The two cover the line between them. What neither covers well is a curvature close to zero, and there the problem is not the sign but the resolution: the rate is 1 + |μ|/δ, and for a saddle a hundred times shallower than the shift that is a number a run has to watch for hundreds of steps to tell from one.

The regularisation that legalises every order read refinement as a repair. It found refinement removing the perturbation until δ reached the matrix’s smallest singular value, and called the limit a cliff. On an indefinite problem the cliff is no longer a limit on how much regularisation can be taken back. It is the second-order test, and falling off it is the result.

That reading has a relative in the accuracy that is thrown away, where an outer loop decides what an inner solve’s accuracy is worth; here refinement’s history decides what the regularisation cost. It also names the way to lose the test. A run stopped after the few steps a residual test allows once the correction looks small — the kind of test a stopping test is a race describes — reads the rate over too few steps to see a growth of 1.0014, and returns the regularised answer with the count’s blindness intact.

None of this touches the count taken before δ is added. On the unregularised matrix the signs are the second-order test exactly, as the zero that is not a missing entry and its successors established, and the pivoting that factorises that matrix stably with no perturbation is the one when symmetry is not enough describes. The blindness belongs to what was added. A code that wants both the free ordering and the test can count once, on a factorisation it does not reuse, and regularise after.

What was not measured #

Two problems, one constraint, one coupling between the range and null-space blocks. The most negative eigenvalue of H depends on that coupling as well as on the range-space curvatures, and a problem whose Hessian is indefinite only in the null space — where every negative eigenvalue of H is a saddle’s — would make the guarantee’s δ and the saddle’s curvature the same number. Refinement here runs in the natural order with γ = 10⁻⁸; in a poor ordering the factorisation’s own residual adds an error refinement also has to remove, and whether that masks the rate on a shallow saddle is not measured.

The refinement rate is read off the error, which needs the true solution. A code has the residual, and the residual’s rate is the same product seen through K; how cleanly the residual’s history shows a growth of 1.0014 against a contraction of 0.986 is what a practical test would have to establish.

Still open: can the rate be read from the residual, and how small a regularisation keeps the count? #

The residual’s rate. The error was the quantity measured here because it was available. The residual history of the same refinement runs is what a solver sees, and whether a least-squares fit of its logarithm over a few dozen steps separates a shallow saddle from a minimum at the resolution the curvature sweep needs is the direct continuation.

A δ that keeps the count. The count is right for every δ below the shallowest negative curvature a problem has, and the orderings factorise with γ alone. A regularisation that takes δ = 0 and relies on γ gives up the guarantee and keeps the test; the measurement is how often, over orderings a fill-reducing heuristic actually produces, a pivot small enough to matter appears when H is indefinite.

Negative curvature confined to the null space. On a construction whose Hessian is negative only in allowed directions, the guarantee’s δ and the saddle’s depth coincide, and the count flips exactly where quasi-definiteness begins. Whether real Lagrangians look more like that construction or like this one is a question about optimisation problems rather than about matrices, and it decides how much of this essay a practitioner meets.