Numerical Linear Algebra
where the algebra stops being the arithmetic
Concept

Lagrange multiplier — where it appears

The number attached to each equality constraint at the optimum of a constrained minimisation, solving Bᵀλ = Aᵀ(b − Ax) for a least-squares fit. It is the rate at which the best achievable objective changes as that constraint's datum moves, which makes it a price on the constraint rather than a property of the arithmetic.

Named by 6 essays across 2 fields — each of them below, with the objects they name alongside it.

-1-0.582271-0.1645420.2531860.6709151.088641.506370eigenvalue4 negative10 positivecounted before it was formedpositive10negative4at zero0innermost ratio39the zero block is a theoremand so is the count either side of it

The zero that is not a missing entry

A constrained minimisation produces a matrix with a zero block, and the zero is a theorem rather than a sparsity pattern. No pivot order makes it positive definite, no precision changes that, and Cholesky does not fail somewhere on it — it fails at the first constraint row, on a number the problem already contained.

constraint · Saddle-point systems same κ(B), two right-hand sides‖λ‖ ÷ κ(B), asking0.0081‖λ‖ at κ(B) = 10⁶·⁷, consistent0.00410¹10³10⁵10⁷10⁹10¹¹10¹³10⁻³10⁻¹10¹10³10⁵10⁷10⁹10¹¹κ(B), the conditioning of the constraint block‖λ‖, the multipliers' sizethird constraint asksasks nothing∝ κ(B)the same B at every point, two values of d₃the multipliers read the right-hand side

A multiplier is a force

A third constraint nearly parallel to the first made the multipliers of a constrained fit rise in exact proportion to κ(B), which looked like the conditioning measured a second, dearer way. It was not. Give the third constraint a datum that asks for nothing new and, at the same κ(B) = 4.6·10¹², the multipliers are eighteen thousand times smaller; give it a strain δ and they are 0.0133 δ/ε², a force on a lever of length ε. What they measure is what the constraint asks. What they do not measure is the error of the best route, which sits at the same level whether the constraint asks for nothing or for a displacement of 3·10⁹.

leastsquares · Constrained least squares error at the largest strainas given4.6·10⁻⁴multipliers to the size of x3.3·10⁻⁸first-solve scale, never below one1.8·10⁻⁸null-space route1.8·10⁻⁸10⁻¹⁰10⁻⁹10⁻⁸10⁻⁷10⁻⁶10⁻⁵10⁻⁴10⁻³strain δ (left: none)relative error in x10⁻¹⁴10⁻¹¹10⁻⁸10⁻⁵10⁻²noneas givenmultipliers to the size of xfirst-solve scale, never below onenull-space routethe loss was the multipliers' sizeand it scales away

The scale that only moved a pivot

Multiply the constraint rows of a saddle-point system until its multipliers are the size of its solution, and the extra error the route was blamed for — 4.6·10⁻⁴ against the null-space route's 1.8·10⁻⁸ — falls to 3.3·10⁻⁸. The prediction holds and its reason does not. A scale of ten does what a scale of 6·10⁵ does; hold the elimination's row order fixed and nine decades of scale move the error by less than a factor of five. What the scale changed was which row partial pivoting took at the second step, and taking the constraint rows first does the same job with no scale at all.

leastsquares · Constrained least squares predicted against measuredproblems49worst relative difference4.4·10⁻¹⁶1.522.533.5coupling, from one to ten to the minus twelveswitching scale11e-21e-41e-61e-81e-101e-12repeatedconsistentstrainedrings: predictedevery dot inside its ringone elimination tells the switch

The switch is read before the solve

Scaling the constraint rows of a saddle-point system rescued the route to a constrained least-squares fit by changing which row partial pivoting takes at the second step. The scale at which it changes can be read before anything is solved: scaling multiplies every constraint row's candidate by s and leaves every other row's alone, so one unscaled elimination, recording the two kinds of candidate at each step, gives the switch exactly — on all forty-nine problems, to within one part in 10¹⁵ of what bisection finds, decided at the second step everywhere but at a coupling of one. A scale just past it removes the catastrophe where there was one. It does not make the route as good as eliminating the constraints first: on four problems every scale tried is thirty to thirty-nine times worse, and they are the problems where the unscaled route was too.

leastsquares · Constrained least squares 0246810121416neverno extra rowsthe guess as it standsa basis chosen by z/sregularised, δ = 10⁻¹⁰basis point, any multipliers2 extra rowsthe guess as it stands3 of 6a basis chosen by z/sregularised, δ = 10⁻¹⁰4 of 6basis point, any multipliers4 extra rowsthe guess as it stands6 of 6a basis chosen by z/s4 of 6regularised, δ = 10⁻¹⁰4 of 6basis point, any multipliers8 extra rowsthe guess as it stands6 of 6a basis chosen by z/s5 of 6regularised, δ = 10⁻¹⁰5 of 6basis point, any multipliersfirst iterate whose crossover certifiessix programmes a row; QP shown, LP the samethe multipliers are a set

The multipliers were a set

A crossover that solves the equality problem an interior-point iterate's diagonal suggests, then certifies the answer, refuses a guess with more active rows than unknowns — which a degenerate vertex produces as a matter of course. The two remedies a simplex code and a regularised solver would reach for, choosing a basis or regularising the extra rows, both return the right point from the first or second iterate, and both fail the certificate on most programmes, at almost every iterate. The point is never what fails. The certificate checks the one multiplier vector a solve happens to return, and at a degenerate vertex the multipliers are a set; asking whether the set holds a nonnegative vector certifies the same point at once.

constraint · Interior-point conditioning 0246810121416182022slack exactly zerothe guess as it stands××××××a basis by the diagonal×××××regularised××××××the set questionslack 10⁻⁶the guess as it standsa basis by the diagonalregularisedthe set questionslack 10⁻⁸the guess as it stands××××××a basis by the diagonalregularised××××××the set questionslack 10⁻¹⁰the guess as it stands××××××a basis by the diagonalregularised××××××the set questionslack 10⁻¹²the guess as it stands××××××a basis by the diagonalregularised××××××the set questionslack 10⁻¹⁴the guess as it stands××××××a basis by the diagonal×××××regularised××××××the set questioniterate from which every later iterate certifies× at the right: never settles in the runlate where the rows are near, not on

The row that was nearly there

Move the spare rows of a degenerate vertex off it by 10⁻⁶ to 10⁻¹⁴ and the set question still certifies the last iterate of every run, as predicted. It no longer certifies early. Between 10⁻⁶ and 10⁻¹⁰ it waits nine to seventeen iterates, because the basis it certifies holds a near row at zero and its point sits three to forty-eight times that row's slack outside the feasible set. At 10⁻¹² the same displacement falls under the certificate's tolerance and the set certifies from the first iterate. The basis turns when μ passes a tenth of the slack, while the diagonal still calls every near row active.

constraint · Interior-point conditioning

Named alongside it

The objects these essays reach for when they reach for this one.

Saddle-point systemsEquality-constrained least squaresExact ground truthForward errorActive setCertificateCondition numberDegeneracyElimination orderInterior-point methodNull space methodPartial pivoting

All concepts