The active set before the digits

A condition number sent to infinity placed an interior-point iterate on the central path at a chosen barrier parameter and asked what the linear algebra does there. Its last sentence made a claim about the method rather than about the matrix: the ill-conditioning is what the method uses to locate the active set, and a method that avoided it would never find out which constraints bind.

The claim is about what the method learns, and it is true. It says nothing about when. That is a separate question and a measurable one, and the answer turns out to separate two things the claim runs together — the information the method needs, and the digits it goes on to compute with it.

A programme whose answer is known before it is solved #

The measurement needs a problem with a known solution, a known active set and known multipliers, so it is built backwards. Twenty unknowns, forty inequality constraints Cx ≥ d with Gaussian rows, a positive definite H with condition number 100. A point x* is drawn; ten constraints are made to hold with equality at it and given multipliers between 0.5 and 1.5; the other thirty are given slacks in the same range and zero multipliers; and the linear term of the objective is whatever makes x* stationary. The programme is convex, so x* is its unique solution, and every error below is measured against it.

The method is the plainest long-step primal–dual path-following method there is. From x = 0 with every slack and multiplier equal to one, it takes Newton steps on the perturbed optimality conditions with the products sᵢzᵢ driven to a tenth of their current average, steps to 99% of the way to the boundary of the positive orthant, and stops when the average product and both residuals are below 10⁻¹³. Each step is one solve with the (n + p)-square matrix [[H, −Cᵀ], [C, S/Z]], which is the augmented form the previous essay found keeps its digits.

It takes fifteen iterations. Its iterate’s relative error falls from 1 to 0.22, 0.07 and 0.06 over the first three, crosses 10⁻³ at the sixth, and passes 10⁻⁸ at the eleventh. It ends at 5·10⁻¹³.

A guess, one solve, and a check #

The diagonal of that matrix’s second block holds sᵢ/zᵢ, and its reciprocal Dᵢ = zᵢ/sᵢ is the quantity that separates: towards 1/μ where a constraint is active and towards μ where it is not. So at any iterate the diagonal offers a guess at the active set — the constraints whose zᵢ/sᵢ exceeds one.

A guess is not an answer, and a threshold of one is a number somebody chose. What turns the guess into something that can be trusted is that a guessed active set defines a problem that can be solved exactly and checked exactly. Treat the guessed constraints as equalities and ignore the rest: that is an equality-constrained quadratic programme, and its solution is one solve with a saddle-point matrix of size n + k, where k is the number guessed — the matrix this whole field is about. Then check two things. Every constraint left out must be satisfied by the point that comes back, and every multiplier of a constraint kept must be nonnegative. Both are measured on rows normalised to unit length, so a change of units cannot pass a point that would otherwise fail.

For a convex programme, a point that passes both checks satisfies every optimality condition and is the solution, whatever produced the guess. A wrong guess cannot pass as a right one; it fails a check and costs one solve. That is the property that makes the question of when the active set is known answerable without choosing anything: the test is a certificate, in the sense the indefiniteness proof used the word, and the threshold only decides which guess gets tested.

Production interior-point codes do exactly this, and call it crossover. They do it at the end.

Certified at the first iterate #

The crossover from the very first iterate passes. At that point μ is 0.24, the method’s own iterate has a relative error of 0.22 — not one correct digit — and the point the crossover returns is x* to a relative error of 4·10⁻¹⁴. Every one of the fourteen iterates after it passes too, and every one returns the same point to rounding.

Six draws of the construction give the same shape. The first certified iterate is the first on three of them and the second on the other three, out of fifteen iterations each. At the certifying iterate the method’s error is between 0.07 and 0.29, and the crossover’s between 9·10⁻¹⁵ and 4·10⁻¹⁴. The method goes on to reach eight digits at the eleventh or twelfth iteration on every draw.

So on this family the interior-point method knows the active set, in the only sense that can be checked, ten iterations before it knows the answer to two digits — and the last thirteen or fourteen iterations of each run are spent computing, one step at a time, digits a single solve would have handed over at once.

What the diagonal looked like when it was enough #

