Proposition 3.5 — saddle point theorem: a saddle point solves both the primal and the dual problem
ProvedKallMayerSLP.KKT.proposition_3_5Throughout, and are convex and continuously differentiable, the book's standing assumptions for the program
with feasible set .
Let be the Lagrange function of (3.1), and suppose with is a saddle point of , i.e. for all and all . Then
and solves each of these two problems: attains the maximum on the left and attains the minimum on the right.
The saddle point theorem can be read as a strong duality theorem for nonlinear programming: the left-hand side is the dual problem of (3.1), the right-hand side the primal problem.
Formalization Note Both inner optimizations take values in the extended reals (EReal). The conclusion states the equality of the outer supremum and infimum, that maximizes the dual function over , that minimizes the primal function over , and that the two attained values coincide.
Differences from the source:
- encoding: ℝⁿ with zᵀv → EuclideanSpace ℝ (Fin n) with the inner product ⟪z, v⟫ and Mathlib's gradient; reason: Lean convention; the same space and the same gradient for differentiable functions
- encoding: max_{u≥0} inf_x L and min_x sup_{u≥0} L, attained at û and x̂ → EReal-valued dual/primal functions; ⨆_{u≥0} = ⨅_x, IsMaxOn at û, IsMinOn at x̂, equal values; reason: the inner inf and sup may be ∓∞; max/min are a supremum/infimum together with attainment
import Mathlib import Definitions.Def_KallMayerSLP_KKT_IsSaddlePoint import Definitions.Def_KallMayerSLP_KKT_dualFunction import Definitions.Def_KallMayerSLP_KKT_primalFunction
namespace KallMayerSLP.KKT
/-- **Proposition 3.5 (saddle point theorem).**
Kall & Mayer, *Stochastic Linear Programming* (2005), Chapter 1, §3.1, Proposition 3.5, p.66 (PDF 77): "If for the Lagrange function to (3.1) there exists a
saddle point `(x̂, û ≥ 0)`, then
`max_{u≥0} inf_{x∈ℝⁿ} L(x, u) = min_{x∈ℝⁿ} sup_{u≥0} L(x, u)`, (3.7)
and `(x̂, û)` solves each of these two problems."
Here `f` and every `gᵢ` are convex on `ℝⁿ` and continuously differentiable (`ContDiff ℝ 1`), the
book's standing assumptions for (3.1) (p.61 and p.62), and `(x̂, û)` is a saddle point in the sense of (3.6).
**Formalization Note.** `inf_x L(x, u)` (`dualFunction`) and `sup_{u≥0} L(x, u)`
(`primalFunction`) take values in `EReal`. The conclusion has four conjuncts: the supremum over
`u ≥ 0` of the dual function equals the infimum over `x` of the primal function; `û` maximizes the
dual function over `u ≥ 0` and `x̂` minimizes the primal function over `ℝⁿ` (so the `max` and the
`min` of (3.7) are attained, at `û` and `x̂`); and the two attained values coincide. -/
theorem proposition_3_5 {n m : ℕ} (f : EuclideanSpace ℝ (Fin n) → ℝ) (g : Fin m → EuclideanSpace ℝ (Fin n) → ℝ)
(hf : ConvexOn ℝ Set.univ f) (hg : ∀ i, ConvexOn ℝ Set.univ (g i))
(hf1 : ContDiff ℝ 1 f) (hg1 : ∀ i, ContDiff ℝ 1 (g i))
(xh : EuclideanSpace ℝ (Fin n)) (uh : Fin m → ℝ) (h : IsSaddlePoint f g xh uh) :
((⨆ (u : Fin m → ℝ) (_ : 0 ≤ u), dualFunction f g u) = ⨅ x, primalFunction f g x) ∧
IsMaxOn (dualFunction f g) {u | 0 ≤ u} uh ∧
IsMinOn (primalFunction f g) Set.univ xh ∧
dualFunction f g uh = primalFunction f g xh := by sorry
end KallMayerSLP.KKT
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.