Fixed-weight gradient
DefinitionMatrixLeeSidford_Supplement_fixedGradinterior-point-methodsp2o-gran-per-chapterp2o-plan-bookp2o-v1self-concordant-barrierssemidefinite-programming
Let be feasible, , and let be the gradient matrix at . The fixed-weight gradient is the vector with
where . It is the gradient of with held fixed, and at the optimal weight it equals .
Formalization Note A vector of with its Euclidean structure; is the base mission's published scaling .
Definition code
import Mathlib
import Definitions.Def_MatrixLeeSidford_alphaParam
import Definitions.Def_MatrixLeeSidford_Supplement_gradMatG
open Matrix
namespace MatrixLeeSidford.Supplement
/-- The **fixed-weight gradient** `g = g_G(y)`, `gᵢ := −α tr[M Bᵢ]`, at a query state `(y, G)`, with `M` the
gradient matrix at `(y, G)` and `α = 10⁶ s²` (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; `α` from Definition 5.1, p.37).
**Formalization Note** A vector of `EuclideanSpace ℝ (Fin m)` (the same space as the dual point `y`);
`α` is the published `alphaParam s`. -/
noncomputable def fixedGrad {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) ℝ) : EuclideanSpace ℝ (Fin m) :=
WithLp.toLp 2 fun i => -alphaParam s * (gradMatG A C s y G * normB A (slack A C y) i).trace
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; Definition 5.1, p.37