Newton decrement
DefinitionMatrixLeeSidford_Supplement_newtonDecinterior-point-methodsp2o-gran-per-chapterp2o-plan-bookp2o-v1self-concordant-barrierssemidefinite-programming
Let be the matrix Lee–Sidford barrier on , with and . For an objective vector , the penalized objective and its Newton decrement are
A point is centered for to tolerance when .
Formalization Note is the base mission's published barrier, is the Euclidean gradient, and the dual local norm is the published one (inverse of the Hessian matrix of , positive definite on by Theorem 2.1).
Definition code
import Mathlib
import Definitions.Def_MatrixLeeSidford_barrierF
import Definitions.Def_DoublyOptBandit_LocalNorm
open Matrix
namespace MatrixLeeSidford.Supplement
/-- The **Newton decrement** `λ_c(y) := ‖∇ϕ_c(y)‖_{∇²F(y)⁻¹}` of the penalized objective
`ϕ_c(y) := F(y) + cᵀy`, with `F = αΦ_p` the matrix Lee–Sidford barrier (Song–Zhang, *A Matrix Lee–Sidford Barrier and Faster Semidefinite Programming*, STOC 2027 submission manuscript of October 31, 2026 (sha256 7c638b45…412c1), Section 8.1, p.53).
**Formalization Note** `F` is the published `barrierF A C` (`s = sParam m n`, `α = alphaParam s`);
`∇ϕ_c(y)` is Mathlib's `gradient` on `EuclideanSpace ℝ (Fin m)` and `cᵀy` the Euclidean inner product;
the dual local norm is the published `DoublyOptBandit.dualLocalNorm`, `√(vᵀ H⁻¹ v)` with `H` the matrix
of `iteratedFDeriv ℝ 2 F y` (the paper's `∇²F(y)`, positive definite on `Ω` by Theorem 2.1(b)). -/
noncomputable def newtonDec {n m : ℕ} (A : Fin m → Matrix (Fin n) (Fin n) ℝ)
(C : Matrix (Fin n) (Fin n) ℝ) (c y : EuclideanSpace ℝ (Fin m)) : ℝ :=
DoublyOptBandit.dualLocalNorm (barrierF A C) y
(gradient (fun x : EuclideanSpace ℝ (Fin m) => barrierF A C x + inner ℝ c x) y)
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), Section 8.1, p.53