The row that was nearly there

The multipliers were a set found the reason a crossover fails at a degenerate vertex. An interior-point iterate’s diagonal $z_i/s_i$ calls every row through the solution active, and at a degenerate vertex there are more of those rows than unknowns. Choose a basis among them and solve, and the point comes back right to fifteen digits from the first or second iterate; the certificate refuses it anyway, because the solve returns one vector of multipliers and at a degenerate vertex the multipliers are a whole set, of which the solve’s member is usually not nonnegative. Asking the set — is there any nonnegative combination of the tight rows that matches the gradient? — certified the same point at once, on every one of forty-eight runs.

That essay’s last section left a case it had not reached, and gave a prediction for it. The spare rows were placed exactly through the vertex, which is the textbook picture of degeneracy and almost never the computed one. A real linear programme built from data has rows that pass nearly through its optimal vertex: a slack of $10^{-9}$ where the model meant zero, or a constraint that is redundant at the solution up to rounding in the data that produced it. The prediction ran:

Perturb each extra row so its slack at $x^*$ is $10^{-k}$ instead of zero. The prediction with a sign is that the set question keeps certifying at every $k$ from 6 to 14, because a row with positive slack at the solution needs no multiplier and is correctly left out of the tight set, and that the basis crossover’s refusal rate falls as $k$ falls, because a row the diagonal no longer calls active cannot be chosen into a basis with the wrong sign.

Both halves are right about where the runs end. Neither is right about the way there, and the first half fails in the middle of the range rather than at either end of it, which is the part worth understanding.

Eight rows a hair’s breadth from the vertex #

The programmes are the earlier ones, rebuilt with one change. Twenty unknowns and forty rows of random normal entries; a solution $x^*$ held by twenty rows with multipliers between one half and three halves; eight further rows with zero multipliers. Before, those eight passed exactly through $x^*$. Now each is moved outward so that its slack at the solution is $10^{-k}$, for $k$ = 6, 8, 10, 12 and 14, with $k$ = 0 standing for exactly zero as the control. The other twelve rows sit between a half and one and a half away and play no part. Each set of rows is used with a quadratic objective and with the Hessian set to zero, which is a linear programme, on the same six seeds: seventy-two runs in all.

Nothing about the solution changes as $k$ moves. It is the same point, held by the same twenty rows, with the same multipliers. What changes is what the solution looks like from an iterate. At an exact vertex the near rows are active, and a method that cannot tell a row with slack $10^{-14}$ from one with slack zero sees them as active too. At slack $10^{-6}$ they are plainly inactive to anything that can resolve a millionth. Somewhere between, the algorithm has to decide which picture it is in, and every crossover and every certificate has a threshold that does the deciding for it.

The method is the long-step path-following one these essays have run since a condition number sent to infinity: Newton on the perturbed optimality conditions, a fixed centring parameter, a step to 99 per cent of the boundary, stopping when μ is under $10^{-13}$. At every iterate the four crossovers are tried exactly as before. The plain one solves the equality problem on every row the diagonal calls active, and refuses when that is more rows than unknowns. The basis one takes the guessed rows in decreasing $z_i/s_i$ and keeps each that is independent of those already kept, until twenty are kept. The regularised one keeps every guessed row with $-\delta I$ in the saddle matrix’s zero block, the quasi-definite construction with $\delta = 10^{-10}$. The set one takes the basis crossover’s point and asks the nonnegative least-squares question over the rows that point makes tight.

Where every run ends #

The first half of the prediction is a claim about certification, and the last iterate is where to check it first.

The set question certifies the last iterate of all seventy-two runs. That much the prediction got right, and so did the second half’s direction: the basis crossover, which certified one run in six at the exact vertex, certifies all six at every slack from $10^{-6}$ to $10^{-12}$, for both kinds of programme. At $10^{-14}$ it is back to one in six, and on inspection the runs at $10^{-14}$ are the exact-vertex runs over again — every crossover certifies or refuses at the same iterates on every seed. A slack of $10^{-14}$ against data of order one is a slack the arithmetic cannot represent as different from zero, and the method never gets close enough to the solution to try.

