p. 76 — nonnegative deviation and its equality case
ProvedVBSDP.Potential.psi_nonneginterior-point-methodsp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1semidefinite-programming
Let be a strictly feasible pair for the semidefinite program with symmetric data, linearly independent variable matrices, and matrix size . Then its deviation from centrality satisfies
Thus vanishing deviation forces the primal and dual matrices to be inverses up to scale. The nonnegativity clause is the central inequality behind the potential bound.
Formalization Note The page says feasible pairs, but its logarithmic formula is meaningful as a finite real quantity on strictly feasible pairs; §4 and the algorithm use that domain. is separate from the zero-based Fin m family.
Preamble
import Mathlib import Definitions.Def_VBSDP_Potential_IsStrictlyFeasiblePair import Definitions.Def_VBSDP_Potential_psi
Formal statement
namespace VBSDP.Potential
/-- The nonnegativity assertion for the deviation from centrality on p. 76. -/
theorem psi_nonneg {m n : ℕ} [NeZero n] (c : Fin m → ℝ)
(F₀ : Matrix (Fin n) (Fin n) ℝ)
(F : Fin m → Matrix (Fin n) (Fin n) ℝ)
(hF₀ : F₀.IsHermitian) (hF : ∀ i, (F i).IsHermitian)
(hlin : LinearIndependent ℝ F)
(x : Fin m → ℝ) (Z : Matrix (Fin n) (Fin n) ℝ)
(h : IsStrictlyFeasiblePair c F₀ F x Z) :
0 ≤ psi F₀ F x Z ∧
(psi F₀ F x Z = 0 → ∃ t : ℝ, VBSDP.Duality.lmi F₀ F x * Z = t • 1) := by sorry
end VBSDP.Potential
Source
Vandenberghe and Boyd, Semidefinite Programming, SIAM Rev. 38 (1996), p. 76 (PDF p. 28), §4.5, ψ ≥ 0 statement, with §4 assumptions on p. 70, https://doi.org/10.1137/1038003
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.