The multipliers were a set

A test with no tolerance in it scored two ways of stopping an interior-point method on a convex quadratic programme. The method’s own test is a tolerance on μ, the barrier parameter. The other is a crossover: take the constraints whose diagonal entry $z_i/s_i$ exceeds one, solve the equality problem they define, and certify the answer — feasible for every row left out, nonnegative multipliers on every row kept. A point that passes is the solution, whatever produced it. The crossover won by thirteen iterations and two orders of magnitude, certifying from an iterate with one correct digit.

Its last section listed what it had not reached, and one item was blunter than the rest. 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.”

Both remedies are easy to build, and both work in the sense that matters least. They return the right point. They do not return a point the certificate will accept, and the reason is not in the point.

A vertex with rows to spare #

The programmes are built so the answer is known before they are solved. Twenty unknowns, forty rows of random normal entries, and a solution $x^*$ that is a vertex: twenty rows pass through it with positive multipliers, which pins it down whatever the objective is. Then $e$ further rows are made to pass through the same point with zero multipliers — two, four or eight of them. Those rows are active, and nothing holds them there; remove any one and the solution does not move. That is degeneracy in the strict sense, and it is what a linear programme’s optimal vertex usually looks like, because a vertex in a high-dimensional polytope of many constraints commonly lies on more of them than it needs.

Each set of rows is used twice: with a quadratic objective, and with the Hessian set to zero, which is a linear programme. The method is the plain long-step path-following one the earlier essays ran — Newton on the perturbed optimality conditions, a fixed centring parameter, a step to 99 per cent of the boundary — and at every iterate four crossovers are tried:

• plain — the guess as it stands, refused if it has more rows than unknowns;
• basis — the guessed rows in decreasing $z_i/s_i$, each kept only if it is independent of those already kept, until twenty are kept: a basis chosen by the diagonal, as a simplex code would choose one by its own pricing;
• regularised — every guessed row kept, with $-\delta I$ in place of the saddle matrix’s zero block, $\delta = 10^{-10}$, so that the surplus rows are fitted in least squares instead of contradicting each other;
• set — the basis crossover’s point, certified a different way, described below.

With no extra rows nothing new happens. The guess has twenty rows from the first or second iterate, the plain crossover certifies there as it did before, and so does everything else. With extra rows the guess grows past twenty — the diagonal calls every row through the vertex active, because on every one of them the slack is going to zero — and the plain crossover refuses: at two extra rows it certifies on three programmes of six, and only at iterates where the guess happened to leave a degenerate row out; at four and eight it never does.

The two remedies do little better. At four extra rows the basis certifies on two programmes of six and the regularised crossover on two; at eight, on one each.

The point was never what failed #

The figure invites the reading that the remedies return the wrong point. They do not.

On every programme, with any number of extra rows, the basis crossover’s point is within $10^{-12}$ of $x^*$ by the third iterate, and on most by the first. That is the earlier essays’ finding in its purest form: at a vertex the point is fixed by any twenty independent rows through it, so any basis of guessed rows that are truly active gives exactly $x^*$, and the diagonal knows which rows are truly active almost at once. The regularised crossover’s point is correct to ten digits on 685 of the 709 iterates at which the guess holds every strongly active row, the difference being $\delta$ acting on the surplus rows; on the other twenty-four the guess also holds a row that is not active, which the least-squares fit cannot honour exactly. The method itself takes its usual sixteen or seventeen iterates and ends at about $10^{-13}$; degeneracy at a vertex does not slow it, unlike the weakly active rows of the active set before the digits, where the solution lay on a face and the method’s error fell only as the square root of μ.

And on every iterate where the basis crossover refuses after its point is exact, the refusal has the same form: the point is feasible for every row to rounding, and one of the multipliers the solve returned is negative — by between 1.07 and 3,278 over all the quadratic programmes with four or eight extra rows, and by 3.6 to 59 on the programme the next figure follows.

