Skip to main content

Module kkt

Module kkt 

Source
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), the n primal 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.

  1. 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 method D spreads to 10^{±10} and max|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 unregularized K stalls (418 of 558 at or below 10⁻¹⁰ after 50 classical steps). Shifts taken in the equilibrated matrix (step K2″, ShiftScale::Equilibrated) are relative row by row.
  2. 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).
  3. The normal equations see only δ, and every unit of δ slows the refinement on their small eigenvalues: δ = 10⁻⁶ left 46 systems above 10⁻¹⁰ 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).
RefineReport
What refinement achieved (S7).
RefineWorkspace
Work vectors of Algorithm F, reusable across calls of KktSolver::solve_refined_with: (2m + 3) N + O(m²) scalars for a budget of m = max_iters solves and order N. 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.
ShiftScale
Where the static shifts ρ, δ of a Regularization are 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.