Theorem 3.1: strong duality and attainment under strict feasibility
ProvedVBSDP.Duality.theorem_3_1dualityp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1semidefinite-programming
Let and let be symmetric real matrices. For the primal problem (1) and dual problem (27), either of the following conditions implies equality of extended optimal values:
- There is with .
- There is a dual feasible .
If both strict-feasibility conditions hold, then both optimal sets are nonempty: and .
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_lmi import Definitions.Def_VBSDP_Duality_pStar import Definitions.Def_VBSDP_Duality_dStar import Definitions.Def_VBSDP_Duality_Xopt import Definitions.Def_VBSDP_Duality_Zopt
Formal statement
namespace VBSDP.Duality
theorem theorem_3_1 {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, (lmi F₀ F x).PosDef) ∨
(∃ Z : Matrix (Fin n) (Fin n) ℝ, Z.PosDef ∧ ∀ i, (F i * Z).trace = c i)) →
pStar c F₀ F = dStar c F₀ F) ∧
(((∃ x, (lmi F₀ F x).PosDef) ∧
(∃ Z : Matrix (Fin n) (Fin n) ℝ, Z.PosDef ∧ ∀ i, (F i * Z).trace = c i)) →
(Xopt c F₀ F).Nonempty ∧ (Zopt c F₀ F).Nonempty) := by sorry
end VBSDP.Duality
Source
Vandenberghe and Boyd, Semidefinite Programming, SIAM Review 38(1) (1996), p. 64, Theorem 3.1, continued on p. 65, 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.