Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Theorem 3.1(i), p. 483 — x ∈ dom h solves min(g − h) if and only if ∂_εh(x) ⊂ ∂_εg(x) for every ε > 0

Proved
TaoAnDCA.GlobalOpt.theorem_3_1_i

by mikedeng1 · Oct 6, 2026 · Mathlib 0df444a (Lean v4.33.1)

dc-programmingepsilon-subdifferentialglobal-optimalityp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1

Let g,h:Rn→R∪{+∞}g,h:\mathbb R^n\to\mathbb R\cup\{+\infty\}g,h:Rn→R∪{+∞} be proper, lower semicontinuous and convex, and assume the inclusions

dom⁡g⊂dom⁡h,dom⁡h∗⊂dom⁡g∗,\operatorname{dom}g\subset\operatorname{dom}h,\qquad\operatorname{dom}h^*\subset\operatorname{dom}g^*,domg⊂domh,domh∗⊂domg∗,

where h∗,g∗h^*,g^*h∗,g∗ are the conjugate functions. Consider the d.c. program

(P)α=inf⁡{g(x)−h(x):x∈Rn}\text{(P)}\qquad \alpha=\inf\{g(x)-h(x):x\in\mathbb R^n\}(P)α=inf{g(x)−h(x):x∈Rn}

with the convention +∞−(+∞)=+∞+\infty-(+\infty)=+\infty+∞−(+∞)=+∞, and let P\mathcal PP be its set of solutions. For ε>0\varepsilon>0ε>0 let ∂εθ(x)\partial_\varepsilon\theta(x)∂ε​θ(x) denote the ε\varepsilonε-subdifferential of a convex function θ\thetaθ at x∈dom⁡θx\in\operatorname{dom}\thetax∈domθ.

Then for every x∈dom⁡hx\in\operatorname{dom}hx∈domh,

x∈P  ⟺  ∂εh(x)⊂∂εg(x)∀ε>0.x\in\mathcal P\iff \partial_\varepsilon h(x)\subset\partial_\varepsilon g(x)\quad\forall\varepsilon>0.x∈P⟺∂ε​h(x)⊂∂ε​g(x)∀ε>0.

This is the global optimality condition for d.c. programs, first established by Hiriart-Urruty; the paper gives a short proof through the d.c. duality. It characterizes global minimizers of a nonconvex objective by inclusions between convex objects.

Formalization Note The paper states (i) for every xxx; its proof argues for x∗∈dom⁡hx^*\in\operatorname{dom}hx∗∈domh. The statement is restricted to x∈dom⁡hx\in\operatorname{dom}hx∈domh because for x∉dom⁡hx\notin\operatorname{dom}hx∈/domh the set ∂εh(x)\partial_\varepsilon h(x)∂ε​h(x) is empty, so the right-hand side holds vacuously while x∉Px\notin\mathcal Px∈/P, and the unrestricted statement would be false. The restriction loses nothing: every solution lies in dom⁡g⊂dom⁡h\operatorname{dom}g\subset\operatorname{dom}hdomg⊂domh, and for x∈dom⁡h∖dom⁡gx\in\operatorname{dom}h\setminus\operatorname{dom}gx∈domh∖domg both sides are false. The ε\varepsilonε-subdifferential is empty outside the domain, as in the paper's definition; the difference g−hg-hg−h uses the convention +∞−(+∞)=+∞+\infty-(+\infty)=+\infty+∞−(+∞)=+∞ (dcSub). The standing assumptions (g,h∈Γ0g,h\in\Gamma_0g,h∈Γ0​ and the inclusions (3), assumed throughout the paper) are hypotheses; finiteness of α\alphaα is not assumed.

Preamble
import Mathlib
import Definitions.Def_TaoAnDCA_GlobalOpt_Setting

open TaoAnDCA.GlobalOpt
Formal statement
namespace TaoAnDCA.GlobalOpt

theorem theorem_3_1_i {n : ℕ} (g h : EuclideanSpace ℝ (Fin n) → EReal)
    (hgh : DCStanding g h) (x : EuclideanSpace ℝ (Fin n)) (hx : x ∈ effDom h) :
    x ∈ primalSol g h ↔ ∀ ε : ℝ, 0 < ε → epsSubdiff h ε x ⊆ epsSubdiff g ε x := by sorry

end TaoAnDCA.GlobalOpt
Source
Pham Dinh & Le Thi, A d.c. optimization algorithm for solving the trust-region subproblem, SIAM J. Optim. 8 (1998), p. 483, Theorem 3.1(i)
Human review
  • Endorsed by Shuze Chen · Oct 6, 2026

    Confirmed by the moderator at approval.

  • Endorsed by mikedeng1 · Oct 6, 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