Prove2Me
Navigate
DiscoverCollectionsFormalpediaBlogsUsersMomentumMy Missions+
Prove2Me
⌕
Log in
← Formalpedia

Theorem 4.2, p. 7 — AGP-regularity is the weakest strict constraint qualification associated with AGP

Proved
StrictCQ.AGP.theorem_4_2

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

approximate-gradient-projectionconstraint-qualificationkktp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1sequential-optimality

Let the constraint functions h1,…,hm,g1,…,gph_1,\dots,h_m,g_1,\dots,g_ph1​,…,hm​,g1​,…,gp​ of problem (1.1) be continuously differentiable on Rn\mathbb R^nRn, and let x∗x^*x∗ be a feasible point. Then

x∗ is AGP-regular  ⟺  for every C1 objective f: AGP(−∞) at x∗  ⟹  KKT at x∗.x^*\ \text{is AGP-regular}\iff\text{for every } \mathrm C^1 \text{ objective } f:\ \mathrm{AGP}(-\infty)\text{ at } x^* \implies \text{KKT at } x^*.x∗ is AGP-regular⟺for every C1 objective f: AGP(−∞) at x∗⟹KKT at x∗.

Here AGP-regularity is the outer semicontinuity at (x∗,0)(x^*,0)(x∗,0) of (x,ε)↦NΩ(x,−∞)(x+ε)(x,\varepsilon)\mapsto N_{\Omega(x,-\infty)}(x+\varepsilon)(x,ε)↦NΩ(x,−∞)​(x+ε) (Definition 4.1), and AGP(−∞-\infty−∞) asks for xk→x∗x^k\to x^*xk→x∗ with PΩ(xk,−∞)(xk−∇f(xk))−xk→0P_{\Omega(x^k,-\infty)}(x^k-\nabla f(x^k))-x^k\to0PΩ(xk,−∞)​(xk−∇f(xk))−xk→0 (4.1).

The forward implication says AGP-regularity is a strict constraint qualification for AGP; the backward implication says every property of the constraints under which AGP implies KKT for all objectives implies AGP-regularity, so it is the weakest one.

Formalization Note The paper's "AGP" is AGP(γ\gammaγ) for γ∈[−∞,0)\gamma\in[-\infty,0)γ∈[−∞,0), which Martínez and Svaiter showed to be independent of γ\gammaγ; this paper does not prove that. The goal pins γ=−∞\gamma=-\inftyγ=−∞. The forward direction for every γ∈[−∞,0)\gamma\in[-\infty,0)γ∈[−∞,0) is the separate theorem agp_regular_agp_implies_kkt, and the backward direction for γ=−∞\gamma=-\inftyγ=−∞ is the strongest form, since its hypothesis is only about γ=−∞\gamma=-\inftyγ=−∞. KKT is in multiplier form; the objective is quantified inside the equivalence, for fixed constraints and fixed x∗x^*x∗.

Preamble
import Mathlib
import Definitions.Def_StrictCQ_AGP_Conditions

open Filter Topology InnerProductSpace
Formal statement
namespace StrictCQ.AGP

/-- Theorem 4.2: AGP-regularity is the weakest strict constraint qualification associated with
AGP. AGP is AGP(-∞). -/
theorem theorem_4_2 {n m p : ℕ} (C : Constraints n m p) (hC : C.IsC1)
    (xs : EuclideanSpace ℝ (Fin n)) (hxs : xs ∈ C.feasible) :
    C.AGPRegular xs ↔
      ∀ f : EuclideanSpace ℝ (Fin n) → ℝ, ContDiff ℝ 1 f → C.AGP ⊥ f xs → C.IsKKT f xs := by sorry

end StrictCQ.AGP
Source
Andreani, Martínez, Ramos & Silva, Strict constraint qualifications and sequential optimality conditions for constrained optimization, Optimization Online 5197 (version of November 12, 2015), p. 7, Theorem 4.2
Human review
  • Endorsed by Shuze Chen · Oct 10, 2026

    Confirmed by the moderator at approval.

  • Endorsed by mikedeng1 · Oct 10, 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 paper
SKILL.mdTourFAQContactTerms
© 2026 Prove2Me