The plain crossover and the regularised one certify only at $10^{-6}$, and there for an obvious reason: by the end of those runs the diagonal has stopped calling the near rows active, the guess has exactly twenty rows, and the equality problem is square. At every smaller slack the guess still holds all twenty-eight rows when the run stops, and the plain crossover refuses the surplus on sight, as it did at the exact vertex.

So far this is a table of agreements, and it would be easy to stop. The earlier essay did not report where its crossovers ended. It reported when they started, and the start is what made the set question worth having: a certificate that arrives at iterate one is a stopping test that ends a run fifteen iterates early, which is what a test with no tolerance in it priced it at.

At an exact vertex, and at $10^{-12}$ and $10^{-14}$, the set question settles — certifies that iterate and every one after it — at iterate 1 on four seeds, 2 on one and 3 on one. At $10^{-6}$ it settles at iterates 9 to 13, at $10^{-8}$ at 12 to 15, at $10^{-10}$ at 12 to 17, out of runs of seventeen to twenty-two. The linear programmes give the same numbers to within one iterate. In the middle of the range the set question is not a fast certificate at all. At the exact vertex it arrived fourteen or fifteen iterates before the run stopped on μ; here it arrives four to nine before, and at $10^{-10}$ never more than five.

That is the first refutation. The set question keeps certifying, in the sense that it certifies the end; it does not keep certifying in the sense the earlier essay valued it for. And the shape of the failure — fine at both ends, late in the middle — says that the explanation the prediction gave, a near row correctly left out of the tight set, is not what decides it, because that explanation gets better monotonically as the slack grows and the result does not.

A point a near row’s width outside #

The set question certifies the basis crossover’s point. Before it can ask about multipliers, that point has to be feasible for every row to within $10^{-10}$, after each row is scaled to unit length — the normalisation two repairs for one symptom showed a certificate cannot do without. At the exact vertex this was never in doubt: any twenty independent rows through the solution pin it exactly. With near rows it is the whole story.

By the second to the seventh iterate the diagonal calls all eight near rows active, at every slack. The basis crossover ranks the twenty-eight guessed rows by $z_i/s_i$ and keeps the first twenty independent ones, and early in the run some near rows rank above some of the strong ones. A near row in the basis is solved as an equality: the crossover’s point is placed exactly on it, which is $10^{-k}$ away from where the solution is. Twenty rows still pin the point, but they pin it at the vertex of the wrong twenty rows, and that vertex sits outside one of the strong rows that was left out.

On the run in the figure, at $10^{-8}$, the point is outside by $2 \times 10^{-8}$ to $5 \times 10^{-7}$ for the first eleven iterates. The certificate’s tolerance is $10^{-10}$, so the point fails feasibility, and the set question, which starts by checking feasibility, refuses it before it reaches the multipliers. At iterate 12 the point is exactly feasible again but still wrong: the basis has moved off the near rows that violated a strong one, but it still holds near rows in place of strong ones, and the point is a feasible vertex that is not the solution. Its error is about $10^{-8}$, and the set question refuses it there too, this time on the multipliers: the strong rows the point is not on are not tight, and no nonnegative combination of the rows that are can match the gradient. That is the earlier essays’ warning about an answer that is feasible and wrong, arriving here from a different direction, and the certificate catches it correctly. At iterate 13 the basis is the twenty strong rows, the point is $x^*$ to rounding, and both crossovers certify from then on.

Drag the slack to zero and the same mechanism is harmless: a near row with slack zero is a row through the vertex, and putting the point on it costs nothing. Drag it to $10^{-12}$ and the mechanism is still at work — the basis still holds near rows, the point is still outside — but by $2 \times 10^{-12}$ to $5 \times 10^{-11}$, which the tolerance cannot see. The set question treats the point as feasible, finds the near rows tight, finds a nonnegative combination over all twenty-eight, and certifies from the first iterate.

The tolerance decides which side a row is on #

That one run generalises without exception, and the general version is simpler than the single run suggests.

