The shift that stops at the first right count

A minimum the Hessian cannot see turned Gould’s theorem into a test: the saddle-point matrix K has n positive eigenvalues exactly when the reduced Hessian ZᵀHZ is positive definite, so the signs of a factorisation the solver performs anyway say whether a point is a constrained minimum. It then measured the test’s blind spot. Inside a band that grows like u·κ(A)² — κ(A) being the constraint’s condition number — the count can read either way, and at κ(A) = 10⁸ saddles of curvature a tenth were reported as minima.

It ended on the use codes make of the count, and on a number nobody reports. When the count is wrong, a nonconvex interior-point or sequential quadratic programming code adds a multiple of the identity to H, factorises again and recounts, raising the multiple until the count is right. The step it then takes is a Newton step on a problem made convex along the constraint by that shift. So the shift is a real quantity with a real consequence — too small and the step is not a descent step, too large and the step is a timid one — and the loop’s output is the only estimate of it the solver ever makes.

This essay measures that estimate against the right answer. The construction makes the right answer exact: with Z orthonormal, adding δ to the diagonal of H adds δ to the diagonal of ZᵀHZ, so the smallest shift that fixes the count is μ, where −μ is the reduced Hessian’s smallest eigenvalue, and μ is chosen when the problem is built.

The schedule, written out #

The loop measured is the one published for IPOPT, taken from its first iterate, where there is no previous shift to start from. Factorise with no shift. If the count is wrong, try δ = 10⁻⁴. If that fails, multiply by a hundred, and after that by eight each time, until the count is right. The shift is then the first value in that sequence at which the factorisation reports n positive eigenvalues.

Every problem here is 10 × 4: ten unknowns, four constraints, a Hessian with three negative eigenvalues in the directions the constraint fixes, and a reduced Hessian with eigenvalues 0.5, 1, 2, 3, 4 and one at −μ. Eight draws of the construction at each μ, with μ from 10⁻⁸·²⁵ to 10⁰·⁷⁵ in half decades — offset by a quarter so that no curvature sits exactly on a point of the schedule, where the count would be deciding a sign at zero.

Too large, by an amount the curvature does not set #

On a constraint with κ(A) = 10 the loop never stops early. Every one of 152 trials ends at a shift at least as large as μ, and every one ends exactly where the schedule predicts: the eight draws at each curvature agree to all digits, because the count is right at every shift it reads and the only thing left to decide the answer is the sequence of shifts tried.

That sequence produces three regimes, and none of them is about the problem.

Below the first guess, every curvature gets δ = 10⁻⁴. The ratio of shift taken to shift needed is 10⁻⁴/μ: 18 at μ = 5.6·10⁻⁶, 1,800 at 5.6·10⁻⁸ and 1.8·10⁴ at the smallest curvature drawn. A reduced Hessian that is nearly flat is convexified as though it curved at 10⁻⁴.

Just above it, the jump of a hundred decides. A curvature of 1.8·10⁻⁴ fails at 10⁻⁴ and succeeds at 10⁻², so the shift is 56 times the need, and it falls back to 1.8 by a curvature of 5.6·10⁻³.

Beyond the jump, each failure multiplies by eight and the ratio saws between one and eight — 1.8, 4.5, 1.4, 3.6, 1.1, 2.9 and 7.3 at the half decades from 10⁻²·²⁵ to 10⁰·⁷⁵. The median over the whole range is 7.3 and the solve costs 3.2 factorisations on average.

None of this is a defect of the loop in the sense of a bug. It is what a loop does that is designed to find a shift that works in few factorisations rather than the smallest shift that works, and the essay that measured refinement with a regularised Hessian — a shift that certifies a saddle — found the cost of that design in another currency: a step computed with an over-large shift is a short step, and recovering the unshifted one takes iterations at a rate set by the shift over the curvature. What the measurement adds is that the ratio is not a property of the problem. Two problems whose curvatures differ by a factor of thirty — 1.8·10⁻⁴ and 5.6·10⁻³ — get the same shift, and two whose curvatures differ by a factor of three — 5.6·10⁻⁵ and 1.8·10⁻⁴ — get shifts a hundred apart.

Where the count cannot tell, the loop stops #

Now make the constraint ill conditioned and run the same sweep.

At κ(A) = 10⁶ the picture above a curvature of 10⁻⁵ is the one at κ(A) = 10 to the last digit. Below it, 19 of the 152 trials stop below μ, and all 19 stop at δ = 0: the first factorisation, with no shift, read n positive eigenvalues on a reduced Hessian with an eigenvalue at −μ. The deepest such saddle has μ = 5.6·10⁻⁶. The earlier measurement put the median width of the count’s blind band at 6.6·10⁻⁸ at this conditioning, and a single count can be wrong well outside the median; eight draws at nineteen curvatures find it wrong out to 5.6·10⁻⁶.

The grid the earlier measurement drew for one draw at this conditioning shows where those stops come from. It is the same count read at every |δ| on both sides of zero, and the band where it reads wrong is not a clean interval but a scatter:

