Proposition 2.3.1 — weak duality theorem
ProvedModernConvex.ConicDuality.weak_dualityLet be a pointed closed convex cone with nonempty interior, let be an matrix with linearly independent columns (Assumption A), and let , . Consider the conic problem and its dual
The optimal value of (D) is a lower bound on the optimal value of (CP): for every feasible solution of (CP) and every feasible solution of (D),
This is the first and easiest relation between a conic problem and its dual; strong duality (Theorem 2.4.1) builds on it.
Formalization Note The book compares optimal values in ; the Lean statement gives the equivalent pointwise form ( of the dual objective of the primal objective is the same as for every feasible pair, with the conventions , ). The cone conditions (p. 46) and Assumption A (p. 53) are the book's standing assumptions and appear as hypotheses.
import Mathlib import Definitions.Def_ModernConvex_ConicDuality_ConicProblem open Matrix
namespace ModernConvex.ConicDuality
/-- Ben-Tal–Nemirovski, Proposition 2.3.1 (weak duality theorem), p. 52: the optimal value of
`(D) : max { bᵀλ | Aᵀλ = c, λ ≥_{K∗} 0 }` is a lower bound on the optimal value of
`(CP) : min { cᵀx | Ax − b ≥_K 0 }`, stated pointwise: `bᵀλ ≤ cᵀx` for every dual feasible `λ`
and every primal feasible `x`. `K` is a good cone (p. 46) and Assumption A (p. 53) is in force. -/
theorem weak_duality {m n : ℕ} (K : Set (Fin m → ℝ)) (hK : IsGoodCone K)
(A : Matrix (Fin m) (Fin n) ℝ) (hA : AssumptionA A) (b : Fin m → ℝ) (c : Fin n → ℝ) :
∀ (x : Fin n → ℝ) (l : Fin m → ℝ), PrimalFeasible K A b x → DualFeasible K A c l →
b ⬝ᵥ l ≤ c ⬝ᵥ x := by sorry
end ModernConvex.ConicDuality
Read-back
What the Lean code literally says, in plain math · claude-opus-5-5
Let , and let be a good cone. This means four things:
- is nonempty, closed under addition, and closed under multiplication by every real ;
- is pointed: and imply ;
- is topologically closed;
- has nonempty interior.
Let be a real matrix satisfying Assumption A: is injective. Let and be arbitrary.
The statement asserts the following. Take any with (primal feasibility). Take any with and (dual feasibility), where . Then
with dot products .
Degenerate cases.
- No feasible pair. If no primal feasible or no dual feasible exists, the statement is vacuous.
- . Assumption A holds automatically, is empty, and every satisfies . The statement then reads: if , then for every .
- . must be , and Assumption A forces . Both sides are then .
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.