What survives one step of the barrier

This anchor’s first essay asked what a factorisation is worth when the matrix has moved a little, and answered it with a drift: a matrix perturbed by 10⁻³ relatively has a factorisation good for many steps of an outer iteration, and where the perturbation lands matters more than how large it is. The essay after it turned that into a rebuild policy with a crossover in it.

An interior-point method is the cleanest sequence of solves this collection has, and it gives the anchor’s question an answer with a threshold rather than a curve.

The sequence, and what changes in it #

An interior-point method for a quadratic programme solves one saddle-point system per iteration:

[ H Cᵀ ] [ C −D⁻¹ ]

with D = Z/S the diagonal that the constraint field’s fifth essay is about. From one iteration to the next, H does not change, C does not change, and the sparsity pattern does not change. Exactly p entries move — the diagonal of the (2, 2) block, one per constraint — and no off-diagonal entry moves at all. Measured, at every step: 6 of 196 entries, 0 of them off the diagonal.

That is as close to “the same matrix again” as a sequence gets, and it is the case the anchor’s machinery was built for. The obvious expectation is that a factorisation of one step’s matrix is an excellent preconditioner for the next.

What survives for nothing: the pattern #

The sparsity pattern is identical at every step, so the symbolic factorisation is computed once for the whole optimisation and is free thereafter — provided the numeric phase never moves a pivot, which for the regularised form it never does. The sparsity field’s essay on that has the argument and the fill counts.

That is a genuine and large saving, and it is not what this page is about, because it is not a numerical reuse. Nothing about the values is being carried; what is carried is a shape.

The second thing that survives for nothing is the active set, once it has emerged. By μ = 10⁻⁸ the diagonal’s two groups are sixteen orders apart and no later step reclassifies anything. A code can use that: the split it reads off at one step is the split at every subsequent step, and that is what warm-starting an interior-point method means.

What survives numerically: nothing #

Carry the factorisation of K(μ) to K(σμ) and clean up with iterative refinement — the residual formed against the new matrix, the correction solved with the old factors. Twelve steps, at several reduction factors:

σ steps the factorisation survives 0.999 6 of 6 measured 0.99 6 of 6 0.95 2 0.9 1 0.5 0 0.1 0

Reuse holds while σ is within about a per cent of one, and fails outright by σ = 0.9. Real interior-point schedules reduce μ by a factor of two to ten, and at σ = 0.5 the first reused step already leaves a relative residual of 1.0 — no digits at all — while at σ = 0.1 it leaves 3.8·10⁹.

So the answer to the anchor’s question, on this family, is: every step. Not “rebuild when the drift exceeds a threshold” and not “rebuild every k steps”; rebuild every time, for a reason that is structural rather than a matter of tuning.

Nor of how large the problem is. The same sweep at the two ends of the size the figure will draw:

Why the intuition fails, in one number #

Six entries out of a hundred and ninety-six sounds like a small update, and it is not, because those six are the six that dominate the matrix.

The relative change ‖K(σμ) − K(μ)‖ / ‖K(μ)‖ at σ = 0.1 is 9 — the matrix has changed by nine times its own norm in one step. The entries that moved are the ones of size 1/μ, and they moved by a factor of 1/σ, so the change is (1/σ − 1) times the largest thing in the matrix.

Put that on the same axis as the drift the anchor’s first essay measured, where a factorisation was still useful at a relative drift of 10⁻³ and marginal at 10⁻¹. A barrier step is a drift of nine. The reason the reuse fails is not subtle and not about where the perturbation landed: the perturbation is larger than the matrix.

The refusal this page publishes is the reading that counts entries instead of measuring them: a matrix that changes in only p of its entries between two solves is a small update, so a factorisation of the first is a good preconditioner for the second. It is fed the run at σ = 0.5 and required to fail.

What the entry count is measuring, and what it is not #

It is worth separating two readings of “six entries changed”, because the second is the one that makes the intuition wrong.

As a statement about structure it is exactly right and it is what the previous section uses: the pattern is unchanged, the elimination tree is unchanged, the allocation is unchanged, and everything a symbolic phase computed is still valid. Structural sparsity of an update is what lets a code avoid re-analysing.

As a statement about magnitude it says nothing at all, and the collection has met that distinction before from the other side. A rank-one update changes every entry of a matrix and can be applied to a factorisation in O(n²) because it is small in rank; a diagonal update changes p entries and cannot be applied at all when those p entries are the matrix’s norm. Sparsity of an update and smallness of an update are unrelated properties, and only the second governs whether a stale factorisation is any use.

The clean way to say it is that the relevant quantity is ‖ΔK‖·‖K⁻¹‖, and neither factor is a count. Here it is 9 times something of order one, and the count of six was never going to reveal that.

The threshold is a property of the schedule, not of the problem #

