A test with no tolerance in it

A stopping test is a race made the general point about tolerances: a test that stops whichever iteration reaches a threshold first has no opinion about whether it is the iteration that should have, and two tests measuring different things will disagree. An interior-point method carries exactly that arrangement and has done since the first of these essays, without the disagreement having been scored.

Its own test is a tolerance on μ, the barrier parameter, which is the average of the products $s_i z_i$ and falls geometrically along the run. Set the tolerance and the method stops. The other test is the one the active set before the digits built: take the constraints whose $z_i/s_i$ exceeds one, solve the equality-constrained problem they define once, and check the result against the conditions for optimality. It has no tolerance in it — primal feasibility of the constraints left out and dual feasibility of the ones kept are either satisfied or not, measured on rows normalised to unit length so the check cannot be passed by a change of units.

They are not close.

The race, in two columns #

Six programmes, twenty unknowns, forty constraints, ten active at a known solution. Averaged over the six:

The μ column behaves exactly as it should: each two decades of tolerance costs two iterations and buys two decades of accuracy, which is what a method with linear convergence in μ and an error proportional to it looks like, and it is the relationship the whole apparatus of interior-point theory is built to produce.

The certificate does not sit on that line. It arrives at iterate 1.5, where the method’s own iterate carries a relative error of 1.42·10⁻¹ — one correct digit — and the point it returns carries fourteen. There is no tolerance on μ that reaches it, because the method’s iterate never becomes that accurate: the run stops at 1.60·10⁻¹² and the certificate had 1.78·10⁻¹⁴ thirteen iterations earlier.

So this is not a race in which one test is faster and the other more careful. One test is faster and more accurate, and it is more accurate by two orders of magnitude at the point where it is thirteen iterations ahead.

Why one correct digit is enough #

The reason is the finding this whole field is built on and it is worth restating in the form this essay needs. The iterate’s accuracy and the active set’s correctness are different quantities with different rates.

The active set is a discrete object — ten constraints out of forty — and the diagonal $z_i/s_i$ separates the ones that will be active from the ones that will not almost immediately: at iterate 1 the smallest z/s among the truly active constraints is already 2.4 times the largest among the inactive ones, and by iterate 5 it is nine million times. The iterate’s own position, by contrast, converges at the rate μ falls, because it is being dragged along a central path toward a boundary it may not touch until μ is at rounding.

A crossover reads the discrete object and discards the continuous one. It does not use the iterate’s coordinates at all — only its diagonal, and only to decide which ten constraints to impose as equalities. The solve that follows is a fresh linear system whose accuracy has nothing to do with how far along the path the method had got.

That is why the certified error is flat. It is not improving along the run because there is nothing in it to improve: it is the accuracy of one well-conditioned dense solve, and the step matrix’s condition number at that iterate is 43 rather than the 7·10¹⁵ it reaches at the last.

There is a second reading of the same fact that matters more for how a code should be written. The method is doing two things along its run and only one of them is finishing. It is locating the active set, which it does in one or two iterations, and it is walking to the solution of the problem that active set defines, which it does slowly and approximately. The second job is redundant: once the set is known, the point it defines can be computed directly, and computing it directly is both cheaper and better than walking to it.

That framing also says why the μ test cannot be repaired by choosing a better tolerance. μ measures how far the iterate is from the boundary, and the iterate’s distance from the boundary is the quantity the method controls deliberately — it is kept away from the boundary so the Newton steps stay well defined. A condition number sent to infinity is the same observation about the step matrix: the method manufactures an extreme condition number on purpose because separating the diagonal is how it discovers the active set, and a quantity manufactured on purpose is not a measure of progress toward anything. μ is the schedule, and reading a schedule as an error estimate is what the table above costs.

What one attempt costs #

None of this is free, and the cost is the reason the test is not simply always used.

The method’s own step, with the slack eliminated, is one (n + p)-square solve — sixty by sixty here — at (n + p)³/3 ≈ 72,000 flops. The crossover is one (n + k)-square solve where k is the size of the guessed active set, thirty by thirty here, at ≈ 9,000. So an attempt costs an eighth of a step, and trying it at every iterate adds about 12.5 per cent to the dominant cost of the method.

