(4.11)–(4.15), proof of Theorem 4.2, pp. 9–10 — approximate KKT sequences converge to KKT points under CPLD
ProvedAugLagLLC.KKT.cpld_limit_kktConsider the nonlinear program "minimize subject to (), ()" on with finite index sets and continuously differentiable , , . Let be feasible and satisfy the CPLD condition, and let . Suppose there are coefficients and such that, for every ,
- for all , and whenever ;
- the residual tends to zero:
Then is a KKT point of the program.
This is the core of Theorem 4.2 with the algorithm abstracted away: by (4.9) and (4.10), the iterates of Algorithm 3.1 along a subsequence converging to satisfy (4.11), which is exactly the hypothesis above with , the equality constraints , the inequality constraints , and , .
Formalization Note. The paper's index sets ", " are re-indexed as the whole sequence . The sign and support conditions on refer to the constraints inactive at the limit , as in (4.11), not at . CPLD and KKT are the definitions of AugLagLLC.KKT.ConstraintQualifications.
import Mathlib import Definitions.Def_AugLagLLC_KKT_ConstraintQualifications
namespace AugLagLLC.KKT
open Filter Topology
/-- (4.11)–(4.15), proof of Theorem 4.2, pp. 9–10, without the algorithm: let `F`, `H i`, `G j`
be `C¹`, let `xs` be feasible and satisfy CPLD, and let `yₖ → xs`. If there are coefficients
`aₖ` (free) and `bₖ ≥ 0`, with `[bₖ]ⱼ = 0` for every constraint inactive at `xs`, such that
`∇F(yₖ) + ∑ᵢ [aₖ]ᵢ ∇Hᵢ(yₖ) + ∑ⱼ [bₖ]ⱼ ∇Gⱼ(yₖ) → 0`, then `xs` is a KKT point. -/
theorem cpld_limit_kkt {n : ℕ} {ι κ : Type*} [Fintype ι] [Fintype κ]
{F : EuclideanSpace ℝ (Fin n) → ℝ} {H : ι → EuclideanSpace ℝ (Fin n) → ℝ}
{G : κ → EuclideanSpace ℝ (Fin n) → ℝ}
(hF : ContDiff ℝ 1 F) (hH : ∀ i, ContDiff ℝ 1 (H i)) (hG : ∀ j, ContDiff ℝ 1 (G j))
{xs : EuclideanSpace ℝ (Fin n)} (hHx : ∀ i, H i xs = 0) (hGx : ∀ j, G j xs ≤ 0)
(hcpld : CPLDAt H G xs)
{y : ℕ → EuclideanSpace ℝ (Fin n)} (hy : Tendsto y atTop (𝓝 xs))
(a : ℕ → ι → ℝ) (b : ℕ → κ → ℝ) (hb : ∀ k j, 0 ≤ b k j)
(hbG : ∀ k j, G j xs < 0 → b k j = 0)
(hres : Tendsto (fun k => gradient F (y k) + ∑ i, a k i • gradient (H i) (y k)
+ ∑ j, b k j • gradient (G j) (y k)) atTop (𝓝 0)) :
IsKKT F H G xs := by sorry
end AugLagLLC.KKT
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.