Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Concavity of the dual function

Proved
ConvexOptimization.dualFunction_concave

by Shuze Chen · Aug 12, 2026 · Mathlib 0df444a (Lean v4.33.1)

convexoptimizationdualitykkt

The Lagrange dual function is concave, whatever the problem it comes from.

For the standard problem with objective f0f_0f0​, inequality-constraint functions fif_ifi​ and equality data (aj,bj)(a_j, b_j)(aj​,bj​), let

g(λ,ν)  =  inf⁡x∈Rn[f0(x)+∑i=1mλifi(x)+∑j=1pνj(⟨aj,x⟩−bj)]  ∈  [−∞,+∞].g(\lambda,\nu) \;=\; \inf_{x \in \mathbb{R}^n}\Bigl[f_0(x) + \sum_{i=1}^{m}\lambda_i f_i(x) + \sum_{j=1}^{p}\nu_j(\langle a_j,x\rangle - b_j)\Bigr] \;\in\; [-\infty,+\infty].g(λ,ν)=x∈Rninf​[f0​(x)+i=1∑m​λi​fi​(x)+j=1∑p​νj​(⟨aj​,x⟩−bj​)]∈[−∞,+∞].

Then for all multiplier pairs (λ1,ν1)(\lambda_1,\nu_1)(λ1​,ν1​), (λ2,ν2)(\lambda_2,\nu_2)(λ2​,ν2​) and every θ∈(0,1)\theta \in (0,1)θ∈(0,1),

θ g(λ1,ν1)+(1−θ) g(λ2,ν2)  ≤  g(θλ1+(1−θ)λ2, θν1+(1−θ)ν2),\theta\, g(\lambda_1,\nu_1) + (1-\theta)\, g(\lambda_2,\nu_2) \;\le\; g\bigl(\theta\lambda_1 + (1-\theta)\lambda_2,\ \theta\nu_1 + (1-\theta)\nu_2\bigr),θg(λ1​,ν1​)+(1−θ)g(λ2​,ν2​)≤g(θλ1​+(1−θ)λ2​, θν1​+(1−θ)ν2​),

the inequality being read in the extended reals.

Concavity holds with no convexity assumption whatsoever on f0f_0f0​ or the fif_ifi​: ggg is a pointwise infimum of functions that are affine in (λ,ν)(\lambda,\nu)(λ,ν), and such an infimum is always concave. This is why the dual problem — maximize ggg over λ⪰0\lambda \succeq 0λ⪰0 — is a convex problem even when the primal is not, and it is the reason duality is useful for hard nonconvex problems.

Formalization Note ggg is EReal-valued, so the convex combination is formed with EReal scalar multiplication and the statement avoids any finiteness hypothesis; the degenerate cases g=−∞g = -\inftyg=−∞ are covered by the arithmetic of the extended reals. Source: B&V §5.1.2, p. 216.

Preamble
import Mathlib
import Definitions.Def_ConvexOptimization_lagrangeDuality

open scoped RealInnerProductSpace ENNReal
open MeasureTheory

Formal statement
theorem ConvexOptimization.dualFunction_concave {n mm p : ℕ}
    (f₀ : EuclideanSpace ℝ (Fin n) → ℝ)
    (fc : Fin mm → EuclideanSpace ℝ (Fin n) → ℝ)
    (a : Fin p → EuclideanSpace ℝ (Fin n)) (b : Fin p → ℝ)
    (lam₁ lam₂ : Fin mm → ℝ) (nu₁ nu₂ : Fin p → ℝ)
    (θ : ℝ) (hθ0 : 0 < θ) (hθ1 : θ < 1) :
    (θ : EReal) * dualFunction f₀ fc a b lam₁ nu₁ +
      ((1 - θ : ℝ) : EReal) * dualFunction f₀ fc a b lam₂ nu₂ ≤
    dualFunction f₀ fc a b
      (fun i => θ * lam₁ i + (1 - θ) * lam₂ i)
      (fun j => θ * nu₁ j + (1 - θ) * nu₂ j) := by
  sorry
Source
Boyd & Vandenberghe 2004, Convex Optimization, Cambridge University Press (seventh printing with corrections, 2009), https://web.stanford.edu/~boyd/cvxbook/, pp. 216, §5.1.2 (the dual function is concave, whatever the primal problem)

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