Lemma 1 — minimax equality for convex–concave functions on compact convex sets
ProvedWorstCaseCVaR.Discrete.lemma_1Let and be nonempty compact convex sets, and let be such that
- for each , is convex and lower semicontinuous on ;
- for each , is concave and upper semicontinuous on .
Then has a saddle point :
and therefore
with every minimum and maximum attained.
This is the minimax theorem of Ky Fan (1953) in the form the paper quotes; it is the tool that exchanges the minimization over the threshold with the maximization over the distribution .
Formalization Note The paper states Lemma 1 without the two semicontinuity conditions; they are added because without them the minima and maxima need not exist (on , for and is convex in and constant in , and is not attained). The conclusion is the saddle-point form, which is equivalent to the attained min–max equality. Mission 1 of this series states the same lemma under the name WorstCaseCVaR.Mixture.lemma_1.
import Mathlib
namespace WorstCaseCVaR.Discrete
/-- Lemma 1, Zhu & Fukushima (2009), p. 1157 (Fan 1953): for nonempty compact convex
`𝒳 ⊆ ℝⁿ`, `𝒴 ⊆ ℝᵐ` and `φ(x, y)` convex and lower semicontinuous in `x` for each `y ∈ 𝒴`, concave
and upper semicontinuous in `y` for each `x ∈ 𝒳`, `φ` has a saddle point `(x₀, y₀)` on `𝒳 × 𝒴`;
equivalently, `min_{x ∈ 𝒳} max_{y ∈ 𝒴} φ(x, y) = max_{y ∈ 𝒴} min_{x ∈ 𝒳} φ(x, y)` with every
minimum and maximum attained. The semicontinuity hypotheses are not printed in the paper; they
are needed for the minima and maxima to exist. -/
theorem lemma_1 {n m : ℕ} (X : Set (Fin n → ℝ)) (Y : Set (Fin m → ℝ))
(hXne : X.Nonempty) (hXc : IsCompact X) (hXcv : Convex ℝ X)
(hYne : Y.Nonempty) (hYc : IsCompact Y) (hYcv : Convex ℝ Y)
(φ : (Fin n → ℝ) → (Fin m → ℝ) → ℝ)
(hconv : ∀ y ∈ Y, ConvexOn ℝ X (fun x => φ x y))
(hconc : ∀ x ∈ X, ConcaveOn ℝ Y (fun y => φ x y))
(hlsc : ∀ y ∈ Y, LowerSemicontinuousOn (fun x => φ x y) X)
(husc : ∀ x ∈ X, UpperSemicontinuousOn (fun y => φ x y) Y) :
∃ x₀ ∈ X, ∃ y₀ ∈ Y, ∀ x ∈ X, ∀ y ∈ Y, φ x₀ y ≤ φ x₀ y₀ ∧ φ x₀ y₀ ≤ φ x y₀ := by sorry
end WorstCaseCVaR.Discrete
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.