The perturbation that does the work

The regularisation that legalises every order perturbed the two blocks of a saddle-point matrix in opposite directions — H by +δI, the zero block by −γI — and read four laws off the result. Every one of five hundred random orderings factorised, against 69 per cent unperturbed. The worst ordering’s growth factor was about 0.64/δ. The worst residual fell like $\delta^{-1.8}$. And the regularised answer was wrong by about 1,489·δ, a perturbation refinement could remove until δ reached the smallest singular value of the matrix.

Every one of those laws was measured with δ and γ equal, and every one was written in δ. That is the natural way to run the experiment, and it hides the question a code choosing the two separately has to answer: which block is doing what. The primal block’s perturbation δ is the one the name “regularisation” suggests, since it makes H more definite. The dual block’s γ is the one the theorem cannot do without, since a zero block is not −F for any positive definite F. The two are chosen against different scales in practice and adapted separately during a run, so the laws are worth having one block at a time.

Moved apart, they are not shared. All four belong to γ, and the one that looked like δ’s — the price in the answer — is the price of γ, set by the smallest eigenvalue of the dual Schur complement to three figures. The perturbation of H, on a problem whose H is already positive definite, is almost free.

The system, and the two blocks #

The matrix is the same one the first measurement used: a positive definite H of ten unknowns with condition number 100, a constraint matrix A of four rows with condition number 100, and the saddle-point matrix $K = \begin{bmatrix} H & A^{\mathsf T} \\ A & 0 \end{bmatrix}$ they make. Regularised, it is

$$K(\delta, \gamma) = \begin{bmatrix} H + \delta I & A^{\mathsf T} \\ A & -\gamma I \end{bmatrix}$$

and the two perturbations sit in blocks that play different parts in any elimination of it.

Two ways to remove a constraint named those parts. Eliminating the unknowns first leaves the dual Schur complement AH⁻¹Aᵀ, an m × m matrix whose conditioning is the range-space method’s. Eliminating the constrained directions first leaves the reduced Hessian ZᵀHZ, an (n − m) × (n − m) matrix whose conditioning is the null-space method’s. Every factorisation of K, in any order, is implicitly working with both, and the two perturbations land in them separately: γ shifts the dual Schur complement, and δ shifts the reduced Hessian.

On this system the smallest eigenvalue of AH⁻¹Aᵀ is ν = 6.876·10⁻⁴, and the smallest eigenvalue of ZᵀHZ is μ = 3.306·10⁻². The two floors are 48 times apart, and every price measured below turns out to be one of them.

Legality is bought by the zero block #

The first law is the theorem’s, and it separates cleanly. With γ = 0 and δ = 10⁻⁸, 202 of 300 orderings factorise — 67 per cent, the first measurement’s figure with a smaller sample. The failures are exact zero pivots: an ordering that brings two constraint rows to the front meets a leading block of zeros and stops. With γ > 0 there are no exact zeros to meet, and at γ = 10⁻⁸ all 300 orderings factorise at every δ from 0 to 10⁻².

That δ = 0 still gives a quasi-definite matrix here is a property of this H, which is positive definite on its own. The theorem needs positive definiteness of H + δI, and negative definiteness of −γI; the first holds at δ = 0 and the second at any γ > 0. So on a problem whose Hessian is already definite the whole of the guarantee is the dual block’s, and the primal perturbation adds nothing to it. On a problem whose Hessian is not, δ has a job, and a shift that certifies a saddle measures what doing it costs.

The worst ordering belongs to γ #

The second law is where the separation is most striking, because the first measurement’s statement of it was a clean inverse law in δ.

Moving γ alone, the worst growth over the 300 orderings is 0.511/γ at γ = 10⁻¹⁰, 10⁻⁸, 10⁻⁶, 10⁻⁴ and 10⁻², the product constant to three figures over eight decades. Moving δ alone, from zero to 10⁻², the worst growth stays between 5.02·10⁷ and 5.11·10⁷, a spread of under 2 per cent, and that value is 0.511 divided by the γ it was held at.

The first measurement’s 0.64 was the same law read from five hundred orderings rather than three hundred — the worst of a larger sample is worse — and read in δ because δ and γ were equal. It is a statement about how close a pivot on the dual side can come to zero: a pivot built from a constraint row after the unknowns it touches have been eliminated is −γ minus something that can be arbitrarily small under a bad ordering, and dividing by it is the growth.

The worst residual follows γ in the same way and faster. At γ = 10⁻¹⁰ the worst of 300 orderings reproduces its matrix to 6.2; at 10⁻⁸ to 6.2·10⁻⁴; at 10⁻⁶ to 2.0·10⁻⁷; at 10⁻⁴ to 5.3·10⁻¹². Between 10⁻⁸ and 10⁻⁴ that is a slope of −2.02, the square of the growth law, which is what a residual made of one large multiplier times one large pivot should do. Moving δ at γ = 10⁻⁸ leaves the worst residual wandering between 5·10⁻⁴ and 1.6·10⁻³ with no trend at all.

