Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Theorem 4.2, p. 8 — feasible limit points of Algorithm 3.1 satisfying CPLD are KKT points of (2.1); under MFCQ the multiplier estimates are bounded

Proved
AugLagLLC.KKT.theorem_4_2

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

augmented-lagrangiancpldglobal-convergencekktmfcqp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1

Let {xk}k∈N\{x_k\}_{k\in\mathbb N}{xk​}k∈N​ be a sequence generated by the augmented Lagrangian Algorithm 3.1 for problem (2.1),

minimize f(x)subject toh1(x)=0, g1(x)≤0, h2(x)=0, g2(x)≤0,\text{minimize } f(x)\quad\text{subject to}\quad h_1(x)=0,\ g_1(x)\le 0,\ h_2(x)=0,\ g_2(x)\le 0,minimize f(x)subject toh1​(x)=0, g1​(x)≤0, h2​(x)=0, g2​(x)≤0,

with continuously differentiable data. Assume that x∗∈Ω1∩Ω2x_*\in\Omega_1\cap\Omega_2x∗​∈Ω1​∩Ω2​ is a limit point of {xk}\{x_k\}{xk​} that satisfies the CPLD constraint qualification with respect to all constraints of (2.1). Then:

  1. x∗x_*x∗​ is a KKT point of (2.1): there are λ∈Rm1\lambda\in\mathbb R^{m_1}λ∈Rm1​, μ∈R+p1\mu\in\mathbb R^{p_1}_+μ∈R+p1​​, v∈Rm2v\in\mathbb R^{m_2}v∈Rm2​, u∈R+p2u\in\mathbb R^{p_2}_+u∈R+p2​​, vanishing on the inequality constraints inactive at x∗x_*x∗​, with
∇f(x∗)+∑i=1m1λi∇[h1(x∗)]i+∑i=1p1μi∇[g1(x∗)]i+∑i=1m2vi∇[h2(x∗)]i+∑j=1p2uj∇[g2(x∗)]j=0.\nabla f(x_*)+\sum_{i=1}^{m_1}\lambda_i\nabla[h_1(x_*)]_i+\sum_{i=1}^{p_1}\mu_i\nabla[g_1(x_*)]_i+\sum_{i=1}^{m_2}v_i\nabla[h_2(x_*)]_i+\sum_{j=1}^{p_2}u_j\nabla[g_2(x_*)]_j=0 .∇f(x∗​)+i=1∑m1​​λi​∇[h1​(x∗​)]i​+i=1∑p1​​μi​∇[g1​(x∗​)]i​+i=1∑m2​​vi​∇[h2​(x∗​)]i​+j=1∑p2​​uj​∇[g2​(x∗​)]j​=0.
  1. If moreover x∗x_*x∗​ satisfies MFCQ, then for every subsequence {xk}k∈K\{x_k\}_{k\in K}{xk​}k∈K​ converging to x∗x_*x∗​ the set
{∥λk+1∥, ∥μk+1∥, ∥vk∥, ∥uk∥}k∈K(4.8)\{\|\lambda_{k+1}\|,\ \|\mu_{k+1}\|,\ \|v_k\|,\ \|u_k\|\}_{k\in K}\tag{4.8}{∥λk+1​∥, ∥μk+1​∥, ∥vk​∥, ∥uk​∥}k∈K​(4.8)

is bounded, where [λk+1]i=[λˉk]i+ρk[h1(xk)]i[\lambda_{k+1}]_i=[\bar\lambda_k]_i+\rho_k[h_1(x_k)]_i[λk+1​]i​=[λˉk​]i​+ρk​[h1​(xk​)]i​ and [μk+1]i=max⁡{0,[μˉk]i+ρk[g1(xk)]i}[\mu_{k+1}]_i=\max\{0,[\bar\mu_k]_i+\rho_k[g_1(x_k)]_i\}[μk+1​]i​=max{0,[μˉ​k​]i​+ρk​[g1​(xk​)]i​} are the first-order multiplier estimates of the algorithm and vkv_kvk​, uku_kuk​ the lower-level multipliers of Step 2.

The theorem is the main optimality result of the paper: limit points of the method that are feasible are stationary under CPLD, a constraint qualification strictly weaker than MFCQ and LICQ, with no assumption on the penalty parameters.

