A minimum the Hessian cannot see

Everything the first essay in this field established about the saddle-point matrix rested on one hypothesis stated in its second line: H is positive definite. Under it the inertia of K is (n, m, 0) for every H and every A, and the count is a theorem about the shape of the matrix rather than a measurement of anything.

An optimisation code does not have that hypothesis. The H in its saddle-point matrix is the Hessian of a Lagrangian, and at a perfectly good constrained minimum that Hessian is routinely indefinite — the objective may curve downwards in directions the constraint does not allow the solution to move in, and nothing about the minimum cares. A ball resting in the bottom of a groove cut across the top of a hill is at a minimum of its height along the groove, and the height’s Hessian has a negative eigenvalue.

So the question an optimisation code actually has to answer is not the one the field has answered. It is: given an H that is not definite, is the point a minimum on the constraint or a saddle on it? And the tool the field used first — a Cholesky, which fails exactly when a matrix is not definite — has nothing to say, because it fails on H before it reaches the part of the question that matters.

The theorem that survives without the hypothesis #

Write the unknowns in an orthonormal basis [Y Z], with Y spanning the range of Aᵀ and Z its null space. In that basis A becomes [A Y, 0] — the constraint sees only the Y directions — and H splits into four blocks, of which the one in the corner, ZᵀHZ, is the reduced Hessian: the curvature of the objective along the directions the constraint leaves free. It is the object the null-space method factorises, and it is the object the second-order condition for a minimum is about. A point satisfying the first-order conditions is a strict constrained minimum when ZᵀHZ is positive definite, and not when it has a negative eigenvalue. H itself does not appear in the condition.

The theorem that connects that condition to K is Gould’s, and its statement is short:

In(K) = In(ZᵀHZ) + (m, m, 0)

The inertia of the saddle-point matrix is the inertia of the reduced Hessian with m positive and m negative eigenvalues added. The proof is Sylvester’s law again — a congruence built from [Y Z] and a block elimination through the nonsingular m × m block AY, which pairs each constraint direction with one multiplier and contributes one eigenvalue of each sign per pair — and nowhere in it is H required to be definite. When H happens to be, ZᵀHZ is too and the count collapses to the (n, m, 0) of the first essay. When it is not, the count stops being a fact about the shape and becomes a test: n positive eigenvalues if and only if the reduced Hessian is positive definite.

That is a strong statement, and the reason it is worth an essay is the next sentence. Counting the eigenvalues of K does not require them. Sylvester’s law read as an algorithm says the signs of the pivots of any symmetric elimination give the same count, so the second-order test is available from a factorisation of K — the factorisation a code computing a Newton step on this system performs anyway — without Z, without ZᵀHZ and without an eigenvalue anywhere.

Four negative eigenvalues, and a minimum #

The figure above is built so that every quantity in it is known in advance. The constraint A is 4 × 10 with singular values from 1 down to 1/10; Y and Z come from a QR of Aᵀ; the range block of H has eigenvalues −3, −2, −1 and 0, the coupling block is random, and the reduced block is given eigenvalues 0.5, 1, 2, 3, 4 and 5 before H is assembled. The Hessian that comes out has eigenvalues

−4.612 −3.988 −1.809 −1.485 1.307 2.549 2.946 4.036 5.022 5.533

— four negative, the coupling having pushed the range block’s spectrum around — and a Cholesky of it computes pivots 1.687 and 0.674 and then −7.456, and stops. As a statement about H that is right: H is indefinite. As a statement about the optimisation problem it is useless, since the problem was built with a minimum.

K has fourteen eigenvalues and they are

−4.734 −4.047 −1.879 −1.539 0.001 0.009 0.062 0.168 1.315 2.562 2.951 4.073 5.023 5.536