σ is chosen by the optimisation, for reasons about the outer convergence: an aggressive σ reaches the solution in fewer iterations and risks leaving the region where the Newton step is good, and every implementation has a rule for adapting it. Nothing in that rule is about linear algebra.

The measurement says the linear algebra’s reuse horizon is a function of exactly that number, and that the number the optimisation wants is two orders away from the number reuse would need. The counts do not move when the constraint count changes — the threshold is at σ ≈ 0.99 at four constraints and at ten — and they do not move with the size either.

The residuals are not invariant and the verdict is. Across n = 4, 6, 8, 10 and 12 the residual after one reused step at σ = 0.5 reads 1.13, 0.822, 1.02, 0.424 and 0.263 — a factor of four, falling with the size and not monotonically. The steps-survived line is 6 6 2 1 0 0 0 at all five.

Which is the right relationship between the two, and it is worth saying why rather than treating the constancy as luck. A relative error of 0.263 and one of 1.13 are the same answer: no correct digits. Once a quantity has lost everything, a factor of four in how thoroughly it has lost it changes no decision, and the integer the figure reports is a count of steps that converged — a threshold applied to that quantity, far above where any of these sit.

The two σ columns carry a tighter invariant still. Divide the residual at σ = 0.1 by the residual at σ = 0.5 and the five sizes give 2.89·10¹¹, 2.82·10¹¹, 2.82·10¹¹, 2.83·10¹¹ and 2.83·10¹¹ — constant to a per cent while both terms move by four. The ratio between two schedules is a property of the schedules, and the size cancels out of it.

That makes it a clean example of something this field keeps finding: a policy question that looks like it should be tuned turns out to be settled, and settled by a quantity chosen elsewhere in the program for unrelated reasons. The rebuild policy essay found the optimum walking with a setup cost; here there is no optimum to walk, because the whole reusable region is on the wrong side of where the method operates.

What refinement is doing, and why more of it does not help #

The refinement iteration multiplies the error by roughly ‖I − K̂⁻¹K‖ each step, where K̂ is the stale matrix. That is a contraction only while the quantity is under one, and the tempting estimate for it is the relative perturbation, 1/σ − 1.

That estimate is wrong by a constant, and the constant is exactly what makes the formula agree with the table three sections up. Computing ‖I − K₀⁻¹K₁‖ directly:

   σ        ‖I − K₀⁻¹K₁‖    1/σ − 1     ratio
 0.999        3.07·10⁻²     1.00·10⁻³   30.640
 0.99         3.10·10⁻¹     1.01·10⁻²   30.640
 0.95         1.61          5.26·10⁻²   30.640
 0.9          3.40          1.11·10⁻¹   30.640
 0.5          3.06·10¹      1.00        30.640
 0.1          2.76·10²      9.00        30.640

A constant of 30.640, across four orders of the estimate. The relative perturbation is exactly 1/σ − 1 — that half of the reasoning is right to six digits — and what the estimate omits is the amplification: ‖K₀⁻¹ΔK‖·‖K₀‖/‖ΔK‖, which is 30.6 here.

The constant decides where the divergence starts. 30.64·(1/σ − 1) passes one at σ = 0.968, and the measured table has reuse holding at σ = 0.99 and failing by σ = 0.95 — which brackets it. The uncorrected estimate would put the threshold at σ = 0.5, contradicting the same table.

So the failure is a divergence rather than a slow convergence, it begins at σ = 0.968 rather than at 0.5, and adding steps makes it worse rather than better. Twelve steps at σ = 0.1 leave a residual of 3.8·10⁹, and a hundred would leave more.

The amplification is worth one more sentence, because it is small. κ₂(K₀) at this μ is 3.0·10⁵, so a worst-case perturbation of the same size would be amplified ten thousand times harder than this one is. The barrier’s update is a favourable direction — it moves the diagonal, which is where the matrix is already largest and where its inverse is smallest — and the reuse fails anyway. That is the strongest form of the essay’s conclusion: not that the perturbation is badly aimed, but that it is well aimed and still nine times the matrix.

Why a formula that contradicted the table survived being written #

It is worth being explicit about how the wrong constant got there, because the shape recurs and it is not carelessness.

The estimate came from the right place. ‖I − K̂⁻¹K‖ = ‖K̂⁻¹ΔK‖, and reading that as a relative perturbation is the move — it is ΔK measured against K, which is 1/σ − 1, and the K̂⁻¹ silently becomes a division by K. That step is exactly the one the site’s own error identity forbids: a backward error is not a forward error until a condition number has been applied, and here the condition number is the 30.6.

What makes it worth recording is that the essay contained the refutation already. The table of survival counts says reuse fails between σ = 0.99 and σ = 0.95; the formula says it fails below σ = 0.5; and the two sat four sections apart in the same document without either one being read against the other. A measurement and a formula in the same essay are two routes to one number, which is this site’s oldest habit, and it was not applied because one of them did not look like a measurement.

