Weight gap
DefinitionMatrixLeeSidford_Supplement_weightGapinterior-point-methodsp2o-gran-per-chapterp2o-plan-bookp2o-v1self-concordant-barrierssemidefinite-programming
Let be a feasible dual point, , and let be the Lewis-weight objective at , minimized over by the optimal weight . The weight gap of a weight is
A weight is accurate at if and warm if , with fixed in (8.11).
The gap measures how far the weight maintained by the algorithm is from the optimal weight that defines the barrier.
Formalization Note and are the base mission's published objective and optimal weight (a chosen minimizer). The trace power is a parameter; Part II takes .
Definition code
import Mathlib
import Definitions.Def_MatrixLeeSidford_fObj
import Definitions.Def_MatrixLeeSidford_optWeightAt
import Definitions.Def_MatrixLeeSidford_slack
open Matrix
namespace MatrixLeeSidford.Supplement
/-- The **weight gap** `Δ_y(G) := f_y(G) − f_y(G_*(y))` of a weight `G ≻ 0` at a feasible point `y`
(Song–Zhang, *A Matrix Lee–Sidford Barrier and Faster Semidefinite Programming*, STOC 2027 submission manuscript of October 31, 2026 (sha256 7c638b45…412c1), Definition 8.1, p.53). A weight is *accurate* at `y` if `Δ_y(G) ≤ η` and *warm* if
`Δ_y(G) ≤ η_w` (p.53).
**Formalization Note** `f_y` is the published `fObj` at the slack `S(y)` and `G_*(y)` the published
`optWeightAt` (a chosen minimizer of `f_y` over `G ≻ 0`, Theorem 2.1(a)). The trace power `s` is a
parameter; Part II uses `s = sParam m n` (Definition 5.1). -/
noncomputable def weightGap {n m : ℕ} (A : Fin m → Matrix (Fin n) (Fin n) ℝ)
(C : Matrix (Fin n) (Fin n) ℝ) (s : ℕ) (y : EuclideanSpace ℝ (Fin m))
(G : Matrix (Fin m) (Fin m) ℝ) : ℝ :=
fObj A (slack A C y) s G - fObj A (slack A C y) s (optWeightAt A C s 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), Definition 8.1, p.53