The previous essay’s reading of the ill-conditioning suggests that the knowing and the ill-conditioning arrive together — that the active set becomes identifiable as D spreads. The measurement says they do not.

At the certifying iterate the whole diagonal spans a factor of 3,979, and the smallest zᵢ/sᵢ among the active constraints is only 2.4 times the largest among the inactive ones. The two groups have not separated in any sense a reader of the figure would call a split; they overlap to within less than half a decade. By the last iterate the spread is 2.6·10²⁸.

The matrix tells the same story in the number every library prints. Its condition number at the certifying iterate is 43. At the last iterate it is 7.3·10¹⁵. Across the six draws the gap between the groups at certification runs from 1.24 to 17.6, and the spread from 2.4·10³ to 5.3·10⁴, against final spreads between 7·10²⁶ and 2.6·10²⁸.

So the ill-conditioning the previous essay measured is not the method finding out which constraints bind. It is the method continuing after it has found out, driving the slacks of the active constraints to zero one Newton step at a time instead of setting them to zero and solving. The 43 is the price of the information. The 7·10¹⁵ is the price of computing the answer to fifteen digits by a route that approaches it from the interior — which is the whole design of the method and a good design, since a step that set slacks to zero on a wrong guess would have nowhere to go back to. But it is a price paid for digits, not for the active set.

That reading also answers the question the second form of the step raised about where the lost digits of the condensed system go: into the iterations that follow identification, which are exactly the ones a crossover makes unnecessary.

Two constraints that cannot be classified #

Everything so far had strict complementarity: every active constraint carried a multiplier bounded away from zero, so exactly one of sᵢ and zᵢ went to zero on every constraint. The construction lets that fail. Two of the ten active constraints are given a multiplier of exactly zero, so both sᵢ and zᵢ go to zero on them, and their ratio has no reason to go anywhere.

The method slows. Twenty-one iterations instead of fifteen, and the error of its iterate no longer falls with μ: it falls roughly with its square root, and the run stops — on μ = 4·10⁻¹⁴ — with an iterate accurate to 6.5·10⁻⁷. Four draws give final errors between 6.4·10⁻⁷ and 1.5·10⁻⁶. An interior-point code facing a degenerate programme typically delivers six or seven digits and a warning, and this is that behaviour reproduced.

The diagonal shows why. The eight strongly active lines climb and the thirty inactive lines fall exactly as before. The two weakly active lines go nowhere: after twenty-one iterations their zᵢ/sᵢ sits between 0.008 and 0.023. No reading of the diagonal classifies them — not a threshold at one, not a largest gap, not anything that looks at D alone — because D carries no information about them.

And the crossover passes anyway — from the first iterate on three of the four draws and the second on the fourth, to 2·10⁻¹⁴ on the one drawn.

Why the unclassifiable ones do not matter #

The reason is short and worth having in full, because it looks like luck and it is not.

A constraint that is active with a zero multiplier holds with equality at the solution, so the solution satisfies it whether it is imposed or not. Treated as an inactive constraint, it is satisfied with a slack of exactly zero, which passes the feasibility check. Treated as an active one, it is imposed as an equality with a multiplier of exactly zero, which passes the sign check. Both classifications are correct, and the crossover certifies either. The library checks both explicitly — the weakly active constraints forced into the guess and forced out of it, on four draws — and both return x* to eleven digits or better.

So the constraints the diagonal cannot classify are precisely the constraints whose classification does not affect the answer. The degeneracy costs the interior-point method its convergence rate, because the method is approaching the solution along a path that cannot distinguish them; it costs the crossover nothing, because the crossover never needed them distinguished. That is a clean example of a difficulty that belongs to an algorithm rather than to a problem — the site’s standing question of whose fault a lost digit is, answered in favour of the problem.

The same programme in other units #

One qualification belongs here, and it is a large one. The measurements above are on constraints whose rows are Gaussian with unit scale. Rescale each row by a factor between 10⁻ᵘ and 10ᵘ — the same solution, the same active set, each slack scaled with its row and each multiplier against it — and nothing about the programme has changed except its units.

