Theorem 4.1, p. 56 — strong second-order sufficiency and independent binding gradients make the KKT system (4.3) strongly regular
ProvedRobinsonSR.NLP.theorem_4_1Consider the nonlinear program
where are defined on an open set with values in , , , are Fréchet differentiable on , and are twice differentiable at a point . Let and be such that solves the KKT generalized equation
with . Write for the Hessian in . Assume
- (a′) strong second-order sufficiency: for every nonzero with whenever and for all ;
- (b) linear independence: the gradients of the binding inequality constraints () together with all are linearly independent.
Then (4.3) is strongly regular at : for some , the linearisation of (4.3) at has, for all perturbations in a neighbourhood of , a unique solution near , depending -Lipschitz-continuously on the perturbation.
The theorem does not assume strict complementary slackness: weakly active constraints () are allowed, and (a′) is imposed only on the directions annihilated by the gradients of constraints with positive multipliers.
Formalization Note "Differentiable on " is the standing assumption of (4.1); "twice differentiable at " is encoded as differentiability at of each gradient , , . Symmetry of is not assumed; it follows from these hypotheses. Triples carry the Euclidean norm of .
import Mathlib import Definitions.Def_RobinsonSR_NLP_Setting open scoped RealInnerProductSpace Matrix
namespace RobinsonSR.NLP
/-- Theorem 4.1, p. 56: let `θ, g, h` be functions from an open set `Ω ⊆ ℝⁿ` to `ℝ, ℝᵖ, ℝ^q`,
differentiable on `Ω` (the standing assumption of (4.1)) and twice differentiable at `x₀ ∈ Ω`.
Suppose `(x₀, u₀, v₀)` solves (4.3). If the strong second-order sufficient condition (a′) holds
at `(x₀, u₀, v₀)` together with linear independence (b) of the gradients of the binding
constraints, then (4.3) is strongly regular there. -/
theorem theorem_4_1 {n p q : ℕ} (Ω : Set (EuclideanSpace ℝ (Fin n)))
(hΩ : IsOpen Ω) (x0 : EuclideanSpace ℝ (Fin n)) (hx0 : x0 ∈ Ω)
(θ : EuclideanSpace ℝ (Fin n) → ℝ)
(g : EuclideanSpace ℝ (Fin n) → EuclideanSpace ℝ (Fin p))
(h : EuclideanSpace ℝ (Fin n) → EuclideanSpace ℝ (Fin q))
(hθ : DifferentiableOn ℝ θ Ω)
(hg : ∀ i, DifferentiableOn ℝ (fun x => g x i) Ω)
(hh : ∀ j, DifferentiableOn ℝ (fun x => h x j) Ω)
(hθ2 : DifferentiableAt ℝ (gradient θ) x0)
(hg2 : ∀ i, DifferentiableAt ℝ (gradient (fun x => g x i)) x0)
(hh2 : ∀ j, DifferentiableAt ℝ (gradient (fun x => h x j)) x0)
(u0 : EuclideanSpace ℝ (Fin p)) (v0 : EuclideanSpace ℝ (Fin q))
(hsol : -(kktMap θ g h (mk x0 u0 v0)) ∈ RobinsonSR.Reduction.normalCone (kktCone n p q) (mk x0 u0 v0))
(hSSOSC : ∀ y : EuclideanSpace ℝ (Fin n), y ≠ 0 →
(∀ i, 0 < u0 i → ⟪gradient (fun x => g x i) x0, y⟫ = 0) →
(∀ j, ⟪gradient (fun x => h x j) x0, y⟫ = 0) →
0 < ⟪y, lagHess θ g h x0 u0 v0 y⟫)
(hLI : LinearIndependent ℝ
(Sum.elim (fun i : {i : Fin p // g x0 i = 0} => gradient (fun x => g x i) x0)
(fun j : Fin q => gradient (fun x => h x j) x0))) :
StronglyRegularAt (kktMap θ g h) (kktCone n p q) (mk x0 u0 v0) := by sorry
end RobinsonSR.NLP
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.