Ten positive and four negative, which is In(ZᵀHZ) = (6, 0, 0) plus (4, 4, 0). The four small positive values between 0.001 and 0.168 are worth a glance. They belong to the pairing of constraint directions with multipliers, and their sizes are set by the constraint’s singular values — the smallest here is a tenth — against the curvature of H in the directions the constraint fixes, which in this construction is negative. Their signs are what the theorem fixes; their sizes are what a floating-point count will eventually have to resolve, and the second half of this essay is about what happens when it cannot.

The count was taken four ways and the four agree. A Bunch–Kaufman LDLᵀ of K, which chose one 2 × 2 pivot on the way, returns (10, 4, 0) from the signs of its blocks. An elimination with no interchanges at all returns (10, 4, 0). A Jacobi sweep over K returns it. And the route that forms Z and takes the eigenvalues of ZᵀHZ returns six positive values and adds four of each. Only the last of those needs to know what Z is.

One curvature turned, and one eigenvalue moves across #

The theorem is an equality of counts, so it has a sharper test than agreement at one point: change the reduced Hessian’s inertia and see whether K’s changes by exactly the same amount.

One eigenvalue of the reduced Hessian set to −1, everything else as before. H still has four negative eigenvalues — the top row barely changes, because the negative curvature introduced lives in one null-space direction and H’s own spectrum is dominated by the range block. The middle row now has a mark to the left of zero: the point is a saddle on the constraint. And K’s count is (9, 5, 0), one eigenvalue having crossed from the positive side to the negative.

The library checks this at nine configurations — three shapes (10 × 4, 12 × 3 and 9 × 6) and zero, one and two negative reduced curvatures — and requires every route to return In(ZᵀHZ) + (m, m, 0) at each. In all nine H is indefinite, with between three and five negative eigenvalues, and its Cholesky stops between the second row and the fourth. The count read off K follows the middle row of the figure every time and the top row never.

The 9 × 6 case is the one that shows most plainly how little H has to do with it. Five of H’s nine eigenvalues are negative. The constraint removes six directions and leaves three, the objective curves upwards along all three, and K reports (9, 6, 0) — a minimum. A reader looking only at H would have concluded, with more than half its spectrum below zero, that nothing here could be a minimum at all.

A test the solve was going to pay for #

The practical weight of Gould’s theorem is in what it costs, so it is worth being exact about the comparison.

The route through the null space needs a basis. An orthonormal Z from a Householder QR of Aᵀ costs about 2m²(n − m/3) operations; forming ZᵀHZ costs n²(n − m) more; and an eigenvalue decomposition or a Cholesky of the (n − m)-square result finishes it. On a sparse problem it costs something worse than operations: the orthonormal basis of a sparse constraint is dense, and the basis that preserves sparsity has a condition number the reduced Hessian inherits squared.

The route through K needs a symmetric indefinite factorisation of an (n + m)-square matrix — about (n + m)³/3 operations dense, and on a sparse problem whatever fill the ordering allows. That looks like the more expensive of the two until the context is added. A Newton or interior-point step on this problem is a solve with K, and the factorisation that allows 2 × 2 pivots is how codes perform it. The count is sitting in the factor’s diagonal blocks when the solve finishes. It costs a pass over n + m pivots, which is nothing.

That is why interior-point codes for nonconvex problems read it at every iteration. When the count comes out wrong — fewer than n positive pivots — they add a multiple of the identity to H and factorise again, repeating until the count is right, so that the step they take is a descent step for a problem that has been locally convexified along the constraint. The inertia of K is used as the certificate that the modification has gone far enough, and nobody forms Z to check.

Where the count is right to the last digit #

A count is an integer, and a count cannot be slightly wrong: it is exactly right or wrong by a whole eigenvalue. The question the spectra field asked of Sylvester’s law is the one to ask here — how close to zero can the deciding eigenvalue come before the count is wrong — and here the deciding eigenvalue is the reduced Hessian’s smallest, δ, which is a quantity the factorisation of K never computes.

