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 2 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

Named alongside it

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

Condition numberExact ground truthSaddle-point systemsCholeskyConstrained minimisationEquality constrained least-squaresIndefinite matrixInertiaNull-space methodSchur complementSensitivitySymmetric indefinite

All concepts