Numerical Linear Algebra
where the algebra stops being the arithmetic
Concept

Inertia correction — where it appears

The loop a nonconvex optimiser runs when an eigenvalue count says its reduced Hessian is indefinite: add a multiple of the identity and factorise again. The multiple is chosen by a schedule and checked only by the count.

Named by 2 essays across one field — each of them below, with the objects they name alongside it.

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.

constraint · Saddle-point systems 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|δ).

constraint · Saddle-point systems

Named alongside it

The objects these essays reach for when they reach for this one.

CertificateInertiaLDLᵀ factorisationReduced hessianSaddle-point systemsBunch–KaufmanCondition numberConstrained minimisationIndefinite matrixNull-space methodNumerical rankQuasi-definite matrix

All concepts