Chapter 12 — Sequential Quadratic Programming
Proofs omitted. Hover over highlighted terms to see their Lean types.
Exercise 12.1
Lean contributors (project-level attribution): Chenyi Li, Wanli Ma, Zichen Wang.
Chapter12 Exercise 12.1 (1): the first unit-step Lagrange-Newton iterate for the constrained Rosenbrock problem with initial state ((4 / 5, 3 / 5)^T, 1) is ((9 / 10, 4 / 5)^T, 0).
local notation "Multiplier" => LagrangeNewtonMultiplier 1
local notation "State" => rosenbrockPoint × Multiplier
-- Domain sampling:
-- * primary domain: equality-constrained Lagrange-Newton steps for a concrete Rosenbrock
-- exercise with one scalar constraint;
-- * inspected owner declarations:
-- `EqualityConstrainedProblem` from `Chapter12.EqualityConstrainedProblem`;
-- `lagrangeNewtonTrialPoint` / `lagrangeNewtonTrialMultiplier` from
-- `Chapter12.Algorithm_12_1_1`;
-- `lagrangeNewtonDirectionEquation` from `Chapter12.Theorem_12_1_2`;
-- the shared Rosenbrock carrier/objective owner `rosenbrockPoint` / `rosenbrockFunction`
-- from `Chapter03.Exercise_3_4`.
-- Source/core/bridge triage:
-- * source-facing: the concrete Rosenbrock exercise data and its first three iterates;
-- * core/canonical: the Chapter 12 owner `EqualityConstrainedProblem 2 1` together with the
-- generic trial-update surface `lagrangeNewtonTrialPoint` / `lagrangeNewtonTrialMultiplier`;
-- * bridge/view: the source scalar multiplier `λ` viewed in the canonical one-constraint
-- multiplier space `EuclideanSpace ℝ (Fin 1)`.
theorem rosenbrockExercise_firstIterate :
rosenbrockExerciseLagrangeNewtonStep rosenbrockExerciseInitialState =
rosenbrockExerciseFirstIterateExercise 12.2
— source only (outside the published documentation root) (Lean source)
Lean contributors (project-level attribution): Chenyi Li, Wanli Ma, Zichen Wang.
Chapter12 Exercise 12.2, first candidate: at stage k, choose the comparison vector B_k s_k, so ȳ_k = α • y_k + β • (B_k s_k).
theorem WilsonHanPowellMethod.dampedBfgsModifiedSecantVectorAt_eq_hessianStepImage {n m : ℕ}
(method : WilsonHanPowellMethod n m) (α β : ℝ) (k : ℕ) :
method.dampedBfgsModifiedSecantVectorAt α β k (method.hessianStepImageAt k) =
α • method.gradientDifferenceAt k + β • method.hessianStepImageAt k
Exercise 12.3
— source only (outside the published documentation root) (Lean source)
Lean contributors (project-level attribution): Chenyi Li, Wanli Ma, Zichen Wang.
Chapter12 Exercise 12.3 records the same source-facing equivalence as hasSuperlinearlyConvergentStep_iff_projectedStationarityResidualRatio_tendsto_zero, now reused directly from the canonical Corollary 12.3.4 owner.
#check hasSuperlinearlyConvergentStep_iff_projectedStationarityResidualRatio_tendsto_zero
Exercise 12.4
Lean contributors (project-level attribution): Chenyi Li, Wanli Ma, Zichen Wang.
Chapter12 Exercise 12.4: if (d(σ), θ(σ)) solves the θ-relaxed SQP subproblem at two ordered penalty parameters σ₁ ≤ σ₂, then θ(σ) is nondecreasing. The hypotheses use the chapter's canonical augmented WilsonHanPowellSubproblem owner.
variable {n m me mi : ℕ}
local notation "Point" => EuclideanSpace ℝ (Fin n)
local notation "ConstraintPoint" => EuclideanSpace ℝ (Fin m)
local notation "MatrixN" => Matrix (Fin n) (Fin n) ℝ
local notation "Jacobian" => Matrix (Fin n) (Fin m) ℝ
local notation "RelaxedStep" => Point × ℝ
local notation "AugmentedDirection" => Fin (n + 1) → ℝ
-- Domain sampling for this refine pass:
-- * primary domain: mixed equality/inequality SQP quadratic subproblems with a `θ`-relaxed
-- feasibility-restoration variable;
-- * inspected project owners/views for the same constraint-splitting and solution notions:
-- `feasibleConstraintValueSet`,
-- `StandardPenaltyProblem`,
-- `StandardPenaltyProblem.wilsonHanPowellSubproblem`,
-- and `WilsonHanPowellSubproblem.IsSolution`;
-- * best owner abstraction:
-- `StandardPenaltyProblem` fixes the canonical equality/inequality split datum `eqCount ≤ m`,
-- while `WilsonHanPowellSubproblem` is the canonical quadratic-model owner for the subproblem
-- itself;
-- * primitive data vs. derived API:
-- the primitive source-facing data retained here are the textbook objective
-- `gᵀ d + (1 / 2) dᵀ B d + σ (1 - θ)^2`, the linearized constraint vector
-- `Aᵀ d + θ c`, the bounds `0 ≤ θ ≤ 1`, and the augmented-variable embedding `(d, θ) ↦ (d, θ)`;
-- the mixed equality/inequality block decomposition is determined by the explicit source
-- hypothesis `eqCount ≤ m`, rather than by clipping `eqCount` with `min`;
-- * source/core/bridge triage:
-- the textbook `(d, θ)` presentation is `bridge/view`,
-- `WilsonHanPowellSubproblem` is `core/canonical`,
-- and the augmented block data below are the minimal bridge to that owner.
-- This file therefore deletes the parallel local feasibility/optimality owner and presents the
-- exercise through an augmented `WilsonHanPowellSubproblem`, with source-facing `(d, θ)`
-- statements kept only as bridge theorems.
theorem thetaSolution_nondecreasing_of_thetaRelaxedWilsonHanPowellSubproblem_isSolution
(eqCount : ℕ) (hEqCount : eqCount ≤ m) (c : ConstraintPoint) (g : Point)
(A : Jacobian) (B : MatrixN)
(d : ℝ → Point) (θ : ℝ → ℝ)
{σ₁ σ₂ : ℝ}
(hσ : σ₁ ≤ σ₂)
(hsol₁ :
(thetaRelaxedWilsonHanPowellSubproblem eqCount hEqCount c g A B σ₁).IsSolution
(relaxedStepToDirection (d σ₁, θ σ₁)))
(hsol₂ :
(thetaRelaxedWilsonHanPowellSubproblem eqCount hEqCount c g A B σ₂).IsSolution
(relaxedStepToDirection (d σ₂, θ σ₂))) :
θ σ₁ ≤ θ σ₂Exercise 12.5
— source only (outside the published documentation root) (Lean source)
Lean contributors (project-level attribution): Chenyi Li, Wanli Ma, Zichen Wang.
Exercise 12.5 as an equality-constrained problem with objective exercise125Objective and the single equality constraint exercise125Constraint.
local notation "Point" => LagrangeNewtonPoint local notation "Multiplier" => LagrangeNewtonMultiplier -- Domain-style sampling for this file: -- * primary domain: concrete equality-constrained SQP, exact-penalty, and second-order -- correction constructions; -- * inspected owner declarations: -- `EqualityConstrainedProblem`, -- `exercise125Problem.toStandardPenaltyProblem.l1ExactPenalty`, -- `isSqpSubproblemSolution`, -- `IsSecondOrderCorrectionSubproblemSolution`; -- * core/canonical owner: the chapter's equality-constrained problem together with its SQP -- subproblem and exact-penalty surfaces; -- * source-facing data kept here: the concrete objective, constraint, path, and explicit -- Exercise 12.5 step formulas. def exercise125Problem : EqualityConstrainedProblem 2 1
Exercise 12.6
— source only (outside the published documentation root) (Lean source)
Lean contributors (project-level attribution): Chenyi Li, Wanli Ma, Zichen Wang.
Chapter12 Exercise 12.6: for every positive penalty parameter σ, every β ∈ (0, 1 / 2), every fixed Chapter 12 watchdog method method, and every fixed stage-1 model sequence hessianApprox, there is a threshold δ > 0 such that whenever 0 < ε < δ, that watchdog run with Maratos data x₁ = maratosPath ε, d₁ = maratosStep ε, α₁ = 1, and x₁ + α₁ d₁ = maratosTrialPoint ε satisfies the specialized Step-3 sufficient-reduction condition SR_[σ, β, method.iterate, hessianApprox], and therefore switches to relaxed mode at stage 2 and keeps maratosTrialPoint ε as the next iterate, even though the usual L₁ exact penalty function increases there. In this sense the watchdog technique can overcome the Maratos effect.
local notation "Point" => EuclideanSpace ℝ (Fin 2)
local notation "PenaltyWeights" => EuclideanSpace ℝ (Fin 1)
local notation "Matrix2" => Matrix (Fin 2) (Fin 2) ℝ
open scoped StandardPenaltyProblem
local notation:max "P_" σ =>
P_[maratosProblem.toStandardPenaltyProblem] (maratosPenaltyWeights σ)
local notation:max "SR_[" σ ", " β ", " iterate ", " hessianApprox "]" =>
StandardPenaltyProblem.IsWatchdogSufficientReduction
maratosProblem.toStandardPenaltyProblem
(maratosPenaltyWeights σ)
β
iterate
hessianApprox
1
1
theorem watchdogTechnique_overcomesMaratosEffect
{σ β : ℝ} (hσ : 0 < σ) (hβ : β ∈ Set.Ioo (0 : ℝ) ((1 / 2 : ℝ)))
(method : WatchdogMethod 2)
(hessianApprox : ℕ → Matrix2) :
∃ δ > 0, ∀ {ε : ℝ} (hε : 0 < ε) (hεδ : ε < δ)
(hRun : maratosWatchdogRunAt σ β ε method hessianApprox),
SR_[σ, β, method.iterate, hessianApprox] ∧
WatchdogOvercomesMaratosEffectAt σ ε method
Exercise 12.7
— source only (outside the published documentation root) (Lean source)
Lean contributors (project-level attribution): Chenyi Li, Wanli Ma, Zichen Wang.
Exercise 12.7 as the equality-constrained problem with objective exercise127Objective and single equality constraint exercise127Constraint.
open Filter local notation "Point" => LagrangeNewtonPoint 2 local notation "Multiplier" => LagrangeNewtonMultiplier 1 local notation "Reduced" => LagrangeNewtonPoint 1 -- Domain sampling for this refine pass: -- * primary domain: Chapter 12 reduced-Hessian iterations for equality-constrained problems; -- * sampled owner declarations: -- `EqualityConstrainedProblem.constraintVector`, -- `EqualityConstrainedProblem.constraintGradientMatrix`, -- the single-constraint companion pattern from `Exercise_12_5`, -- `IsReducedNullMap` and `IsReducedHessianStep` from `Theorem_12_8_1`, -- `HasSuperlinearlyConvergentStep` from `Definition_12_3_extra_1`, -- and mathlib's `=O[atTop]`; -- * source-facing layer kept here: the concrete Exercise 12.7 objective, scalar constraint, -- its denominator-safe domain, the iterate recursion, and the one-fast-one-slow convergence -- conclusion; -- * core/canonical layer reused here: the chapter owners `EqualityConstrainedProblem` and -- `IsReducedHessianStep`, mathlib's `gradient`, and the standard gradient-matrix owner -- `exercise127Problem.constraintGradientMatrix` viewed through `Matrix.toEuclideanLin`; -- * primitive data vs derived API: -- primitive/source data are the concrete objective, scalar equality constraint, denominator -- domain, iterate recursion, and solution; -- derived API are the concrete owner `exercise127Problem` and its single-constraint vector -- and gradient-matrix views `exercise127Problem.constraintVector` and -- `exercise127Problem.constraintGradientMatrix`; -- * bridge/view layer here: the equality-constrained owner's canonical gradient matrix viewed -- as a Euclidean linear map through `Matrix.toEuclideanLin`. noncomputable def exercise127Problem : EqualityConstrainedProblem 2 1
12.1 — Lagrange-Newton Method
Algorithm 12.1.1
Lean contributors (project-level attribution): Chenyi Li, Wanli Ma, Zichen Wang.
Chapter12 Algorithm 12.1.1: a source-facing owner over a primal ℝ-module Point and multiplier ℝ-module Multiplier. The textbook ℝ^n × ℝ^m presentation is recovered by specializing to LagrangeNewtonPoint n and LagrangeNewtonMultiplier m. It records an initial primal point x₁, an initial multiplier λ₁, a line-search parameter β ∈ (0, 1), and a tolerance ε ≥ 0. At each stage k ≥ 1, Step 2 evaluates the source merit function P (x_k, λ_k) and stops when P (x_k, λ_k) ≤ ε; otherwise (δx)_k and (δλ)_k are the Newton directions obtained by solving (12.1.6). Step 3 starts from α = 1, repeatedly replaces α by α / 4 until (12.1.11) holds, and Step 4 updates x_(k + 1) = x_k + α (δx)_k and λ_(k + 1) = λ_k + α (δλ)_k.
variable {Point Multiplier : Type*}
variable [AddCommGroup Point] [Module ℝ Point]
variable [AddCommGroup Multiplier] [Module ℝ Multiplier]
structure LagrangeNewtonMethod (Point Multiplier : Type*)
[AddCommGroup Point] [Module ℝ Point]
[AddCommGroup Multiplier] [Module ℝ Multiplier] where
meritFunction : Point → Multiplier → ℝ
beta : ℝ
tolerance : ℝ
initialPoint : Point
initialMultiplier : Multiplier
iterate : ℕ → Point
multiplier : ℕ → Multiplier
directionEquation :
ℕ →
Point →
Multiplier →
Point →
Multiplier →
Point × Multiplier
pointDirection : ℕ → Point
multiplierDirection : ℕ → Multiplier
quarteringCount : ℕ → ℕ
beta_mem : beta ∈ Set.Ioo (0 : ℝ) 1
tolerance_nonneg : 0 ≤ tolerance
iterate_one : iterate 1 = initialPoint
multiplier_one : multiplier 1 = initialMultiplier
directionsSolveEquation
(k : ℕ)
(hk : 1 ≤ k)
(hcontinue : ¬ meritFunction (iterate k) (multiplier k) ≤ tolerance) :
solvesLagrangeNewtonDirectionEquation
directionEquation
k
(iterate k)
(multiplier k)
(pointDirection k)
(multiplierDirection k)
stop_or_step
(k : ℕ)
(hk : 1 ≤ k) :
meritFunction (iterate k) (multiplier k) ≤ tolerance ∨
IsLagrangeNewtonAcceptedStep
meritFunction beta
(iterate k) (multiplier k)
(pointDirection k) (multiplierDirection k)
(quarteringCount k) ∧
lagrangeNewtonStepUpdate
iterate
multiplier
pointDirection
multiplierDirection
quarteringCount
kTheorem 12.1.2
Lean contributors (project-level attribution): Chenyi Li, Wanli Ma, Zichen Wang.
Chapter12 Theorem 12.1.2: assume problem.objective and each component of problem.constraint are twice continuously differentiable. If the inverse of the source KKT matrix [[W(x_k, λ_k), -A(x_k)], [-A(x_k)ᵀ, 0]] from (12.1.12) has uniformly bounded inverse norm along the Algorithm 12.1.1 sequence generated by the canonical owner method, whose Step 2 equation and merit-function root condition are connected to the fixed problem problem by hMethod : method.IsFor problem W, then every accumulation point of the primal-dual iterate sequence {(x_k, λ_k)} is a root of the source equation IsLagrangeNewtonRoot problem xStar lamStar; equivalently, under hMethod, the recorded merit function also vanishes there. The subsequence encoding φ k + 1 matches the source indexing from stage 1.
open Filter
open Matrix
open scoped Matrix.Norms.Elementwise
variable {n m : ℕ}
local notation "Point" => LagrangeNewtonPoint n
local notation "Multiplier" => LagrangeNewtonMultiplier m
local notation "HessianMatrix" => Matrix (Fin n) (Fin n) ℝ
-- Domain-style sampling:
-- * primary domain: equality-constrained Lagrange-Newton accumulation-point theory for the
-- Chapter 12 KKT residual and block system
-- * inspected owner declarations in the minimal semantic closure:
-- - `LagrangeNewtonMethod` from `Algorithm_12_1_1`
-- - `EqualityConstrainedProblem` and
-- `EqualityConstrainedProblem.lagrangeNewtonKKTMatrix` from
-- `Chapter12.EqualityConstrainedProblem`
-- - the generic Chapter 12 Jacobian owner `lagrangeNewtonConstraintJacobian` from
-- `Theorem_12_1_4`
-- * best owner abstraction: the source-facing problem data are owned by
-- `EqualityConstrainedProblem`, and the algorithm run is owned by the canonical
-- `LagrangeNewtonMethod`; this file keeps only thin bridge predicates and owner-side derived
-- API connecting them
-- * primitive data vs derived API:
-- - primitive data: `problem : EqualityConstrainedProblem n m`, the recorded
-- `LagrangeNewtonMethod`, and the explicit Hessian field
-- `W : Point → Multiplier → HessianMatrix`
-- - derived API here: the theorem-local residual `lagrangeNewtonRootResidual`, the
-- Step-2 residual map, the thin bridge predicate `method.IsFor problem W`, and the
-- bounded-inverse hypothesis for the source KKT matrices
-- Semantic recall: `lean_leansearch` surfaced generic accumulation-point APIs such as `AccPt`,
-- while Chapter 10/12 precedent encodes accumulation points of algorithmic sequences by
-- convergent subsequences `φ` with `StrictMono φ`. The canonical Algorithm 12.1.1 owner now
-- lives in `Algorithm_12_1_1`, while the fixed equality-constrained problem data now live in
-- `Chapter12.EqualityConstrainedProblem`.
local notation "Method" => _root_.LagrangeNewtonMethod Point Multiplier
theorem lagrangeNewtonMethod_accumulationPoint_isRoot
(problem : EqualityConstrainedProblem n m)
(method : Method)
(W : Point → Multiplier → HessianMatrix)
(hMethod : method.IsFor problem W)
(hObjectiveC2 : ContDiff ℝ 2 problem.objective)
(hConstraintC2 : ∀ i : Fin m, ContDiff ℝ 2 (problem.constraint i))
(hBoundedInverse : method.HasUniformlyBoundedKKTInverse problem W)
{xStar : Point} {lamStar : Multiplier} {φ : ℕ → ℕ}
(hφ : StrictMono φ)
(hAccumulation :
Tendsto
(fun k : ℕ ↦ method.primalDualIterate (φ k + 1))
atTop
(nhds (xStar, lamStar))) :
IsLagrangeNewtonRoot problem xStar lamStarTheorem 12.1.3
— source only (outside the published documentation root) (Lean source)
Lean contributors (project-level attribution): Chenyi Li, Wanli Ma, Zichen Wang.
Chapter12 Theorem 12.1.3: assume problem.objective and every component of problem.constraint are twice continuously differentiable. If the KKT matrix (12.1.12) along the Algorithm 12.1.1 sequence generated by the canonical owner method, whose Step-2 equation and merit-function root condition are related to problem by hMethod : method.IsFor problem W, is uniformly bounded, then every accumulation point of the primal iterate sequence {x_k} is a KKT point of the equality-constrained problem (12.1.1)-(12.1.2). The accumulation-point hypothesis is encoded by a strictly monotone subsequence of the source stages k ≥ 1 converging to xStar.
open Filter
open scoped BigOperators Matrix.Norms.Elementwise
variable {n m : ℕ}
local notation "Point" => LagrangeNewtonPoint n
local notation "Multiplier" => LagrangeNewtonMultiplier m
local notation "Method" => _root_.LagrangeNewtonMethod Point Multiplier
local notation "HessianMatrix" => Matrix (Fin n) (Fin n) ℝ
-- Domain sampling:
-- * source-facing layer: the equality-constrained KKT conclusion of Theorem 12.1.3 and the
-- theorem-local uniform bound on the stagewise KKT matrices
-- * core/canonical layer already in the repository:
-- `EqualityConstrainedProblem` from `Chapter12.EqualityConstrainedProblem` and
-- `LagrangeNewtonMethod` together with the bridge predicate `LagrangeNewtonMethod.IsFor`
-- from `Theorem_12_1_2`
-- * bridge/view layer here:
-- the source-facing comparison theorems from `problem.IsKKTPoint` to the canonical Chapter 8
-- and Chapter 10 KKT owners on the equality-only bridge
-- `problem.toStandardPenaltyProblem`
theorem lagrangeNewton_accumulationPoint_isKKTPoint
(problem : EqualityConstrainedProblem n m)
(method : Method)
(W : Point → Multiplier → HessianMatrix)
(hMethod : method.IsFor problem W)
(hObjectiveC2 : ContDiff ℝ 2 problem.objective)
(hConstraintC2 : ∀ i : Fin m, ContDiff ℝ 2 (problem.constraint i))
(hKKTBound : method.HasUniformlyBoundedKKTMatrix problem W)
{xStar : Point} {φ : ℕ → ℕ}
(hφ : StrictMono φ)
(hxStar : Tendsto (fun k : ℕ ↦ method.iterate (φ k + 1)) atTop (nhds xStar)) :
∃ lamStar : Multiplier, problem.IsKKTPoint xStar lamStar
Theorem 12.1.4
— source only (outside the published documentation root) (Lean source)
Lean contributors (project-level attribution): Chenyi Li, Wanli Ma, Zichen Wang.
Chapter12 Theorem 12.1.4 (2): under the same hypotheses, the primal-dual iterate sequence method.primalDualIterate converges quadratically to the feasible stationary Lagrange pair (xStar, lambdaStar), in the canonical Chapter 3 sense that the next primal-dual error is O of the square of the current error.
open Filter
variable {n m : ℕ}
local notation "Point" => LagrangeNewtonPoint n
local notation "Multiplier" => LagrangeNewtonMultiplier m
local notation "Method" => _root_.LagrangeNewtonMethod Point Multiplier
-- Domain sampling:
-- * primary domain: local convergence-rate theory for equality-constrained
-- Lagrange-Newton sequences
-- * inspected owner declarations in the minimal semantic closure:
-- - `HasQuadraticConvergenceTo`
-- - `EqualityConstrainedProblem` and `EqualityConstrainedProblem.IsKKTPoint`
-- - `LagrangeNewtonMethod` together with `LagrangeNewtonMethod.IsFor`
-- - `StandardPenaltyProblem.SecondOrderSufficientCondition`
-- - `hessianMatrixAt` from Chapter 3 for the Euclidean matrix Hessian bridge
-- * source/core/bridge triage:
-- - source-facing layer: the textbook local assumptions and primal-dual convergence
-- conclusion for a fixed equality-constrained problem
-- - core/canonical layer: `HasQuadraticConvergenceTo`
-- - bridge/view layer: the source `=O[atTop]` formula `(12.1.34)` and the Chapter 3
-- Hessian-matrix bridge used only to specialize `method.IsFor`
-- * best owner abstraction: the fixed equality-constrained problem data are owned by
-- `EqualityConstrainedProblem`, the generated run is owned by `LagrangeNewtonMethod`, and
-- the canonical convergence owner is `HasQuadraticConvergenceTo`
-- * primitive data vs. derived API:
-- - primitive data here are the explicit source pair `(xStar, lambdaStar)`, the fixed
-- `problem`, the generated `method`, the local `C^3` neighborhood hypotheses, convergence
-- of `method.iterate`, and the rank condition on `problem.constraintGradientMatrix xStar`
-- The matrix field used in `method.IsFor` is derived from the Chapter 3 owner
-- `hessianMatrixAt`; this file keeps no second local Hessian bridge.
variable (problem : EqualityConstrainedProblem n m) (method : Method)
variable (xStar : Point) (lambdaStar : Multiplier)
variable
(hMethod :
method.IsFor problem (fun x lam ↦ hessianMatrixAt (fun y ↦ problem.lagrangian y lam) x))
(hObjectiveContDiffOn :
∃ s : Set Point, s ∈ nhds xStar ∧ ContDiffOn ℝ 3 problem.objective s)
(hConstraintContDiffOn :
∃ s : Set Point, s ∈ nhds xStar ∧ ContDiffOn ℝ 3 problem.constraintVector s)
(hIterateTendsto : Tendsto method.iterate atTop (nhds xStar))
(hFullColumnRank :
Function.Injective <| Matrix.toEuclideanLin (problem.constraintGradientMatrix xStar))
(hSecondOrderSufficient :
problem.toStandardPenaltyProblem.SecondOrderSufficientCondition xStar lambdaStar)
include problem method xStar lambdaStar hMethod hObjectiveContDiffOn hConstraintContDiffOn
hIterateTendsto hFullColumnRank hSecondOrderSufficient
theorem lagrangeNewtonMethod_primalDualIterate_hasQuadraticConvergenceTo
: HasQuadraticConvergenceTo method.primalDualIterate (xStar, lambdaStar)
Lemma 12.1.5
— source only (outside the published documentation root) (Lean source)
Lean contributors (project-level attribution): Chenyi Li, Wanli Ma, Zichen Wang.
Chapter12 Lemma 12.1.5: under the assumptions of Theorem 12.1.4, the source scalar primal-dual error quantity ‖x_k - xStar‖ + ‖λ_k - lambdaStar‖ satisfies `‖x_(k + 1) - xStar‖ + ‖λ_(k + 1) - lambdaStar‖ = O(‖x_k - xStar‖ * (‖x_k - xStar‖ + ‖λ_k - lambdaStar‖))` along atTop, matching (12.1.38) and (12.1.39). This is a source-facing bridge theorem above the canonical owner HasQuadraticConvergenceTo method.primalDualIterate (xStar, lambdaStar) from Theorem 12.1.4.
open Filter
variable {n m : ℕ}
local notation "Point" => LagrangeNewtonPoint n
local notation "Multiplier" => LagrangeNewtonMultiplier m
local notation "Method" => _root_.LagrangeNewtonMethod Point Multiplier
-- Domain sampling:
-- * primary domain: local asymptotic convergence rates for equality-constrained
-- Lagrange-Newton primal-dual iterates;
-- * inspected owner declarations in the minimal semantic closure:
-- - `HasQuadraticConvergenceTo`
-- - `LagrangeNewtonMethod.primalDualIterate`
-- - `lagrangeNewtonMethod_primalDualIterate_hasQuadraticConvergenceTo`
-- - `lagrangeNewtonMethod_primalDualError_isBigO_square`
-- * source/core/bridge triage:
-- - source-facing layer: the textbook scalar error quantity
-- `‖x_k - xStar‖ + ‖λ_k - lambdaStar‖` from Lemma 12.1.5;
-- - core/canonical layer: the Chapter 03 convergence owner
-- `HasQuadraticConvergenceTo method.primalDualIterate (xStar, lambdaStar)`;
-- - bridge/view layer: the source `=O[atTop]` product estimate for that scalar
-- error quantity;
-- * best owner abstraction: the generated sequence is already owned by
-- `LagrangeNewtonMethod.primalDualIterate`, so this file keeps only the source-facing
-- scalar bridge theorem and does not introduce a second local error owner;
-- * primitive data vs. derived API:
-- - primitive data are the fixed `problem`, `method`, `(xStar, lambdaStar)`, and the
-- Theorem 12.1.4 hypotheses;
-- - the scalar sum-of-norms estimate in this file is derived API built on the existing
-- primal-dual convergence owner.
variable (problem : EqualityConstrainedProblem n m) (method : Method)
variable (xStar : Point) (lambdaStar : Multiplier)
variable
(hMethod :
method.IsFor problem (fun x lam ↦ hessianMatrixAt (fun y ↦ problem.lagrangian y lam) x))
(hObjectiveContDiffOn :
∃ s : Set Point, s ∈ nhds xStar ∧ ContDiffOn ℝ 3 problem.objective s)
(hConstraintContDiffOn :
∃ s : Set Point, s ∈ nhds xStar ∧ ContDiffOn ℝ 3 problem.constraintVector s)
(hIterateTendsto : Tendsto method.iterate atTop (nhds xStar))
(hFullColumnRank :
Function.Injective <| Matrix.toEuclideanLin (problem.constraintGradientMatrix xStar))
(hSecondOrderSufficient :
problem.toStandardPenaltyProblem.SecondOrderSufficientCondition xStar lambdaStar)
include problem method xStar lambdaStar hMethod hObjectiveContDiffOn hConstraintContDiffOn
hIterateTendsto hFullColumnRank hSecondOrderSufficient
theorem lagrangeNewtonMethod_primalDualErrorSum_succ_isBigO_iterateError_mul_primalDualErrorSum
:
(fun k ↦
‖method.iterate (k + 1) - xStar‖ + ‖method.multiplier (k + 1) - lambdaStar‖) =O[atTop]
(fun k ↦
‖method.iterate k - xStar‖ *
(‖method.iterate k - xStar‖ + ‖method.multiplier k - lambdaStar‖))
Theorem 12.1.6
— source only (outside the published documentation root) (Lean source)
Lean contributors (project-level attribution): Chenyi Li, Wanli Ma, Zichen Wang.
Chapter12 Theorem 12.1.6 (1): under the assumptions of Theorem 12.1.4, the primal iterate sequence x_k converges to xStar superlinearly in the canonical Chapter 03 sense.
open Filter
open scoped BigOperators
variable {n m : ℕ}
local notation "Point" => LagrangeNewtonPoint n
local notation "Multiplier" => LagrangeNewtonMultiplier m
local notation "Method" => _root_.LagrangeNewtonMethod Point Multiplier
-- Domain sampling:
-- * primary domain: local asymptotic convergence rates for the equality-constrained
-- Lagrange-Newton iterate sequence
-- * inspected owner declarations in the minimal semantic closure:
-- - `HasSuperlinearConvergenceTo`
-- - `HasQuadraticConvergenceTo`
-- - `lagrangeNewtonMethod_primalDualIterate_hasQuadraticConvergenceTo`
-- - `lagrangeNewtonMethod_primalDualError_isBigO_square`
-- * best owner abstraction:
-- `EqualityConstrainedProblem` owns the fixed optimization data,
-- `LagrangeNewtonMethod` owns the generated sequence, and the Chapter 03 convergence owner
-- `HasSuperlinearConvergenceTo` is the canonical public home for Theorem 12.1.6 (1)
-- * source/core/bridge triage:
-- - source-facing layer: the textbook higher-order error product formula `(12.1.41)`
-- - core/canonical layer: `HasSuperlinearConvergenceTo method.iterate xStar`
-- - bridge/view layer: the raw little-`o` error formula for part `(1)`
-- * primitive data vs derived API:
-- - primitive data here are exactly the Theorem 12.1.4 hypotheses on
-- `problem`, `method`, `xStar`, and `lambdaStar`
-- - derived API here are the superlinear-convergence owner and its source-formula
-- companions; this file keeps no second local convergence package
variable (problem : EqualityConstrainedProblem n m) (method : Method)
variable (xStar : Point) (lambdaStar : Multiplier)
variable
(hMethod :
method.IsFor problem (fun x lam ↦ hessianMatrixAt (fun y ↦ problem.lagrangian y lam) x))
(hObjectiveContDiffOn :
∃ s : Set Point, s ∈ nhds xStar ∧ ContDiffOn ℝ 3 problem.objective s)
(hConstraintContDiffOn :
∃ s : Set Point, s ∈ nhds xStar ∧ ContDiffOn ℝ 3 problem.constraintVector s)
(hIterateTendsto : Tendsto method.iterate atTop (nhds xStar))
(hFullColumnRank :
Function.Injective <| Matrix.toEuclideanLin (problem.constraintGradientMatrix xStar))
(hSecondOrderSufficient :
problem.toStandardPenaltyProblem.SecondOrderSufficientCondition xStar lambdaStar)
include problem method xStar lambdaStar hMethod hObjectiveContDiffOn hConstraintContDiffOn
hIterateTendsto hFullColumnRank hSecondOrderSufficient
theorem lagrangeNewtonMethod_iterate_converges_superlinearly
: HasSuperlinearConvergenceTo method.iterate xStar
12.2 — Wilson-Han-Powell Method
Lemma 12.2.1
— source only (outside the published documentation root) (Lean source)
Lean contributors (project-level attribution): Chenyi Li, Wanli Ma, Zichen Wang.
Chapter12 Lemma 12.2.1 (1): under the KKT and directional-derivative hypotheses, the canonical one-sided directional derivative of the exact-penalty owner is bounded above by the source quadratic and multiplier expression.
variable {n m : ℕ}
local notation "Point" => EuclideanSpace ℝ (Fin n)
local notation "ConstraintPoint" => EuclideanSpace ℝ (Fin m)
local notation "Multiplier" => EuclideanSpace ℝ (Fin m)
local notation "MatrixN" => Matrix (Fin n) (Fin n) ℝ
local notation "Jacobian" => Matrix (Fin n) (Fin m) ℝ
-- Domain sampling:
-- * primary domain: Wilson-Han-Powell SQP penalty analysis for a mixed equality/inequality
-- constrained problem on `ℝ^n`
-- * inspected owner abstractions in the project:
-- `StandardPenaltyProblem.constraintMap`, `StandardPenaltyProblem.constraintViolation`, and
-- `StandardPenaltyProblem.nonsmoothExactPenalty` in Chapter 10,
-- `WilsonHanPowellSubproblem` / `WilsonHanPowellSubproblem.SatisfiesKKT` in Chapter 12, and
-- the Chapter 1 `‖·‖₁` and `‖·‖∞` norm notation on finite coordinate spaces
-- * retained source-facing local layer here:
-- the affine linearized constraint residual `c + Aᵀ d`, the mixed-constraint bridge to the
-- canonical Wilson-Han-Powell KKT predicate on a combined multiplier `λ`, the named `L₁`
-- exact penalty `x ↦ f(x) + σ * ‖c⁽-⁾(x)‖₁`, and the scalar path `α ↦ P(xk + α • dk, σ)`
-- Semantic recall: `lineDeriv` / `HasLineDerivAt` is the canonical directional-derivative API,
-- and the repository owner `HasOneSidedDirectionalDerivAt` packages the right directional
-- derivative of the Chapter 12 penalty function along a search direction. The mixed-constraint
-- penalty object itself is already owned upstream by `StandardPenaltyProblem`, and the Chapter 12
-- SQP subproblem/KKT data are already owned by `WilsonHanPowellSubproblem`.
theorem sqpPenaltyRightDeriv_le_of_satisfiesKKT
(problem : StandardPenaltyProblem n m)
(σ : ℝ)
(xk dk gk : Point)
(Bk : MatrixN)
(Ak : Jacobian)
(lamk : Multiplier)
(h_objective :
HasLineDerivAt ℝ problem.objective (dotProduct gk dk) xk dk)
(h_constraint :
∀ i : Fin m,
HasLineDerivAt ℝ (problem.constraint i) ((Matrix.toEuclideanLin Ak.transpose dk) i) xk dk)
(h_kkt : problem.SatisfiesKKT (problem.constraintMap xk) gk Ak Bk dk lamk) :
oneSidedDirectionalDeriv (problem.l1ExactPenalty σ) xk dk ≤
-dotProduct dk (Matrix.toEuclideanLin Bk dk)
- σ * (c⁽-⁾[problem] xk).sunYuanL1Norm
+ dotProduct lamk (problem.constraintMap xk)
Algorithm 12.2.2
— source only (outside the published documentation root) (Lean source)
Lean contributors (project-level attribution): Chenyi Li, Wanli Ma, Zichen Wang.
Chapter12 Algorithm 12.2.2: the Wilson-Han-Powell method records the primitive algorithm/run data for the SQP iteration. It consists of an objective function f, a constraint map c, the positive parameters σ and δ, the tolerance ε, the initial point x₁, the initial Hessian approximation B₁, the stage-indexed iterates x_k, directions d_k, step sizes α_k, multipliers λ_k, Hessian approximations B_k, errors ε_k, and the recorded stage data g_k, A_k, and ∇ₓ L(x_k, λ). For every stage k ≥ 1, the direction d_k solves the canonical Wilson-Han-Powell quadratic subproblem built from g_k, B_k, c(x_k), and A_k; if ‖d_k‖ ≤ ε the method stops, and otherwise Step 2 chooses α_k ∈ [0, δ] satisfying (12.2.14) for the canonical L₁ exact penalty function. Step 3 updates x_(k + 1) = x_k + α_k d_k, and Step 4 sets λ_(k + 1) = -((A_(k + 1)ᵀ * A_(k + 1))⁻¹ * (A_(k + 1)ᵀ * g_(k + 1))), s_k = α_k d_k, and y_k = ∇ₓ L(x_(k + 1), λ_(k + 1)) - ∇ₓ L(x_k, λ_(k + 1)), then updates B_(k + 1) by the chosen quasi-Newton formula. The inexact line-search errors satisfy the summability condition ∑' k, ε_(k + 1) < ∞, the canonical form of (12.2.15).
structure WilsonHanPowellMethod (n m : ℕ) where
objectiveFunction : WilsonHanPowellPoint n → ℝ
constraintFunction : WilsonHanPowellPoint n → WilsonHanPowellMultiplier m
objectiveGradient : ℕ → WilsonHanPowellPoint n
constraintJacobian : ℕ → WilsonHanPowellConstraintJacobian n m
lagrangianGradient : ℕ → WilsonHanPowellMultiplier m → WilsonHanPowellPoint n
quasiNewtonUpdate
(B : WilsonHanPowellHessianApproximation n)
(s y : WilsonHanPowellPoint n) :
WilsonHanPowellHessianApproximation n
sigma : ℝ
delta : ℝ
tolerance : ℝ
initialPoint : WilsonHanPowellPoint n
initialHessianApproximation : WilsonHanPowellHessianApproximation n
iterate : ℕ → WilsonHanPowellPoint n
direction : ℕ → WilsonHanPowellPoint n
stepSize : ℕ → ℝ
multiplier : ℕ → WilsonHanPowellMultiplier m
hessianApproximation : ℕ → WilsonHanPowellHessianApproximation n
lineSearchError : ℕ → ℝ
objectiveGradient_stage_spec (k : ℕ) (hk : 1 ≤ k) :
HasGradientAt
objectiveFunction
(objectiveGradient k)
(iterate k)
constraintJacobian_stage_spec (k : ℕ) (hk : 1 ≤ k) (i : Fin m) :
HasGradientAt
(fun y : WilsonHanPowellPoint n ↦ constraintFunction y i)
(wilsonHanPowellConstraintGradient (constraintJacobian k) i)
(iterate k)
lagrangianGradient_stage_spec
(k : ℕ) (hk : 1 ≤ k) (lam : WilsonHanPowellMultiplier m) :
HasGradientAt
(fun y : WilsonHanPowellPoint n ↦
wilsonHanPowellLagrangian objectiveFunction constraintFunction y lam)
(lagrangianGradient k lam)
(iterate k)
sigma_pos : 0 < sigma
delta_pos : 0 < delta
tolerance_nonneg : 0 ≤ tolerance
iterate_one : iterate 1 = initialPoint
hessianApproximation_one : hessianApproximation 1 = initialHessianApproximation
direction_solution (k : ℕ) (hk : 1 ≤ k) :
IsStageSearchDirection
(objectiveGradient k)
(hessianApproximation k)
(constraintFunction (iterate k))
(constraintJacobian k)
(direction k)
lineSearchError_nonneg (k : ℕ) (hk : 1 ≤ k) : 0 ≤ lineSearchError k
lineSearchError_summable : Summable fun k : ℕ ↦ lineSearchError (k + 1)
multiplierUpdateMatrix_isUnit
(k : ℕ) (hk : 1 ≤ k) (h_continue : ¬ ‖direction k‖ ≤ tolerance) :
IsUnit
(wilsonHanPowellNormalMatrix
(constraintJacobian (k + 1)))
approximatePenaltyStep_spec
(k : ℕ) (hk : 1 ≤ k) (h_continue : ¬ ‖direction k‖ ≤ tolerance) :
IsApproximatePenaltyStep
(fun x σ ↦
(wilsonHanPowellPenaltyProblem objectiveFunction constraintFunction).nonsmoothExactPenalty
(fun c ↦ c.sunYuanL1Norm) σ x)
(iterate k)
(direction k)
sigma
delta
(stepSize k)
(lineSearchError k)
iterate_succ_eq_trialPoint_spec
(k : ℕ) (hk : 1 ≤ k) (h_continue : ¬ ‖direction k‖ ≤ tolerance) :
iterate (k + 1) =
wilsonHanPowellTrialPoint
(iterate k)
(direction k)
(stepSize k)
multiplier_succ_eq_update_spec
(k : ℕ) (hk : 1 ≤ k) (h_continue : ¬ ‖direction k‖ ≤ tolerance) :
multiplier (k + 1) =
wilsonHanPowellMultiplierUpdate
(constraintJacobian (k + 1))
(objectiveGradient (k + 1))
hessianApproximation_succ_eq_update_spec
(k : ℕ) (hk : 1 ≤ k) (h_continue : ¬ ‖direction k‖ ≤ tolerance) :
hessianApproximation (k + 1) =
quasiNewtonUpdate
(hessianApproximation k)
(wilsonHanPowellStepVector
(direction k)
(stepSize k))
(lagrangianGradient (k + 1) (multiplier (k + 1)) -
lagrangianGradient k (multiplier (k + 1)))
Theorem 12.2.3
— source only (outside the published documentation root) (Lean source)
Lean contributors (project-level attribution): Chenyi Li, Wanli Ma, Zichen Wang.
Chapter12 Theorem 12.2.3 in source-facing KKT form: let method be a Wilson-Han-Powell sequence generated by Algorithm 12.2.2 for the fixed equality-constrained problem problem, with theorem-local compatibility hypothesis hMethod : method.IsFor problem, so the recorded objective and constraint surfaces agree with the canonical ones coming from problem. Assume problem.objective and every component of problem.constraint are continuously differentiable, the Hessian approximations of method satisfy uniform positive quadratic lower and upper bounds along the active stages k ≥ 1, and ‖λ_k‖∞ ≤ σ for every active-stage multiplier. Then every accumulation point of the primal iterate sequence {x_k} is a KKT point of problem.
open Filter
variable {n m : ℕ}
local notation "Point" => WilsonHanPowellPoint n
local notation "Multiplier" => WilsonHanPowellMultiplier m
-- Domain sampling:
-- * primary domain: Wilson-Han-Powell SQP accumulation-point theory and KKT multipliers for a
-- fixed equality-constrained problem
-- * inspected owner abstractions:
-- `EqualityConstrainedProblem`, `EqualityConstrainedProblem.IsKKTPoint`,
-- `EqualityConstrainedProblem.toStandardPenaltyProblem`,
-- `LagrangeNewtonMethod.IsFor` in `Theorem_12_1_2`,
-- `SmoothExactPenaltyMethodFor` in `Theorem_12_7_3`, and
-- `WilsonHanPowellMethod`, `WilsonHanPowellMethod.toStandardPenaltyProblem`,
-- `WilsonHanPowellMethod.approximatePenaltyStepAt`, and
-- `WilsonHanPowellMethod.subproblemAt` in `Algorithm_12_2_2`,
-- together with `StandardPenaltyProblem.IsLagrangeMultiplier` in `Theorem_10_6_1`
-- * source/core/bridge triage:
-- - source-facing layer here: a Wilson-Han-Powell run specialized to a fixed
-- equality-constrained problem;
-- - core/canonical owner for the problem data: `EqualityConstrainedProblem`;
-- - bridge/view layer here: the theorem-local compatibility predicate
-- `method.IsFor problem`, together with the equality-only Chapter 10 bridge
-- `problem.toStandardPenaltyProblem` used only for the Lagrange-multiplier conclusion
-- * primitive data vs. derived API:
-- - primitive owner data are the fixed `EqualityConstrainedProblem` and the underlying
-- `WilsonHanPowellMethod`;
-- - the specialization equalities `objectiveFunction = problem.objective` and
-- `constraintFunction = problem.constraintVector` are theorem-local bridge data relating
-- the canonical method owner to the fixed problem owner;
-- - the mixed-constraint `StandardPenaltyProblem` surface is derived only as the equality-only
-- bridge used by the conclusion
theorem wilsonHanPowell_accumulationPoint_isKKTPoint
(problem : EqualityConstrainedProblem n m)
(method : WilsonHanPowellMethod n m)
(hMethod : method.IsFor problem)
(hObjectiveC1 : ContDiff ℝ 1 problem.objective)
(hConstraintC1 : ∀ i : Fin m, ContDiff ℝ 1 (problem.constraint i))
(hHessianBounds : method.HasUniformHessianBounds)
(hMultiplierBound : ∀ k : ℕ, 1 ≤ k → ‖method.multiplier k‖∞ ≤ method.sigma)
{xStar : Point} {φ : ℕ → ℕ}
(hφ : StrictMono φ)
(hxStar : Tendsto (fun k : ℕ ↦ method.iterate (φ k + 1)) atTop (nhds xStar)) :
∃ lamStar : Multiplier, problem.IsKKTPoint xStar lamStar
Definition 12.2.extra.1
— source only (outside the published documentation root) (Lean source)
Lean contributors (project-level attribution): Chenyi Li, Wanli Ma, Zichen Wang.
The Wilson-Han-Powell quadratic subproblem on ℝ^n records the Hessian approximation B, the linear term g = ∇ f(x_k), the equality block Aeq.mulVec d + ceq = 0, and the inequality block Aineq.mulVec d + cineq ≥ 0 from (12.2.1)-(12.2.4). Here the rows of Aeq and Aineq encode the vectors a_i(x_k)ᵀ.
variable {n me mi : ℕ}
local notation "Direction" => Fin n → ℝ
local notation "Point" => EuclideanSpace ℝ (Fin n)
local notation "EqPoint" => EuclideanSpace ℝ (Fin me)
local notation "IneqPoint" => EuclideanSpace ℝ (Fin mi)
local notation "pointEquiv" => (EuclideanSpace.equiv (Fin n) ℝ)
local notation "eqResidualEquiv" => (EuclideanSpace.equiv (Fin me) ℝ)
local notation "ineqResidualEquiv" => (EuclideanSpace.equiv (Fin mi) ℝ)
local notation "EqResidual" => Fin me → ℝ
local notation "IneqResidual" => Fin mi → ℝ
local notation "EqMultiplier" => Fin me → ℝ
local notation "IneqMultiplier" => Fin mi → ℝ
-- Domain-style sampling for this refine pass:
-- * primary domain: SQP quadratic subproblems and KKT conditions for Wilson-Han-Powell steps;
-- * inspected owner/data declarations:
-- `TrustRegionSubproblem.IsSolution`,
-- `QuadraticProgram.feasibleSet`,
-- `QuadraticProgram.objective`,
-- and `IsMinOn`;
-- * core/canonical owner for optimality: feasibility together with `IsMinOn` on the subproblem
-- objective and feasible set;
-- * primitive data here: the Wilson-Han-Powell quadratic model and the linearized
-- equality/inequality blocks from `(12.2.1)`-`(12.2.3)`;
-- * derived API here: feasibility as set membership, search-direction optimality, and KKT
-- multipliers.
-- This file keeps the source-facing subproblem data instead of collapsing directly to
-- `QuadraticProgram`, because the current item does not assume the Hessian approximation `B`
-- is symmetric.
structure WilsonHanPowellSubproblem (n me mi : ℕ) where
B : Matrix (Fin n) (Fin n) ℝ
g : Fin n → ℝ
Aeq : Matrix (Fin me) (Fin n) ℝ
ceq : Fin me → ℝ
Aineq : Matrix (Fin mi) (Fin n) ℝ
cineq : Fin mi → ℝ
12.3 — Superlinear Convergence of SQP Step
Assumption 12.3.1
— source only (outside the published documentation root) (Lean source)
Lean contributors (project-level attribution): Chenyi Li, Wanli Ma, Zichen Wang.
Chapter12 Assumption 12.3.1: for the SQP problem problem, the objective and constraints are twice continuously differentiable, the iterates xSeq k converge to a KKT point xStar with multiplier lamStar, the active gradients ∇ c_i(xStar) for i ∈ E ∪ I(xStar) are linearly independent, the quadratic form d ↦ dᵀ W(xStar, lamStar) d is nondegenerate on the nullspace of A(xStar)ᵀ, and the active inequality set at the solution is eventually identified by the working sets activeSet k.
variable {n m : ℕ}
local notation "Point" => EuclideanSpace ℝ (Fin n)
local notation "Multiplier" => EuclideanSpace ℝ (Fin m)
-- Canonical reuse:
-- * `StandardPenaltyProblem` is the repository owner for mixed equality/inequality problems.
-- * `StandardPenaltyProblem.activeConstraintSet` is the Chapter 10 bridge to the canonical
-- Chapter 8 active-set owner on `problem.toConstrainedOptimizationProblem`.
-- * `StandardPenaltyProblem.LicqAt` and Chapter 10's KKT owner are the canonical
-- constraint-qualification and multiplier layers on the mixed-constraint surface.
-- * This file keeps only the Chapter 12 SQP-specific source-facing companions and bridges.
structure HasSqpSuperlinearConvergenceAssumptions
(problem : StandardPenaltyProblem n m) (xSeq : ℕ → Point) where
activeSet : ℕ → Set (Fin m)
xStar : Point
lamStar : Multiplier
objective_contDiff : ContDiff ℝ 2 problem.objective
constraint_contDiff : ∀ i : Fin m, ContDiff ℝ 2 (problem.constraint i)
tendsto_xSeq : Filter.Tendsto xSeq Filter.atTop (nhds xStar)
isSqpLagrangeMultiplier : problem.IsSqpLagrangeMultiplier xStar lamStar
activeConstraint_linearIndependent :
LinearIndepOn ℝ (fun i : Fin m ↦ gradient (problem.constraint i) xStar)
(problem.activeConstraintSet xStar)
lagrangianHessianQuadratic_nondegenerate :
∀ d : Point,
d ≠ 0 →
problem.activeConstraintOrthogonal xStar d →
problem.lagrangianHessianQuadratic xStar lamStar d ≠ 0
activeSet_eventually_eq :
∀ᶠ k in Filter.atTop, activeSet k = problem.activeIneqIndexSet xStar
Assumption 12.3.2
Lean contributors (project-level attribution): Chenyi Li, Wanli Ma, Zichen Wang.
Chapter12 Assumption 12.3.2: for all sufficiently large k, the recorded SQP step d k solves the quadratic program min_d (inner ℝ (g k) d + (1 / 2) * inner ℝ d (B k d)) subject to the active linearized constraints (activeJacobian (x k) xStar).adjoint d = -activeConstraintValues (x k) xStar, where activeJacobian (x k) xStar represents A(x_k) and activeConstraintValues (x k) xStar represents ĉ(x_k) for the active index set E ∪ I(x*).
variable {Point Multiplier : Type*}
variable [NormedAddCommGroup Point] [InnerProductSpace ℝ Point] [CompleteSpace Point]
variable [NormedAddCommGroup Multiplier] [InnerProductSpace ℝ Multiplier]
[CompleteSpace Multiplier]
def satisfiesEventualSqpSubproblemAssumption
(x : ℕ → Point) (xStar : Point) (g : ℕ → Point)
(B : ℕ → Point →L[ℝ] Point)
(activeJacobian : Point → Point → Multiplier →L[ℝ] Point)
(activeConstraintValues : Point → Point → Multiplier)
(d : ℕ → Point) : Prop :=
∃ K : ℕ, ∀ k ≥ K,
isSqpSubproblemSolution
(g k) (B k)
(activeJacobian (x k) xStar)
(activeConstraintValues (x k) xStar)
(d k)Theorem 12.3.3
— source only (outside the published documentation root) (Lean source)
Lean contributors (project-level attribution): Chenyi Li, Wanli Ma, Zichen Wang.
Chapter12 Theorem 12.3.3: under Assumptions 12.3.1 and 12.3.2 for the canonical active Jacobian problem.activeConstraintJacobian (x k) h1231.xStar, active-constraint values problem.activeConstraintValues (x k) h1231.xStar, and projection problem.activeConstraintNullspaceProjection (x k) h1231.xStar, the SQP step sequence d_k is superlinearly convergent in the sense of (12.3.11) if and only if the projected Hessian-model error ratio (12.3.12) tends to 0, with W(h1231.xStar, h1231.lamStar) represented by the canonical owner problem.lagrangianHessianAt h1231.xStar h1231.lamStar.
open Filter
open scoped BigOperators
open scoped StandardPenaltyProblem
variable {n m : ℕ}
local notation "Point" => EuclideanSpace ℝ (Fin n)
local notation "Multiplier" => EuclideanSpace ℝ (Fin m)
local notation "∇" => @gradient ℝ Point _ _ _ _
-- This file reuses the canonical Assumption 12.3.1 / 12.3.2 owners together with the Chapter
-- 12 source-facing SQP step owner from `Definition_12_3_extra_1`, and adds only the projection
-- and error-ratio API needed for Theorem 12.3.3.
theorem hasSuperlinearlyConvergentStep_iff_projectedHessianErrorRatio_tendsto_zero
(problem : StandardPenaltyProblem n m)
(x g d : ℕ → Point)
(B : ℕ → Point →L[ℝ] Point)
(h1231 : HasSqpSuperlinearConvergenceAssumptions problem x)
(hAssumption1232 :
satisfiesEventualSqpSubproblemAssumption
x
h1231.xStar
g
B
problem.activeConstraintJacobian
problem.activeConstraintValues
d) :
HasSuperlinearlyConvergentStep x d h1231.xStar ↔
Tendsto
(sqpProjectedHessianErrorRatio
(fun k ↦ problem.activeConstraintNullspaceProjection (x k) h1231.xStar)
B
(problem.lagrangianHessianAt h1231.xStar h1231.lamStar)
d)
atTop
(nhds (0 : ℝ))
Corollary 12.3.4
— source only (outside the published documentation root) (Lean source)
Lean contributors (project-level attribution): Chenyi Li, Wanli Ma, Zichen Wang.
Chapter12 Corollary 12.3.4: under the assumptions of Theorem 12.3.3, if lam is the eventual SQP multiplier sequence satisfying `∀ᶠ k in atTop, g_k + B_k d_k = A(x_k) λ_k, then the superlinear step condition (12.3.11)` is equivalent to the projected stationarity-residual limit (12.3.27).
open Filter
variable {n m : ℕ}
local notation "Point" => EuclideanSpace ℝ (Fin n)
local notation "Multiplier" => EuclideanSpace ℝ (Fin m)
local notation "∇" => @gradient ℝ Point _ _ _ _
-- Domain-style sampling:
-- * primary domain: Chapter 12 SQP superlinear convergence through the active-constraint
-- Jacobian/projection owners on `StandardPenaltyProblem`;
-- * sampled same-domain owners in the minimal semantic closure:
-- `satisfiesEventualSqpSubproblemAssumption` from `Assumption_12_3_2`,
-- `StandardPenaltyProblem.activeConstraintJacobian`,
-- `StandardPenaltyProblem.activeConstraintNullspaceProjection`, and
-- `sqpProjectedHessianErrorRatio` from `Theorem_12_3_3`;
-- * best owner abstraction: the active-constraint operators are owned by
-- `StandardPenaltyProblem`, while eventual stagewise hypotheses should use the canonical
-- `Filter.atTop` eventuality rather than a new local threshold wrapper;
-- * source/core/bridge triage: the projected stationarity-residual ratio is a source-facing
-- companion for Corollary 12.3.4; the active-set operators remain core owners on
-- `StandardPenaltyProblem`; no extra bridge wrapper is needed here;
-- * primitive data here: `problem`, `xStar`, and the sequences `x`, `d`, `lam`; the assumption
-- package `h1231` is derived theorem input, not owner data for the ratio itself.
theorem hasSuperlinearlyConvergentStep_iff_projectedStationarityResidualRatio_tendsto_zero
(problem : StandardPenaltyProblem n m)
(x g d : ℕ → Point)
(B : ℕ → Point →L[ℝ] Point)
(lam : ℕ → Multiplier)
(h1231 : HasSqpSuperlinearConvergenceAssumptions problem x)
(hAssumption1232 :
satisfiesEventualSqpSubproblemAssumption
x
h1231.xStar
g
B
problem.activeConstraintJacobian
problem.activeConstraintValues
d)
(hLam :
∀ᶠ k in atTop,
g k + B k (d k) =
problem.activeConstraintJacobian (x k) h1231.xStar (lam k)) :
HasSuperlinearlyConvergentStep x d h1231.xStar ↔
Tendsto
(sqpProjectedStationarityResidualRatio problem h1231.xStar x d lam)
atTop
(nhds (0 : ℝ))
Definition 12.3.extra.1
— source only (outside the published documentation root) (Lean source)
Lean contributors (project-level attribution): Chenyi Li, Wanli Ma, Zichen Wang.
The SQP step error ratio ‖x k + d k - xStar‖ / ‖x k - xStar‖ from (12.3.2).
open Filter Asymptotics
universe u
variable {E : Type u} [NormedAddCommGroup E]
-- Domain sampling:
-- * primary domain: asymptotic convergence rates for normed-space sequences.
-- * sampled core owners: mathlib's `Asymptotics.IsLittleO` / `=o[atTop]`,
-- Chapter 03's `HasSuperlinearConvergenceTo`, and Chapter 01's
-- `HasQSuperlinearConvergenceTo`.
-- * source/core/bridge triage: `HasSuperlinearlyConvergentStep` is the source-facing owner for
-- the SQP trial-step notion `(12.3.2)`. The raw ratio `sqpStepErrorRatio` is derived API, and
-- the little-`o` and Chapter 03 superlinear-sequence formulations are only bridges because the
-- source ratio uses totalized division, so equivalence with `=o[atTop]` needs an explicit
-- zero-denominator compatibility hypothesis.
def sqpStepErrorRatio (x d : ℕ → E) (xStar : E) : ℕ → ℝ :=
fun k ↦ ‖x k + d k - xStar‖ / ‖x k - xStar‖
12.4 — Maratos Effect
Remark 12.4.extra.1
— source only (outside the published documentation root) (Lean source)
Lean contributors (project-level attribution): Chenyi Li, Wanli Ma, Zichen Wang.
The Maratos-effect objective is f(u, v) = 3 * v^2 - 2 * u.
open Filter local notation "Multiplier" => LagrangeNewtonMultiplier -- Domain sampling for this file: -- * source-facing layer: the concrete Maratos data `f`, `c`, `x̄(ε)`, `d̄(ε)`; -- * core/canonical layer: `EqualityConstrainedProblem`, -- `IsMinOn`, `sqpSubproblemObjective`, `satisfiesSqpLinearizedConstraints`, and -- `maratosProblem.toStandardPenaltyProblem.l1ExactPenalty` through -- `Chapter12/Theorem_12_7_3`; -- * bridge/view layer here: the Maratos example as a concrete equality-constrained problem plus -- its single-column linearized constraint Jacobian and Hessian model. -- -- The file therefore keeps only the concrete Maratos data locally and reuses the chapter owner -- declarations for the SQP subproblem and `L₁` exact penalty surfaces. def maratosObjective (x : Point 2) : ℝ := 3 * (x 1) ^ (2 : ℕ) - 2 * x 0
12.5 — Watchdog Technique
Algorithm 12.5.1
Lean contributors (project-level attribution): Chenyi Li, Wanli Ma, Zichen Wang.
Chapter12 Algorithm 12.5.1: the watchdog method records a penalty function Pσ, an initial point x₁ : ℝ^n, a positive watchdog window n̄, the current iterate sequence x_k, trial points x_k + α_k d_k, search directions d_k, step sizes α_k > 0, the line-search type (standard or relaxed), and the watchdog index l. Step 1 starts with standard line search and k = l = 1. At each stage k ≥ 1, Step 2 chooses d_k, carries out the selected line search to obtain α_k > 0, and forms the trial point x_k + α_k d_k. Step 3 sets the next line-search type to relaxed when (12.5.6) holds and to standard otherwise. Step 4 updates l to k + 1 when Pσ (x_(k + 1)) ≤ Pσ (x_l). Step 5 keeps the trial point while k < l + n̄ and otherwise resets x_(k + 1) to x_l and l to k + 1. Step 6 stops when the chosen convergence criterion is satisfied.
variable {n : ℕ}
local notation "Point" => WatchdogPoint n
-- Semantic recall: `lean_leansearch` did not surface a canonical mathlib owner for the SQP
-- watchdog loop in this item. Nearby Chapter 12 algorithm files package such methods as
-- explicit iterate, line-search, and update data, so this file follows the same owner shape.
structure WatchdogMethod (n : ℕ) where
penaltyFunction : WatchdogPoint n → ℝ
lineSearch (searchType : WatchdogLineSearchType)
(x d : WatchdogPoint n) (α : ℝ) : Prop
relaxedCriterion : ℕ → Prop
terminationCriterion : ℕ → Prop
watchdogWindow : ℕ
initialPoint : WatchdogPoint n
iterate : ℕ → WatchdogPoint n
trialIterate : ℕ → WatchdogPoint n
direction : ℕ → WatchdogPoint n
stepSize : ℕ → ℝ
lineSearchType : ℕ → WatchdogLineSearchType
watchdogIndex : ℕ → ℕ
candidateWatchdogIndex : ℕ → ℕ
watchdogWindow_pos : 0 < watchdogWindow
iterate_one : iterate 1 = initialPoint
lineSearchType_one : lineSearchType 1 = WatchdogLineSearchType.standard
watchdogIndex_one : watchdogIndex 1 = 1
stepSize_pos (k : ℕ) (hk : 1 ≤ k) : 0 < stepSize k
lineSearch_spec (k : ℕ) (hk : 1 ≤ k) :
lineSearch (lineSearchType k) (iterate k) (direction k) (stepSize k)
trialIterate_eq (k : ℕ) (hk : 1 ≤ k) :
trialIterate k = watchdogTrialPoint (iterate k) (direction k) (stepSize k)
lineSearchType_succ_relaxed (k : ℕ) (hk : 1 ≤ k) (hrelaxed : relaxedCriterion k) :
lineSearchType (k + 1) = WatchdogLineSearchType.relaxed
lineSearchType_succ_standard (k : ℕ) (hk : 1 ≤ k) (hstandard : ¬ relaxedCriterion k) :
lineSearchType (k + 1) = WatchdogLineSearchType.standard
candidateWatchdogIndex_eq (k : ℕ) (hk : 1 ≤ k) :
candidateWatchdogIndex k =
watchdogCandidateIndex
penaltyFunction
iterate
(watchdogIndex k)
k
(trialIterate k)
iterate_succ_eq (k : ℕ) (hk : 1 ≤ k) :
iterate (k + 1) =
watchdogNextIterate
iterate
(trialIterate k)
(candidateWatchdogIndex k)
watchdogWindow
k
watchdogIndex_succ_eq (k : ℕ) (hk : 1 ≤ k) :
watchdogIndex (k + 1) =
watchdogNextIndex
(candidateWatchdogIndex k)
watchdogWindow
kDefinition 12.5.extra.1
Lean contributors (project-level attribution): Chenyi Li, Wanli Ma, Zichen Wang.
The source penalty contribution of the i-th constraint in P_σ(x): equality constraints contribute |cᵢ(x)|, while inequality constraints contribute |min (0, cᵢ(x))|.
open scoped BigOperators
variable {n m : ℕ}
local notation "Point" => EuclideanSpace ℝ (Fin n)
local notation "PenaltyWeights" => EuclideanSpace ℝ (Fin m)
local notation "MatrixN" => Matrix (Fin n) (Fin n) ℝ
local notation "∇" => @gradient ℝ Point _ _ _ _
-- Semantic recall and owner triage:
-- * core/canonical layer: `StandardPenaltyProblem` and `c⁽-⁾[problem]` are already owned by
-- Chapter 10's penalty-method API;
-- * source-facing layer: the watchdog merit function, its quadratic model, and the best-index /
-- sufficient-reduction predicates from Definition 12.5-extra-1;
-- * bridge layer: the companions below restate the watchdog formulas in the source's piecewise
-- form while reusing the earlier canonical constrained-problem owner.
namespace StandardPenaltyProblem
def watchdogPenaltyTerm
(problem : StandardPenaltyProblem n m) (x : Point) (i : Fin m) : ℝ :=
|c⁽-⁾[problem] x i|12.6 — Second-Order Correction Step
Assumption 12.6.1
Lean contributors (project-level attribution): Chenyi Li, Wanli Ma, Zichen Wang.
Chapter12 Assumption 12.6.1 (1): the SQP iterates x k converge to the limit point xStar.
open Filter
variable {Point : Type*} [TopologicalSpace Point]
abbrev secondOrderCorrectionIteratesConverge
(x : ℕ → Point) (xStar : Point) : Prop :=
Tendsto x atTop (nhds xStar)Lemma 12.6.2
Lean contributors (project-level attribution): Chenyi Li, Wanli Ma, Zichen Wang.
Chapter12 Lemma 12.6.2: under secondOrderCorrectionIteratesConverge x xStar, ContinuousAt A xStar, secondOrderCorrectionJacobianHasFullColumnRankAt A xStar, and secondOrderCorrectionUniformModelBounds x A B, there exist constants η > 0 and K such that for every k ≥ K and every direction d, the stacked residual ‖WithLp.toLp 2 (P_k (B_k d), A(x_k)ᵀ d)‖, with P_k = ((A (x k)).adjoint.ker).starProjection, is bounded below by η * ‖d‖, matching (12.6.12) in the finite-dimensional Euclidean setting on the canonical L²-product surface WithLp 2 (Point × Multiplier).
open Filter
variable {Point Multiplier : Type*}
variable [NormedAddCommGroup Point] [InnerProductSpace ℝ Point] [FiniteDimensional ℝ Point]
variable [NormedAddCommGroup Multiplier] [InnerProductSpace ℝ Multiplier]
variable [FiniteDimensional ℝ Multiplier]
-- Domain sampling for this file:
-- * primary domain: Section 12.6 second-order-correction residual coercivity in finite-dimensional
-- real inner-product spaces, i.e. the Euclidean matrix setting of the source lemma;
-- * sampled owner declarations:
-- `secondOrderCorrectionJacobianHasFullColumnRankAt`,
-- `secondOrderCorrectionUniformModelBounds`,
-- `LinearMap.injective_iff_antilipschitz`,
-- `ContinuousLinearMap.isOpen_injective`,
-- and `Submodule.starProjection`;
-- * source-facing layer: the eventual lower bound `(12.6.12)` for the stacked residual
-- `((P_k (B_k d)), A(x_k)ᵀ d)`;
-- * core/canonical layer: the Chapter 12 owner
-- `secondOrderCorrectionJacobianHasFullColumnRankAt A xStar` for full column rank and the
-- orthogonal projection owner `Submodule.starProjection`;
-- * bridge/view layer: finite-dimensional injectivity-to-antilipschitz control via
-- `LinearMap.injective_iff_antilipschitz`, plus openness of injectivity through
-- `ContinuousLinearMap.isOpen_injective`;
-- * the canonical `L²`-product owner `WithLp 2 (Point × Multiplier)` packages the stacked
-- residual norm without adding a second owner abstraction;
-- * primitive data vs derived API: `x`, `xStar`, `A`, `B`, convergence of `x k`, continuity of
-- `A` at `xStar`, full column rank of `A xStar` in the finite-dimensional Euclidean sense, and
-- the uniform nullspace-curvature bounds are
-- primitive, while the uniform lower bound for the stacked residual is derived.
theorem exists_eventually_uniform_lowerBound_stackedSecondOrderCorrectionResidual
(x : ℕ → Point)
(xStar : Point)
(A : Point → Multiplier →L[ℝ] Point)
(B : ℕ → Point →L[ℝ] Point)
(hx : secondOrderCorrectionIteratesConverge x xStar)
(hAcont : ContinuousAt A xStar)
(hAstar : secondOrderCorrectionJacobianHasFullColumnRankAt A xStar)
(hBounds : secondOrderCorrectionUniformModelBounds x A B) :
∃ η : ℝ,
0 < η ∧
∃ K : ℕ,
∀ ⦃k : ℕ⦄ (_hk : K ≤ k) (d : Point),
η * ‖d‖ ≤
‖WithLp.toLp 2
((((A (x k)).adjoint.ker).starProjection (B k d),
(A (x k)).adjoint d))‖Lemma 12.6.3
Lean contributors (project-level attribution): Chenyi Li, Wanli Ma, Zichen Wang.
Chapter12 Lemma 12.6.3: under the conditions of Assumption 12.6.1, if d_k is the base SQP step, dHat_k solves the second-order correction subproblem (12.6.3)-(12.6.4), dHat_k is chosen with least norm among all such minimizers as in (12.6.5), and the next-constraint residual c (x_k + d_k) is quadratically small in d_k, then there exist a positive constant etaBar and a threshold K such that for every k ≥ K, ‖dHat_k‖ ≤ etaBar * ‖d_k‖^2, matching the eventual quadratic estimate (12.6.22).
open Asymptotics Filter
variable {Point Multiplier : Type*}
variable [NormedAddCommGroup Point] [InnerProductSpace ℝ Point] [CompleteSpace Point]
variable [NormedAddCommGroup Multiplier] [InnerProductSpace ℝ Multiplier]
[CompleteSpace Multiplier]
-- Domain sampling:
-- * primary domain: Section 12.6 second-order correction subproblems and the quadratic-size
-- estimate for their chosen least-norm minimizers in real inner-product spaces;
-- * sampled owner declarations:
-- `isSqpSubproblemSolution`,
-- `IsSecondOrderCorrectionSubproblemSolution`,
-- `secondOrderCorrectionUniformModelBounds`,
-- and `Asymptotics.IsBigO`;
-- * best owner abstraction: `IsSecondOrderCorrectionSubproblemSolution` is the primitive
-- correction-subproblem owner, while the quadratic residual-size and correction-size bounds
-- should both use the canonical asymptotic owner `Asymptotics.IsBigO`;
-- * source/core/bridge triage:
-- - source-facing item here: Lemma 12.6.3, the quadratic correction estimate;
-- - core/canonical owners: `isSqpSubproblemSolution`,
-- `IsSecondOrderCorrectionSubproblemSolution`, and
-- `secondOrderCorrectionUniformModelBounds`;
-- - bridge/view: the threshold estimate and the residual hypothesis are both expressed through
-- `Asymptotics.IsBigO`;
-- * primitive data vs derived API: the primitive correction-step hypothesis is that `dHat k`
-- solves the correction subproblem, while the least-norm selection among all such minimizers is
-- extra source-facing data; the quadratic residual bound on `c (x k + d k)` and the
-- asymptotic bound on `‖dHat k‖` are derived API.
variable
(x : ℕ → Point)
(xStar : Point)
(g : ℕ → Point)
(c : Point → Multiplier)
(A : Point → Multiplier →L[ℝ] Point)
(B : ℕ → Point →L[ℝ] Point)
(d dHat : ℕ → Point)
theorem exists_eventually_norm_secondOrderCorrection_le_mul_sq_norm
(hConverge : secondOrderCorrectionIteratesConverge x xStar)
(hFullColumnRank : secondOrderCorrectionJacobianHasFullColumnRankAt A xStar)
(hUniformBounds : secondOrderCorrectionUniformModelBounds x A B)
(hBaseStep :
∀ k : ℕ,
isSqpSubproblemSolution (g k) (B k) (A (x k)) (c (x k)) (d k))
(hCorrectionSolution :
∀ k : ℕ,
IsSecondOrderCorrectionSubproblemSolution
(g k) (d k) (B k) (A (x k)) (c (x k + d k)) (dHat k))
(hCorrectionLeastNorm :
∀ k : ℕ, ∀ d' : Point,
IsSecondOrderCorrectionSubproblemSolution
(g k) (d k) (B k) (A (x k)) (c (x k + d k)) d' →
‖dHat k‖ ≤ ‖d'‖)
(hNextResidual :
IsBigO atTop (fun k ↦ ‖c (x k + d k)‖) (fun k ↦ ‖d k‖ ^ (2 : ℕ))) :
∃ etaBar : ℝ,
0 < etaBar ∧
∃ K : ℕ, ∀ k : ℕ, K ≤ k → ‖dHat k‖ ≤ etaBar * ‖d k‖ ^ (2 : ℕ)Definition 12.6.extra.1
Lean contributors (project-level attribution): Chenyi Li, Wanli Ma, Zichen Wang.
Chapter12 Definition 12.6-extra-1: for a penalty function Pσ, iterate sequence x_k, SQP step sequence d_k, and correction sequence dHat_k, `IsSecondOrderCorrectionStep Pσ x d dHatmeans that‖dHat_k‖ = O(‖d_k‖^2)` and Pσ (x_k + d_k + dHat_k) < Pσ (x_k) for all sufficiently large k, matching (12.6.1) and (12.6.2).
open Asymptotics Filter
-- The source-facing 12.6 correction-step surface is expressed with the chapter's canonical SQP
-- subproblem owners from `Assumption_12_3_2`, while the asymptotic pieces use the canonical
-- mathlib owners `Asymptotics.IsBigO` and `Filter.Eventually`.
variable {Point : Type*}
variable [NormedAddCommGroup Point]
class IsSecondOrderCorrectionStep
(Pσ : Point → ℝ) (x d dHat : ℕ → Point) : Prop where
isBigO :
IsBigO atTop (fun k ↦ ‖dHat k‖) (fun k ↦ ‖d k‖ ^ (2 : ℕ))
penaltyDecrease :
∀ᶠ k in atTop, Pσ (x k + d k + dHat k) < Pσ (x k)12.7 — Smooth Exact Penalty Functions
Algorithm 12.7.1
— source only (outside the published documentation root) (Lean source)
Lean contributors (project-level attribution): Chenyi Li, Wanli Ma, Zichen Wang.
Chapter12 Algorithm 12.7.1: Powell-Yuan's method records an initial point x₁ : ℝ^n, line-search parameters β₁ ∈ (0, 1), β₂ ∈ (β₁, 1), and μ ∈ (0, 1 / 2), an initial positive penalty parameter σ_(1,-1), an initial Hessian approximation B₁, and a tolerance ε ≥ 0. At each stage k ≥ 1, Step 2 solves the SQP subproblem (12.2.1)-(12.2.3) for the recorded direction d_k via the chapter's canonical Wilson-Han-Powell SQP subproblem owner and stops when ‖d_k‖ ≤ ε. Otherwise the inner Step-3 loop starts from βₖ,0 = 1, chooses each σₖ,i so that (12.7.7) holds, accepts the first index satisfying Φₖ,i(βₖ,i) ≤ Φₖ,i(0) + μ βₖ,i Φₖ,i'(0), and otherwise replaces βₖ,i by some βₖ,i+1 ∈ [β₁, β₂] βₖ,i. Step 4 updates x_(k + 1) = x_k + βₖ,i d_k, sets σ_(k + 1),-1 = σₖ,i, and updates B_(k + 1) by the recorded Hessian-update rule.
variable {n me mi : ℕ}
local notation "Point" => EuclideanSpace ℝ (Fin n)
local notation "MatrixN" => Matrix (Fin n) (Fin n) ℝ
-- Domain sampling for this refine pass:
-- * primary domain: Chapter 12 Powell-Yuan SQP line search and stage updates;
-- * inspected project owners:
-- `WilsonHanPowellSubproblem.IsSearchDirection` in `Definition_12_2_extra_1` for the
-- canonical Step-2 SQP search-direction surface,
-- `StandardPenaltyProblem.nonsmoothExactPenalty` in `Chapter10.Definition_10_6_extra_1` as the
-- chapter's penalty owner reused by the Section 12.7 analysis, and
-- `IsOneSidedDescentDirection` in `Lemma_12_2_1` as the line-search-side predicate layer;
-- * source-facing layer kept here: the Powell-Yuan algorithm data with its recorded initial
-- point, initial penalty parameter, Hessian approximation, and Step-4 update rule;
-- * primitive data vs. derived API: the Step-2 SQP subproblem is primitive through the chapter
-- owner `WilsonHanPowellSubproblem`, while the Step-3 acceptance predicate remains local here
-- because the later Section 12.7 theory files already import this algorithm file.
structure PowellYuanMethod (n me mi : ℕ) where
beta₁ : ℝ
beta₂ : ℝ
μ : ℝ
tolerance : ℝ
initialPoint : EuclideanSpace ℝ (Fin n)
initialSigma : ℝ
initialHessianApproximation : Matrix (Fin n) (Fin n) ℝ
iterate : ℕ → EuclideanSpace ℝ (Fin n)
searchDirection : ℕ → EuclideanSpace ℝ (Fin n)
acceptedInnerIndex : ℕ → ℕ
beta : ℕ → ℕ → ℝ
sigmaStart : ℕ → ℝ
sigma : ℕ → ℕ → ℝ
phi : ℕ → ℕ → ℝ → ℝ
phiDerivAtZero : ℕ → ℕ → ℝ
phiHasDerivAtZero : ∀ k i : ℕ, HasDerivAt (phi k i) (phiDerivAtZero k i) 0
sqpSubproblem : ℕ → WilsonHanPowellSubproblem n me mi
sigmaCondition : ℕ → ℕ → ℝ → Prop
hessianApproximation : ℕ → Matrix (Fin n) (Fin n) ℝ
hessianUpdateRule :
ℕ → Matrix (Fin n) (Fin n) ℝ → Matrix (Fin n) (Fin n) ℝ → Prop
beta₁_mem : beta₁ ∈ Set.Ioo (0 : ℝ) 1
beta₂_mem : beta₂ ∈ Set.Ioo beta₁ 1
mu_mem : μ ∈ Set.Ioo (0 : ℝ) ((1 / 2 : ℝ))
initialSigma_pos : 0 < initialSigma
tolerance_nonneg : 0 ≤ tolerance
iterate_one : iterate 1 = initialPoint
sigmaStart_one : sigmaStart 1 = initialSigma
hessianApproximation_one : hessianApproximation 1 = initialHessianApproximation
direction_solution :
∀ k : ℕ, 1 ≤ k →
(sqpSubproblem k).IsSearchDirection (searchDirection k)
stop_or_step :
∀ k : ℕ, 1 ≤ k →
‖searchDirection k‖ ≤ tolerance ∨
IsPowellYuanAcceptedInnerLoop
beta₁
beta₂
μ
(phi k)
(phiDerivAtZero k)
(sigmaCondition k)
(beta k)
(sigma k)
(acceptedInnerIndex k) ∧
powellYuanStepUpdate
iterate
searchDirection
beta
acceptedInnerIndex
sigmaStart
sigma
hessianApproximation
hessianUpdateRule
k
Lemma 12.7.2
— source only (outside the published documentation root) (Lean source)
Lean contributors (project-level attribution): Chenyi Li, Wanli Ma, Zichen Wang.
Chapter12 Lemma 12.7.2 (1): assume that the iterate sequence x_k, the search directions d_k, and the Hessian models B_k of the Section 12.7 Powell-Yuan smooth exact penalty method method are bounded. If A(x) is full column rank for every x ∈ ℝ^n, encoded as injectivity of constraintJacobian x, and if there exists δ > 0 such that δ * ‖d‖^2 ≤ ⟪d, B_k d⟫ for every k and every direction satisfying A(x_k)ᵀ d = 0, then there exists a positive integer k' such that the accepted penalty parameter σ_(k, i_k) = σ_(k',-1) = σbar > 0 for all k ≥ k'.
open Filter
variable {n m : ℕ}
-- Domain sampling for this file:
-- * primary domain: Section 12.7 Powell-Yuan smooth exact penalty SQP iterates;
-- * sampled owner declarations:
-- `PowellYuanMethod.acceptedPenaltyParameter`,
-- `PowellYuanMethod.hessianOperator`,
-- `Bornology.IsBounded`,
-- and `SmoothExactPenaltyMethod`;
-- * source-facing layer here: the continuous-linear-map method owner and the eventual
-- penalty-parameter stabilization statement of Lemma 12.7.2;
-- * core/canonical layer reused here: `Bornology.IsBounded` for bounded ranges and the
-- Section 12.7 algorithm owner from `Algorithm_12_7_1`;
-- * bridge/view layer here: `method.hessianOperator` and `method.constraintJacobian`, the
-- continuous-linear-map surfaces used for formulas of the form `A(x)ᵀ d = 0`.
theorem penaltyParameters_eventuallyConstant_of_bounded
(method : SmoothExactPenaltyMethod n m)
(hx_bounded : Bornology.IsBounded (Set.range method.iterate))
(hd_bounded : Bornology.IsBounded (Set.range method.searchDirection))
(hB_bounded : Bornology.IsBounded (Set.range method.hessianOperator))
(hA_fullColumnRank : ∀ x : Point n, Function.Injective (method.constraintJacobian x))
{δ : ℝ} (hδ : 0 < δ)
(hNullspaceCurvature :
∀ k : ℕ, ∀ d : Point n,
ContinuousLinearMap.adjoint (method.constraintJacobian (method.iterate k)) d = 0 →
δ * ‖d‖ ^ (2 : ℕ) ≤ inner ℝ d (method.hessianOperator k d)) :
∃ k' : ℕ,
0 < k' ∧ PenaltyParameterStabilizesAt method k'
Theorem 12.7.3
— source only (outside the published documentation root) (Lean source)
Lean contributors (project-level attribution): Chenyi Li, Wanli Ma, Zichen Wang.
Chapter12 Theorem 12.7.3: under the hypotheses of Chapter12 Lemma 12.7.2 for the Section 12.7 smooth exact penalty method method generated by Algorithm 12.7.1 for the fixed equality-constrained problem (12.7.4)-(12.7.5), assume problem.objective and every component of problem.constraint are continuously differentiable. Then any accumulation point of the iterate sequence {x_k}, encoded by a strictly monotone subsequence converging to xStar, is a KKT point of problem.
open Filter
variable {n m : ℕ}
local notation "Multiplier" => LagrangeNewtonMultiplier m
-- Semantic recall: `lean_leansearch` surfaced generic accumulation-point APIs such as
-- `TopologicalSpace.FirstCountableTopology.tendsto_subseq`, while local Chapter 12 precedent
-- states accumulation points through a strictly monotone subsequence and `Tendsto`. This file
-- reuses the chapter SQP owners `sqpSubproblemObjective` and
-- `satisfiesSqpLinearizedConstraints`, the exact-penalty owner
-- `problem.toStandardPenaltyProblem.l1ExactPenalty`, and the scalar penalty path
-- `sqpPenaltyPath`, while tying `method.constraintJacobian` explicitly to the fixed problem's
-- constraint map.
theorem smoothExactPenalty_accumulationPoint_isKKTPoint
(problem : EqualityConstrainedProblem n m)
(method : SmoothExactPenaltyMethodFor problem)
(hObjectiveC1 : ContDiff ℝ 1 problem.objective)
(hConstraintC1 : ∀ i : Fin m, ContDiff ℝ 1 (problem.constraint i))
(hx_bounded : Bornology.IsBounded (Set.range method.iterate))
(hd_bounded : Bornology.IsBounded (Set.range method.searchDirection))
(hB_bounded : Bornology.IsBounded (Set.range method.hessianOperator))
(hA_fullColumnRank : ∀ x : Point n, Function.Injective (method.constraintJacobian x))
{δ : ℝ} (hδ : 0 < δ)
(hNullspaceCurvature :
∀ k : ℕ, ∀ d : Point n,
(method.constraintJacobian (method.iterate k)).adjoint d = 0 →
δ * ‖d‖ ^ (2 : ℕ) ≤ inner ℝ d (method.hessianOperator k d))
{xStar : Point n} {φ : ℕ → ℕ}
(hφ : StrictMono φ)
(hxStar : Tendsto (method.iterate ∘ φ) atTop (nhds xStar)) :
∃ lamStar : Multiplier, problem.IsKKTPoint xStar lamStar
Lemma 12.7.4
— source only (outside the published documentation root) (Lean source)
Lean contributors (project-level attribution): Chenyi Li, Wanli Ma, Zichen Wang.
Chapter12 Lemma 12.7.4: assume that the hypotheses of Chapter12 Lemma 12.7.2 hold for the Section 12.7 smooth exact penalty method method, and that the iterate sequence x_k converges to xStar. For any subsequence κ, if the trial-point error ‖x_(κ i) + d_(κ i) - xStar‖ / ‖x_(κ i) - xStar‖ tends to 0, encoded by the chapter owner HasSuperlinearlyConvergentStep (method.iterate ∘ κ) (method.searchDirection ∘ κ) xStar, then the accepted Step-3 steplength is eventually the full step method.stepSizeAt (κ i) = 1.
open Filter
variable {n m : ℕ}
-- Domain sampling for this file:
-- * primary domain: subsequential trial-step asymptotics for the Section 12.7 smooth exact
-- penalty SQP method;
-- * sampled owner declarations:
-- `HasSuperlinearlyConvergentStep`,
-- `hasSuperlinearlyConvergentStep_iff_isLittleO`,
-- `PowellYuanMethod.stepSizeAt`,
-- `PowellYuanMethod.iterate_succ_eq_trialPoint`,
-- and `SmoothExactPenaltyMethod`;
-- * source/core/bridge triage:
-- `eventually_fullStep_along_subsequence_of_trialPoint_superlinearStep` is the source-facing
-- theorem because Chapter 12 already owns both the trial-step notion through
-- `HasSuperlinearlyConvergentStep` and the accepted Step-3 steplength through
-- `PowellYuanMethod.stepSizeAt`;
-- `=o[atTop]` is the core/canonical asymptotic API;
-- `eventually_fullStep_along_subsequence_of_trialPoint_isLittleO` is the bridge theorem that
-- keeps the explicit little-`o` hypothesis surface.
-- * primitive vs. derived API:
-- the primitive trial-step datum is the owner predicate on the subsequence
-- `(method.iterate ∘ κ, method.searchDirection ∘ κ)`, together with the algorithm owner
-- `method.stepSizeAt` for the accepted Step-3 steplength;
-- the explicit little-`o` condition and the iterate identity
-- `x_(κ i + 1) = x_(κ i) + d_(κ i)` are derived bridge data.
variable
(method : SmoothExactPenaltyMethod n m)
(hx_bounded : Bornology.IsBounded (Set.range method.iterate))
(hd_bounded : Bornology.IsBounded (Set.range method.searchDirection))
(hB_bounded : Bornology.IsBounded (Set.range method.hessianOperator))
(hA_fullColumnRank : ∀ x : Point n, Function.Injective (method.constraintJacobian x))
{δ : ℝ} (hδ : 0 < δ)
(hNullspaceCurvature :
∀ k : ℕ, ∀ d : Point n,
(method.constraintJacobian (method.iterate k)).adjoint d = 0 →
δ * ‖d‖ ^ (2 : ℕ) ≤ inner ℝ d (method.hessianOperator k d))
{xStar : Point n}
(hxstar : Tendsto method.iterate atTop (nhds xStar))
(κ : ℕ → ℕ)
(hκ : StrictMono κ)
include
method
hx_bounded
hd_bounded
hB_bounded
hA_fullColumnRank
hδ
hNullspaceCurvature
hxstar
κ
hκ
theorem eventually_fullStep_along_subsequence_of_trialPoint_superlinearStep
(htrial :
HasSuperlinearlyConvergentStep
(method.iterate ∘ κ)
(method.searchDirection ∘ κ)
xStar) :
∀ᶠ i : ℕ in atTop,
method.stepSizeAt (κ i) = 1
Theorem 12.7.5
— source only (outside the published documentation root) (Lean source)
Lean contributors (project-level attribution): Chenyi Li, Wanli Ma, Zichen Wang.
Chapter12 Theorem 12.7.5: assume that the hypotheses of Chapter12 Lemma 12.7.2 hold for the Section 12.7 smooth exact penalty method method, and that the iterate sequence x_k converges to xStar. If the trial-point ratio (12.7.19) ‖x_k + d_k - xStar‖ / ‖x_k - xStar‖ tends to 0, encoded by HasSuperlinearlyConvergentStep method.iterate method.searchDirection xStar, then the accepted Step-3 steplength is eventually the full step method.stepSizeAt k = 1. Under the current algorithm owner this is the source-facing conclusion: Step 4 only records the raw update x_(k + 1) = x_k + β_k d_k on nonterminal stages, so iterate-level consequences require a separate continuation-tail hypothesis.
open Filter
variable {n m : ℕ}
-- Domain sampling for this file:
-- * primary domain: eventual full-step acceptance and induced `Q`-superlinear iterate
-- convergence for the Section 12.7 smooth exact penalty SQP method;
-- * sampled owner declarations:
-- `SmoothExactPenaltyMethod`,
-- `eventually_fullStep_along_subsequence_of_trialPoint_superlinearStep`,
-- `HasSuperlinearlyConvergentStep`,
-- and `HasQSuperlinearConvergenceTo`;
-- * source/core/bridge triage:
-- the source-facing layer here is the eventual full-step conclusion
-- `method.stepSizeAt k = 1` and its Step-4 iterate-update consequence;
-- the core/canonical owners are the method owner `SmoothExactPenaltyMethod` and the chapter
-- convergence owners `HasSuperlinearlyConvergentStep` and `HasQSuperlinearConvergenceTo`;
-- the trial-point ratio wording and raw Step-4 update are bridge views of those owners;
-- * primitive vs. derived API:
-- the primitive data are the method owner together with the boundedness, rank, and
-- nullspace-curvature hypotheses already used in `Lemma_12_7_4`;
-- the eventual update identity and `Q`-superlinear iterate convergence are derived
-- consequences once eventual continuation is supplied.
variable
(method : SmoothExactPenaltyMethod n m)
(hx_bounded : Bornology.IsBounded (Set.range method.iterate))
(hd_bounded : Bornology.IsBounded (Set.range method.searchDirection))
(hB_bounded : Bornology.IsBounded (Set.range method.hessianOperator))
(hA_fullColumnRank : ∀ x : Point n, Function.Injective (method.constraintJacobian x))
{δ : ℝ} (hδ : 0 < δ)
(hNullspaceCurvature :
∀ k : ℕ, ∀ d : Point n,
(method.constraintJacobian (method.iterate k)).adjoint d = 0 →
δ * ‖d‖ ^ (2 : ℕ) ≤ inner ℝ d (method.hessianOperator k d))
include
method
hx_bounded
hd_bounded
hB_bounded
hA_fullColumnRank
hδ
hNullspaceCurvature
-- Semantic recall: the Section 12.7 method owner now lives in `Lemma_12_7_2`, and this file
-- only adds the Section 12.7 main theorem while reusing the chapter's canonical
-- `HasSuperlinearlyConvergentStep` owner for the trial-point ratio `(12.7.19)`. The accepted
-- Step-3 steplength `method.stepSizeAt` is the source-facing owner conclusion here; the raw
-- iterate update and the Chapter 1 `HasQSuperlinearConvergenceTo` conclusion are only bridge
-- consequences once an explicit eventual-continuation tail is supplied.
theorem eventually_fullStep_of_trialPointRatio_tendsto_zero
{xStar : Point n}
(hxstar : Tendsto method.iterate atTop (nhds xStar))
(htrial : HasSuperlinearlyConvergentStep method.iterate method.searchDirection xStar) :
∀ᶠ k in atTop, method.stepSizeAt k = 1
12.8 — Reduced Hessian Matrix Method
Theorem 12.8.1
— source only (outside the published documentation root) (Lean source)
Lean contributors (project-level attribution): Chenyi Li, Wanli Ma, Zichen Wang.
Chapter12 Theorem 12.8.1: let d_k be the reduced-Hessian step from (12.8.26), so that x_(k + 1) = x_k + d_k. If x_k ⟶ x*, A(x*) has full column rank, the reduced-Hessian second-order sufficient condition holds at x* for W(x*, λ*), ‖B_k⁻¹‖ is uniformly bounded, and the reduced-Hessian error ratio (12.8.27) tends to 0, then the two-step source ratio (12.8.28) holds. The source-facing conclusion is expressed by the chapter owner HasSuperlinearlyConvergentStep applied to the two-step displacement twoStepDisplacement x.
open Filter
variable {Point Multiplier Reduced : Type*}
variable [NormedAddCommGroup Point] [InnerProductSpace ℝ Point] [CompleteSpace Point]
variable [NormedAddCommGroup Multiplier] [InnerProductSpace ℝ Multiplier]
[CompleteSpace Multiplier]
-- Domain sampling:
-- * primary domain: reduced-Hessian local convergence rates for equality-constrained
-- optimization in Hilbert spaces, with reduced-space maps parametrizing `ker(A(x_k)ᵀ)`;
-- * sampled owners in the minimal semantic closure:
-- - Chapter 9 `IsReducedNullMatrix`,
-- - Chapter 13 `IsNullSpaceBasisFor`,
-- - Chapter 12 `HasSuperlinearlyConvergentStep`,
-- - Chapter 01 `HasQSuperlinearConvergenceTo`.
-- * best owner abstraction: the reduced-space maps `Z_k` should be recorded first through the
-- null-space owner pattern "range equals `ker(A(x_k)ᵀ)`", before using `Z_kᵀ` in the reduced
-- Hessian equations; this null-space owner itself only needs a normed reduced coordinate
-- space, while Hilbert-space structure on `Reduced` enters only once `Z_kᵀ` is used in the
-- reduced-Hessian equations. The source-facing conclusion `(12.8.28)` is then a two-step
-- instance of the chapter owner `HasSuperlinearlyConvergentStep`, with step
-- `twoStepDisplacement x k = x (k + 2) - x k`.
-- * primitive data vs derived API:
-- - primitive/source data: `IsReducedNullMap`, `IsReducedHessianStep`,
-- `ReducedHessianSecondOrderSufficientCondition`, the iterate update `x (k + 1) = x k + d k`,
-- and the reduced-Hessian ratio from `(12.8.27)`;
-- - derived/bridge API: `twoStepDisplacement`, `reducedHessianErrorRatio`, and the bridge from
-- the two-step source ratio to Chapter 1 `Q`-superlinear convergence of the even subsequence.
-- * source/core/bridge triage:
-- - source-facing: `IsReducedNullMap`, `IsReducedHessianStep`,
-- `ReducedHessianSecondOrderSufficientCondition`, `twoStepDisplacement`,
-- `reducedHessianErrorRatio`, and the main theorem below stated via
-- `HasSuperlinearlyConvergentStep`;
-- - core/canonical: `HasSuperlinearlyConvergentStep`, `ContinuousLinearMap.adjoint`,
-- `ContinuousLinearMap.IsInvertible`, `ContinuousLinearMap.inverse`, `Function.Injective`,
-- `Tendsto`, and `HasQSuperlinearConvergenceTo`;
-- - bridge/view: the explicit unfold lemmas and the even-subsequence bridge theorem below.
variable [NormedAddCommGroup Reduced] [InnerProductSpace ℝ Reduced] [CompleteSpace Reduced]
theorem reducedHessianMethod_convergesTwoStepQSuperlinearly_of_errorRatio_tendsto_zero
(x d g : ℕ → Point)
(c : ℕ → Multiplier)
(A : Point → Multiplier →L[ℝ] Point)
(B : ℕ → Reduced →L[ℝ] Reduced)
(ZAt : Point → Reduced →L[ℝ] Point)
(W : Point → Multiplier → Point →L[ℝ] Point)
(xStar : Point)
(lambdaStar : Multiplier)
(h_stepDef :
∀ k : ℕ, IsReducedHessianStep (g k) (A (x k)) (c k) (B k) (ZAt (x k)) (d k))
(h_update : ∀ k : ℕ, x (k + 1) = x k + d k)
(hx : Tendsto x atTop (nhds xStar))
(h_fullColumnRank : Function.Injective (A xStar))
(h_sosc :
ReducedHessianSecondOrderSufficientCondition (A xStar) (W xStar lambdaStar))
(hB_invertible : ∀ k : ℕ, (B k).IsInvertible)
(h_inverse_bounded : ∃ C > 0, ∀ k : ℕ, ‖(B k).inverse‖ ≤ C)
(h_ratio :
Tendsto
(reducedHessianErrorRatio
B
(fun k ↦ ZAt (x k))
(ZAt xStar)
(W xStar lambdaStar)
d)
atTop
(nhds (0 : ℝ))) :
HasSuperlinearlyConvergentStep x (twoStepDisplacement x) xStar
Remark 12.8.extra.1
Lean contributors (project-level attribution): Chenyi Li, Wanli Ma, Zichen Wang.
The source remark records that the reduced Hessian matrix method was developed from the Lagrange-Newton method.
inductive ReducedHessianMethodDevelopedFromLagrangeNewton : Prop where
| introNotation 12.8.extra.2
— source only (outside the published documentation root) (Lean source)
Lean contributors (project-level attribution): Chenyi Li, Wanli Ma, Zichen Wang.
Chapter12 Notation 12.8-extra-2 (2): A_k = A(x_k) = ∇ c(x_k)ᵀ is the direct stagewise evaluation of the canonical Jacobian owner, viewed as a Euclidean linear map.
variable {n m : ℕ}
local notation "Point" => LagrangeNewtonPoint n
local notation "Multiplier" => LagrangeNewtonMultiplier m
local notation "ReducedHessian" => Point →L[ℝ] Point
-- Domain-style sampling pass for this item:
-- * primary domain: Chapter 12 SQP / reduced-Hessian stage notation on the operator-valued
-- Jacobian surface.
-- * sampled owner declarations in the minimal semantic closure:
-- - `LagrangeNewtonPoint`
-- - `LagrangeNewtonMultiplier`
-- - `constraintJacobian`
-- - `lagrangeNewtonTrialMultiplier`
-- * best owner abstraction: this file lives at the bridge/view layer. The primitive owners are
-- the ambient Chapter 12 point and multiplier owners `LagrangeNewtonPoint` and
-- `LagrangeNewtonMultiplier`, the reduced-Hessian field `W`, the Chapter 10 Jacobian owner
-- `constraintJacobian`, the Euclidean matrix-action bridge `Matrix.toEuclideanLin`, the
-- gradient owner `gradient`, the constraint map `c`, and the Chapter 12 trial-multiplier
-- owner `lagrangeNewtonTrialMultiplier`.
-- * primitive data vs derived API:
-- - primitive data: `W`, `constraintJacobian c`, `f`, `c`, `xSeq`, `lamSeq`, and
-- `deltaLamSeq`;
-- - derived/source-facing API: the stagewise symbols `W_k`, `A_k`, `g_k`, `c_k`, and `λ̂_k`,
-- obtained by evaluating those owners along the recorded sequences.
-- This file therefore deletes the duplicate local wheel definitions and records the textbook
-- formulas directly on the canonical owners.
-- Source/core/bridge triage:
-- * source-facing items: the displayed stage formulas `W_k`, `A_k`, `g_k`, `c_k`, and `λ̂_k`
-- * core/canonical owners: `gradient`, `constraintJacobian`, `lagrangeNewtonTrialMultiplier`
-- * bridge/view: `Matrix.toEuclideanLin`, sequence evaluation/composition, plus the
-- specialization of `lagrangeNewtonTrialMultiplier` at step size `1`
#check constraintJacobian
Supporting modules
These source modules support the indexed items and are listed separately so the chapter inventory remains complete.
-
EqualityConstrainedProblem.lean(Documentation) (Lean source)
Lean contributors (project-level attribution): Chenyi Li, Wanli Ma, Zichen Wang.