Equation (30): the primal–dual gap identity
ProvedVBSDP.Duality.eq_30dualityp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1semidefinite-programming
Let be primal feasible and dual feasible for (1) and (27). Then
This identifies the duality gap with the trace pairing of two positive semidefinite matrices.
This statement supplies a target in the duality development.
Formalization Note Matrices have dimension , with coefficients indexed in Lean from 0 and passed separately. Positive semidefiniteness and positive definiteness are matrix conditions; trace is the matrix trace.
Preamble
import Mathlib import Definitions.Def_VBSDP_Duality_IsPrimalFeasible import Definitions.Def_VBSDP_Duality_IsDualFeasible
Formal statement
namespace VBSDP.Duality
theorem eq_30 {m n : ℕ} (c : Fin m → ℝ) (F₀ : Matrix (Fin n) (Fin n) ℝ)
(F : Fin m → Matrix (Fin n) (Fin n) ℝ) (x : Fin m → ℝ)
(Z : Matrix (Fin n) (Fin n) ℝ)
(hx : IsPrimalFeasible F₀ F x) (hZ : IsDualFeasible F c Z) :
c ⬝ᵥ x + (Z * F₀).trace = (∑ i, (Z * F i).trace * x i) + (Z * F₀).trace ∧
(∑ i, (Z * F i).trace * x i) + (Z * F₀).trace =
(Z * lmi F₀ F x).trace ∧
0 ≤ (Z * lmi F₀ F x).trace := by sorry
end VBSDP.Duality
Source
Vandenberghe and Boyd, Semidefinite Programming, SIAM Review 38(1) (1996), p. 64, equation (30), PDF p. 16, https://doi.org/10.1137/1038003
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.