On every run at a slack from $10^{-6}$ to $10^{-12}$, the worst infeasibility of the basis point before it settles is between 3.1 and 48.4 times the near rows’ slack, and each seed lands on the same ratio at every slack to within two per cent. The geometry is linear in the perturbation: solving on a near row instead of a strong one moves the point by the slack times a factor fixed by the angles between the rows, and that factor belongs to the programme, not to $k$. Only at $10^{-14}$ does rounding start to blur it.

So the question of whether the set certifies early reduces to arithmetic. The point is outside by between three and fifty times $10^{-k}$; the certificate accepts anything outside by less than $10^{-10}$. At $k = 10$ the point is outside by $3 \times 10^{-10}$ at least, and every run is refused until the basis turns. At $k = 12$ it is outside by $5 \times 10^{-11}$ at most, and no run is. The boundary between “a near row is a different row” and “a near row is the same row” is drawn by a number the certificate chose for an unrelated reason — to forgive rounding in a feasibility check — and it falls between $10^{-10}$ and $10^{-12}$ because that number is $10^{-10}$ and the programmes’ amplification factor is under a hundred.

There is a second threshold in the certificate, and it agrees. The set question counts a row as tight when its scaled slack is under $10^{-9}$. At $10^{-12}$ the near rows are tight, the set question has twenty-eight rows to combine, and the twenty strong ones carry a nonnegative solution with the eight near ones at zero. At $10^{-8}$ the near rows are not tight at the solution, the set has twenty rows, and it can only certify a point sitting on exactly those twenty. Either way the set question gives the right answer at the end; what the tolerances choose is how long the iterates are made to wait for it.

Neither tolerance was set with near rows in mind, and nothing about the problem says the line should fall where it does. By the same arithmetic, a certificate with a feasibility tolerance of $10^{-8}$ would end the late band at $10^{-8}$ and certify early from $10^{-10}$; one with $10^{-12}$ would stretch the band to $10^{-12}$. Those are predictions from a ratio, not runs. A tolerance is priced by the problem found the same thing about stopping tests across three fields: the number in the test is a choice, and the shape of the answer follows it.

The basis waits for μ, not for the diagonal #

The second half of the prediction explained the basis crossover’s improvement: a near row the diagonal no longer calls active cannot be put in the basis. That would make the basis turn at the iterate where the guess drops the near rows. It does not, and on most of the runs that iterate never comes.

At $10^{-6}$ the diagonal drops all eight near rows before the run stops; at every smaller slack it calls all eight active at the last iterate. That has a short explanation. On the central path a row’s multiplier and slack multiply to about μ, so a near row whose slack has settled at $s$ carries $z \approx \mu/s$ and a diagonal of $\mu/s^2$, which exceeds one until μ falls below $s^2$. At $10^{-6}$ that is $10^{-12}$, which the runs pass; on all twelve runs at $10^{-6}$ the plain crossover — which needs the near rows gone — settles at the iterate where μ falls from between $10^{-12}$ and $5 \times 10^{-12}$ to between $10^{-13}$ and $5 \times 10^{-13}$. At $10^{-8}$ it would be $10^{-16}$, and the runs stop at $10^{-13}$.

Yet the basis turns at every slack from $10^{-6}$ to $10^{-12}$, with the near rows still called. What decides it is not whether a near row is called but where it ranks. A strong row with multiplier $z^*$ has slack about $\mu/z^*$ and so a diagonal of about $z^{*2}/\mu$; a near row’s diagonal is $\mu/s^2$. The basis keeps the first twenty in ranking order, and the strong rows outrank every near row once $z^{*2}/\mu$ exceeds $\mu/s^2$, which with multipliers near one is once μ falls below about the slack. Measured on all forty-eight runs at slacks from $10^{-6}$ to $10^{-12}$, both kinds, the basis settles at exactly the iterate where μ first falls under three tenths of the slack, from an iterate above a tenth of it. At $10^{-12}$ that is μ near $10^{-13}$, the last iterate or two of the run; at $10^{-14}$ the run stops with μ still above the slack, the ranking never turns, and the basis behaves as at an exact vertex.

