Damped inverse update (Algorithm 8, Eq. (8.2))
DefinitionMatrixLeeSidford_Supplement_updateWeightinterior-point-methodsp2o-gran-per-chapterp2o-plan-bookp2o-v1self-concordant-barrierssemidefinite-programming
Given a weight , a symmetric estimate of the stationarity matrix and a step size , the procedure computes , checks
reports failure if a check or the factorization fails, and otherwise returns the damped inverse update
Algorithm 8 uses .
Formalization Note Failure is the value none. The Cholesky factorization of fails exactly when is not positive definite, so that is checked too. The step size is a parameter.
Definition code
import Mathlib
import Definitions.Def_MatrixLeeSidford_Supplement_cholFactor
open Matrix
namespace MatrixLeeSidford.Supplement
/-- The **damped inverse update** `UpdateWeight(G, R̂)` (Song–Zhang, *A Matrix Lee–Sidford Barrier and Faster Semidefinite Programming*, STOC 2027 submission manuscript of October 31, 2026 (sha256 7c638b45…412c1), Algorithm 8, p.82, and Eq. (8.2),
p.54): compute `L = chol(G)`; check `I + R̂ ≻ 0` and `(1 − γ_G)I + 2γ_G(I + R̂)⁻¹ ≻ 0`, reporting failure if a
check or a factorization fails; return `L((1 − γ_G)I + 2γ_G(I + R̂)⁻¹)Lᵀ`.
**Formalization Note** Failure is `none`. The factorization `chol(G)` fails exactly when `G` is not
positive definite, so `G ≻ 0` is checked as well. The step size `γ_G` is a parameter (Algorithm 8
computes `γ_G = 1/(1000 s)`, which the theorems pass). -/
noncomputable def updateWeight {m : ℕ} (γG : ℝ) (G R : Matrix (Fin m) (Fin m) ℝ) :
Option (Matrix (Fin m) (Fin m) ℝ) :=
open Classical in
if G.PosDef ∧ (1 + R).PosDef ∧ ((1 - γG) • (1 : Matrix (Fin m) (Fin m) ℝ) + (2 * γG) • (1 + R)⁻¹).PosDef
then some (cholFactor G * ((1 - γG) • (1 : Matrix (Fin m) (Fin m) ℝ) + (2 * γG) • (1 + R)⁻¹) *
(cholFactor G)ᵀ)
else none
end MatrixLeeSidford.Supplement
Source
Song–Zhang, A Matrix Lee–Sidford Barrier and Faster Semidefinite Programming, STOC 2027 submission (manuscript of October 31, 2026, sha256 7c638b45…412c1), Algorithm 8, p.82; Eq. (8.2), p.54