Two repairs for one symptom

The active set before the digits ended with a repair it argued and did not run. A quadratic programme whose constraint rows are written in units spread over four decades loses most of what the essay had just demonstrated: the crossover that certifies the answer from the first or second iterate stops certifying until very late, and the diagnosis offered was that rescaling the rows would restore it. The sentence read the two-decade rescaling moved the certified share from an eighth of the run to four fifths — a measurement of the damage, and a claim about the cure.

Two cures are available and they are not the same cure. Normalising each constraint row to unit length changes the matrix the Newton step factorises. Starting the iteration at the magnitudes the rows imply changes nothing about the matrix and only moves where the method begins. If the symptom has one cause, one of them is the repair and the other is irrelevant. It has two, and they divide neatly.

What the damage is, measured properly #

The programme is the same one throughout: twenty unknowns, forty constraints, ten of them active at a solution that is known before anything is solved, and a Hessian with a condition number of a hundred. The row-scaling parameter multiplies row $i$ of the constraint matrix by $10^u$ with u uniform on [−k, k], and scales the slack and multiplier that row carries so that the same point is still the solution. It is a change of units and nothing else.

Averaged over six programmes, with nothing done about it:

• at k = 0 the crossover certifies from 91 per cent of the run, first at iterate 1.5, and the method takes 15.0 iterations;
• at k = 1, 61 per cent, first at 8.3, 20.3 iterations;
• at k = 2, 28 per cent, first at 30.0, 39.7 iterations;
• at k = 3, 10 per cent, first at 69.8, 74.3 iterations, and two of the six programmes never certify at all before the run stops.

The earlier measurement reported one column of that table from two programmes. The shape is the same and the collapse is steeper than it looked: at six decades of spread the method takes five times as many iterations and spends nine tenths of them unable to certify anything.

The collapse is not the ill-conditioning that measurement’s headline was about, and the distinction is worth holding. A condition number sent to infinity found the step matrix’s condition number climbing to 3·10¹⁵ by design, on a well-scaled programme, without costing the answer a digit — because the separating of the diagonal is how the method discovers which constraints are active, and the form the step is written in keeps the digits through it. That condition number is benign. A change of units produces a second and quite different kind of ill-conditioning, one the method was not built to exploit, and the two are separable because the first grows with 1/μ along the run while the second is there at the first iterate and does not move.

The units the matrix is measured in is the same distinction one level down, for a linear solve: a condition number that reports a choice of units rather than a difficulty, and a scaling that removes it. A condition number scaling cannot move is the other half — the part no rescaling reaches. What is new here is that the units are not reaching the answer’s accuracy at all. Every certified point in every run below is accurate to eleven digits or more when it certifies. What the units delay is when a certificate becomes available, which is a property of a classification rather than of an arithmetic.

The repair that removes the spread #

Dividing row i of C and entry i of d by $\|C_i\|$ leaves the feasible set exactly where it was — a constraint and a positive multiple of it define the same half-space — so x* does not move, the slack it carries divides with the row and the multiplier multiplies. Any solver that does this at all does it before the first iteration.

What it does to the table is more decisive than “it helps”. At k = 1, 2 and 3 the certified share is 64 per cent, the first certificate is at iterate 7.2 and the method takes 18.8 iterations — the same three numbers, to every digit printed, at all three spreads. That is not a repair that works well; it is a repair that is complete. Normalising rows maps every rescaling of a programme to one programme, so after it there is no spread left for anything to depend on.

A second equilibration behaves identically and is worth having for the same reason a second route to a number is always worth having: dividing row $i$ by $|d_i|$ rather than by $\|C_i\|$ is a different normalisation with a different justification — it makes the initial slack at x = 0 equal to one in every constraint rather than making the rows comparable to each other. It gives 60 per cent, first at 8.3, 20.0 iterations, flat at every spread. Two normalisations that share no arithmetic, both flat, landing four points apart.

Two independent normalisations agreeing that the repair is complete is what makes it safe to say the spread is gone rather than merely reduced. It is the same standard the two routes to the general-form operator are held to elsewhere in this field, and it is cheap here because the second normalisation was one line.

And the repair that does not touch the matrix #

