SDP strong duality
ProvedConvexOptimization.sdp_strong_dualityStrong duality for the inequality-form semidefinite program.
Consider, with variable and symmetric data ,
Assume strict feasibility — some makes negative definite — and that the optimal value is finite. Then the dual optimum is attained: there is a symmetric with
where is the optimal value of the primal.
Semidefinite programming inherits strong duality from the conic theorem because the positive semidefinite cone is closed, convex and has nonempty interior, and the strict-feasibility hypothesis is exactly the generalized Slater condition for it. The dual variable is a matrix rather than a vector, and the equality constraints are the conic analogue of dual feasibility.
Formalization Note Matrices are Matrix (Fin k) (Fin k) ℝ with symmetry IsSymm; the semidefinite inequality appears as (-M).PosSemidef, strict feasibility as PosDef, and the trace pairing as (F i * Z).trace. The optimal value is an sInf over the image of the feasible set, guarded by BddBelow. Source: B&V §5.9.2, pp. 265–266.
import Mathlib open scoped RealInnerProductSpace ENNReal open MeasureTheory
theorem ConvexOptimization.sdp_strong_duality {n nn : ℕ} (c : Fin n → ℝ)
(F : Fin n → Matrix (Fin nn) (Fin nn) ℝ) (hF : ∀ i, (F i).IsSymm)
(G : Matrix (Fin nn) (Fin nn) ℝ) (hG : G.IsSymm)
(xs : Fin n → ℝ) (hxs : (-(G + ∑ i, xs i • F i)).PosDef)
(hbdd : BddBelow ((fun x : Fin n → ℝ => c ⬝ᵥ x) ''
{x | (-(G + ∑ i, x i • F i)).PosSemidef})) :
∃ Z : Matrix (Fin nn) (Fin nn) ℝ, Z.PosSemidef ∧
(∀ i, ((F i) * Z).trace + c i = 0) ∧
(G * Z).trace =
sInf ((fun x : Fin n → ℝ => c ⬝ᵥ x) ''
{x | (-(G + ∑ i, x i • F i)).PosSemidef}) := by
sorry
Read-back
What the Lean code literally says, in plain math · claude-fable-5
Theorem. Fix natural numbers , . Assume: a vector ; matrices and , all real and each assumed symmetric (); a point such that is positive definite — Mathlib's positive definiteness includes the symmetry/Hermitian requirement together with for every (for there are no nonzero vectors, so this holds vacuously); and the hypothesis that the value set
is bounded below (positive semidefiniteness likewise includes symmetry, plus for all ). Conclusion: there exists a real matrix such that (i) is positive semidefinite (hence symmetric); (ii) for every , , where the trace of the matrix product means ; and (iii) , an equality of real numbers with no sign flip on . Here is Lean's real infimum with junk value on an empty or unbounded-below set; in this statement is nonempty (it contains , since positive definite implies positive semidefinite) and bounded below by hypothesis, so it is the genuine infimum. No attainment of the primal infimum by a feasible is claimed, and no uniqueness of . Edge cases: for the linear combination is empty and , the strict-feasibility hypothesis reads " is positive definite", condition (ii) is vacuous, and ; for all matrix conditions are vacuous and both sides of (iii) reduce to with .
Confirmed by the mission captain (proposal self-audit).