Numerical Linear Algebra
where the algebra stops being the arithmetic
Series

Interior-point conditioning — the series

4 essays on one idea, from the one that introduces it to the one that assumes the rest.
  1. -14-12-10-8-6-4-2010⁻¹⁷10⁻¹³10⁻⁹10⁻⁵10⁻¹10³10⁷10¹¹10¹⁵log₁₀ μ — the barrier parametercondition number, and relative errorκ₂, condensedκ₂, augmentederror, condensederror, augmentedagainst a BigInt answerκ₂ augmented, μ = 10⁻¹⁴3·10¹⁵its relative error10⁻¹⁵κ₂ condensed2.4·10¹⁶its relative error0.31the same step, written two waysand only one of them is solvable

    A condition number sent to infinity

    An interior-point method manufactures an ill-conditioned matrix on every iteration, deliberately, because the separating of a diagonal is how it discovers which constraints are active. Written one way the answer keeps fifteen digits at a condition number of 3·10¹⁵. Written the other way — the way almost every code writes it — it has none left.

    part 1 · constraint
  2. 0246810121410⁻¹⁶10⁻¹³10⁻¹⁰10⁻⁷10⁻⁴10⁻¹interior-point iterationrelative error, and μcertified from iterate 1μthe iterate's errorthe crossover's errorone solve, checkediterations15first certified iterate1iterate error there0.22crossover error there4·10⁻¹⁴the active set arrives long before the digitsand a crossover collects them at once

    The active set before the digits

    An interior-point method takes fifteen iterations on a quadratic programme with forty constraints, and its iterate has eight correct digits at the eleventh. Take the constraints its diagonal calls active at the first iterate, solve the equality problem they define once, and check the answer against the conditions for optimality. It passes, to thirteen digits. The step's matrix had a condition number of 43 at that iterate, and 7·10¹⁵ at the last.

    part 2 · constraint
  3. the damagewell scaled, nothing done0.9110^±3, nothing done0.095never certified, of 62at 10^±3rows to unit norm0.64rows by right-hand side0.6start at the rows0.43012300.250.50.751rows rescaled by 10ᵏshare that certifiesnothing donestart at the rowsrows to unit normrows by their right-hand sidethe grey line is a well-scaled programme with nothing doneboth equilibrations are flat, and below it

    Two repairs for one symptom

    Rescale a quadratic programme's constraint rows over six decades and the crossover that certified its answer at iterate 1.5 first certifies at 69.8, with two of six programmes never certifying at all. Normalising the rows removes the spread completely — the same numbers at 10¹, 10² and 10³ either way. Starting the method at the magnitudes the rows imply repairs the iteration count completely and the identification only halfway. They are two repairs and they fix different halves.

    part 3 · constraint
  4. the certificatecertificate, iterate1.5its error1.8·10⁻¹⁴the iterate's own error0.14the tightest μ testμ < 10⁻¹³, iterate15its error1.6·10⁻¹²one attempt ÷ one step0.130246810121410⁻¹⁶10⁻¹³10⁻¹⁰10⁻⁷10⁻⁴10⁻¹interior-point iterationrelative error returnedμ < 10⁻⁴μ < 10⁻⁶μ < 10⁻⁸μ < 10⁻¹⁰μ < 10⁻¹³the certificatethe iterate it is built fromthe grey line is the certificate's own errorno tolerance on μ reaches it, at any iterate

    A test with no tolerance in it

    An interior-point method's own stopping test is a tolerance on μ, and at the tightest it can be set to it stops after 15 iterations with 1.6·10⁻¹². A crossover from the iterate at 1.5 returns a point whose error is 1.8·10⁻¹⁴ — ten times sooner and a hundred times better, from an iterate carrying one correct digit. One attempt costs an eighth of a step, and the guess's own margin says which iterate to spend it on.

    part 4 · constraint

All series