Expand description
§Chapter 5.14 — KKT systems: analyze once, factorize many
New with task L1.5 (PLAN.md trilha L; the contract’s §5.7).
§Purpose
At every iteration a primal-dual interior-point method solves a linear
system whose matrix has a fixed pattern and changing values: the
normal equations A D Aᵀ or the augmented (KKT) system
[−D, Aᵀ; A, 0], where the diagonal D > 0 spreads over many orders
of magnitude as the iterates approach the boundary (Wright 1997, ch.
11). The interface below is the shape of CHOLMOD (Chen, Davis, Hager &
Rajamanickam 2008): a symbolic phase that depends on the pattern only
(ordering, elimination tree, structure of the factor) is done once, a
numeric phase is repeated for every new set of values, and a solve
phase uses the factor. On top of it sit two things that every backend
shares and that therefore live here, not in a backend:
- the regularization policy (Altman & Gondzio 1999): which static
shifts
ρ,δenter which diagonal block, which sign each pivot must have, which pivots a backend may bump, and the inertia check (S6); - iterative refinement against the matrix the caller really wants
solved (
KktSolver::solve_refined, a provided method), which keeps its best iterate (S7).
§Notation
K ∈ R^{N×N} symmetric, given by its lower triangle in a
CscMatrix (entries i ≥ j; CHOLMOD’s stype < 0). A matrix that
stores both triangles is accepted when its pattern is symmetric: the
entries above the diagonal are then ignored. Two forms (KktForm):
NormalEquations:K = A D Aᵀ(N = m), positive (semi)definite;Augmented { n_primal: n, n_dual: m }:K = [−D, Aᵀ; A, 0](N = n + m), thenprimal unknowns first.
A Regularization (ρ, δ, τ, β, scale) = (primal, dual,
pivot_tol, bump, scale) defines the matrix the backend
factorizes. With S = diag(s) the symmetric equilibration of K
(step K2′ below; powers of two) and Σ = diag(−ρ I_n, δ I_m) for the
augmented system (Σ = δ I_m for the normal equations),
K_reg = K + S⁻¹ Σ S⁻¹ (ShiftScale::Equilibrated, the default),
K_reg = K + Σ (ShiftScale::Absolute),so the default shifts are taken in the equilibrated matrix
K̃ = S K S, whose rows have their largest entry near 1: δ = 10⁻⁸ is
then relative to the magnitude of each row, whatever the spread of
D. The pivot signs are σ_k = −1 for the primal rows, +1 for the
dual rows (all +1 for the normal equations). The inertia of a symmetric
matrix is the triple (Inertia) of the numbers of positive, negative
and zero eigenvalues; by Sylvester’s law it equals the count of
positive, negative and zero pivots of any P K Pᵀ = L Δ Lᵀ with Δ
diagonal, and, for Δ block diagonal with 1×1 and 2×2 blocks,
the sum of the inertias of the blocks. The relative residual of x
is res(x) = ‖K x − b‖_∞ / (1 + ‖b‖_∞).
§Why the regularized augmented system needs no pivoting
With D > 0, ρ > 0 and δ > 0, K_reg is quasi-definite: its
(1,1) block is negative definite and its (2,2) block positive
definite. Vanderbei (1995) proved that every symmetric permutation of a
quasi-definite matrix has an LDLᵀ factorization with diagonal Δ,
the first block’s pivots negative and the second’s positive; Gill,
Saunders & Shinnerl (1996) bound its stability by the size of the
regularization. So the ordering can be chosen for sparsity alone, at
analysis time — the property that makes “analyze once” possible for the
augmented system — and the inertia is known in advance: (m, n, 0).
Without regularization (ρ = 0 or δ = 0) this guarantee is lost, and
a backend needs 2×2 pivots (Bunch & Kaufman 1977) or dynamic
regularization to factorize.
On the sign convention. The contract’s (S6) writes the expected
inertia of the augmented system as (n, m, 0) for the matrix
[−D − ρI, Aᵀ; A, δI]; for that matrix the n primal pivots are
negative and the m dual pivots positive, so with the field order
(positive, negative, zero) of Inertia the triple is
{ positive: m, negative: n, zero: 0 } — which is what this chapter
checks (n primal and m dual eigenvalues, each block with its own
sign; listed for ratification in L1.5).
§Algorithm K (the regularization policy shared by every backend)
K1. [Validate.] K satisfies (S1); it is square, of order N equal to
the form’s (n + m for the augmented system); its lower triangle
lies inside the pattern given to the analysis (missing entries are
zeros: an IPM value that became exactly zero leaves the CSC
pattern, (C3) of Chapter 5.8).
K1′. [Finite input.] Every stored value of the lower triangle of K
is finite (KktError::Structure otherwise): a NaN or an infinity
in K would otherwise surface as a NaN solution.
K2. [Assemble.] The lower triangle of K on the analyzed pattern, which
has a full diagonal (a dual diagonal entry absent from K is 0).
K2′. [Symmetric equilibration (Ruiz 2001).] Scale K to
K̃ = S K S, S = diag(s) with powers of two: start from
s = 1; in each pass compute, for every row i of the scaled
matrix (both triangles), r_i = max_j |k̃_ij| and multiply s_i by
⌊1/√r_i⌉₂ (rows without entries keep s_i); stop after a pass
that changes no s_i — exact, the factors being powers of two — or
after EQUILIBRATION_PASSES passes. Every row of K̃ then has
its largest entry in [2^{-1}, 2^{1}] roughly, whatever the spread
of D. The scaling is a congruence, so the inertia of K̃ is that
of K (Sylvester). Being by powers of two it is exact, and an
LDLᵀ without pivoting commutes with it: the factor of K̃ is
(S L S⁻¹)(S Δ S)(S L S⁻¹)ᵀ bit for bit, barring overflow and
underflow. So K2′ by itself changes exactly two things: the
thresholds τ, β of K3 become relative to the magnitude of
each row, and the intermediate values stay in range.
K2″. [Static regularization.] Add the shifts on the diagonal of K̃:
Σ itself with ShiftScale::Equilibrated (K̃_reg = K̃ + Σ),
S Σ S with ShiftScale::Absolute (K̃_reg = S (K + Σ) S): −ρ
on the primal diagonal and +δ on the dual one (normal equations:
+δ everywhere; ρ does not apply, the caller folds it into
D). The backend factorizes K̃_reg and solves with S F̃⁻¹ S;
S⁻¹ K̃_reg S⁻¹ is the K_reg of the notation above.
K3. [Dynamic regularization.] If τ = pivot_tol is Some, the backend
replaces every pivot d_k with σ_k d_k ≤ τ (too small, or of the
wrong sign) by σ_k β while it eliminates — the dynamic part of
Altman & Gondzio’s (1999) primal-dual regularization, in the form
faer’s LdltRegularization applies — and counts the bumped pivots. Bumping
needs the sign σ_k, which only the form knows — the policy is
here; the elimination loop that applies it is the backend’s.
K3′. [Finite factor (S10).] Every stored value of the factor is
finite; otherwise the call fails with KktError::NotFinite at
the first column (original numbering) holding a NaN or an infinity
— an overflow of the elimination is reported, never handed to the
solves (where it would become a NaN solution).
K4. [Inertia (S6).] From the pivots of the factor, count the inertia.
If it is not (N, 0, 0) (normal) or (m, n, 0) (augmented),
return KktError::WrongInertia. With τ = Some, every pivot has
the sign σ_k by K3, so the check cannot fail: the factor is that
of a perturbation of K_reg with the right inertia, and refinement
(Algorithm F) measures how far it is from K.
§Choosing the regularization
Three facts, measured on the 558 Netlib systems of L1.5/L1.5b (93 LPs ×
normal and augmented × the start, middle and end regimes of D),
decide the default.
- A shift must be above the rounding level of its row. A shift
δ < ε_T · max|k_ij|changes nothing in floating point. At the end of an interior-point methodDspreads to10^{±10}andmax|K| ≈ 10^{10}, so the absoluteρ = δ = 10⁻⁸of L1.5 failed on 32 of the 558 systems (zero pivots after overflow, or NaN solutions). One shift relative to the whole matrix (Regularization::relative_to(k, 10⁻⁸),δ ≈ 10²there) factorizes all 558, but perturbs the rows of small magnitude so much that refinement against the unregularizedKstalls (418 of 558 at or below10⁻¹⁰after 50 classical steps). Shifts taken in the equilibrated matrix (step K2″,ShiftScale::Equilibrated) are relative row by row. - The product
ρδmust be well above the unit roundoff. Eliminating a primal pivot of size~ρadds terms of size~1/ρto the dual block, whose pivots must stay aboveδ: withρ = δ = 10⁻⁸in the equilibrated matrix (ρδ = 10⁻¹⁶ < ε) nine augmented systems of the end regime still got pivots of the wrong sign; withρδ ≥ 10⁻¹⁴none did (the stability analysis of quasi-definite factorizations of Gill, Saunders & Shinnerl 1996 bounds the growth by the shifts). - The normal equations see only
δ, and every unit ofδslows the refinement on their small eigenvalues:δ = 10⁻⁶left 46 systems above10⁻¹⁰after ten steps,δ = 10⁻⁸none (with Algorithm F’s GMRES).
Hence the default ρ = 10⁻⁶, δ = 10⁻⁸, equilibrated: all 558 systems
with the right inertia, no bump, and a residual against the
unregularized K at or below 10⁻¹⁰ after the ten steps of
Refinement::default (L1.5b, D1–D3; the bumping of K3 is the safety
net, not the mechanism). An interior-point method that wants other
values passes them; ShiftScale::Absolute keeps shifts in the
caller’s units.
§Algorithm F (Refinement by preconditioned GMRES, with the best iterate; (S7))
Given a factor F ≈ K_reg, the matrix K to be solved (the
unregularized one, or K_reg itself — whichever the caller passes),
b and a Refinement (t_max, target) = (max_iters,
target_residual), where t_max bounds the solves with F after the
first one:
F1. x ← F⁻¹ b; r ← b − K x; ρ ← res(x); x* ← x, ρ* ← ρ;
t ← 0.
F2. [Done?] If ρ* ≤ target, ρ is not finite, or t = t_max, go to
F6.
F3. [Arnoldi cycle, right preconditioned (Saad 2003, §9.3.2).] x ← x*,
r ← b − K x (the residual of the best iterate), β ← ‖r‖₂,
v₁ ← r/β, g ← β e₁, m ← t_max − t. For j = 1, 2, …, m:
z_j ← F⁻¹ v_j, t ← t + 1; w ← K z_j; modified Gram–Schmidt
h_ij ← ⟨w, v_i⟩, w ← w − h_ij v_i for i ≤ j;
h_{j+1,j} ← ‖w‖₂; apply the previous Givens rotations to column
j of H, compute the rotation that annihilates h_{j+1,j} and
apply it to g. Leave the loop with k = j when h_{j+1,j} = 0
(the Krylov space is invariant: the solution is in it), when
|g_{j+1}| ≤ target·(1 + ‖b‖_∞) (in exact arithmetic |g_{j+1}|
is the 2-norm of the residual, which bounds its ∞-norm), or when
j = m.
F4. [Update.] Solve the k × k upper triangular system R y = g_{1:k}
(the rotated H); x ← x* + Σ_j y_j z_j; r ← b − K x;
ρ ← res(x). If ρ < ρ*, set x* ← x, ρ* ← ρ.
F5. Go to F2 (a new cycle restarts from x*).
F6. Return x* with iters = t, residual = ρ* and
converged = (ρ* ≤ target).
Why GMRES and not the classical iteration. The classical refinement
x ← x + F⁻¹ r of L1.5 contracts the error by the factor
‖I − F⁻¹ K‖ = ‖F⁻¹ (K_reg − K)‖ per step; on the eigenvectors of K
whose eigenvalues are not much larger than the shifts — the nearly
rank-deficient A D Aᵀ of the middle of an interior-point method, or
an augmented system with D spread to 10^{±4} — that factor is close
to 1, and ten steps left 15 of the 558 Netlib systems of L1.5b above
10⁻¹⁰ against the unregularized K. Right-preconditioned GMRES
minimizes ‖b − K x‖₂ over the same affine Krylov space
x₀ + span{F⁻¹r₀, (F⁻¹K) F⁻¹r₀, …} that holds the classical
iterates, so in exact arithmetic it is never worse, and the few
eigenvalues of F⁻¹ K far from 1 — one per small eigenvalue of K,
the regularization being a small perturbation elsewhere — cost one
step each. This is GMRES preconditioned by a perturbed (statically
pivoted, here statically regularized) LDLᵀ, analyzed by Arioli,
Duff, Gratton & Pralet (2007), and GMRES-based iterative refinement
(Carson & Higham 2017). One cycle with all the budget is the normal
case; F5 restarts only when the estimate |g_{k+1}| and the computed
residual disagree (rounding) or the budget allows another cycle after
a breakdown.
Memory. A cycle of m steps keeps m + 1 Arnoldi vectors v_j and
m preconditioned vectors z_j (so F4 needs no further solve), plus
H and the rotations: (2m + 3) N + O(m²) scalars, held by a
RefineWorkspace that KktSolver::solve_refined_with reuses
across calls — after the first call with a given order and budget,
refinement allocates nothing (Chapter 5.15 for the solves themselves).
The residual is computed with the stored lower triangle of K
(y_i += k_ij x_j and, for i ≠ j, y_j += k_ij x_i), in the working
precision of T — fixed-precision refinement, which brings the
componentwise backward error of a backward-stable factorization down to
the order of the unit roundoff (Skeel 1980; Higham 2002, ch. 12); with
a regularized factor it also removes the bias of the shifts (Altman &
Gondzio 1999, §6). When K is singular but b is consistent the
iteration still converges in the residual.
§Invariants
(K1) The pattern given to KktSolver::analyze is square and either
lower triangular or structurally symmetric
(KktError::NotSymmetric otherwise).
(S6) (the contract’s) KktSolver::factorize returns the inertia of
the factor it computed; it is (N, 0, 0) for the normal equations
and (m, n, 0) = {positive: m, negative: n, zero: 0} for the
augmented system, or the call fails with
KktError::WrongInertia. Asserted on every successful
factorization in debug builds.
(S7) (the contract’s) KktSolver::solve_refined never returns a
residual larger than that of its first solve: it keeps the best
iterate (step F4). Asserted in debug builds.
(S10) A factor returned by KktSolver::factorize holds only finite
values (step K3′); KktSolver::solve_refined reports a
non-finite solution explicitly: its residual is NaN or infinite
exactly when the returned x has a non-finite entry, and then
converged = false (the input K, b being finite).
§References
Chen, Davis, Hager & Rajamanickam, “Algorithm 887: CHOLMOD, supernodal
sparse Cholesky factorization and update/downdate”, ACM TOMS 35(3),
2008 (the analyze/factorize/solve shape, the lower-triangle input, the
supernodal/simplicial selection by flops per nnz(L) — read, not
copied); Altman & Gondzio, “Regularized symmetric indefinite systems in
interior point methods for linear and quadratic optimization”, Optim.
Methods Softw. 11–12, 1999; Vanderbei, “Symmetric quasidefinite
matrices”, SIAM J. Optim. 5(1), 1995; Gill, Saunders & Shinnerl, “On
the stability of Cholesky factorization for symmetric quasidefinite
systems”, SIAM J. Matrix Anal. Appl. 17(1), 1996; Wright,
Primal-Dual Interior-Point Methods, SIAM 1997, ch. 11; Bunch &
Kaufman, “Some stable methods for calculating inertia and solving
symmetric linear systems”, Math. Comp. 31, 1977; Skeel, “Iterative
refinement implies numerical stability for Gaussian elimination”, Math.
Comp. 35, 1980; Higham, Accuracy and Stability of Numerical
Algorithms, 2nd ed. 2002, ch. 11–12; Ruiz, “A scaling algorithm to
equilibrate both rows and columns norms in matrices”, RAL-TR-2001-034,
2001 (symmetric variant, rounded to powers of two here); Stellato et al., “OSQP: an
operator splitting solver for quadratic programs”, Math. Prog. Comp.
12, 2020 (quasi-definite LDLᵀ without pivoting in an optimization
solver); Saad, Iterative Methods for Sparse Linear Systems, 2nd ed.,
SIAM 2003, §6.5 and §9.3 (GMRES, right preconditioning, Givens
rotations); Arioli, Duff, Gratton & Pralet, “A note on GMRES
preconditioned by a perturbed LDLᵀ decomposition with static
pivoting”, SIAM J. Sci. Comput. 29(5), 2007; Carson & Higham, “A new
analysis of iterative refinement and its application to accurate
solution of ill-conditioned sparse linear systems”, SIAM J. Sci.
Comput. 39(6), 2017; Saunders & Tomlin, “Solving regularized linear
programs using barrier methods and KKT systems”, SOL 96-4, 1996 (the
product ρδ above the rounding level for a stable quasi-definite
factorization).
Structs§
- Inertia
- Inertia
(positive, negative, zero)of a symmetric factorization: the numbers of positive, negative and zero pivots (eigenvalues, by Sylvester’s law). - Refine
Report - What refinement achieved (S7).
- Refine
Workspace - Work vectors of Algorithm F, reusable across calls of
KktSolver::solve_refined_with:(2m + 3) N + O(m²)scalars for a budget ofm = max_iterssolves and orderN. Grows on demand, never shrinks. - Refinement
- Iterative refinement parameters (Algorithm F).
- Regularization
- Regularization of a quasi-definite KKT matrix (Altman & Gondzio 1999; Algorithm K).
Enums§
- KktForm
- Which system the interior-point method hands over.
- Shift
Scale - Where the static shifts
ρ,δof aRegularizationare applied (step K2″ of Algorithm K).
Constants§
- EQUILIBRATION_
PASSES - Most passes of the symmetric equilibration (step K2′). A cap, not a threshold: with power-of-two factors the iteration stops by itself when no factor changes, which happens after a few passes in practice (Ruiz 2001 reports convergence of the infinity-norm iteration to within a factor 2 in a handful of steps).
Traits§
- KktSolver
- Analyze/factorize/solve of symmetric systems with a fixed pattern (the CHOLMOD shape, read, not copied). Regularization (its policy, Algorithm K) and refinement (Algorithm F) are shared by every backend.