Theorem 6 (Duality Theorem) — ELSD: weak duality, zero gap and dual attainment for every SDP
ProvedExactSDPDuality.ELSD.duality_theoremLet be real symmetric matrices, , and consider the primal semidefinite program
with feasible region . Let (ELSD) be subject to , , , and (Weak-ELSD) the same program with in place of . No constraint qualification is assumed. Then:
- (Weak duality) If is primal feasible and is dual feasible (or weakly dual feasible), then .
- (Primal boundedness) If the primal is feasible, then its optimal value is finite if and only if (ELSD) is feasible, and if and only if (Weak-ELSD) is feasible.
- (Zero gap) If the primal and (ELSD) (or (Weak-ELSD)) are both feasible, then the optimal values of (P), (ELSD) and (Weak-ELSD) are equal: there is a real that is the supremum of the primal objective values and the infimum of the objective values of both duals.
- (Dual attainment) Whenever the common optimal value of the primal and (ELSD) is finite, i.e. the primal is feasible and bounded above, (ELSD) has a feasible pair with equal to it.
This is the semidefinite analogue of the linear programming duality theorem, obtained without Slater's condition: the standard Lagrangian dual of (P) can have a positive duality gap or fail to attain, whereas (ELSD), which has polynomial size in the data, never does.
Formalization Note Optimal values are expressed by least upper and greatest lower bounds of the sets of objective values, never by real sSup/sInf. "Finite optimal value" of a feasible primal is boundedness above of its objective values. In part 3 the hypothesis "(ELSD) or (Weak-ELSD) is feasible" is stated as a disjunction, which covers both readings of the page. For , .
import Mathlib import Definitions.Def_ExactSDPDuality_ELSD_Model open Matrix
namespace ExactSDPDuality.ELSD
/-- Theorem 6, the Duality Theorem (Ramana 1997, p. 138), for the primal SDP
`sup cᵀx s.t. ∑ᵢ xᵢ Qᵢ ⪯ Q₀` with real symmetric data and no constraint qualification:
(i) weak duality for (ELSD) and (Weak-ELSD);
(ii) a feasible primal has finite optimal value iff (ELSD) (resp. (Weak-ELSD)) is feasible;
(iii) if the primal and (ELSD) (or (Weak-ELSD)) are feasible, the three optimal values coincide;
(iv) when the common optimal value is finite, (ELSD) attains it. -/
theorem duality_theorem {n m : ℕ} (Q0 : Matrix (Fin n) (Fin n) ℝ)
(Q : Fin m → Matrix (Fin n) (Fin n) ℝ) (c : Fin m → ℝ)
(hQ0 : Q0.IsSymm) (hQ : ∀ i, (Q i).IsSymm) :
-- (i) weak duality
((∀ x ∈ feasibleSet Q0 Q, ∀ U W : Matrix (Fin n) (Fin n) ℝ,
ELSDFeasible Q0 Q c U W → c ⬝ᵥ x ≤ frob (U + W) Q0) ∧
(∀ x ∈ feasibleSet Q0 Q, ∀ U W : Matrix (Fin n) (Fin n) ℝ,
WeakELSDFeasible Q0 Q c U W → c ⬝ᵥ x ≤ frob (U + W) Q0)) ∧
-- (ii) primal boundedness
((feasibleSet Q0 Q).Nonempty →
(BddAbove (primalValues Q0 Q c) ↔ ∃ U W, ELSDFeasible Q0 Q c U W) ∧
(BddAbove (primalValues Q0 Q c) ↔ ∃ U W, WeakELSDFeasible Q0 Q c U W)) ∧
-- (iii) zero gap
((feasibleSet Q0 Q).Nonempty →
((∃ U W, ELSDFeasible Q0 Q c U W) ∨ (∃ U W, WeakELSDFeasible Q0 Q c U W)) →
∃ v : ℝ, IsLUB (primalValues Q0 Q c) v ∧ IsGLB (elsdValues Q0 Q c) v ∧
IsGLB (weakElsdValues Q0 Q c) v) ∧
-- (iv) dual attainment
((feasibleSet Q0 Q).Nonempty → BddAbove (primalValues Q0 Q c) →
∃ v : ℝ, IsLUB (primalValues Q0 Q c) v ∧
∃ U W, ELSDFeasible Q0 Q c U W ∧ frob (U + W) Q0 = v) := by sorry
end ExactSDPDuality.ELSD
Read-back
What the Lean code literally says, in plain math · claude-opus-5-5
The declaration takes the following data:
- natural numbers and , with no restriction (either may be );
- a real matrix ;
- a family of real matrices, indexed by ;
- a real vector .
It assumes that is symmetric () and that every is symmetric. There are no other hypotheses. It does not assume positive semidefiniteness, feasibility or any constraint qualification.
The statement relies on several objects from the imported definitions module. Their definitions are not shown to this auditor, so this read-back cannot unfold them. It can only say how they are used here:
- is a set of vectors . It is used as the primal feasible set, and is taken for its members.
- , and are sets of real numbers. The statement itself never ties them to , to or to the dual objective. Any such link lives only in the unseen definitions.
- and are two predicates on a pair of real matrices . They are written as and . The statement itself places no symmetry or definiteness condition on and ; any such condition must come from these predicates.
- is a real-valued function of two matrices. It is applied as . Its formula (for instance, whether it is ) is not visible.
The conclusion is the conjunction of four parts.
(i) For every and every pair of real matrices :
and for every and every such :
(ii) If , then both of the following hold:
(iii) Suppose , and at least one of the following holds: some pair satisfies , or some pair satisfies . Then there is a single real number with all three of these properties:
- is the least upper bound of : it is an upper bound of , and it is every upper bound of .
- is the greatest lower bound of .
- is the greatest lower bound of .
These are exact order-theoretic properties, not a or operator with default values. So the conclusion also forces:
- to be nonempty and bounded above;
- and both to be nonempty and bounded below.
The reason is that in no real number is the least upper bound or greatest lower bound of the empty set or of an unbounded set.
(iv) Suppose and is bounded above. Then there is a real that is the least upper bound of . For that , there are real matrices such that:
Part (iv) states attainment only for , not for . It relates the attained value to . It does not state that is also the greatest lower bound of .
All values are real numbers, so an infinite optimal value cannot be expressed as a value. "Finite optimal value" appears only indirectly, as " is bounded above" or as the existence of a real least upper bound.
Degenerate cases.
The hypotheses. The symmetry hypotheses can always be satisfied (for example by all-zero matrices). When they hold automatically, since every matrix is symmetric.
Case . The family is empty and is the empty vector, so for every . Part (i) then says that for every dual-feasible pair, as long as is nonempty.
Case . All matrices, including , and , are the unique empty matrix. What , , , , the two predicates and become in that case depends entirely on the unseen definitions.
When the premises fail.
- If , parts (ii), (iii) and (iv) are vacuously true, and so is part (i).
- If no pair satisfies , the first half of part (i) is vacuous. Likewise, if no pair satisfies , the second half is vacuous.
- If neither dual predicate has a satisfying pair, part (iii) is vacuous.
Total functions with default values. None appear in the statement itself: there is no division, no subtraction in , no integral, no or operator and no extended reals. Any such behaviour inside , , , , or the two feasibility predicates cannot be determined from the code provided.
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.