Formalization Note. "Limit point" is a cluster point of the sequence (MapClusterPt); a subsequence KKK is xφ(j)x_{\varphi(j)}xφ(j)​ with φ\varphiφ strictly increasing, and (4.8) is required for every such subsequence. λk+1\lambda_{k+1}λk+1​ and μk+1\mu_{k+1}μk+1​ are the unsafeguarded estimates (3.5), (3.7), not the safeguarded λˉk+1\bar\lambda_{k+1}λˉk+1​, μˉk+1\bar\mu_{k+1}μˉ​k+1​, which are bounded by construction. The norms in (4.8) are sup norms (the paper's ∥⋅∥\|\cdot\|∥⋅∥ is arbitrary). Both sentences are stated under the theorem's single hypothesis list, as on the page. Problem data, the run, CPLD, MFCQ and KKT are the definitions of AugLagLLC.KKT.Setting and AugLagLLC.KKT.ConstraintQualifications; the constraints of (2.1) are the families h1⊕h2h_1\oplus h_2h1​⊕h2​ and g1⊕g2g_1\oplus g_2g1​⊕g2​.

Preamble
import Mathlib
import Definitions.Def_AugLagLLC_KKT_Setting
Formal statement
namespace AugLagLLC.KKT

open Filter Topology

/-- Theorem 4.2, p. 8: let `{xₖ}` be generated by Algorithm 3.1 and let `xs ∈ Ω₁ ∩ Ω₂` be a limit
point satisfying CPLD with respect to all constraints of (2.1). Then `xs` is a KKT point of (2.1).
Moreover, if `xs` satisfies MFCQ and `x ∘ φ` is any subsequence converging to `xs`, the multiplier
estimates `λₖ₊₁`, `μₖ₊₁`, `vₖ`, `uₖ` (sup norms) are bounded along it ((4.8)). -/
theorem theorem_4_2 {n m1 p1 m2 p2 : ℕ} (P : Problem n m1 p1 m2 p2) (hP : P.IsC1)
    {τ γ ρ1 : ℝ} {lamMin lamMax : Fin m1 → ℝ} {muMax : Fin p1 → ℝ} {ε : ℕ → ℝ}
    (hpar : Problem.IsParams τ γ ρ1 lamMin lamMax muMax ε)
    {x : ℕ → EuclideanSpace ℝ (Fin n)} {ρ : ℕ → ℝ} {lamBar : ℕ → Fin m1 → ℝ}
    {muBar : ℕ → Fin p1 → ℝ} {v : ℕ → Fin m2 → ℝ} {u : ℕ → Fin p2 → ℝ}
    (hrun : P.IsRun τ γ ρ1 lamMin lamMax muMax ε x ρ lamBar muBar v u)
    {xs : EuclideanSpace ℝ (Fin n)} (hlim : MapClusterPt xs atTop x)
    (hfeas : xs ∈ P.Omega1 ∩ P.Omega2)
    (hcpld : CPLDAt (Sum.elim P.h1 P.h2) (Sum.elim P.g1 P.g2) xs) :
    IsKKT P.f (Sum.elim P.h1 P.h2) (Sum.elim P.g1 P.g2) xs ∧
      (MFCQAt (Sum.elim P.h1 P.h2) (Sum.elim P.g1 P.g2) xs →
        ∀ φ : ℕ → ℕ, StrictMono φ → Tendsto (x ∘ φ) atTop (𝓝 xs) →
          ∃ C : ℝ, ∀ j, ‖P.lamNext x ρ lamBar (φ j)‖ ≤ C ∧ ‖P.muNext x ρ muBar (φ j)‖ ≤ C ∧
            ‖v (φ j)‖ ≤ C ∧ ‖u (φ j)‖ ≤ C) := by sorry

end AugLagLLC.KKT
Source
Andreani, Birgin, Martínez & Schuverdt, On augmented Lagrangian methods with general lower-level constraints, HAL hal-01295437v1, p. 8, Theorem 4.2 and (4.8)
Human review
  • Endorsed by Shuze Chen · Oct 7, 2026

    Confirmed by the moderator at approval.

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