The general form of the check is cheap: whenever an essay states both a threshold it measured and a formula for that threshold, evaluate the formula at the measured point. It takes one line and it would have caught this the day it was written.

This is the same mechanism as the regularisation cliff in the constraint field, where refinement against the unregularised matrix works below δ = σ_min(K) and diverges above it. In both cases the useful reading is that iterative refinement is a fixed-point iteration and its convergence has a condition, and the condition is checkable before the iteration is run.

A code that reused a factorisation and refined until the residual stopped falling would get a diverging sequence and would have to detect it. A code that computed 1/σ − 1 first would not attempt it.

The one reuse that would work, and what it would cost #

There is a way to make the factorisation reusable, and it is worth naming because it is not available and the reason is instructive.

The change between steps is D⁻¹(σμ) − D⁻¹(μ), a diagonal matrix supported on p entries. A factorisation can be updated for a diagonal change of rank p at a cost of O(p) rank-one updates, each O((n + p)²) for a dense factor or O(fill) for a sparse one — the machinery the least-squares field builds for exactly this shape. For p small against n that is cheaper than refactorising.

The obstacle is stability rather than cost. A rank-one update to a symmetric indefinite factorisation with a large multiplier is not backward stable — the update can be arbitrarily ill conditioned when the modification changes the inertia or nearly does, and here the entries being modified are the ones with the largest magnitude. The downdate essay in the least-squares field measures the same failure on a Cholesky, where removing an observation is a rank-one downdate that can lose every digit.

So the update exists, is cheap, and cannot be trusted on this family, which leaves refactorising. That is a common enough ending for an update argument that it is worth having the reason on the page rather than leaving the technique looking overlooked.

What could be reused instead, and is #

The negative result is not the end of the matter, because there are three things a code does carry across a barrier step and all of them are cheaper than a factorisation.

The ordering and the symbolic factors, as above, which is most of the analysis cost.

The scaling. Equilibrating the matrix — which this collection has measured as making a reuse free elsewhere — depends on H and C, which do not change. So the row and column scalings are computed once.

The starting point. The previous step’s solution is a warm start for the next, and the whole design of a path-following method is that consecutive solutions are close. That is a reuse of the answer rather than of the machinery, and it is the one that pays: the outer iteration count is what it is because each Newton step starts near its target.

So the sequence is heavily reused and none of the reuse is a factorisation. Reading the anchor’s question as “how often to rebuild” gets a trivial answer here; reading it as “what is carried” gets three.

What an iterative method would do instead #

Refinement is a stationary iteration and diverges when its contraction factor exceeds one. A Krylov method has no such requirement: it does not need the preconditioner to be close, only for the preconditioned spectrum to be clustered, and it will make progress from a preconditioner that refinement cannot use at all.

So a code that wants to reuse a stale factorisation across a barrier step has a route: use it as a preconditioner inside GMRES or MINRES rather than as a fixed-point map. The stale factors then buy a reduction in iteration count instead of an exact solve, and the question becomes how many iterations, which is a smoother trade than the cliff this page measures.

What the measurement here says about that route is not encouraging but it is quantitative. The preconditioned operator is K̂⁻¹K = I + K̂⁻¹ΔK, and ‖K̂⁻¹ΔK‖ is the same 9 that made refinement diverge, so the preconditioned spectrum is spread over a region of radius nine about one — not a cluster, and not obviously better than no preconditioner at all. At σ = 0.9 the radius is 0.11 and the clustering is excellent, which is the same threshold arriving in a different currency.

That is worth stating as a boundary on the negative result: reuse fails here for refinement and for a Krylov method, and it fails at approximately the same σ, because both are governed by the size of the same product.

A control, and a boundary #

The measurement needs a case where reuse does work, or the conclusion could be about the refinement machinery rather than about the barrier. σ = 0.999 is that case: six steps out of six at the rounding level, on the identical code path.

And the boundary between working and not is sharp enough to read off the figure — 0.99 works, 0.95 gives two steps, 0.9 gives one, 0.5 gives none — which is what makes the negative result a measurement rather than an absence.

The library’s other refusal covers the second half of the argument. It is fed the claim that a saddle-point matrix’s off-diagonal entries move between steps, and required to reject it: zero of them do, at every step, which is what makes the count of six meaningful and the drift of nine surprising.

What this says about the anchor #

Three essays into reuse, the shape of the answer has settled into a pattern worth stating.

Whether a factorisation can be carried is not a question about how many entries changed. It is a question about how much of the matrix’s norm changed, and about whether the change landed where the inverse is sensitive. The first essay found the second half of that; this one supplies a case where the first half is decisive and the entry count is actively misleading.

The interior-point sequence is the extreme instance: the sparsest possible update, in the densest possible sense. Six numbers out of two hundred, and a relative change of nine.