So the construction is swept. δ is set to ±10⁰, ±10⁻¹, and so on down to ±10⁻¹⁶, and at each value three routes are asked for the positive count: ten is right when δ > 0 and nine when δ < 0.

With κ(A) = 1 the grid is almost entirely right. All three routes return the correct count down to |δ| = 10⁻¹⁵ and go wrong only at 10⁻¹⁶, where the reduced Hessian’s smallest eigenvalue is smaller than the rounding of the entries it is computed from. That is not a failure of any method. A matrix whose smallest eigenvalue is 10⁻¹⁶ and a matrix whose smallest eigenvalue is −10⁻¹⁶ differ by less than the arithmetic can represent, and no route can be asked to tell them apart. Over eight draws of the construction the median band is 10⁻¹⁶ for the LDLᵀ count and for the null-space count alike.

At this conditioning the free certificate is exactly as good as the expensive one.

The same test on a constraint that is not #

The constraint in this family has singular values geometric from 1 down to 1/κ(A), so κ(A) is a knob that leaves everything else in place.

At κ(A) = 10⁴ the picture separates. The Bunch–Kaufman count is wrong at several values of |δ| up to 10⁻¹⁰, the count from an elimination with no interchanges at values up to 10⁻⁸, and the count through the orthonormal null-space basis only at 10⁻¹³ and below. The wrong cells are not contiguous — a count that is wrong at 10⁻¹¹ can be right at 10⁻¹² — which is what a sign decided by rounding looks like: each value of δ is a different matrix and the rounding lands differently on each.

The cells marked × are the ones worth dwelling on. They are δ < 0 — a saddle — reported as ten positive eigenvalues — a minimum. On this draw the LDLᵀ route produces six of them. A certificate that is wrong by raising an alarm costs a code an unnecessary modification of H; a certificate that is wrong by passing a saddle lets a nonconvex method step towards a point that is not a minimum and report that it is.

At κ(A) = 10⁸ the count read off K is wrong at |δ| = 10⁻¹. The reduced Hessian’s smallest eigenvalue is a tenth, a number nobody would describe as near zero, and a factorisation of the saddle-point matrix cannot reliably tell whether it is plus or minus. Nine saddles on this draw are reported as minima. The route that forms Z, on the same matrices, is wrong only below 10⁻⁹.

The square, measured across eight draws #

A single draw of a sign decided by rounding is an anecdote, so the band is measured properly: eight seeds of the construction, five conditionings of the constraint, δ swept over ±10⁰ to ±10⁻¹⁶ in half decades, and for each seed the widest |δ| at which each route returns the wrong count.

The medians for the Bunch–Kaufman count off K run 3.2·10⁻¹⁵, 2.1·10⁻¹¹, 6.6·10⁻⁸ and 6.6·10⁻³ at κ(A) = 10², 10⁴, 10⁶ and 10⁸ — four decades of band for every two of conditioning, a fitted slope of 2.02. The medians for the count through an orthonormal Z run 3.2·10⁻¹⁶, 3.2·10⁻¹⁴, 3.2·10⁻¹² and 6.6·10⁻¹⁰ — two decades for every two, a fitted slope of 1.05. The unpivoted elimination of K sits above the Bunch–Kaufman line at every conditioning, by about a factor of two to thirty, with the same slope; the pivoting helps the constant and does not touch the exponent.

The worst single draw is starker than the median. At κ(A) = 10⁸ one seed’s LDLᵀ count is wrong at |δ| = 1, where the reduced Hessian’s smallest eigenvalue is as large as its next one. And the dangerous errors grow with the band: over the 528 trials at each conditioning, the LDLᵀ count reports a saddle as a minimum 6 times at κ(A) = 1, 16 times at 10², 46 at 10⁴, 71 at 10⁶ and 111 at 10⁸.

The two dashed reference lines, u·κ(A)² and u·κ(A), are drawn with a constant of one rather than fitted, and each median line runs parallel to its reference — the count off K between two and two and a half decades beneath u·κ(A)², the count through Z between one and one and a half beneath u·κ(A). The slopes are measured; the constants in front of them are not derived here.

