A loop that asks the null space why

The loop at the centre of these essays is the one every nonconvex constrained optimiser runs. Factorise the saddle-point matrix with a symmetric indefinite LDLᵀ, count its positive and negative pivots, and if the count is not n positive and m negative, add $\delta I$ to the Hessian and try again with δ growing on a schedule. A minimum the Hessian cannot see showed why the count is the right test in exact arithmetic: by Gould’s theorem it equals the count of the reduced Hessian $Z^{\mathsf T}HZ$ plus (m, m, 0), so it says whether the point is a constrained minimum without ever forming Z.

Two essays then measured what the loop does with the count in floating point. The shift that stops at the first right count found the shift it settles on is the schedule’s number, not the curvature’s, and that on an ill-conditioned constraint it stops wherever the count first reads right — certifying saddles as minima in a band that grows like u·κ(A)². A constraint the count stops seeing found the opposite fault: a constraint nearly dependent on the others makes the count wrong at a genuine minimum, and the loop shifts a problem that needed nothing. Both ended on the same repair, stated and not measured. “The null-space route can. Its count is right to rounding on every draw here … at the cost of one QR of $A^{\mathsf T}$ performed only when the count has gone wrong.” And from the earlier one: “Check the passing reading once.”

Those are two different loops, and they do not do the same thing.

Two faults behind one integer #

The integer the loop reads cannot say why it is wrong. A wrong count means either that $Z^{\mathsf T}HZ$ has a negative eigenvalue — the point is a saddle and H needs a shift — or that the factorisation of K could not resolve a pair of eigenvalues of size $\sigma^2/|h|$, where σ is a constraint’s smallest singular value and h the curvature along the direction it barely constrains, and has read that pair as though the constraint were not there. The first needs a shift. The second is a minimum and needs nothing; shifting H at any size does not bring the constraint back.

A QR of $A^{\mathsf T}$ separates them. Its last n − m columns are an orthonormal basis Z of the null space, and the eigenvalues of $Z^{\mathsf T}HZ$ are the second-order verdict directly, with an error that grows like κ(A) rather than κ(A)². It also answers the question the loop’s schedule guesses at. Shifting H by $\delta I$ shifts $Z^{\mathsf T}HZ$ by exactly $\delta I$, because Z is orthonormal, so the most negative reduced eigenvalue is the curvature the shift has to overcome. The loop measured here takes twice it, in one step.

Two arbitrated loops follow. The first consults the null space only when the count is wrong: a positive reduced Hessian means a weak constraint and no shift; a negative one means a saddle and a shift of twice its depth. The second consults it on every count, right or wrong. Both are compared with the ordinary loop on the same problems.

A weak constraint is left alone #

The problems are the preceding essay’s: ten unknowns, four constraints, the smallest singular value σ of the constraint matrix from 10⁻⁴ down to 10⁻¹⁴, curvature −1 along the direction it barely constrains, and a reduced Hessian that is positive definite, so that every problem is at a minimum. Down to σ = 10⁻⁸ the count is right and neither loop does anything. From 10⁻⁹ the count is wrong on three to five of eight draws, and the ordinary loop shifts each of them — 22 problems in all, by as much as 2,621 on one draw at σ = 10⁻¹⁰.

The arbitrated loop meets the same 22 wrong counts, performs one QR on each, finds the reduced Hessian positive definite on every one, and shifts nothing. It reports a weak constraint instead, which is information the ordinary loop cannot produce: the solver learns that a constraint is nearly redundant, where the ordinary loop reports only that it needed a large shift. The cost is one factorisation of K and one QR, where the ordinary loop spent between 1.5 and 2.6 factorisations on average in each row of the sweep.

That essay’s own figure is the ordinary loop’s half of the comparison drawn at full resolution, and it is what the arbitrated loop removes entirely. Its shifts are not small corrections to a nearly right answer: they are a Hessian made positive definite by adding up to 2,621 times the identity to a problem that was already at a minimum, and a Newton step taken with that matrix is a steepest-descent step with a step length of about 1/2,621. A solver that takes it does not fail; it slows down on the iterations where the constraint is weak, and nothing it reports says why. The arbitrated loop’s report — a weak constraint, with σ from the QR — is the diagnosis that slowdown never came with.

A saddle is shifted by what it needs #