The two histograms are the same experiment with the perturbations exchanged in size, and they are nothing alike. With δ a million times γ, the residuals span thirteen orders and the worst is 7.9·10⁻⁴. With γ ten thousand times δ they span five and the worst is 5.3·10⁻¹². The perturbation of H was a million times larger in the first and changed nothing; the perturbation of the zero block changed everything.

Each block has a price, and it is its own Schur complement #

The regularised answer is the exact answer to a different problem, so its error against the unregularised answer is proportional to the perturbation. The first measurement put the constant at 1,489. With the blocks moved apart there are two constants, and they differ by a factor of seventy-six.

With only the zero block perturbed, the error is 1,451·γ at every γ from 10⁻¹⁰ to 10⁻⁶. The reciprocal of ν is 1,454. With only H perturbed, the error is 19.1·δ over the same range, against a reciprocal of μ of 30.3. The first measurement’s 1,489 was very nearly all γ.

The γ constant matches its floor to three figures for a reason that can be written down. Perturbing the zero block by −γI changes the multipliers λ by (AH⁻¹Aᵀ + γI)⁻¹ applied to something of the size of γλ, and the largest amplification that inverse can give is 1/ν, along the dual Schur complement’s weakest direction. The exact answer’s multipliers have a component along that direction, and the error is that component times γ/ν. The δ constant sits below its bound because the solution has less weight along the reduced Hessian’s weakest direction: 19.1 against 30.3 is the share of x that lies there. Both are properties of the problem, computable before anything is regularised.

Past γ = 10⁻⁵ the γ curve bends below its line — 1,431 per unit at 10⁻⁵ and 1,267 at 10⁻⁴ — because γ is no longer small against ν = 6.9·10⁻⁴ and the amplification becomes 1/(ν + γ) rather than 1/ν. That bend is the price law and the next section’s refinement law being the same fraction.

Refinement removes each perturbation at its own rate #

Refinement forms the residual against K and solves the correction with the regularised factorisation. Its error after each step is multiplied by K(δ, γ)⁻¹ times the perturbation, and on each block that product has one eigenvalue that matters.

With γ = 10⁻³ alone the error falls by 0.5925 a step, and γ/(ν + γ) is 0.5925. With γ = 10⁻² alone it falls by 0.9357 a step, and γ/(ν + γ) is 0.9357: after sixty steps that leaves 1.7 per cent of an error that started at 93 per cent. With δ = 0.1 alone it falls by 0.7515 a step, and δ/(μ + δ) is 0.7516.

The first measurement put refinement’s limit at the smallest singular value of K, 6.797·10⁻⁴, and on this system that is almost the same number as ν, 6.876·10⁻⁴. The rates decide between them. At γ = 10⁻³ the smallest singular value predicts γ/(σ_min + γ) = 0.5953, and the measured rate is 0.5925, which is ν’s prediction to four figures. The limit belongs to the dual Schur complement, and on this system the dual Schur complement’s floor happens to lie within 1.2 per cent of the whole matrix’s smallest singular value.

Two cliffs, fifty times apart #

A refinement limit is where a perturbation stops being removable in a reasonable number of steps, and with the blocks apart there are two of them.

After fifty steps with γ alone, the error is at rounding for every γ up to 10⁻⁴, 2.6·10⁻¹² at 10⁻³, 0.034 at 10⁻², 0.70 at 0.1 and 0.96 at 1. With δ alone it is at rounding for every δ up to 10⁻², 8.1·10⁻⁸ at 0.1 and 0.038 at 1. The two curves are the same curve shifted by the ratio of the floors, which is 48, and each cliff sits a decade or so past its own floor, where the per-step factor passes about 0.9.

So a code that perturbs both blocks by the same amount and refines is limited by γ’s cliff, and could perturb H fifty times harder before its own cliff mattered. Nothing about that is visible from the matrix K as a whole. The whole matrix’s smallest singular value said 6.8·10⁻⁴ and said nothing about which perturbation the number was a limit for.

What each perturbation is for #

Put in the order a solver makes the choices, the separation gives one parameter nearly all of the decisions.

γ is the ordering parameter. It makes every ordering legal, it sets the worst ordering’s growth at 0.51/γ and its residual near $\gamma^{-2}$, it costs the answer 1/ν per unit, and refinement removes that cost only while γ is below about ten times ν. Every trade the first measurement described — existence against stability, a perturbation too small to be stable against one too large to remove — is a trade in γ alone, and its optimum is set by ν.

δ is almost free when H is positive definite. It adds nothing to legality, nothing to the worst ordering, 19 per unit to the answer, and refinement removes it up to 10⁻². On this problem it could be set a hundred times larger than γ and cost less.

The first measurement’s design rule still holds, with the names corrected. It said δ has to be large enough that the factorisation is stable — 0.64/δ is the growth — and small enough that refinement converges below the smallest singular value, and it found about eight decades between. Both ends are γ’s: the growth is 0.51/γ, and the refinement limit is ν. The room between them is the same eight decades, and it is the dual block’s room.

