Theorem 2.1, Weak duality, p. 4 — cᵀx − bᵀy = xᵀs ≥ 0 for feasible x and (y, s)
ProvedConicQuadIPM.Homogeneous.weak_dualityConsider the conic primal–dual pair : and : , where is a pointed closed convex cone and its dual cone.
If is feasible for and is feasible for , then
The difference is the duality gap and the complementarity gap; weak duality says the two coincide on feasible points and are nonnegative, so every dual objective value bounds every primal objective value from below.
Formalization Note is Fin n → ℝ, is the dot product u ⬝ᵥ v, is A *ᵥ x and is Aᵀ *ᵥ y; the paper's first coordinate is index 0. The standing assumption that is a pointed closed convex cone is carried as the hypothesis IsPointedClosedConvexCone K. The paper's additional assumption that has full row rank ("for convenience and without loss of generality", p. 4) is not imposed, so the statement is a (harmless) generalization.
import Mathlib import Definitions.Def_ConicQuadIPM_Homogeneous_Setting
namespace ConicQuadIPM.Homogeneous
open Matrix
/-- Theorem 2.1, Weak duality (p. 4): for `x` feasible for (P) and `(y, s)` feasible for (D),
`cᵀx − bᵀy = xᵀs ≥ 0`. -/
theorem weak_duality {m n : ℕ} (A : Matrix (Fin m) (Fin n) ℝ) (b : Fin m → ℝ) (c : Fin n → ℝ)
(K : Set (Fin n → ℝ)) (hK : IsPointedClosedConvexCone K)
(x : Fin n → ℝ) (y : Fin m → ℝ) (s : Fin n → ℝ)
(hx : PrimalFeasible A b K x) (hys : DualFeasible A c K y s) :
c ⬝ᵥ x - b ⬝ᵥ y = x ⬝ᵥ s ∧ 0 ≤ x ⬝ᵥ s := by sorry
end ConicQuadIPM.Homogeneous
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.