A multiplier is a force

Feasible and wrong added a third equality constraint to a least-squares fit, the first constraint plus ε times an independent direction, and let ε fall from 1 to 10⁻¹². The constraint block’s condition number rose from 8.19 to 4.64·10¹², the null-space route’s error rose with it to 1.16·10⁻⁴, and every answer satisfied every constraint to 10⁻¹⁵. It ended on the one output of those solves nobody had read. The saddle-point route produces the Lagrange multipliers along with the answer, and a nearly parallel pair of constraint rows ought to make them large: they solve

$$B^{\mathsf T}\lambda = A^{\mathsf T}(b - Ax),$$

and $B^{\mathsf T}$ is nearly rank-deficient. The question was whether $\lVert\lambda\rVert$ rises in proportion to κ(B) and so carries the same information as the diagonal of B’s triangular factor at a higher price, or whether — because it depends on the constraint data $d$ as well as on $B$ — it says something the conditioning cannot.

Both, and the second half turns out to be the interesting one for a reason nobody asked about.

Proportional on the construction that was measured #

The multipliers here are exact: the optimality conditions are solved in rational arithmetic from the stored doubles of $A$, $b$, $B$ and $d$, with $A^{\mathsf T}A$ accumulated exactly, so nothing is rounded between the data and the reference.

On the earlier construction the answer to the first question is yes, and precisely. From ε = 10⁻² onwards $\lVert\lambda\rVert$ is 0.0081 times κ(B) at every point, reaching 3.8·10¹⁰ at the end. The three multipliers are worth looking at individually: at ε = 10⁻¹² they are −2.66·10¹⁰, 0.0134 and +2.66·10¹⁰. The second constraint’s multiplier has not moved from where it was at ε = 1. The first and third are equal and opposite and enormous — two constraints pulling against each other along nearly the same row, with forces that nearly cancel, and whose small difference is the only force either of them exerts on the fit.

That picture is the whole answer to what a multiplier is measuring, and the second family says so.

A near repeat that asks for nothing #

The third constraint’s datum in the earlier construction was $d_3 = d_1 + \varepsilon\,d_v$, with $d_v$ a random number. Subtract the first constraint from the third and divide by ε, and what the pair says is

$$v^{\mathsf T}x = d_v :$$

an ordinary, well-conditioned constraint on a new direction, written at scale ε. However small ε is, it asks for exactly as much as it did at ε = 1. The second family asks for nothing: $d_3$ is set to $B_3 x_2$, where $x_2$ is the exact answer of the problem with only the first two constraints, so the third is implied by the other two and changes nothing — in exact arithmetic. Stored as a double, $d_3$ is rounded, and the rounding is a demand of its own of about $10^{-16}$.

At κ(B) = 4.64·10¹², the same B in both, the multipliers of the consistent family are 2.0·10⁶ against 3.8·10¹⁰: eighteen thousand times smaller. Below κ(B) of about 10⁶ they are 0.0040 whatever ε is, the size they would have without the third constraint at all, and its own multiplier is −4.8·10⁻¹⁸. Only past 10⁶ does the rounding of $d_3$, multiplied by the lever the next section measures, lift them — to 0.040 at κ(B) = 4.6·10⁸, 440 at 4.6·10¹⁰ and 2.0·10⁶ at the end.

So the multipliers see the right-hand side, which the conditioning never looks at. That was the prediction, and it holds.

How far the answer moves #

The earlier essay described the near repeat as harmless in principle: “the feasible set is the same set, and the answer is the same answer; a repeated equation constrains nothing new.” On its own construction that sentence was not true, and the exact answers show it before any solver is involved.

With $d_3 = d_1 + \varepsilon\,d_v$, the exact answer is 0.886 of its own size away from the two-constraint answer — at ε = 1 and at ε = 10⁻¹² alike. The third constraint was never a near repeat of the first in what it did, only in how it was written. The error measurements the earlier essay made are right, and its reading of them stands: the arithmetic costs κ(B)·u and feasibility cannot see it. What needs correcting is the premise that the problem being solved was the two-constraint problem in disguise. It was a different problem at every ε, whose difference from the original happened to be expressed through a row of size ε.