The other cure changes nothing about the programme. The method starts at s = z = 1 for every constraint, which is what every account of it writes and what assumes the constraints are in comparable units. Starting instead at $s_i = \|C_i\|$ and $z_i = 1/\|C_i\|$ leaves the product $s_iz_i$ at one — so μ starts where it started, and only the split between slack and multiplier moves.

That alone takes the iteration count at k = 3 from 74.3 to 18.8. And 18.8 is the count it has at k = 0, k = 1 and k = 2 as well: the iteration count, unlike the certified share, is completely repaired by the starting point and does not care about the spread at all.

The certified share is not completely repaired: 80, 66, 53 and 43 per cent at the four spreads, against equilibration’s flat 64. So starting well recovers a little over half of what a wide spread costs the crossover, and recovers all of what it costs the iteration.

That is the separation the earlier measurement could not make. How long the method runs is set by where it starts. How early the active set can be certified is set by the matrix it factorises. A starting point that respects the units stops the method wasting fifty iterations recovering from a bad first point; it does not make the diagonal $z_i/s_i$ separate the active constraints from the inactive ones any sooner, because that separation is a property of the steps, and the steps come from a matrix whose rows are still six decades apart.

There is a second way to see that the two are separate, and it does not need a second run. The diagonal’s spread at the first iterate is 1.0 with nothing done — every constraint starts at z/s = 1 by construction, whatever its units — and it is 7.3·10³, 3.7·10⁷ and 2.2·10¹¹ at the three spreads once the start respects the rows. So the repair that fixes the iteration count is the one that makes the first iterate’s diagonal disagree, spectacularly, and the repair that fixes the identification is the one that makes it agree at 1.0 again. A single quantity cannot be the explanation for both.

The repair that costs something #

The table has one more entry in it and it is the uncomfortable one. Equilibration applied to a programme that was already well scaled — k = 0, where the rows were never rescaled at all — moves the certified share from 91 per cent to 64, the first certificate from iterate 1.5 to 7.2, and the iteration count from 15.0 to 18.8.

So “always equilibrate” is not free advice. It is a trade that is overwhelmingly worth making at k = 2 or k = 3, is roughly neutral at k = 1, and is a real loss at k = 0.

The reason is the same one that makes the starting point matter, arriving from the other side. The rows of this programme are drawn from a standard normal in twenty dimensions, so each has norm about $\sqrt{20} \approx 4.5$, and its slack at the solution is order one. Normalising the row to unit length divides the slack by 4.5 and multiplies the multiplier by 4.5 — so after equilibration the solution’s own s and z are around 0.2 and 4.5 rather than both around one, and the start at s = z = 1 is a factor of four out in each direction. Making the rows comparable to each other has made them less comparable to the starting point.

Which means the two causes are not independent after all, and the honest statement of the finding is one step more careful than “two repairs, two causes”. There is one quantity that matters — how far the method’s starting point is from the magnitudes the solution carries — and there are two things that move it: the units the constraints are written in, and the point the method chooses to start from. Equilibration fixes the first completely and disturbs the second; starting at the rows fixes the second for the units it can see and leaves the first alone. Neither is the whole repair, and the combination of unit-norm rows with a start at s = z = 1 is exactly the combination measured as “equilibrate” above, because unit-norm rows make the two starts identical.

What survives one step of the barrier measured the same programme family from the other direction — what a factorisation carried from one barrier step to the next is still worth — and found only the diagonal moving. That is the reading that makes the sentence above precise: the units live in the off-diagonal blocks, which do not move along the run, so a change of units is a property of the whole sequence of steps rather than of any one of them. It cannot be waited out, and the measurement says so — at k = 3 the method takes 74.3 iterations and certifies from the last 10 per cent of them.

What a solver should therefore do #

The measurement supports one recommendation and refuses another.

It supports equilibrating when the rows disagree, and says by how much to care: at a spread of two decades either way the crossover recovers from 28 per cent of the run to 64, and the method from 39.7 iterations to 18.8. It refuses equilibrating unconditionally, because at no spread at all the same operation costs 27 points of certified share and four iterations.

What it does not supply is a test for “the rows disagree” that a solver could apply, because the spread of row norms is itself a quantity in the constraints’ own units and a programme can have badly matched rows with well-matched norms. The ratio of largest to smallest row norm is the obvious candidate and it is the quantity the row scaling was built to move, which makes it a circular test on this family and an untested one elsewhere.