So the prediction’s direction was right — the basis refuses less as the slack grows — and its blame was misplaced. The diagonal’s guess is irrelevant to the basis crossover at every slack below $10^{-6}$; the ordering inside the guess is what matters, and the ordering turns at μ equal to the slack, not at μ equal to the slack squared. The active set before the digits made the general version of this point for weakly active rows on a face: the diagonal separates rows at a rate set by μ, and a row’s place in the order is decided long before its place in or out of the guess.

What the near rows cost a stopping rule #

Put the two findings together and the set question’s value as a stopping test has a shape. At an exact vertex it ends runs at iterate one to three. At a near vertex whose slack is under the feasibility tolerance divided by the amplification, it does the same, because to the certificate those rows are through the vertex. At a near vertex whose slack is larger, the set question waits for the basis, the basis waits for μ to pass the slack, and the certificate arrives one iterate later for every decade the slack shrinks — settling around iterate 11 at $10^{-6}$, 13 at $10^{-8}$, 15 at $10^{-10}$ — because that is the rate at which this method reduces μ.

That is not a failure of the certificate, though the runs do show what it certifies. Of the 1,281 iterates in the seventy-two runs it certified 866, and at twenty of them the point was further from $x^*$ than $10^{-10}$ in relative terms — at most $3.2 \times 10^{-10}$, every one at a slack of $10^{-10}$, where the near rows’ slack and the tolerance are the same number. There the certificate is accepting a point that solves the programme with each row relaxed by its tolerance, which is exactly what it promises and no more: a certificate with a tolerance certifies a nearby problem, and when the data’s own near-degeneracy is the size of the tolerance, the nearby problem and the real one are different vertices. At every other slack its points are right to the tolerance, and where it is late every alternative in the comparison is later or never. It is a failure of the earlier essay’s account of why it was early: the set question was early because the basis’s point was exact from the start, and at a near vertex the basis’s point is not exact until the basis turns. The repair, if one is wanted, is a basis that does not wait for the diagonal’s ordering — which is the third question the earlier essay left open, and which these runs make more urgent rather than less.

What seventy-two runs do not show #

Every near row here has the same slack. Real near-degeneracy is a spread: a few rows at $10^{-14}$, a few at $10^{-9}$, one at $10^{-5}$, and the runs above say nothing about which of them a basis will hold at a given iterate when the rankings interleave. The amplification factor, three to fifty on these random programmes, is a property of the angles between the rows, and a programme whose near rows meet a strong row at a small angle would push it far higher and move the line toward larger slacks. The method is one method with one centring rule; a predictor–corrector method reduces μ faster and would compress the late band into fewer iterates without moving it. And twenty unknowns is small: what survives one step of the barrier is the reminder that a crossover tried at every iterate costs a factorisation each time on a large programme, which a late certificate pays for longer.

Still open: mixed slacks, the amplification, and a basis from the set #

A spread of slacks. Give the eight near rows slacks spread log-uniformly from $10^{-14}$ to $10^{-6}$. The prediction with a sign is that the set question settles at the iterate where μ passes three tenths of the largest slack among the near rows whose amplified displacement exceeds $10^{-10}$, so that one row at $10^{-6}$ delays certification as much as eight do, and rows under $10^{-12}$ cost nothing whatever their number.

The amplification as a condition number. The ratio of infeasibility to slack, three to fifty here, should be bounded by the condition of the basis matrices the ranking passes through. The prediction is that on programmes whose near rows meet a strong row at an angle of $10^{-3}$ the ratio exceeds a thousand, and the late band then reaches down to a slack of $10^{-13}$, below which the near rows are certified as exact.

A basis from the set, at a near vertex. The earlier essay predicted that taking the nonnegative least-squares support as the basis would make the basis crossover certify as early as the set question. At a near vertex the set question is itself late, so the prediction here is stronger and riskier: that a basis chosen by the set question’s support on the first iterate’s tight rows, with tightness judged at $10^{-9}$, is the twenty strong rows on every run with slack $10^{-8}$ or larger, and certifies by the third iterate at every slack.