Why the square is there #

The count read off K is range-space arithmetic, and the second essay in this field priced range-space arithmetic already: eliminating the multipliers produces AH⁻¹Aᵀ, and that matrix carries the square of the constraint’s condition number.

An elimination of K does not form AH⁻¹Aᵀ explicitly — when H is indefinite it cannot even eliminate H first — but every symmetric elimination of K passes through Schur complements that pair constraint rows with the unknowns they constrain, and those pivots are the small positive eigenvalues noted above: the ones that sat between 0.001 and 0.168 at κ(A) = 10. Their size is governed by the constraint’s smallest singular value. The reduced Hessian’s curvature reaches the pivot signs only as a difference between quantities of that size, so a relative rounding error of u in the elimination is a relative error of about κ(A)² in the difference. Rounding of that size decides the sign of δ whenever |δ| is smaller than it, and the measured band is that statement with the constant left in.

The null-space route separates the constraint from the curvature before any curvature is computed. Its only contact with the conditioning of A is the QR that produces Z. A Householder QR keeps its Q orthogonal to rounding whatever the matrix, and the subspace that Q spans is as accurate as the null space of A is well determined, which the standard perturbation theory puts at about κ(A)·u. ZᵀHZ is then formed from an orthonormal matrix and H, neither of which is ill conditioned, and its smallest eigenvalue is perturbed by the subspace error times ‖H‖. One power of κ(A), measured as 1.05.

That mechanism is the explanation offered here and it matches both exponents. It is argued rather than proved: no bound on the band was derived here, and a proof would have to follow the rounding through Bunch–Kaufman’s pivot choices, which change with δ.

What the certificate is worth, then #

The measurement does not say the free certificate is unreliable. It says exactly where it is reliable, in a form a code can use. A count read off K certifies a constrained minimum whenever the reduced Hessian’s smallest eigenvalue exceeds something of the order of u·κ(A)², and a solver already knows one of those two numbers and can estimate the other from the factorisation it has. On a constraint with κ(A) = 10², which is an ordinary constraint, the band is 10⁻¹⁴ and there is no practical difference between the two routes. On one with κ(A) = 10⁶, a reduced curvature below 10⁻⁷ cannot be certified this way and should not be claimed.

It also says something about the modification loop described above. A code that adds multiples of the identity to H until the count is right is adding them until the count reads right, and inside the band the count can read right on a saddle. The shift that loop settles on is therefore a quantity with a floor of about u·κ(A)², below which it is decided by rounding rather than by the problem. That is a measurable claim about a real loop and it is not measured here.

And it says, once more, the thing the regularisation that legalises every order and the condition number sent to infinity each said in their own field: in a saddle-point system the constraint’s conditioning enters through two doors, and which door an algorithm uses decides whether it pays κ(A) or κ(A)². The null-space method uses one door and the count off K the other, and the count is only free because the price was paid somewhere else.

Where this goes next #

The size of the shift. The inertia-correction loop — add a multiple of the identity to H, factorise again, recount — settles on a shift, and the band measured here puts a floor under what that shift can mean. How large the loop’s shift is against the reduced Hessian’s true smallest eigenvalue, across κ(A), is the direct continuation, and it would say whether the loop over-convexifies well-posed problems or under-convexifies badly posed ones.

Dependent constraints. Every A here has full row rank. As σₘ(A) reaches zero the theorem’s m pairs become m − 1, a zero eigenvalue arrives and the count gains a third entry. A count that must distinguish a nearly dependent constraint from a nearly singular reduced Hessian is asking two questions of one integer.

A count after deliberate regularisation. Sparse codes perturb K’s two blocks in opposite directions so that every ordering is legal, which changes the matrix whose inertia is being read. How far that perturbation can go before it changes the count the second-order test depends on is a question the quasi-definite essay did not ask and this one makes answerable.