That last point matters for the codes the first measurement cited. An interior-point method adapts its regularisation during a run as its matrix is sent to infinity on purpose. What is being sent to infinity is the diagonal of H in the directions of active bounds, which changes μ and leaves ν alone, or sends the other diagonal to zero, which changes ν and leaves μ alone. A rule that adapts one parameter against the other block’s floor is adapting the wrong thing, and on a system where the floors are fifty times apart it would be wrong by that factor.

Where the separation stops being clean #

Two things keep this from being the whole story.

The first is the Hessian. Everything above assumed H positive definite, which is why δ had nothing to do for legality. When H is indefinite — a Lagrangian’s Hessian usually is — the theorem needs δ past the most negative eigenvalue of H before K is quasi-definite at all, and then δ is not small and not free. A shift that certifies a saddle measures that case, and finds the δ the guarantee needs costing something no price law here captures.

The second is the orderings. Three hundred random symmetric permutations of a fourteen-by-fourteen matrix are a sample from a set of 8.7·10¹⁰, and the worst growth of a sample depends on its size — 0.51/γ from three hundred, 0.64 from five hundred. The law’s form, an inverse in γ with δ absent, is what the experiment establishes; the constant is the worst of a sample. An ordering that does not wait for the numbers is the reminder that a code does not order at random, and the orderings a fill-reducing heuristic produces are not the tail of this distribution.

Why the zero block is the expensive one here, and where it would not be #

The asymmetry has a reading in the terms the constraint field already uses, and the reading says when to expect it and when not to.

The zero block is not an accident of how the problem was written down. The zero that is not a missing entry established that it is a theorem — the constraints have no curvature of their own — and that no pivot order and no precision makes the matrix definite. Perturbing it by −γI replaces that theorem with a small curvature of the wrong sign along every constraint, and every multiplier the regularised system returns is the answer to a problem in which the constraints are soft, held with a stiffness of 1/γ. The price of 1/ν per unit of γ is the statement that the softest direction of the constraints, as the unknowns feel it, has stiffness ν, and that a constraint softened by γ against a stiffness of ν gives way by γ/ν.

The perturbation of H is a change of a different kind. It adds curvature to the objective in every direction: along the directions the constraints already fix, where it costs nothing, and along the directions they leave free, where it is resisted by the reduced Hessian’s own curvature. The smallest of those is μ = 3.3·10⁻², forty-eight times stiffer than the constraints’ softest direction, and that ratio is the whole of the difference in price.

So the expectation runs one way on a problem like this one and can run the other way on another. A problem with nearly dependent constraints has a tiny ν, and there the zero block’s perturbation is ruinously expensive and refinement’s limit falls with it. A problem whose objective is nearly flat on the feasible set has a tiny μ, and there the primal perturbation is the dear one. A minimum the Hessian cannot see built a Hessian whose smallest reduced curvature is a parameter, and on that construction μ can be made as small as ν or smaller. What this measurement establishes is a pair of Schur floors and a rule that each block is priced by its own — not that one block is always the cheap one.

It is also why the factorisation the regularisation replaced pays none of these prices. The symmetric indefinite route with 2 × 2 pivots that when symmetry is not enough took perturbs nothing and returns the answer to the problem that was posed. It pays instead in pivots chosen during the factorisation, which is the dynamic work the regularisation was bought to avoid, and in a structure the symbolic phase cannot predict. The active set before the digits meets that trade from the interior-point side, where a new saddle-point system is factorised at every iteration, and where the two prices measured here are paid again on every one of them with floors that move as the iterate does.

What was not measured #

One system, with both condition numbers at 100 and n = 10, m = 4. The ratio of the two floors, 48, is a property of this H and A, and a problem whose constraints are nearly dependent would have ν far smaller and the separation far sharper, while a problem whose reduced Hessian is nearly singular would move δ’s cliff down towards γ’s. How the two prices behave as each floor is moved on its own is not drawn.

The refinement here uses the regularised factorisation in the natural order only. A factorisation in a bad ordering has a worse residual, and refinement against K corrects the residual’s error as well as the perturbation’s; which of the two limits a run in the worst of three hundred orderings is not separated here.

Still open: what the floors say about choosing γ, and what dependent constraints do to ν #

A rule for γ from ν. The price is 1/ν per unit and the refinement limit is about 10ν, and ν is the smallest eigenvalue of an m × m matrix that a few steps of a Lanczos iteration on AH⁻¹Aᵀ can estimate. A rule that sets γ to a fixed fraction of that estimate, and a measurement of how close it lands to the balance between the 0.51/γ growth and the 1/ν price across systems with different floors, would turn the separation into a method.

Dependent constraints. When two rows of A are nearly dependent, ν goes to zero and K becomes nearly singular in the multipliers while x stays well determined. γ then makes every ordering legal and chooses among nearly equivalent multipliers, and the measurement is whether the regularised x stays accurate while the multipliers wander, and whether refinement, whose rate γ/(ν + γ) approaches one, is still worth running on x alone.

Static pivoting’s perturbation. The order that was right last time perturbs whichever pivots turn out too small rather than a whole block, so its perturbation lands in both Schur complements at once and in proportions nobody chose. Whether its refinement rate is the worse of the two floors’ rates, as this separation suggests, is the question that connects the two.