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
ProvedAugLagLLC.KKT.theorem_4_2Let be a sequence generated by the augmented Lagrangian Algorithm 3.1 for problem (2.1),
with continuously differentiable data. Assume that is a limit point of that satisfies the CPLD constraint qualification with respect to all constraints of (2.1). Then:
- is a KKT point of (2.1): there are , , , , vanishing on the inequality constraints inactive at , with
- If moreover satisfies MFCQ, then for every subsequence converging to the set
is bounded, where and are the first-order multiplier estimates of the algorithm and , 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 is with strictly increasing, and (4.8) is required for every such subsequence. and are the unsafeguarded estimates (3.5), (3.7), not the safeguarded , , which are bounded by construction. The norms in (4.8) are sup norms (the paper's 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 and .
import Mathlib import Definitions.Def_AugLagLLC_KKT_Setting
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
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.