Twelve and a half per cent for thirteen iterations is a trade anyone would take on these programmes, and it is not the trade in general. The ratio (n + k)³/(n + p)³ is small only when the active set is small relative to the constraint count; at k = p it is one, and a programme with almost every constraint active pays a full extra step at every iterate for a test that will pass immediately and cost one attempt anyway. The interesting case is the one in between, where the attempt is cheap and the iterate at which it starts passing is not the first.

It is also a trade against a risk rather than only against work. An attempt that fails returns nothing and costs a solve; an attempt that succeeds returns an answer whose optimality has been checked, so the method can stop. A test that is occasionally wasted and never wrong is a very different object from a tolerance, which is never wasted and occasionally wrong — the stopping test that races another one is the general case, and the asymmetry here is what makes the certificate worth paying for rather than merely cheap.

A trigger the method already has #

So the question is which iterate to spend the attempt on, and there is a quantity already computed that answers it.

The diagonal’s true gap — the smallest z/s among the constraints active at the solution divided by the largest among those that are not — is 1.07 at the iterate before the first certification and 3.39 at it. That is a clean separation and it is not available to a code, because it needs the true active set.

What is available is the same ratio across the gap the guess itself draws: the smallest z/s among the constraints the method is calling active over the largest among those it is calling inactive. That needs no truth at all — it is a property of a sorted list of forty numbers and the threshold of one that split them.

At a threshold of two the trigger fires at iterate 1.67 against a first certification at 1.5: no attempt is wasted, 0.17 of an iterate is lost on average, and it never misses a run that certifies. At a threshold of one it fires at iterate 0 in every run and wastes 1.5 attempts. At a hundred it fires at 3.0 and loses 1.5 iterates.

Both costs are small here because the certification is early. The threshold is worth having anyway, because it turns “try it at every iterate” — 12.5 per cent of the method — into “try it once”, and because the programme where it matters is the one where certification is late.

The two costs the figure draws are genuinely different costs and should not be added. An attempt made too early is an eighth of a step, spent and gone. An iterate lost after the certificate would have passed is a whole step, spent on a method that had already finished. So the right threshold is not where the two curves cross but where their weighted sum is least, and at eight to one the weighting pushes it left — toward firing early and wasting attempts, which is the cheap mistake. At a threshold of two on well-scaled rows the weighted cost is 0.17 of a step; at one it is 0.19; at a hundred it is 1.5. The flat bottom over an order of magnitude in the threshold is what makes the rule worth stating at all.

The threshold is not portable, and the earlier measurement says why #

That programme is the badly scaled one, and it is where this essay meets the last.

With rows rescaled by up to 10² either way the crossover first certifies at iterate 30.0 rather than 1.5, and the guess’s own margin reaches two at iterate 8.5. A threshold of two therefore makes 21.5 wasted attempts — a fifth of the method’s own cost, spent on solves that cannot pass. The threshold that works there is a hundred, which fires at 31.2 and loses 1.2 iterates; and a hundred, used on the well-scaled programme, loses 1.5 iterates for no reason.

So the trigger has a parameter and the parameter moves with the units, which is a bad property for a trigger to have and exactly the property the earlier measurement measured a repair for.

Normalising the rows brings the first certification back to iterate 7.2 and puts the threshold of two at 6.2 — one wasted attempt, no iterates lost. Which is the practical shape of the whole argument: the certificate is the better stopping test by a wide margin, the trigger that makes it cheap needs a threshold, and the threshold is portable only after the rows have been equilibrated.

The same figure also answers a question the earlier measurement raised and could not settle: whether the certificate should be the stopping test at all, given that it certifies at iterate 7.2 of 18.8 after equilibration. It should, and the reason is not that 7.2 is earlier than 18.8 — it is that the point certified at 7.2 is better than the point the method reaches at 18.8, by the two orders of magnitude the race measured. Stopping early is not the benefit; stopping at all on the strength of a proof rather than a schedule is.

What the certificate is not #

It is worth being exact about what a passing certificate establishes, because “no tolerance in it” is a claim that has to be qualified twice.

The check is scale-free but not exact. Feasibility of the constraints left out and dual feasibility of the ones kept are compared against −10⁻¹⁰ on unit-normalised rows, which is a tolerance in the sense that a point violating a constraint by 10⁻¹¹ passes. What it is not is a tolerance on how far the answer is from optimal — it is a tolerance on the residual of a proof, and the two are related by the conditioning of the equality problem rather than by the conditioning of the barrier. That is the whole reason the certified error is 1.8·10⁻¹⁴ while μ is still 0.24.