With rows rescaled by up to a decade, the draw above is certified at iterate 5 of 17, at a condition number of 4.1·10⁵ and with the two groups a factor of 20 apart. With rows rescaled by up to two decades it is certified at iterate 13 of 22, at a condition number of 8.6·10⁹, with the groups a factor of 325 apart and the whole diagonal spanning 6.7·10¹⁴.

Over six draws the median first certified iterate moves from 2 of 15 at unit scale to 9 of 21 with a decade of rescaling and 35 of 44 with two, so the certified share of the run goes from 0.13 to 0.43 to 0.80. At two decades the early crossover saves a fifth of the run instead of seven eighths of it.

The mechanism is not mysterious and it is not the diagonal’s fault alone. A row scaled by α scales its slack by α and its multiplier by 1/α, so Dᵢ is scaled by 1/α²: the diagonal is measured in units squared, and a guess that compares its entries to one compares quantities in different units. But the delay is not only a misread threshold — the guess from the largest gap in log D is delayed by the same amount on these draws. The likelier cause is the method’s own path: started from slacks and multipliers of one whatever the rows’ units, it spends its early iterations correcting an infeasibility the starting point created, and its iterates carry little about the solution until that is done. That cause is argued from the error histories rather than separated from the other by a measurement. The units a matrix is measured in are part of the problem here in the plainest possible way: they decide how long the method wanders before its iterates say anything.

Equilibrating the rows before the run — dividing each by its norm — restores unit scale, and by construction restores the early certificate. That is argued from the construction rather than measured on a code that does it, and it is the obvious first thing to measure next.

What a crossover costs, and what it does not save #

The comparison is easy to overstate, so it is worth doing in the units that matter.

Each interior-point iteration is one solve with a 60 × 60 matrix. A crossover is one solve with a (20 + k) × (20 + k) matrix, 30 × 30 here, plus a matrix–vector product for the feasibility check. On this dense family a crossover costs about an eighth of an iteration, so attempting one at every iterate adds an eighth to the cost of each. Certifying at iterate 1 instead of stopping at iterate 15 replaces fourteen solves with about one.

That is not the saving on a large sparse programme, and it would be dishonest to leave it standing. There, the equality problem a crossover solves has the same sparsity as the interior-point step and costs about as much, a guess that fails costs a solve and returns nothing, and a code cannot afford to attempt a crossover at every iterate. What transfers is the shape rather than the ratio: the active set becomes certifiable at an iterate whose step is well conditioned, long before the iterate is accurate, and a code that attempted crossover on a schedule — every few iterations, or whenever the guess stops changing — would stop early by roughly the margin measured here.

And it does not transfer to a nonconvex programme at all without a second test. A point passing both checks satisfies the first-order conditions; for a convex programme that is enough, and for a nonconvex one it is not, because a saddle on the constraint passes too. The test that completes the certificate is the one the sibling essay in this field measures: the inertia of the equality problem’s saddle-point matrix, read off the factorisation the crossover solve has already computed. Which means the crossover’s one solve carries both halves of the certificate, and it also means the second half inherits that essay’s blind band.

Where this goes next #

Equilibration, measured. The two-decade rescaling moved the certified share from an eighth of the run to four fifths, and the repair was argued rather than run. A run with rows normalised before the method starts, and one with the starting point scaled to the rows instead, would separate the two causes the section above could not.

Inexact steps. Every step here was a direct solve. An interior-point method that solves its steps iteratively, reusing what survives from one barrier step to the next, computes each direction to a tolerance, and whether the guess its diagonal offers survives that tolerance is a separate question — the identification may arrive later, or earlier, or not change at all.

More active constraints than unknowns. The crossover here refuses a guess with more equalities than unknowns, which a degenerate vertex of a linear programme produces as a matter of course. What a crossover should do with an overdetermined guess — choose a basis, as the simplex method does, or regularise, as the quasi-definite essay does to the matrix — is the case this essay could not reach.

When to stop. A crossover that certifies is a stopping test with no tolerance in it, and it races the method’s own test on μ. Which of the two a code should trust when they disagree — a certified point at iterate 2 against an iterate the method considers unconverged — is the question the practical use of all this turns on.