On that draw the LDLᵀ count is wrong somewhere at |δ| of 10⁻⁵ and below, and three of its errors are saddles read as minima. The loop’s shift sweep sees the same thing from the other side: a loop is a reading at δ = 0 before it is anything else, so every saddle the grid marks with a cross is a saddle the loop stops on at once. The grid’s scatter is also why the stops in the shift figure appear at some curvatures and not their neighbours. Each curvature is a different matrix, the rounding lands on each differently, and eight draws at one curvature can produce three stops where the next half decade produces one.

At κ(A) = 10⁸ both failures are in the same figure. Sixty-three of 152 trials stop below the curvature, at every half decade from 10⁻⁸·²⁵ to 10⁻⁰·⁷⁵ and once more at 10⁰·⁷⁵, where μ is 5.6. Fifty-four of the sixty-three stopped at the first reading. And the draws that were not stopped early are not on the schedule either: the worst over-shift is 4.5·10⁶ at a curvature of 1.8·10⁻⁸, eight hundred times what the schedule gives, because the count kept reading wrong past shifts that had already fixed the reduced Hessian.

So on an ill-conditioned constraint the loop’s shift carries two errors that point in opposite directions, and which one a given solve suffers is decided by rounding. That is the ordinary behaviour of a threshold read inside its noise.

A sequence of tests stops at its first pass #

The other nine stops at κ(A) = 10⁸ are the part that is specific to a loop rather than to a count. They are trials whose first reading was right — a saddle, shift needed — and whose loop then shifted, read again, and stopped at a shift still below μ because a later reading was wrong in the passing direction.

A single count is one sample of a sign inside a band where the sign is unreliable. The loop is several samples at different shifts, and it stops at the first that reads “minimum”. A test that stops on its first pass is more likely to pass than any one of its readings, and every additional reading is another chance to be wrong in that direction.

Swept over conditioning and with the curvature taken all the way down to rounding, the deepest saddle passed in eight draws is 5.6·10⁻¹⁶ at κ(A) = 1 and 10, 5.6·10⁻¹⁴ at 10², 5.6·10⁻¹² at 10³ and 5.6·10⁻¹⁰ at 10⁴ — two decades of saddle for each decade of conditioning, the exponent of the count’s own band — and then 1.8·10⁻⁷, 5.6·10⁻⁶, 5.6·10⁻³ and 56 as the conditioning reaches 10⁸. The number of trials that stop on a saddle climbs from 11 of 296 at κ(A) = 10, all of them at curvatures within a few units of roundoff, to 132 of 296 at 10⁸.

Those stops at rounding level on a perfectly conditioned constraint are not failures in any useful sense — a curvature of 5.6·10⁻¹⁶ cannot be told from zero by any method — and they are drawn because the line would otherwise start at nothing. What the figure does say is that the loop’s reliability is set by the constraint’s conditioning and by nothing about the shift schedule, and that by κ(A) = 10⁷ a code using this loop cannot distinguish a minimum from a saddle whose negative curvature is several thousandths.

Bisection buys the shift back #

The first failure, over-shifting, has an obvious repair. Once the schedule has bracketed the shift — a failure at one value and a success at the next — bisect the bracket geometrically, one factorisation per halving, and keep the smallest shift at which the count read right.

At κ(A) = 10 it works as well as a bisection can. Two extra factorisations take the median ratio over the whole range from 7.3 to 1.8 and the worst from 1.8·10⁴ to 278; four take the worst to 4.3 and the median to 1.17; eight take the worst to 1.18. The mean cost goes from 3.2 factorisations a solve to 5.2, 7.2 and 11.2, and no trial stops below the curvature at any setting. Four bisections are the sensible place to stop: the shift is within a factor of a few of the curvature everywhere, for a little over twice the factorisations.

That is a real improvement, and it has a real cost that an interior-point code notices: the factorisation is the expensive step of the iteration, and a loop that more than doubles the factorisations more than doubles the linear algebra on every iterate where the inertia was wrong.

And pays for it in saddles #

At κ(A) = 10⁸ the same repair makes the second failure worse.

The trials stopped below the curvature go from 63 to 72, 82 and 90 of 152 as bisection goes from none to two, four and eight steps. The mean cost is lower here than at κ(A) = 10 — 2.8, 4.1, 5.4 and 8.0 factorisations — for the discouraging reason that more solves end at the first reading. Every bisection step is a factorisation read at a shift below the one that last succeeded, which is to say inside the region where the count is least reliable, and each reading that passes wrongly moves the answer down.

The two effects are the same fact seen from the two sides of the band. Outside it, reading the count more often converges on the right shift; inside it, reading more often converges on the first wrong answer. A code that refines the shift gains accuracy on problems whose constraints are well conditioned and loses reliability on the ones that are not, and nothing in the loop can tell which kind of problem it is in, because the only evidence it reads is the count.

What a code could read instead #

The measurement suggests two things a loop could do that it does not.

