p. 76 — the duality gap is bounded by the potential
ProvedVBSDP.Potential.gap_le_expinterior-point-methodsp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1semidefinite-programming
Let be a strictly feasible primal-dual pair for a semidefinite program with symmetric data and linearly independent variable matrices. For and the paper's parameter , its duality gap satisfies
Thus an upper bound on the potential gives an upper bound on the gap.
Formalization Note Strict feasibility keeps all logarithms in the defining within their positive domain. is separate from the zero-based Fin m family.
Preamble
import Mathlib import Definitions.Def_VBSDP_Potential_IsStrictlyFeasiblePair import Definitions.Def_VBSDP_Potential_phi
Formal statement
namespace VBSDP.Potential
/-- The bound immediately following (55) on p. 76. -/
theorem gap_le_exp {m n : ℕ} [NeZero n] (ν : ℝ) (hν : 1 ≤ ν)
(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) :
(VBSDP.Duality.lmi F₀ F x * Z).trace ≤
Real.exp (phi ν F₀ F x Z / (ν * Real.sqrt n)) := by sorry
end VBSDP.Potential
Source
Vandenberghe and Boyd, Semidefinite Programming, SIAM Rev. 38 (1996), p. 76 (PDF p. 28), displayed bound after (55), 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.