Numerical Linear Algebra
where the algebra stops being the arithmetic
Series

Saddle-point systems — the series

6 essays on one idea, from the one that introduces it to the one that assumes the rest.
  1. -1-0.582271-0.1645420.2531860.6709151.088641.506370eigenvalue4 negative10 positivecounted before it was formedpositive10negative4at zero0innermost ratio39the zero block is a theoremand so is the count either side of it

    The zero that is not a missing entry

    A constrained minimisation produces a matrix with a zero block, and the zero is a theorem rather than a sparsity pattern. No pivot order makes it positive definite, no precision changes that, and Cholesky does not fail somewhere on it — it fails at the first constraint row, on a number the problem already contained.

    part 1 · constraint
  2. 01234510⁻¹⁷10⁻¹³10⁻⁹10⁻⁵10⁻¹10³10⁷10¹¹log₁₀ κ(A)condition number, and relative errorκ(S)κ(ZᵀHZ)range-space errornull-space erroragainst a BigInt answerκ(S) at κ(A) = 10⁵4·10¹⁰κ(ZᵀHZ), all stops21range-space forward error5.3·10⁻⁶null-space forward error5.8·10⁻¹²both are the same algebraand only one squares

    Two ways to remove a constraint

    A constrained system can be reduced by eliminating the multipliers or by eliminating the constrained directions. Both give the same answer in exact arithmetic and inherit different condition numbers — one of them squares the constraint's, and the other does not contain it at all.

    part 2 · constraint
  3. -5-3-11350eigenvalueHZᵀHZK4 negative — Cholesky of H stops at row 30 negative — a minimum on the constraint(10, 4, 0) = In(ZᵀHZ) + (4, 4, 0)one factorisation, no Zpositive, LDLᵀ of K10negative, LDLᵀ of K4negative in H4negative in ZᵀHZ0the count follows the reduced Hessiannot the Hessian

    A minimum the Hessian cannot see

    A Hessian with four negative eigenvalues can sit at a constrained minimum, and a Cholesky of it stops at the third row. One symmetric indefinite factorisation of the saddle-point matrix settles the question anyway — ten positive pivots and four negative — without a basis for the null space ever being formed. The count is exact in the algebra and blind in floating point, in a band that grows like κ(A)²; the route through the null space is blind in one that grows like κ(A).

    part 3 · constraint
  4. 10⁻³10⁻²10⁻¹110¹10²10³10⁴10⁵the shift the reduced Hessian neededshift taken ÷ shift needed10⁻⁸10⁻⁷10⁻⁶10⁻⁵10⁻⁴10⁻³10⁻²10⁻¹110¹median of eightexactly enoughκ(A) = 10, eight draws per curvatureworst ratio, curvature 10⁻⁸·²⁵1.8·10⁴worst ratio above 10⁻²7.3trials stopped below the curvature0factorisations a solve, mean3.2above one: more convex than the problemon the floor: the count passed a saddle

    The shift that stops at the first right count

    A nonconvex solver that finds the wrong inertia adds δI to H and tries again, and the δ it settles on is used as though it measured the curvature it corrects. It does not. On a well-conditioned constraint it is the schedule's number — 1.8·10⁴ times the need at a curvature of 5.6·10⁻⁹, between one and 7.3 times above 10⁻² — and on an ill-conditioned one the loop stops wherever the count first reads right: 63 of 152 saddles at κ(A) = 10⁸, the deepest with curvature 56. Refining the shift by bisection removes the first error and adds to the second.

    part 4 · constraint
  5. 10⁻¹⁷10⁻¹⁶10⁻¹⁵10⁻¹⁴10⁻¹³10⁻¹²10⁻¹¹10⁻¹⁰10⁻⁹10⁻⁸10⁻⁷10⁻⁶|h|, the curvature of H along the weak directionσ at which the count is first wrong10⁻⁴10⁻³10⁻²10⁻¹110¹10²no interchangesLDLᵀ of Krank tolerancethrough Z: right to 10⁻¹⁶10 × 4, eight draws per curvatureh = -1·10⁻⁴: LDLᵀ first wrong at σ1.8·10⁻¹¹h = -0.01: LDLᵀ first wrong at σ1.8·10⁻¹⁰h = -1: LDLᵀ first wrong at σ1.4·10⁻⁹h = -100: LDLᵀ first wrong at σ1.8·10⁻⁸the pair's small eigenvalue is σ²/|h|the count loses it long before the rank does

    A constraint the count stops seeing

    Let one constraint drift towards being a combination of the others and the inertia of the saddle-point matrix keeps its promise only while σ²/|h| can be resolved — σ the constraint's smallest singular value, h the curvature along the direction it barely constrains. At h = −1 the count stops seeing the constraint at σ = 1.4·10⁻⁹, six decades before any rank test would drop it, and below that it reports a genuine minimum as a saddle on three to six draws in eight. No shift of H brings the constraint back: the correction loop shifts a problem that needed nothing by as much as 2,620. A perturbation of the constraint block does not bring it back either — it decides, at σ = √(|h|δ).

    part 5 · constraint
  6. κ(A) = 10⁸, 152 saddlespassed, ordinary63passed, on wrong counts57passed, always510⁻⁸10⁻⁷10⁻⁶10⁻⁵10⁻⁴10⁻³10⁻²10⁻¹110¹10⁻⁴10⁻²110²10⁴10⁶10⁸curvature needed, μshift applied ÷ μordinary schedulenull space on wrong countsnull space alwaysbelow the dashed line a saddle was certifiedthe arbitrated shift sits at twice the need

    A loop that asks the null space why

    An inertia-correction loop sees only an integer, and two different faults produce the same wrong one: curvature that needs a shift, and a constraint too weak for the count to see. One QR of the constraint matrix on a wrong count tells them apart — it shifts none of the 22 weak-constraint minima the ordinary loop shifted by up to 2,621 — and its reduced eigenvalue gives the shift a saddle needs in one step, twice the need exactly, where the schedule overshoots by up to 17,783 times. But at κ(A) = 10⁸ the loop still certifies 57 saddles of 152, because a false certificate is a count that read right, and a check made only on wrong counts never sees it. Asking every time leaves five, all shallower than 2·10⁻⁸.

    part 6 · constraint

All series