Proof of Proposition 2 — weak duality for (22)–(23):
ProvedWorstCaseCVaR.Box.weak_dualitydualitylinear-programmingp2o-batch-pfp2bp2o-gran-per-chapterp2o-plan-paperp2o-v1
Let . For every feasible point of the linear program (22) and every feasible point of its dual (23) with the same ,
Consequently, if (22) is feasible, then for every feasible of (23).
This is the inequality used in the first half of the proof of Proposition 2 to show that a feasible point of (24)–(30) yields a feasible point of (16)–(20).
Formalization Note The second clause assumes (22) feasible because is a real supremum, whose value on an empty set is the junk value .
Preamble
import Mathlib import Definitions.Def_WorstCaseCVaR_Box_DualPair open Matrix
Formal statement
namespace WorstCaseCVaR.Box
/-- Proof of Proposition 2, p. 1167: weak duality for the pair (22)–(23). Every feasible `η`
of (22) and every feasible `(z, ξ, ω)` of (23) with the same `u` satisfy
`uᵀη ≤ η̄ᵀξ + η̲ᵀω`; consequently, when (22) is feasible, `γ*(u) ≤ η̄ᵀξ + η̲ᵀω`. -/
theorem weak_duality {S : ℕ} (ηlo ηhi u : Fin S → ℝ) :
(∀ η ∈ lp22Feasible ηlo ηhi, ∀ d ∈ lp23Feasible u, u ⬝ᵥ η ≤ lp23Obj ηlo ηhi d) ∧
((lp22Feasible ηlo ηhi).Nonempty →
∀ d ∈ lp23Feasible u, gammaStar ηlo ηhi u ≤ lp23Obj ηlo ηhi d) := by sorry
end WorstCaseCVaR.Box
Source
Zhu & Fukushima, Worst-Case Conditional Value-at-Risk with Application to Robust Portfolio Management, Oper. Res. 57(5), 2009, p. 1167, proof of Proposition 2
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.