The consistent family’s exact answer does not move in exact arithmetic, and as stored it moves by 9.9·10⁻⁹ at κ(B) = 4.6·10⁸, 1.0·10⁻⁶ at 4.6·10¹⁰ and 4.8·10⁻⁵ at the end. That is the rounding of $d_3$ amplified by $1/\varepsilon$, and it sits right beside κ(B)·u and beside the null-space route’s own error of 2.1·10⁻⁵. The problem a machine holds has already lost the digits the solver is blamed for.

A price, before it is a force #

There is an older reading of a multiplier than the mechanical one, and it can be checked directly. The multiplier of constraint $k$ is the rate at which the fit’s best achievable misfit changes as the constraint’s datum is moved:

$$\frac{\partial}{\partial d_k}\,\tfrac12\lVert Ax^\star - b\rVert^2 = -\lambda_k,$$

with the sign set by the convention in the optimality conditions above. Moving $d_3$ by $10^{-8}$ on the earlier construction at ε = 10⁻⁴ and re-solving exactly changes the minimum misfit by −265.72 times the move; the third multiplier is 265.73. At ε = 10⁻² the two agree to five figures at 2.657. So a multiplier of 2.66·10¹⁰ says that the last digit of $d_3$ — a change of about $10^{-16}$ — is worth a change of about $10^{-6}$ in the squared misfit of the whole fit.

That is the same statement as the lever, made in the fit’s own currency. It also says why the multipliers are a property of the data rather than of the arithmetic: they are derivatives of the exact problem’s optimum, defined before any solver is chosen, and they would be the same numbers if the solve were done in a thousand digits.

A force on a lever of length ε #

To separate what the multipliers measure from κ(B), fix ε and vary the demand. Set $d_3 = B_3 x_2 + \delta$, so the third constraint asks for exactly δ more than the others imply, and move δ from 10⁻¹⁴ to 10⁻².

At ε = 10⁻⁸, where κ(B) is 4.64·10⁸ at every point, the multipliers run from 1.4 at δ = 10⁻¹⁴ to 1.3·10¹² at δ = 10⁻², and the exact answer moves from 3.2·10⁻⁷ of its size to 3.1·10⁵ of it. Both rise in proportion to δ over ten decades. Turn the dial to ε = 10⁻¹² and the lines rise by four and eight decades respectively; turn it to 10⁻⁴ and they fall.

Every strained problem at every ε lies on one line: $\lVert\lambda\rVert$ is between 0.01329 and 0.01348 times $\delta/\varepsilon^2$, eleven problems over twenty-two decades. The displacement is $3.14\,\delta/\varepsilon$ in the same way. The mechanics are those of a lever. The demand δ is made through a row of size ε, so meeting it moves the answer by δ/ε along the direction the other constraints leave free; the fit resists that displacement, and the constraints must hold the answer there with a force proportional to it, applied through the same row of size ε — another factor of $1/\varepsilon$. κ(B) grows as $1/\varepsilon$ and so supplies one of those factors. The other two parts, the demand and the second lever, are properties of the data.

Read in that light, the earlier construction’s proportionality is no longer mysterious. Its demand was $\delta = \varepsilon\,(d_v - v^{\mathsf T}x_2)$, itself proportional to ε, so $\delta/\varepsilon^2$ was proportional to $1/\varepsilon$ and to κ(B). The multipliers were never measuring the conditioning. They were measuring a demand that happened to shrink at the same rate the lever grew.

What the error of the best route follows, which is not the multipliers #

This is where the prediction’s natural sequel fails. If large multipliers mean a pair of constraints straining against each other, the obvious use is as a warning: a solve with a multiplier of 10¹⁰ should be less trustworthy than one with a multiplier of 10⁻², and a code that can report the second should report it.

