Phase ball
DefinitionMatrixLeeSidford_Supplement_phaseBallinterior-point-methodsp2o-gran-per-chapterp2o-plan-bookp2o-v1self-concordant-barrierssemidefinite-programming
For a centering call that starts at the feasible point , its phase ball is the Dikin-type ellipsoid
where is the matrix Lee–Sidford barrier. By self-concordance every phase ball lies in , and the Hessian of is within constant factors of on it.
Formalization Note The local norm is the published one, the square root of the second Fréchet derivative of evaluated on the diagonal.
Definition code
import Mathlib
import Definitions.Def_MatrixLeeSidford_barrierF
import Definitions.Def_DoublyOptBandit_LocalNorm
open Matrix
namespace MatrixLeeSidford.Supplement
/-- The **phase ball** `B(y°) := {y : ‖y − y°‖_{∇²F(y°)} ≤ 2/5}` of a centering call that starts at `y°`
(Song–Zhang, *A Matrix Lee–Sidford Barrier and Faster Semidefinite Programming*, STOC 2027 submission manuscript of October 31, 2026 (sha256 7c638b45…412c1), Eq. (8.3), p.56).
**Formalization Note** `F` is the published `barrierF A C`; the local norm is the published
`DoublyOptBandit.localNorm`, `√(∇²F(y°)[v, v])` with `∇²F = iteratedFDeriv ℝ 2 F`. -/
noncomputable def phaseBall {n m : ℕ} (A : Fin m → Matrix (Fin n) (Fin n) ℝ)
(C : Matrix (Fin n) (Fin n) ℝ) (y₀ : EuclideanSpace ℝ (Fin m)) :
Set (EuclideanSpace ℝ (Fin m)) :=
{y | DoublyOptBandit.localNorm (barrierF A C) y₀ (y - y₀) ≤ 2 / 5}
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), Eq. (8.3), p.56