A negative multiplier would mean, at a nondegenerate solution, that the point is not optimal: relaxing that row would improve the objective, so the row should not be active. Here it means nothing of the kind. The optimality conditions ask for some nonnegative $z$ with $H x - f = C_A^{\mathsf T} z$ on the active rows $A$. At a nondegenerate vertex the active rows are exactly as many as the unknowns and independent, so there is one such $z$, and a solve returns it. At a degenerate vertex there are more active rows than unknowns, the equation has a whole family of solutions, and the nonnegative ones form a polytope inside it. A basis solve returns the one member of the family supported on that basis; the regularised solve returns roughly the smallest member in the least-squares sense. Neither has any reason to be in the polytope, and on these programmes they mostly are not.

Asking the question the conditions ask #

The repair is to certify the way the optimality conditions are stated. Given the crossover’s point, take every guessed row it makes tight — normalised slack under $10^{-9}$ — and ask whether any nonnegative combination of those rows equals $Hx - f$. That is a nonnegative least-squares problem with twenty equations and as many unknowns as there are tight rows: twenty-four here, solved by Lawson and Hanson’s active-set method in a few dozen small solves. If its residual is at rounding, the point satisfies every optimality condition with that $z$, and it is the solution. If not, it is not.

On the programme the figure shows, the residual is about $10^{-15}$ from the first iterate on, where the basis crossover’s own multipliers are wrong by units. Over all forty-eight runs — quadratic and linear, every count of extra rows — the set question certifies the point at the first iterate at which the point is exact and the diagonal has called every strongly active row active, sometimes sooner, and at every iterate after.

The dial shows the whole story in the cells. With no extra rows every row of cells fills from the first iterate; the four crossovers are the same computation. At two extra rows the guess holds twenty-two rows from the first iterate and the plain crossover’s row empties. At four, the basis and regularised rows empty too, though the digits row beneath them reads fifteen from the first iterate onward; only the last row, the same point certified by the set question, stays filled. At eight, the same. The method’s own digits climb one an iterate along the bottom row, and the crossover had all of them before the method had one.

Nothing about the set question depends on degeneracy. With no extra rows the nonnegative combination is unique and it is the multiplier vector the solve returns, so the set question and the plain certificate agree at every iterate; with extra rows it is the only one of the four that still says yes.

Why the diagonal calls the spare rows active #

The guess holds every degenerate row from the first few iterates on, and that is itself worth a measurement, because a row whose multiplier at the solution is zero was expected to look like the weakly active rows of the earlier essays — a diagonal entry that hovers within a decade or two of one and is never classified. It does not. On the programme the figures follow, at the eighth iterate the four degenerate rows’ slacks are between $2 \cdot 10^{-6}$ and $8 \cdot 10^{-6}$ and their multipliers between 0.2 and 0.8, so their diagonal entries are $3 \cdot 10^{4}$ to $5 \cdot 10^{5}$, inside the range of the strongly active rows’ $3 \cdot 10^{4}$ to $3 \cdot 10^{6}$. At the last iterate both groups sit between $10^{12}$ and $10^{14}$; over every programme, the spare rows’ smallest diagonal entry at the end is within three decades of the strong rows’ smallest, and their smallest multiplier is above 0.006. The inactive rows’ entries are at $10^{-14}$.

The multipliers of the degenerate rows do not go to zero, though the multiplier vector the programme was built with has zeros there. That is a known property of path-following methods rather than an accident of these programmes: the method’s iterates converge to the centre of the solution set, and at a degenerate vertex the solution set of the multipliers is the polytope described above, whose centre has every entry strictly positive. So the method has been carrying a nonnegative member of the multiplier set all along — strictly positive on all twenty-four rows — and the diagonal calls the spare rows active because, in the method’s own accounting, they are carrying force. A multiplier is a force read a multiplier as the force a constraint exerts to hold the solution; at a degenerate vertex the force can be shared among more rows than are needed, and the method shares it evenly.

That is also why the set question’s answer is never in doubt once the point is exact. The polytope it asks about is not merely nonempty; it has an interior, and the method’s own multipliers are near its centre. What the basis and the regularised solves return are its edges or points outside it, and a certificate that inspects one of those is inspecting the least representative member of the set.