And it certifies a point, not a programme. A programme with more active constraints than unknowns has no equality-constrained problem to solve — the crossover refuses an overdetermined guess outright — and a degenerate vertex of a linear programme produces exactly that as a matter of course. Every programme measured here has ten active constraints against twenty unknowns and a strictly positive multiplier on each, so the case that would break the construction never arises.

What a code would do with all of this #

Three lines of pseudocode and one of them is the one that was missing.

After each interior-point step, sort the diagonal $z_i/s_i$ and split it at one. If the smallest value above the split divided by the largest below it is at least the threshold, solve the equality problem the split defines and check its two residuals. If they pass, return that point and stop.

The threshold is the only free number and the earlier measurement supplies its calibration: after equilibration a threshold of two is right at every spread of units measured, and without equilibration there is no single right value. The scaling that buys ten orders is the same shape of statement one level down — an operation whose whole value is that it makes a later decision portable rather than that it improves any single number.

What the pseudocode does not contain is a tolerance on μ, and that absence is the point. A method written this way has no accuracy parameter: it returns the answer when it can prove it has it. That is an unusual property for a numerical method and it is available here because the object being identified is discrete. The same argument does not carry to an unconstrained problem, where there is nothing combinatorial to get right and the only thing to stop on is a residual — which is why a stopping test is a race ends where it does, and why this field’s version of the question has an answer and that one’s does not.

The remaining cost is the one a real programme will actually feel. Forty constraints is small, and sorting a diagonal of forty numbers is free; a programme with a million constraints sorts a million numbers per iterate, and the solve whose size is n + k is a solve whose size depends on how many of them the guess keeps. Neither of those changes the argument and both change the arithmetic in the section above, in directions this family cannot measure.

What this does not settle #

Six programmes, one shape, one Hessian conditioning, and one method — primal–dual path-following with σ = 0.1 and a step to 0.99 of the boundary. A Mehrotra predictor–corrector reaches small μ in fewer iterations, which shortens the μ column and does not obviously move the certificate’s, so the ratio the table reports would narrow by an unmeasured amount.

Every step is a direct solve. A method solving its steps iteratively computes a diagonal that is only approximately the right diagonal, and whether the guess and the trigger survive a tolerance on the inner solve is unmeasured — the identification may arrive later, earlier, or not move.

The trigger is scored against the crossover’s own first certification and not against anything external, so “0.17 of an iterate late” is a statement about this decision rule on these runs. The threshold sweep has six values, and the crossing is located to about a decade.

The flop counts are the leading term of a dense factorisation and nothing else. A code that exploits the structure of either system — the saddle-point form of the step, or the sparsity of a real constraint matrix — changes both sides of the ratio, and there is no reason for the two changes to be equal.

Still open: degeneracy, inexact steps, and a certificate that is also a warm start #

Weakly active constraints. Every programme here carries a strictly positive multiplier on each active constraint. An earlier measurement here found what happens when some do not — the method’s own error falls at about the square root of μ and its run ends with six digits where it had twelve, while the crossover’s dots do not move, because the constraints it cannot classify are the ones whose classification does not change the answer. That makes the race above wider rather than narrower, and by an unmeasured amount: the μ column would lose six digits and the certificate column would not.

An overdetermined guess. The crossover refuses more equalities than unknowns, and a degenerate vertex produces them routinely. What a crossover should do then — choose a basis, as the simplex method does, or regularise the matrix, as the quasi-definite construction does — is the case these essays have not reached, and it is the case that decides whether any of this is usable on a linear programme.

The trigger under inexact steps. The guess’s own margin is computed from a diagonal that an inexact solve perturbs. Whether the margin is more or less robust than the guess it is derived from is the measurement that would say whether the trigger survives into a method that never forms its step matrix.

A failed certificate as information. An attempt that does not certify returns a feasibility residual and a dual residual, both signed, and both are discarded here. Whether their size predicts how many iterates remain — so that a failed attempt buys the next trigger rather than costing a solve — is the obvious way to make the trigger adaptive and has not been tried.

And the certified point as a starting point. The crossover’s answer at iterate 1.5 is more accurate than anything the method will produce. Whether the method can be restarted from it, rather than stopped at it, is a different question from stopping: a point on the boundary is not an interior point, and the construction that would take it back inside is the one that decides whether this is a stopping test or a method.