Gradient matrix at a query state
DefinitionMatrixLeeSidford_Supplement_gradMatGinterior-point-methodsp2o-gran-per-chapterp2o-plan-bookp2o-v1self-concordant-barrierssemidefinite-programming
Let be feasible, , and let have Cholesky factor . With for , the gradient matrix at the query state is
Since , depends on only; at it is the matrix of Definition 5.5.
Formalization Note is built from the Cholesky factor, as printed; powers are natural-number matrix powers.
Definition code
import Mathlib
import Definitions.Def_MatrixLeeSidford_Lmap
import Definitions.Def_MatrixLeeSidford_slack
import Definitions.Def_MatrixLeeSidford_Supplement_cholFactor
open Matrix
namespace MatrixLeeSidford.Supplement
/-- The **gradient matrix** at a query state `(y, G)`,
`M := ½ (L_y(G)^s + ∑_a V_a L_y(G)^{s−1} V_a)` with `V_a := ∑_i L_{ia} B_i` and `L` the Cholesky factor of
`G` (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).
**Formalization Note** `B_i = normB A (S(y)) i`, `L_y = Lmap A (S(y))`, `L = cholFactor G`; powers are
natural-number matrix powers. -/
noncomputable def gradMatG {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) ℝ) : Matrix (Fin n) (Fin n) ℝ :=
let V : Fin m → Matrix (Fin n) (Fin n) ℝ :=
fun a => ∑ i, cholFactor G i a • normB A (slack A C y) i
(1 / 2 : ℝ) • ((Lmap A (slack A C y) G) ^ s +
∑ a, V a * (Lmap A (slack A C y) G) ^ (s - 1) * V a)
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