Start the schedule at the band. Below u·κ(A)² the count carries no information about the curvature’s sign, so a shift below it cannot be verified by counting. A loop that knew κ(A) — or an estimate of the constraint’s smallest singular value, which a few steps of an iterative method on AAᵀ provide — could take its first guess from there rather than from 10⁻⁴, and refuse to bisect below it. On a well-conditioned constraint that changes nothing, since the band is at rounding. On an ill-conditioned one it converts a silent false certificate into an explicit floor: the shift is at least this, because nothing smaller can be checked.

Check the passing reading once. A solve that stops on a right count can confirm it by a route whose band is narrower. The count through an orthonormal null-space basis goes blind in a band growing like κ(A) rather than κ(A)², and forming that basis once, at a point where the loop has stopped, costs a factorisation of the constraint — a price paid only when the loop has something to confirm. Two ways to remove a constraint measured the conditioning each route inherits, and this is the place in a solver where the difference between one power of κ(A) and two is an integer.

Neither is measured here, and both have a cost: the first needs an estimate of κ(A) that is itself unreliable at the conditionings where it matters, and the second needs a null-space basis, which on a sparse constraint is exactly what the basis nobody chose on purpose warned is dense or badly conditioned.

What a wrong shift costs the iteration it belongs to #

Both errors have a price that is paid outside the loop, and neither is visible in its output.

An over-large shift gives a step that is correct for a different problem. Along the reduced Hessian’s negative direction the shifted system has curvature δ − μ instead of the true −μ, so a shift of 1.8·10⁴ times the need turns a direction the method should move far along into one it barely moves along at all. Interior-point codes then take more iterations to leave the neighbourhood of a saddle, and the accuracy that is thrown away is the general form of that trade: work spent getting a step exactly right for a problem that is not the one being solved.

A stop on a saddle gives a step computed from an indefinite reduced Hessian, which may not be a descent direction for the merit function the method uses, and the line search then rejects it or accepts a tiny fraction of it. The solver sees a stalled iteration and has no reason to connect it to a count read three factorisations earlier. A test with no tolerance in it found a stopping certificate in the same solver whose only input was the factorisation’s own output; this loop is the opposite case, a certificate whose reliability is set by the constraint’s conditioning, which it never reads.

What the measurement rests on #

One shape, 10 × 4, with a reduced Hessian that has a single negative eigenvalue and the rest from 0.5 to 5, and a constraint whose singular values are geometric from one to 1/κ(A). Eight draws per point. The shift is applied to H only, as the published loop applies it; the loop’s second perturbation, of the constraint block, is applied only when the factorisation reports a zero eigenvalue, which none of these problems produce, and it is the subject of the next measurement.

The schedule’s constants — 10⁻⁴, a hundred and eight — are the published ones, and the regimes above move with them. A loop started at 10⁻⁸ would over-shift small curvatures ten thousand times less and would read the count at shifts four decades closer to the band. The measurement is of this schedule, and the argument — that the ratio is set by the schedule when the count is reliable and by rounding when it is not — is what carries to any other.

The claim that has to fail #

The claim is the one that makes the loop feel safe: it raises the shift until the count is right, a right count is a minimum, so the loop never stops on a saddle. Fed curvatures between 5.6·10⁻⁴ and 5.6·10⁻³ at κ(A) = 10⁸ and required to show that no trial stops below the curvature, it fails. And beside it the measurement at κ(A) = 10 holds the claim to its own standard: there not one of 152 trials stops early, so the failure is the constraint’s conditioning and not the loop.

An eigenvalue count that cannot be slightly wrong is the general form of what this loop runs into. A count is exactly right or wrong by a whole eigenvalue, and a procedure built on reading counts repeatedly inherits both properties: it is exact when the count is, and wrong by a whole verdict when it is not. A condition number sent to infinity found interior-point methods manufacturing ill-conditioning on purpose, and the κ(A) axis here is the constraint’s own; the two compound in a real solver, and neither is visible in the shift the loop reports.

Still open: a constraint that is nearly dependent, and a floor for the schedule #

The constraint that is nearly a combination of the others. Every constraint here has full row rank, and its conditioning is spread geometrically over four singular values. A constraint whose smallest singular value alone approaches zero is the case the published loop treats separately — by perturbing the constraint block — and the question is where the count stops seeing such a constraint, what the Hessian shift does when it has, and whether the second perturbation repairs it or merely decides it. A constraint the count stops seeing makes that measurement.

A floor read from the constraint. The band’s width is known in form, u·κ(A)² times a constant, and a schedule that started there and refused to bisect below it would trade silent false certificates for an explicit lower bound on the shift. How close an estimate of κ(A) from a few iterations gets to the band, and how many false stops it removes at what cost in over-shift, is a single sweep over the same construction.

The previous iterate’s shift. A real solve starts each iterate’s loop from a third of the last shift, so the schedule is path-dependent and an early over-shift propagates. Whether that memory damps the sawtooth or carries a false stop from one iterate to the next is a question about a sequence of solves rather than one.