And it leaves the third possibility unmeasured: a starting point chosen from the programme rather than from its rows. The magnitudes that would make the start right are those of s* and z*, which nobody has; what a solver can have is a least-squares estimate of them, which is what several published starting heuristics compute. Whether such a heuristic lands closer than either repair here is one sweep and is not run.

Why the certificate is the right thing to count #

Everything above is scored on the share of a run from which a crossover certifies, and that choice deserves a sentence because a more obvious quantity was available.

The obvious one is the method’s own error — how many digits its iterate has at each step — and it is the wrong quantity here for the reason the earlier measurement was written about. The iterate’s error and the certified point’s error are two different numbers, and the second is better by ten orders of magnitude for most of the run: at the first certified iterate the method’s own point has one or two digits and the point obtained from it by keeping the constraints its diagonal calls active and solving once has thirteen. A measurement of what units cost the iterate would find them costing iterations. A measurement of what they cost the certificate finds them costing the thing that was actually on offer.

And the certificate is checkable. Primal feasibility of the constraints left out and dual feasibility of the ones kept are measured on rows normalised to unit length, which is the one place in all of this where normalisation is not optional: an unnormalised feasibility test would pass a point at a spread of 10³ either way that it would fail at unit scale, and the whole measurement would be reporting its own test’s units. Stationarity and the kept equalities hold by construction of the solve, so the check has exactly two things to verify and verifies them in the units the answer is in rather than the units the programme was written in.

That is why “never certifies” is a meaningful entry in the table rather than a threshold artefact. Two of six programmes at k = 3 reach the end of a 90-iteration cap without ever producing an active-set guess that passes a scale-free optimality check — not a guess that was nearly right, and not one that failed a tolerance by a little.

What this does not settle #

Six programmes at each spread, one size — twenty unknowns, forty constraints, ten active — and one Hessian conditioning. The counts reported are means over six, so “two of six never certify” is the count and not a rate.

The rescaling is drawn from one distribution: 10^u with u uniform on [−k, k], independently per row. A programme whose badly scaled rows are the active ones would behave differently from one whose badly scaled rows are inactive, and the draw does not distinguish them.

Every run uses the same method — primal–dual path-following, σ = 0.1, a step to 0.99 of the boundary, and the slack eliminated into one (n + p)-square solve. A condition number sent to infinity showed that the form the step is written in decides whether the ill-conditioning is benign, and every measurement here uses the form that keeps its digits. On the other form the whole table would be about something else.

The programmes are all non-degenerate: every active constraint carries a strictly positive multiplier. The previous essay measured what a weakly active constraint does — it slows the method’s own error to about the square root of μ and leaves the crossover’s dots where they were — and that interaction with a change of units is not swept here. The pivot that reads the units is the same question for a factorisation’s own decisions, and its answer there was that a threshold in the wrong units chooses the wrong pivot.

No Mehrotra predictor–corrector, no adaptive σ, and no presolve. Each of those changes the iteration count by a factor that is larger than some of the effects measured here, and none of them is obviously neutral with respect to identification.

Still open: a test for when to equilibrate, and the same question with inexact steps #

A test a solver can apply. The recommendation above needs a statistic that says whether a programme’s rows disagree, and the row-norm ratio is circular on this family. Whether the spread of the diagonal $z_i/s_i$ at the first iterate serves — it is 1.0 by construction at every spread here, because the run starts at s = z = 1, and is 7.3·10³ to 2.2·10¹¹ once the start respects the rows — is the measurement that would turn the finding into a rule, and it is available from quantities the first iteration already computes.

A starting point from the programme. The published heuristics solve a least-squares problem for a starting point rather than taking s = z = 1. If the separation above is right, such a heuristic should behave like the row-start repair — fixing the iteration count and half the identification — and if it behaves like equilibration instead, the account of the mechanism given here is wrong.

Inexact steps. Every step in every run here is a direct solve. A method that solves each direction to a tolerance computes a diagonal that is only approximately the right diagonal, and whether the crossover’s guess survives that tolerance is a separate question the earlier measurement also left: the identification may arrive later, earlier, or not move at all.

Whether the certificate should be the stopping test. The crossover certifies at iterate 7.2 of 18.8 after equilibration, so a method that stopped when it first certified would stop at a third of its run. It would also be a stopping test racing another one — a certified point against a μ the method still considers large — and which of the two to trust when they disagree is the question the practical use of all this turns on.