What the certificate was for #

The shares put a number on how far the two remedies are from usable. Counting only iterates at which the point is already exact — so that any refusal is a refusal of the right answer — the plain crossover certifies 98 per cent of them with no extra rows and none at four or eight; the basis 74 per cent at two extra rows, 18 per cent at four and 11 at eight; the regularised crossover 5, 3 and 1 per cent. The set question certifies 97 to 100 per cent at every count, the remainder being the iterates at which the diagonal has not yet called one of the strongly active rows active.

That last qualification is the honest limit of the set question, and it is not a limit of degeneracy. A crossover reads the active set off the diagonal; if the diagonal has not yet placed a row whose multiplier is needed, no certificate built on that guess can pass, and none should. On four programmes the set question certifies one to three iterates before the diagonal has settled on every strongly active row, because the degenerate rows’ own nonnegative combinations happen to reach the missing row’s direction — a legitimate certificate, since the conditions ask only that some nonnegative combination exists, and degenerate rows are entitled to carry multipliers.

The certificate is also as strict as before. Moved by a millionth in alternating directions, the same point loses its tight rows and is refused; with one strongly active row deleted from the guess, the nonnegative combinations no longer reach $Hx - f$ and it is refused. A test that certifies everything would have passed both. A shift that certifies a saddle and a test with no tolerance in it both rest on certificates whose value is that they can say no, and this one still can.

The objective said nothing #

Every number above is the same for the linear programmes as for the quadratic ones, to within an iterate — the first certifying iterate of the set question differs by at most one on all twenty-four pairs. At a vertex that is not surprising once it is said: twenty independent active rows determine the point, the Hessian enters only through $Hx - f$, which the multipliers absorb, and the diagonal’s identification of the active rows is driven by the slacks going to zero, which is geometry. So the question the earlier essay posed — whether any of this is usable on a linear programme — has the answer that a linear programme at a vertex is the case where it is cleanest, provided the certificate asks for a nonnegative member of the multiplier set rather than for the member a solve returns.

The simplex method meets the same fact as degenerate pivoting. At a degenerate vertex it can hold a basis that is primal feasible with a negative reduced cost, pivot to another basis on the same vertex, and repeat — moving among bases without moving the point, sometimes forever without an anti-cycling rule. That is exactly what the basis crossover’s refusals are: bases on the right vertex, with the wrong multipliers. The simplex method’s way out is to keep pivoting; the crossover’s is to stop asking any single basis for its multipliers. Two ways to remove a constraint and the zero that is not a missing entry are about the same saddle matrix with one multiplier per row, and this is the case where that one-to-one picture fails and the matrix’s solution is no longer the conditions’ only solution.

What forty-eight runs do not show #

The extra rows here pass exactly through the vertex, in exact construction, so their slacks go to zero with the others. On a real degenerate programme the extra rows pass through the vertex only to the data’s rounding, and the tightness threshold of $10^{-9}$ decides which of them count; a row whose slack sits at $10^{-8}$ would be left out, and if its multiplier were needed the certificate would refuse a correct point. That threshold has not been varied. Nonnegative least squares on twenty-four columns is cheap; on a programme with thousands of degenerate rows it is a quadratic programme of its own, and its cost against a crossover’s single solve is not measured. And the random rows here are well conditioned; the near-dependence among degenerate rows that makes real linear programmes hard is absent.

Still open: rows near the vertex, the cost at scale, and a basis chosen by the set #

Rows that only nearly pass through. 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.

What the set question costs. Lawson–Hanson’s iterations grow with the number of tight rows. The prediction is that on programmes of a hundred unknowns with fifty extra rows, the set question costs less than one interior-point step — a square solve of three hundred rows — at every iterate, so that trying it at every iterate still adds less than the fraction the earlier essay priced.

A basis from the set. The nonnegative least-squares solution is supported on at most twenty of the tight rows; those rows form a basis on which the solve’s own multipliers are nonnegative. The prediction is that taking that support as the basis makes the basis crossover certify at the same iterates as the set question, which would turn the certificate into the pivot rule a degenerate simplex step lacks.