The saddles are the problems of the shift essay: ten unknowns, four constraints with a given condition number, and a reduced Hessian with one eigenvalue at −μ, for μ from 5.6·10⁻⁹ to 5.6, eight draws each. At κ(A) = 10 and 10⁴ every count is right, and the ordinary loop’s shift is what that essay found — a median of 7.3 times the need, and 17,783 times at the shallowest saddle, where the schedule’s first guess of 10⁻⁴ is far above a curvature of 10⁻⁸. Both arbitrated loops shift by 2.000 times the need on all 152 saddles, to four figures, because the shift is read off the reduced eigenvalue rather than searched for.

They also spend less. The ordinary loop averages 3.2 factorisations of K on these saddles — the first, then the schedule’s guesses until the count is right. The arbitrated loops spend exactly two: the first, and one of the shifted matrix that the solver needs anyway for its step, plus one QR of $A^{\mathsf T}$, an m-by-n factorisation beside an (n + m)-square one.

Where the certificates slip through #

Turn the dial to κ(A) = 10⁸, and the ordinary loop certifies 63 of the 152 saddles as minima, as the shift essay found: the count of K cannot see a negative curvature smaller than about u·κ(A)², which at 10⁸ is of order one, so it reads right on saddles as deep as 5.6 and the loop stops there.

The loop that consults the null space on wrong counts certifies 57. It catches six — saddles whose count was wrong at the first factorisation, on which the ordinary schedule then stopped at a shift below the need because the shifted count read right in the band — and it reduces the deepest pass from 5.6 to 0.056. But the other 57 had counts that read right at δ = 0. The arbitrated loop, like the ordinary one, accepted them without asking. A false certificate is by definition a count that reads right, and a check that runs only when the count reads wrong is a check that never meets one.

The loop that consults the null space on every count certifies 5 of 152, the deepest at μ = 1.8·10⁻⁸. At κ(A) = 10⁷ the three loops certify 42, 37 and none; at 10⁶, 19, 19 and none; at 10⁵, 5, 5 and none. Below 10⁵ no loop certifies any saddle on this grid.

The six it does catch are worth a sentence, because they show the arbitration working exactly as designed and still not being enough. On each of them the first count was wrong, so the arbitrated loop asked; the reduced Hessian had a negative eigenvalue; and the shift was set from it at twice the depth, which is above the need by construction. The ordinary loop on the same six had shifted by its schedule, and the schedule’s shifted count — in the blind band — read right at a shift below the curvature. Measured shifts replaced guessed ones, and every guess the arbitration replaced was a pass it removed. The 57 it left were never guessed at: the loop was never asked to shift them.

Two bands, one each #

Drawn against the conditioning, the deepest pass of the ordinary loop and of the loop that asks on wrong counts both follow u·κ(A)², the band in which the count of K is blind. The loop that asks on every count follows u·κ(A): its one pass on the grid, 1.8·10⁻⁸ at κ(A) = 10⁸, sits a factor of 1.6 above 1.1·10⁻⁸. The null-space count is not exact either — two ways to remove a constraint measured why, since the QR that forms Z inherits one power of κ(A) — but one power of κ(A) against two is eight decades at 10⁸, and the difference between certifying a saddle of depth 5.6 and one of depth 2·10⁻⁸ is the difference between a wrong answer and a rounding error.

Against bisection, and against the perturbations that legalise the count #

The shift essay tried the obvious refinement of the schedule: after the first right count, bisect between it and the last wrong one, spending more factorisations to land closer to the need. It bought the over-shift back and paid for it in saddles, because every factorisation in the bisection is another count in the blind band and another chance to read right. The arbitrated shift gets closer than bisection did without adding a single count: twice the need is a fixed ratio at every depth, and the one factorisation of the shifted matrix is the one the solver was going to make anyway. The null space does what bisection was trying to do, and it does it by reading the quantity the bisection was searching for.

The other family of repairs perturbs K itself. The regularisation that legalises every order measured the quasi-definite perturbation, adding to H and subtracting from the constraint block, which gives K a factorisation with a diagonal D under every ordering; and the preceding essay found that the constraint-block half of it decides a weak constraint’s fate deterministically, at $\sigma = \sqrt{|h|\,\delta_c}$, dropping it below that. Those perturbations make the count well defined; they do not make it right, and on a weak constraint they make it deliberately wrong in a known way. The arbitration is the complement: it leaves K alone and answers the question the perturbation settles by fiat. A solver that knows from its QR that a constraint is weak can then choose — keep it and apply no shift, or drop it on purpose — instead of having the perturbation choose for it at a threshold it did not compute.

