(32) — the duality gap equals Tr F(x)Z
ProvedVBSDP.Potential.duality_gap_32dualityp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1semidefinite-programming
Let be the affine matrix of the primal semidefinite program, with symmetric data. Suppose and , and satisfies the dual equations . Then the duality gap between the primal objective and the dual objective is
This identifies the trace quantity used by the potential and by Theorem 5.1 with an objective gap.
Formalization Note Positive semidefiniteness includes symmetry in Mathlib. is separate from the zero-based Fin m family of variable matrices.
Preamble
import Mathlib import Definitions.Def_VBSDP_Duality_lmi
Formal statement
namespace VBSDP.Potential
/-- Equation (32): the primal-dual objective difference equals the matrix trace. -/
theorem duality_gap_32 {m 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)
(x : Fin m → ℝ) (Z : Matrix (Fin n) (Fin n) ℝ)
(hx : (VBSDP.Duality.lmi F₀ F x).PosSemidef) (hZ : Z.PosSemidef)
(hdual : ∀ i, (F i * Z).trace = c i) :
c ⬝ᵥ x + (F₀ * Z).trace = (VBSDP.Duality.lmi F₀ F x * Z).trace := by sorry
end VBSDP.Potential
Source
Vandenberghe and Boyd, Semidefinite Programming, SIAM Rev. 38 (1996), p. 64 (PDF p. 16), (32), https://doi.org/10.1137/1038003
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.