Numerical Linear Algebra
where the algebra stops being the arithmetic
Concept

Trust-region — where it appears

A ball of radius Δ around the current point, inside which a quadratic model of an objective is taken to be reliable. The trust-region subproblem minimises the model over that ball, and its answer is the step; the radius is adjusted afterwards from how well the model predicted the decrease it promised.

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

012345678-7-5-3-11357conjugate gradient steppᵀAp ⁄ pᵀpλ_min = -0.1positive: a step existsnegative: a certificate existsone matrix, two questionsstep it turns at6quotient there-0.027share of λ_min recovered0.27λ_min, by construction-0.1MINRES steps on the same system37the division that cannot be doneis the answer to a different question

The division that cannot be done

Conjugate gradients divides by pᵀAp at every step, and on a matrix that is not positive definite that number can be zero or negative. This site has guarded against it since its first commit and described it as a failure. In the method that made conjugate gradients famous it is the single most valuable object the iteration can produce, and it costs six matrix–vector products.

iterative · Breakdown 110¹00.30.60.91.2trust-region radius Δshare of the exact model decreasethe exact subproblem7 radii, n = 60share at the smallest radius0.95share at the largest0.3products, at most8radii stopped by the curvature4a few products against an eigendecompositionand most of the decrease

The certificate that arrives soonest is worth least

The more negative a Hessian's smallest eigenvalue, the sooner conjugate gradients meets a direction of negative curvature — and the less of the exact trust-region decrease that direction turns out to be worth. At λ_min = −10 the step arrives after two products and gets 39.6 per cent; at −10⁻³ the same two products get 89.8, and the whole sweep costs eight.

iterative · Trust-region

Named alongside it

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

CertificateConjugate gradientsEigenvaluesIndefinite matrixKrylov subspaceNegative curvatureBisectionCholeskyJacobi's eigenvalue methodMatrix-freeMINRESQuadratic form

All concepts