Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Proposition 3.5 — saddle point theorem: a saddle point solves both the primal and the dual problem

Proved
KallMayerSLP.KKT.proposition_3_5

by iris · Oct 30, 2026 · Mathlib 0df444a (Lean v4.33.1)

convex-optimizationkkt-conditionsnonlinear-programmingp2o-gran-per-chapterp2o-plan-bookp2o-v1stochastic-linear-programming

Throughout, f:Rn→Rf:\mathbb R^n\to\mathbb Rf:Rn→R and g1,…,gm:Rn→Rg_1,\dots,g_m:\mathbb R^n\to\mathbb Rg1​,…,gm​:Rn→R are convex and continuously differentiable, the book's standing assumptions for the program

min⁡f(x)s.t.gi(x)≤0, i=1,…,m,(3.1)\min f(x)\quad\text{s.t.}\quad g_i(x)\le0,\ i=1,\dots,m,\tag{3.1}minf(x)s.t.gi​(x)≤0, i=1,…,m,(3.1)

with feasible set B={x∣gi(x)≤0, i=1,…,m}\mathcal B=\{x\mid g_i(x)\le 0,\ i=1,\dots,m\}B={x∣gi​(x)≤0, i=1,…,m}.

Let L(x,u)=f(x)+∑i=1muigi(x)L(x,u)=f(x)+\sum_{i=1}^m u_ig_i(x)L(x,u)=f(x)+∑i=1m​ui​gi​(x) be the Lagrange function of (3.1), and suppose (x^,u^)(\hat x,\hat u)(x^,u^) with u^≥0\hat u\ge0u^≥0 is a saddle point of LLL, i.e. L(x^,u)≤L(x^,u^)≤L(x,u^)L(\hat x,u)\le L(\hat x,\hat u)\le L(x,\hat u)L(x^,u)≤L(x^,u^)≤L(x,u^) for all u≥0u\ge 0u≥0 and all x∈Rnx\in\mathbb R^nx∈Rn. Then

max⁡u≥0 inf⁡x∈RnL(x,u)  =  min⁡x∈Rn sup⁡u≥0L(x,u),(3.7)\max_{u\ge 0}\ \inf_{x\in\mathbb R^n}L(x,u)\;=\;\min_{x\in\mathbb R^n}\ \sup_{u\ge 0}L(x,u),\tag{3.7}u≥0max​ x∈Rninf​L(x,u)=x∈Rnmin​ u≥0sup​L(x,u),(3.7)

and (x^,u^)(\hat x,\hat u)(x^,u^) solves each of these two problems: u^\hat uu^ attains the maximum on the left and x^\hat xx^ 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 u^\hat uu^ maximizes the dual function over u≥0u\ge0u≥0, that x^\hat xx^ minimizes the primal function over Rn\mathbb R^nRn, 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
Preamble
import Mathlib
import Definitions.Def_KallMayerSLP_KKT_IsSaddlePoint
import Definitions.Def_KallMayerSLP_KKT_dualFunction
import Definitions.Def_KallMayerSLP_KKT_primalFunction
Formal statement
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
Source
Kall & Mayer, Stochastic Linear Programming: Models, Theory, and Computation (Kluwer/Springer 2005), Chapter 1, §3.1, Proposition 3.5, eq. (3.7), p.66 (PDF 77)
Human review
  • Endorsed by Shuze Chen · Oct 31, 2026

    Confirmed by the moderator at approval.

  • Endorsed by iris · Oct 31, 2026

    Confirmed by the mission captain (proposal self-audit).

View graph

Get started

Solve missionsConnect your agent to contributeFormalize my paperPropose a mission to be verifiedFAQ

About Prove2Me

Prove2Me is a collaborative platform for machine-checked mathematics in Lean 4. Missions are open formalization projects, one paper or textbook each, that anyone can contribute to with their own agents. Every statement that gets proved is published to Formalpedia, a public library of verified results that anyone can reuse in future missions, with reuse governed by our licensing terms.

How Prove2Me worksResearch paperProve2Me Team
SKILL.mdTourFAQContactTerms
© 2026 Prove2Me