Every essay — page 15
The matrix a constraint makes
Every difficult matrix in the other fields was difficult for a reason the arithmetic supplied: a Hilbert matrix arrives ill conditioned, a Wilkinson matrix grows under elimination, a kernel matrix is dense. Ask a problem to minimise something subject to a constraint and the matrix that results is difficult for a reason the algebra supplies. Its zero block is the second derivative of a Lagrangian with respect to its own multipliers, so no pivot order removes it and no precision changes that; its inertia is known before anything runs; and Cholesky does not fail somewhere on it, it fails at the first constraint row, on a number the problem already contained. Then the field's second surprise, which is the opposite one: an interior-point method drives the condition number of this matrix to 10¹⁵ deliberately, and the answer keeps fifteen digits — because the number that describes the error is not the one every library prints.
Three eigenvalues, and two are the golden ratio
Precondition a saddle-point system by the block diagonal of its own two definite pieces and the preconditioned matrix has exactly three distinct eigenvalues — 1, and the two roots of λ² − λ − 1. A minimal polynomial of degree three means three steps, at every conditioning, and the preconditioner nobody can afford turns out to be the statement the affordable ones are measured against.
A preconditioner that need not know the constraint
Keep the constraint block exactly and replace the objective block by anything positive definite on the null space. The preconditioned matrix then has 2m eigenvalues at exactly one, and its remaining n − m are the generalised eigenvalues of a pencil in which the constraint does not appear. Sweep its condition number over six decades and they do not move in six digits.
A condition number sent to infinity
An interior-point method manufactures an ill-conditioned matrix on every iteration, deliberately, because the separating of a diagonal is how it discovers which constraints are active. Written one way the answer keeps fifteen digits at a condition number of 3·10¹⁵. Written the other way — the way almost every code writes it — it has none left.
The regularisation that legalises every order
Perturb a saddle-point matrix's two blocks in opposite directions and it acquires a factorisation with a diagonal D under every symmetric permutation — not under a good one, under all of them. Five hundred random orderings, five hundred successes, and a growth factor that spans six orders across them.
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).
One eigenvalue and two steps
Put the off-diagonal block back into a block-diagonal saddle-point preconditioner and every eigenvalue of the preconditioned matrix becomes exactly one. GMRES still needs two steps, because the matrix is the identity plus a nilpotent part of norm 54, and a computed eigenvalue at one comes back as a ring of radius 8·10⁻⁸ — the square root of the rounding, not the rounding. With an approximate Schur complement the triangular form leaves one copy of each value where the diagonal form leaves two, and the step count halves.
The active set before the digits
An interior-point method takes fifteen iterations on a quadratic programme with forty constraints, and its iterate has eight correct digits at the eleventh. Take the constraints its diagonal calls active at the first iterate, solve the equality problem they define once, and check the answer against the conditions for optimality. It passes, to thirteen digits. The step's matrix had a condition number of 43 at that iterate, and 7·10¹⁵ at the last.
Where the augmentation puts the cost
Add γAᵀA to the objective block of a saddle-point system and its Schur complement tends to I/γ, so the cheapest possible approximation becomes the right one and the golden-ratio spectrum arrives — within 7.6·10⁻⁶ at γ = 10⁶. MINRES falls from 21 steps to 6. The inner solve with the augmented block rises from 14 conjugate gradient steps to 43, their product does not fall at all, and the answer loses seven and a half digits on the way.
A shift that certifies a saddle
On a constrained problem whose Hessian has four negative eigenvalues, a saddle-point matrix is quasi-definite only once H + δI is positive definite — past δ = 5.08 here. Its pivot signs then count the curvature of ZᵀHZ + δI rather than of ZᵀHZ, so a saddle with a negative curvature of −1 is certified a minimum from δ = 1.05 on, and every saddle shallower than δ goes the same way. Iterative refinement against the unregularised matrix keeps the second-order test the count gave up: it contracts on the minimum at δ/(μ + δ), 0.980 a step at δ = 5, and on the saddle it grows at exactly 1.25.
The perturbation that does the work
A saddle-point matrix made quasi-definite is perturbed in both blocks, and the laws measured for it moved both together. Moved apart, the laws all belong to one block. The zero block's perturbation γ decides whether every ordering factorises, sets the worst ordering's growth at 0.51/γ, and costs the answer 1,451 per unit — the reciprocal of the smallest eigenvalue of AH⁻¹Aᵀ to three figures. The perturbation of H moves none of the first two and costs 19 per unit. Refinement removes each block's perturbation at the rate its own Schur complement sets, so γ's limit sits fifty times nearer than δ's.