The null-space route does not care. At κ(B) = 4.64·10¹² it is wrong by 1.16·10⁻⁴ when the third constraint asks for a new condition and by 2.1·10⁻⁵ when it asks for nothing: a factor of five and a half, for multipliers eighteen thousand times apart. In the strain sweep it is flatter still. At ε = 10⁻⁸ its error stays between 7.8·10⁻⁹ and 1.8·10⁻⁸ while δ runs over twelve decades and the answer moves from a part in 10⁷ of itself to three hundred thousand times itself; at ε = 10⁻¹² it stays between 1.1·10⁻⁵ and 2.1·10⁻⁵. Relative to the answer’s size, the route loses about a tenth of κ(B)·u, and the demand has nothing to do with it.

That fits what the condition number that does not know found about this route from the other side: its error is decided by the conditioning of the pieces it actually solves — B’s triangular factor, and A restricted to B’s null space — and the right-hand side enters only as the thing being solved for. A backward-stable method’s relative error is set by the condition number of the problem it is given, and the multipliers do not appear in that condition number for the route that never forms them.

The saddle-point route is different, and in the direction the warning would want. It was already the worse route for a reason of its own — the reference was a method found that forming $A^{\mathsf T}A$ inside its block loses most of what it loses before any elimination begins — and the multipliers add a second. Its error on the consistent family tracks κ(B)·u, 3.3·10⁻⁵ at the end, like the null-space route’s; on the earlier construction it is 8.2·10⁻³. In the strain sweep at ε = 10⁻⁸ it rises from 6.3·10⁻⁹ at the smallest strain to 1.1·10⁻⁴ at δ = 10⁻⁸ and 4.6·10⁻⁴ beyond. The reason is argued rather than isolated here: the saddle-point route solves for $x$ and λ together, as one vector, and a backward-stable elimination commits an error proportional to that vector’s norm, on the indefinite matrix whose eigenvalues the zero that is not a missing entry bracketed in closed form — which, when the multipliers are 10¹², is the multipliers’. An error of a part in $10^{16}$ of 10¹² is not small next to an answer of size one.

So a large multiplier warns about exactly one thing: the route that computed it. A code that solves the saddle-point system and reports a multiplier of 10¹² is reporting, among other things, that its own $x$ is less reliable than a null-space solve of the same problem would have been.

The multipliers of a constraint that asks nothing are not computed at all #

A multiplier made of rounding is not a quantity any route can return, and the reason is a small loop.

Recovered from the null-space answer by a QR factor of $B^{\mathsf T}$, the multipliers of the earlier construction are right to 7.2·10⁻⁵ at the end — about a seventh of κ(B)·u, which is as well as the route computes $x$. The consistent family’s are right to 2.3·10⁻⁸ at ε = 10⁻⁴, to 8·10⁻⁴ at ε = 10⁻⁶, and wrong in every digit from ε = 10⁻⁸: 0.84 there and 0.44 at the end. What they are supposed to measure is the rounding of $d_3$, which moved the exact answer by 9.9·10⁻⁹ at ε = 10⁻⁸; the answer they are computed from is wrong by 7.8·10⁻⁹, the same size. A multiplier computed from a residual is only as good as the residual, and when the whole of the force is the rounding of one datum, the residual cannot resolve it.

That is the reverse of the usual worry about a large number. The large multipliers here are the well-computed ones, because they measure something large; the small ones on an ill-conditioned block are noise that happens to have a size.

Five digits of agreement, revisited #

The earlier essay gave a concrete case for its construction: “a calibration constraint and a physical one can agree to five digits and differ in the sixth, which is ε = 10⁻⁵ in the sweep above and an error of 10⁻¹¹ in the answer — invisible, and present.” The error figure is right for the solver. The lever law says it is the smaller of two effects.