The freedom a symmetric factorisation does not have is the reason none of this can be fixed inside the factorisation. A symmetric permutation of K cannot choose a column independently of its row, so the elimination has no freedom to route around the pair of small eigenvalues a weak constraint creates, or the cancellation that hides a shallow saddle. The information is in the null space, and the factorisation of K does not visit it.

What each loop costs #

The first arbitrated loop costs nothing on a problem whose count is right, and one QR where it is wrong. That is its virtue and its limit. It repairs the two faults that show up as wrong counts: the weak constraint, which it names instead of shifting, and the over-shift, which it replaces with the measured need. It does nothing for the fault that shows up as a right count.

The second costs one QR of $A^{\mathsf T}$ and one eigenvalue problem of order n − m at every Newton step. On the problems here that is trivial. On a large sparse problem it is not: Z is dense, and forming $Z^{\mathsf T}HZ$ costs products with H for every null-space direction — the reason codes count inertia at all, as the basis nobody chose on purpose found in the fill and conditioning a null-space basis brings. So the full check is affordable exactly where the count of K is least needed, on small dense problems, and least affordable where the count’s band matters most.

There is a middle path the measurement points at. Only the steps where κ(A) is large can produce a false certificate, since below 10⁵ none occurred on this grid. A loop that estimated the constraint’s smallest singular value — which the QR of the first arbitration already provides, and which a few steps of an iterative method on $AA^{\mathsf T}$ estimate cheaply — could consult the null space on right counts only when u·κ(A)² exceeds the curvature it cares about. That would pay the full check’s price only where the count cannot be trusted.

What the integer can and cannot carry #

The loop’s defect, seen from here, is not that it uses a count. It is that a count is one integer doing two jobs. As a certificate it answers “is this a minimum”, and in the band u·κ(A)² its answer is sometimes wrong in the dangerous direction. As a trigger it answers “should the loop shift”, and a wrong count can mean a saddle or a weak constraint, which need opposite responses. The null space answers both questions separately, at the price of forming a basis the count was designed to avoid.

What the first arbitrated loop shows is that the trigger can be repaired cheaply and the certificate cannot. Every problem whose count went wrong was diagnosed correctly by one QR, and every problem whose count went right but should not have was missed. The zero that is not a missing entry opened these measurements by showing that the saddle-point matrix is indefinite by construction and no pivot order changes that; the last measurement in it is that the integer an indefinite factorisation returns is trustworthy in one direction only.

What this does not settle #

One problem size, eight draws a point, and a grid of curvatures that stops at 5.6·10⁻⁹. The null-space loop’s passes are measured only down to that depth, so at κ(A) ≤ 10⁷ its band of κ(A)·u lies below the grid and the absence of passes there says nothing about it.

The margin of two in the arbitrated shift is a choice. A smaller margin brings the shift closer to the need and, in the band where the reduced eigenvalue itself is uncertain by κ(A)·u, risks a shift that falls short; a margin of two is safe on every problem here and is not tuned.

The weak-constraint problems are all at minima. A saddle behind a weak constraint — negative curvature in the null space and a constraint the count cannot see — gives a wrong count for two reasons at once, and whether one QR still separates them is not measured.

Still open: when to ask, and a weak constraint in front of a saddle #

Asking when the conditioning says to. The full check is needed only where u·κ(A)² is above the curvature a solver must resolve. A loop that carried the smallest singular value from its first QR forward through the Newton iteration, and asked the null space on right counts only while that product was large, would pay the full price on a few steps. How many steps of a real iteration that is, and whether the estimate stays good as the constraints move, is the measurement.

Both faults at once. A problem with a saddle and a nearly dependent constraint gives the count two reasons to be wrong. The reduced Hessian computed through Z separates the constraint’s weakness from the curvature’s sign, in exact arithmetic; whether it still does when σ is near the resolution of the QR itself, where the weak direction and the null space blur, is the case this loop would meet at the edge of both bands.