Two constraints whose rows agree to five digits have ε = 10⁻⁵. If their data also differ in the sixth digit, the demand is δ ≈ 10⁻⁶, and the displacement law puts the exact answer $3.14\,\delta/\varepsilon$, about a third of its own size, away from where either constraint alone would put it — a constant that belongs to this fit, but a size that belongs to the geometry. The solver then adds its κ(B)·u of about 10⁻¹¹ on top of an answer that has already moved thirty per cent on account of a disagreement in the sixth digit of a datum. Nothing about that is a rounding error, and nothing in the solve can see it: the answer is exactly feasible, its residual is small, and every condition number is reported correctly.

The only number the solve produces that registers it is the multiplier. On that problem it would be about $0.0133\,\delta/\varepsilon^2 = 130$, against about 0.004 for the same pair agreeing in their data as well. A factor of thirty thousand, on two problems whose matrices are identical.

What to compute, and what to delete #

The multipliers are a statement about the data, not about the arithmetic, and read that way they are useful.

A multiplier that is large compared with its neighbours, on a nearly dependent pair of constraints, says the pair disagrees — that the constraint data ask for a condition the rows barely express, and the answer is where it is because of that disagreement. On the earlier construction the answer moved by 0.886 of itself on account of it. The right response is not numerical: the pair should be rewritten as the constraint it is, $v^{\mathsf T}x = d_v$, with a row of size one. That is the same problem, well conditioned.

A multiplier that is ordinary on a nearly dependent pair says the pair is redundant, and the right response is to delete one — the elimination of a constraint that two ways to remove a constraint set out for a constraint that is wanted, applied to one that is not. The consistent family makes the case with a single number. Solved with the third constraint, the answer to the intended problem is wrong by 6.9·10⁻⁵ at ε = 10⁻¹², because the stored problem has moved and the solver has lost κ(B)·u on top. Solved without it, the answer is wrong by 5.5·10⁻¹⁵. Ten digits bought by removing an equation that said nothing.

And a caller who has no multipliers — a null-space code does not produce them — can make the same decision a cheaper way, by solving without the suspect constraint and substituting the answer into it. On the consistent family the dropped constraint is satisfied exactly by that answer; on the earlier construction it misses by 2.8·10⁻¹², which is $\varepsilon$ times the misfit of the condition it was hiding. The residual of the dropped constraint, not its multiplier, is the quantity a null-space route can afford to look at.

Neither reading helps with the error of the solve itself. For the null-space route that remains κ(B)·u, decided by B and indifferent to d, and a constraint is a weight at infinity and its successors have already said what to do about it: choose the route, and condition the block.

What this does not settle #

One fit, well conditioned at κ(A) = 100, with two random constraints and a third near the first in one fixed direction. A near repeat in a direction A cares about more, or two near repeats at once, is not measured, and the constants 0.0133 and 3.14 in the lever law are this problem’s. That the law is $\delta/\varepsilon^2$ and $\delta/\varepsilon$ is argued from the geometry and confirmed across eleven problems; the constants are not predicted.

The saddle-point route’s dependence on the multipliers is measured and explained by an argument about the norm of the combined vector, not isolated. Whether scaling the multiplier block — solving for $\varepsilon\lambda$ instead of λ — removes it is the obvious test and has not been made.

Still open: the scaled saddle point, and a multiplier that decides a rank #

A saddle-point system in balanced units. If the saddle-point route’s extra loss comes from the multipliers dominating the combined vector, then scaling the constraint rows so that the multipliers come out of ordinary size should remove it — at the price of making $B$ itself badly scaled, which is the trade the units the matrix is measured in priced for a single system. Whether the two effects cancel, or whether the null-space route remains strictly better, is one sweep.

A multiplier as a rank decision. Deleting a redundant constraint is a rank decision on $B$ made with the data in view, the kind of decision the rank depends on the ring showed is never a property of the array of numbers alone. A rule that deletes the constraint whose dropped residual is at the rounding level of its datum would make that decision without a threshold on κ(B) — the continuum the earlier essay said a rank check had nothing to cut. Whether such a rule misfires on a constraint whose demand is genuinely small but real, and how small a demand it can tell from none, is the measurement that would turn the last section into a method.