Chapter 13 — Trust-Region Methods for Constrained Problems
Proofs omitted. Hover over highlighted terms to see their Lean types.
Exercise 13.1
— source only (outside the published documentation root) (Lean source)
Lean contributors (project-level attribution): Chenyi Li, Wanli Ma, Zichen Wang.
Chapter 13 Exercise 13.1: the quadratic/ℓ∞/negative-part specialization of the Chapter 13 penalty subproblem is reformulated as the explicit quadratic program on the lifted variable (d, t) ∈ ℝ^(n+1). This declaration is the bridge/view layer from the Chapter 13 trust-region-penalty source data to Chapter 9's canonical owner QuadraticProgram.
variable {n m : ℕ}
local notation "Step" => EuclideanSpace ℝ (Fin n)
local notation "ConstraintPoint" => EuclideanSpace ℝ (Fin m)
local notation "Decision" => EuclideanSpace ℝ (Fin (n + 1))
local notation "MatrixN" => Matrix (Fin n) (Fin n) ℝ
local notation "Jacobian" => Matrix (Fin n) (Fin m) ℝ
-- Domain-style sampling for this refine pass:
-- * primary domain: trust-region penalty subproblems and their quadratic-program
-- reformulations;
-- * sampled owner declarations:
-- `linftyNorm` and `IsVectorNorm` from Chapter 01, `trustRegionPenaltySubproblem` and
-- `trustRegionPenaltyObjective` from Chapter 13, together with Chapter 9's
-- `QuadraticProgram.objective` and `QuadraticProgram.feasibleSet`;
-- * source-facing owner: `trustRegionPenaltySubproblem`;
-- * core/canonical owner: `QuadraticProgram`;
-- * bridge/view in this file: the quadratic/`ℓ∞`/negative-part specialization and its
-- lifted quadratic-program reformulation.
def reformulatedQuadraticProgram
(g : Step) (B : MatrixN) (σ : ℝ)
(c : ConstraintPoint) (A : Jacobian) (Δ : ℝ) :
QuadraticProgram (n + 1) 0 (Fintype.card (ReformulationConstraintIndex n m))
Exercise 13.2
— source only (outside the published documentation root) (Lean source)
Lean contributors (project-level attribution): Chenyi Li, Wanli Ma, Zichen Wang.
Chapter13 Exercise 13.2: an inequality-constrained null-space trust-region method extends the equality-constrained NullSpaceTrustRegionMethod of Algorithm 13.4.1 by adding a fixed inequality residual map and inequality Jacobian map for the constrained problem, the stagewise evaluations of those maps along the iterate sequence, feasible inequality residuals at the iterates, and working sets whose recorded indices are active inequalities. It requires nullSpaceBasis k to parametrize the null space of the combined equality and active-inequality linearization while trialStep k stays in the mixed trust-region feasible set.
variable {ambientDim eqConstraintDim ineqConstraintDim tangentDim : ℕ}
local notation "Point" => EuclideanSpace ℝ (Fin ambientDim)
local notation "EqConstraintPoint" => EuclideanSpace ℝ (Fin eqConstraintDim)
local notation "IneqConstraintPoint" => EuclideanSpace ℝ (Fin ineqConstraintDim)
local notation "TangentPoint" => EuclideanSpace ℝ (Fin tangentDim)
local notation "EqJacobian" => Matrix (Fin ambientDim) (Fin eqConstraintDim) ℝ
local notation "IneqJacobian" => Matrix (Fin ambientDim) (Fin ineqConstraintDim) ℝ
-- Domain sampling for this exercise:
-- * core/canonical owner: `NullSpaceTrustRegionMethod` from `Algorithm_13_4_1`
-- * inspected companion API there: `nullSpaceReducedGradient`,
-- `NullSpaceTrustRegionMethod.terminatedAt`, and
-- `NullSpaceTrustRegionMethod.nextRadiusConditionAt`
-- * checked nearby Chapter 13 feasible-set owners such as `cauchyScaleSet` in
-- `Definition_13_3_extra_2`
-- The equality-constrained null-space method already has its owner upstream, so this file keeps
-- only the inequality-specific working-set layer.
structure InequalityConstrainedNullSpaceTrustRegionMethod
(ambientDim eqConstraintDim ineqConstraintDim tangentDim : ℕ)
extends NullSpaceTrustRegionMethod ambientDim eqConstraintDim tangentDim where
inequalityResidualAt :
EuclideanSpace ℝ (Fin ambientDim) → EuclideanSpace ℝ (Fin ineqConstraintDim)
inequalityJacobianAt :
EuclideanSpace ℝ (Fin ambientDim) →
Matrix (Fin ambientDim) (Fin ineqConstraintDim) ℝ
inequalityResidual : ℕ → EuclideanSpace ℝ (Fin ineqConstraintDim)
inequalityJacobian : ℕ → Matrix (Fin ambientDim) (Fin ineqConstraintDim) ℝ
workingSet : ℕ → Set (Fin ineqConstraintDim)
inequalityResidual_spec :
∀ k : ℕ, 1 ≤ k →
inequalityResidual k = inequalityResidualAt (iterate k)
inequalityJacobian_spec :
∀ k : ℕ, 1 ≤ k →
inequalityJacobian k = inequalityJacobianAt (iterate k)
iterate_inequality_feasible :
∀ k : ℕ, 1 ≤ k →
∀ i : Fin ineqConstraintDim, 0 ≤ inequalityResidual k i
workingSet_subset_activeSet :
∀ k : ℕ, 1 ≤ k →
∀ i : Fin ineqConstraintDim,
i ∈ workingSet k → inequalityResidual k i = 0
nullSpaceBasis_parametrizes_workingLinearizedNullSpace :
∀ k : ℕ, 1 ≤ k →
∀ d : EuclideanSpace ℝ (Fin ambientDim),
inWorkingLinearizedNullSpace
(constraintJacobian k)
(inequalityJacobian k)
(workingSet k)
d ↔
∃ p : EuclideanSpace ℝ (Fin tangentDim),
d = Matrix.toEuclideanLin (nullSpaceBasis k) p
trialStep_feasible :
∀ k : ℕ, 1 ≤ k →
trialStep k ∈
mixedNullSpaceTrustRegionFeasibleSet
(radius k)
(constraintResidual k)
(constraintJacobian k)
(inequalityResidual k)
(inequalityJacobian k)
(workingSet k)
Exercise 13.3
Lean contributors (project-level attribution): Chenyi Li, Wanli Ma, Zichen Wang.
Chapter13 Exercise 13.3 (3): for the solution chapter13Exercise133Solution = (2, 0)ᵀ and the multiplier pair (chapter13Exercise133Lambda, chapter13Exercise133Mu) = (1, 0), the Lagrangian Hessian `cdtShiftedHessian chapter13Exercise133B chapter13Exercise133A chapter13Exercise133Lambda chapter13Exercise133Mu` has one negative eigenvalue.
open Matrix
local notation "StepVector" => EuclideanSpace ℝ (Fin 2)
local notation "Matrix2" => Matrix (Fin 2) (Fin 2) ℝ
theorem chapter13Exercise133HasOneNegativeEigenvalue :
∃ i j : Fin 2,
i ≠ j ∧
chapter13Exercise133ShiftedHessianIsHermitian.eigenvalues i < 0 ∧
0 < chapter13Exercise133ShiftedHessianIsHermitian.eigenvalues jExercise 13.4
Lean contributors (project-level attribution): Chenyi Li, Wanli Ma, Zichen Wang.
Chapter13 Exercise 13.4: the explicit CDT subproblem with data B = chapter13Exercise134B = -I₂, g = 0, A = chapter13Exercise134A = I₂, c = 0, Δ = 1, and ξ = 0 has the solution chapter13Exercise134Solution = 0; for the multiplier pair (chapter13Exercise134Lambda, chapter13Exercise134Mu) = (0, 0), the Lagrangian Hessian `cdtShiftedHessian chapter13Exercise134B chapter13Exercise134A chapter13Exercise134Lambda chapter13Exercise134Mu` has two negative eigenvalues.
open Matrix
local notation "StepVector" => EuclideanSpace ℝ (Fin 2)
local notation "Matrix2" => Matrix (Fin 2) (Fin 2) ℝ
theorem chapter13Exercise134HasTwoNegativeEigenvalues :
∃ i j : Fin 2,
i ≠ j ∧
chapter13Exercise134ShiftedHessianIsHermitian.eigenvalues i < 0 ∧
chapter13Exercise134ShiftedHessianIsHermitian.eigenvalues j < 0Exercise 13.5
— source only (outside the published documentation root) (Lean source)
Lean contributors (project-level attribution): Chenyi Li, Wanli Ma, Zichen Wang.
Chapter13 Exercise 13.5: let C, D : Matrix ι ι ℝ be symmetric. If A ∪ B = Set.univ, x ↦ xᵀ C x is nonnegative on A, and x ↦ xᵀ D x is nonnegative on B, then there exists t ∈ Set.Icc (0 : ℝ) 1 such that t • C + (1 - t) • D is positive semidefinite. The closedness assumption from the source statement is not needed for this reduction.
open Matrix Filter
-- Domain-style sampling for Exercise 13.5:
-- * primary domain: finite real symmetric matrix quadratic forms;
-- * source-facing layer from the textbook: a cover presentation saying that, for each `x`, one
-- of the two quadratic forms `x ↦ xᵀ C x` or `x ↦ xᵀ D x` is nonnegative;
-- * core/canonical owner: `Matrix.PosSemidef`;
-- * sampled canonical declarations in this domain:
-- `Matrix.PosSemidef`,
-- `Matrix.posSemidef_iff_dotProduct_mulVec`,
-- `Matrix.PosSemidef.of_dotProduct_mulVec_nonneg`,
-- `Matrix.PosSemidef.dotProduct_mulVec_nonneg`;
-- * layer triage:
-- - core/canonical owner: the positive-semidefinite matrix predicate;
-- - bridge/view: a set-cover hypothesis implying the pointwise disjunctive nonnegativity used
-- by the main statement;
-- * primitive data for the owner-level theorem: only `C`, `D`, their symmetry, and the pointwise
-- disjunction `0 ≤ xᵀ C x ∨ 0 ≤ xᵀ D x`;
-- * derived API: the cover-based source presentation.
variable {ι : Type*} [Fintype ι]
theorem exists_posSemidef_convexCombination_of_quadratic_nonneg_on_cover
(C D : Matrix ι ι ℝ) (hC_symm : C.IsSymm) (hD_symm : D.IsSymm)
(A B : Set (ι → ℝ)) (h_cover : A ∪ B = Set.univ)
(hC_nonneg : ∀ x ∈ A, 0 ≤ dotProduct x (C.mulVec x))
(hD_nonneg : ∀ x ∈ B, 0 ≤ dotProduct x (D.mulVec x)) :
∃ t ∈ Set.Icc (0 : ℝ) 1, (t • C + (1 - t) • D).PosSemidef
Exercise 13.6
— source only (outside the published documentation root) (Lean source)
Lean contributors (project-level attribution): Chenyi Li, Wanli Ma, Zichen Wang.
Clause (1): under Chapter 13 Assumption 13.6.2, if the Powell-Yuan trust-region run does not terminate finitely, then the trust-region radii Δ_k converge to 0, encoded on the shifted sequence k ↦ method.radius (k + 1).
#check PowellYuanTrustRegionMethod.tendsto_radius_zero_of_not_finitelyTerminates
13.1 — Introduction
Remark 13.1.extra.1
— source only (outside the published documentation root) (Lean source)
Lean contributors (project-level attribution): Chenyi Li, Wanli Ma, Zichen Wang.
A step satisfies the chosen trust-region bound exactly when the chosen Chapter 01 vector norm ρ evaluates to at most Δ on the coordinate realization d.ofLp.
open scoped BigOperators
variable {n m : ℕ}
local notation "Point" => EuclideanSpace ℝ (Fin n)
local notation "ConstraintPoint" => EuclideanSpace ℝ (Fin m)
local notation "Jacobian" => Matrix (Fin n) (Fin m) ℝ
-- Domain-style sampling:
-- * primary domain: constrained trust-region feasibility systems with a chosen vector norm on
-- `ℝ^n`, built from affine linearized constraint residuals and penalty/surrogate replacements;
-- * sampled owner declarations:
-- `IsVectorNorm`, `IsVectorNorm.toSeminorm`, and `IsVectorNorm.toAddGroupNorm` in
-- Chapter 01 Definition 1.2.1, together with `linearizedConstraintValue` in
-- Chapter 13 Definition 13.3-extra-2;
-- * core/canonical owners reused here: `IsVectorNorm` for the chosen trust-region norm and
-- `linearizedConstraintValue` for the affine residual map `c + Aᵀ d`;
-- * primitive data in this file: the chosen vector norm `ρ` on coordinate vectors
-- `Fin n → ℝ`, together with the chosen penalty/surrogate functionals;
-- * derived API in this file: the feasible sets and trust-region penalty subproblem built from
-- those primitive choices.
--
-- Semantic recall: Chapter 13 already owns the affine residual map `c + Aᵀ d` as
-- `linearizedConstraintValue`, so this file reuses that owner instead of restating it locally.
-- The chosen trust-region norm is now expressed through Chapter 01's canonical owner
-- `IsVectorNorm`, while the scaled-constraint, piecewise-squares, and penalty constructions
-- remain source-facing.
def satisfiesTrustRegionConstraint
(ρ : (Fin n → ℝ) → ℝ) [IsVectorNorm ρ] (Δ : ℝ) (d : Point) : Prop :=
ρ d.ofLp ≤ Δ
13.2 — Linear Constraints
Algorithm 13.2.1
Lean contributors (project-level attribution): Chenyi Li, Wanli Ma, Zichen Wang.
Chapter13 Algorithm 13.2.1 records the iterate sequence x_k generated by the method.
variable {n me mi : ℕ}
local notation "Point" => EuclideanSpace ℝ (Fin n)
local notation "HessianMatrix" => Matrix (Fin n) (Fin n) ℝ
-- `LinearTrustRegion.lean` owns the fixed problem data, stage subproblem, and full algorithm
-- structure. This item keeps Algorithm 13.2.1 source-facing by exporting the generated
-- sequences `x_k`, `Δ_k`, and `B_k` together with their recorded update rules.
namespace LinearTrustRegionMethod
def iterate (method : LinearTrustRegionMethod n me mi) (k : ℕ) : Point :=
(method.stageState k).iterateTheorem 13.2.2
— source only (outside the published documentation root) (Lean source)
Lean contributors (project-level attribution): Chenyi Li, Wanli Ma, Zichen Wang.
Chapter13 Theorem 13.2.2: assume method.problem.objective is continuously differentiable on the feasible set of the original linearly constrained problem, and assume (13.2.10), formalized here by HasSourceAssumption13210 method. If the iterate sequence {x_k} generated by Algorithm 13.2.1 has at least one accumulation point, then one accumulation point of the sequence is a KKT point of the original linearly constrained optimization problem, formalized by the canonical Chapter 8 predicate on method.problem.toConstrainedOptimizationProblem.
open Filter
open scoped Matrix.Norms.Frobenius
variable {n me mi : ℕ}
local notation "Point" => EuclideanSpace ℝ (Fin n)
local notation "Multiplier" => EuclideanSpace ℝ (Fin (me + mi))
-- Semantic recall: `lean_leansearch` timed out on this item. This file therefore follows the
-- verified local precedent from `Chapter13.Algorithm_13_2_1`, the mixed-constraint bridge pattern
-- from `Chapter09.Definition_9_1_extra_1`, and the accumulation-point KKT theorem shape from
-- `Chapter11.Theorem_11_5_5`.
open LinearTrustRegionProblem
theorem linearTrustRegionMethod_existsKKTAccumulationPoint
(method : LinearTrustRegionMethod n me mi)
(hObjectiveC1 :
ContDiffOn ℝ 1 method.problem.objective method.problem.feasibleSet)
(h13210 : HasSourceAssumption13210 method)
(hAccum : method.HasAccumulationPoint) :
∃ xStar : Point,
method.HasAccumulationPointAt xStar ∧
∃ lamStar : Multiplier,
method.constrainedOptimizationProblem.IsKKTPoint xStar.ofLp lamStar.ofLp
Definition 13.2.extra.1
Lean contributors (project-level attribution): Chenyi Li, Wanli Ma, Zichen Wang.
The difference quotient (P (x - α • ∇ f x) - x) / α appearing in the projected-gradient definition.
open Filter
variable {n : ℕ}
local notation "Point" => EuclideanSpace ℝ (Fin n)
-- Semantic recall hits verified for this item:
-- Chapter 11 already owns the source nearest-point projection map `P` as
-- `nearestPointProjection`.
-- `DifferentiableAt.hasGradientAt` confirms that the source term `∇ f x` should only be used on
-- the public surface under an actual differentiability hypothesis at `x`.
def projectedGradientDifferenceQuotient
(X : Set Point) (hX_nonempty : X.Nonempty) (hX_complete : IsComplete X)
(hX_convex : Convex ℝ X) (f : Point → ℝ) (x : Point) :
ℝ → Point :=
fun α ↦
α⁻¹ •
(nearestPointProjection X hX_nonempty hX_complete hX_convex (x - α • gradient f x) - x)13.3 — Trust-Region Subproblems
Definition 13.3.extra.1
Lean contributors (project-level attribution): Chenyi Li, Wanli Ma, Zichen Wang.
The affine linearized constraint vector c + Aᵀ d.
variable {m n : ℕ}
local notation "Point" => EuclideanSpace ℝ (Fin n)
local notation "ConstraintPoint" => EuclideanSpace ℝ (Fin m)
local notation "Jacobian" => Matrix (Fin n) (Fin m) ℝ
def linearizedConstraintValue
(c : ConstraintPoint) (A : Jacobian) (d : Point) : ConstraintPoint :=
c + Matrix.toEuclideanLin A.transpose dDefinition 13.3.extra.2
— source only (outside the published documentation root) (Lean source)
Lean contributors (project-level attribution): Chenyi Li, Wanli Ma, Zichen Wang.
The Euclidean constraint space carries the source coordinatewise negative-part operation v ↦ v⁻.
variable {n m : ℕ}
local notation "Point" => EuclideanSpace ℝ (Fin n)
local notation "ConstraintPoint" => EuclideanSpace ℝ (Fin m)
local notation "Jacobian" => Matrix (Fin n) (Fin m) ℝ
-- Semantic recall:
-- * Chapter 12 already owns the affine linearized constraint map `linearizedConstraintValue`
-- together with its evaluation lemma `linearizedConstraintValue_apply`;
-- * the recurring source operation in this file is the coordinatewise negative part `v⁻` on
-- `ConstraintPoint`, exposed through mathlib's canonical `NegPart` notation rather than a
-- duplicate wrapper name;
-- * `IsMinOn` is the canonical minimizer predicate for the one-dimensional Cauchy-step problem;
-- * nearby Chapter 13 files model the trust-region geometry on `EuclideanSpace`, so this file
-- keeps the source-facing `CauchyStep` owner while reusing the existing affine residual API.
instance instNegPartConstraintPoint : NegPart ConstraintPoint
13.4 — Null Space Method
Algorithm 13.4.1
— source only (outside the published documentation root) (Lean source)
Lean contributors (project-level attribution): Chenyi Li, Wanli Ma, Zichen Wang.
Chapter13 Algorithm 13.4.1: a null-space trust-region method on a fixed constrained problem. It records x₁, Δ₁, σ₁; fixed maps for c, g, A; stagewise data x_k, Δ_k, σ_k, c_k, A_k, Z_k, g_k, B_k, d̂_k, A_k⁺, d_k, Ared_k, Pred_k, r_k; the identities c_k = c(x_k), g_k = g(x_k), A_k = A(x_k); a null-space basis matrix Z_k for ker(A_kᵀ); the canonical pseudoinverse identity A_k⁺ = (A_k)⁺; and the nonterminal update rules (13.4.24), (13.4.27), (13.4.16)-(13.4.17), (13.4.28), (13.4.29).
open scoped Matrix
open scoped Matrix.Norms.L2Operator
variable {ambientDim constraintDim tangentDim : ℕ}
local notation "Point" => EuclideanSpace ℝ (Fin ambientDim)
local notation "ConstraintPoint" => EuclideanSpace ℝ (Fin constraintDim)
local notation "TangentPoint" => EuclideanSpace ℝ (Fin tangentDim)
local notation "HessianMatrix" => Matrix (Fin ambientDim) (Fin ambientDim) ℝ
local notation "ConstraintJacobianMatrix" => Matrix (Fin ambientDim) (Fin constraintDim) ℝ
local notation "NullSpaceMatrix" => Matrix (Fin ambientDim) (Fin tangentDim) ℝ
local notation "PseudoInverseMatrix" => Matrix (Fin constraintDim) (Fin ambientDim) ℝ
-- Semantic recall: `lean_leansearch` did not surface a reusable mathlib owner for the
-- constrained null-space trust-region method of Section 13.4. Following nearby Chapter 13 and
-- Chapter 6 algorithm files, this item keeps the stopping residual, the Step-2 penalty test and
-- reset, the Step-4 actual/predicted reductions, the acceptance update, and the radius-choice
-- rule explicit on the main owner.
structure NullSpaceTrustRegionMethod (n m t : ℕ) where
β₀ : ℝ
β₁ : ℝ
β₂ : ℝ
β₃ : ℝ
β₄ : ℝ
ρ : ℝ
ρ₁ : ℝ
ρ₂ : ℝ
ε : ℝ
initialPoint : EuclideanSpace ℝ (Fin n)
initialRadius : ℝ
initialIncomingSigma : ℝ
penaltyFunction : EuclideanSpace ℝ (Fin n) → ℝ
constraintResidualAt : EuclideanSpace ℝ (Fin n) → EuclideanSpace ℝ (Fin m)
gradientAt : EuclideanSpace ℝ (Fin n) → EuclideanSpace ℝ (Fin n)
constraintJacobianAt : EuclideanSpace ℝ (Fin n) → Matrix (Fin n) (Fin m) ℝ
predictedModel : ℕ → EuclideanSpace ℝ (Fin n) → ℝ
iterate : ℕ → EuclideanSpace ℝ (Fin n)
radius : ℕ → ℝ
incomingSigma : ℕ → ℝ
stageSigma : ℕ → ℝ
constraintResidual : ℕ → EuclideanSpace ℝ (Fin m)
constraintJacobian : ℕ → Matrix (Fin n) (Fin m) ℝ
nullSpaceBasis : ℕ → Matrix (Fin n) (Fin t) ℝ
gradient : ℕ → EuclideanSpace ℝ (Fin n)
hessianApproximation : ℕ → Matrix (Fin n) (Fin n) ℝ
dHat : ℕ → EuclideanSpace ℝ (Fin n)
aPseudoInverse : ℕ → Matrix (Fin m) (Fin n) ℝ
trialStep : ℕ → EuclideanSpace ℝ (Fin n)
actualReduction : ℕ → ℝ
predictedReduction : ℕ → ℝ
ratio : ℕ → ℝ
beta3_pos : 0 < β₃
beta3_lt_beta4 : β₃ < β₄
beta4_lt_one : β₄ < 1
one_lt_beta1 : 1 < β₁
beta0_nonneg : 0 ≤ β₀
beta0_le_beta2 : β₀ ≤ β₂
beta2_lt_one : β₂ < 1
beta2_pos : 0 < β₂
rho1_nonneg : 0 ≤ ρ₁
rho2_nonneg : 0 ≤ ρ₂
epsilon_nonneg : 0 ≤ ε
initialRadius_pos : 0 < initialRadius
initialIncomingSigma_pos : 0 < initialIncomingSigma
iterate_one : iterate 1 = initialPoint
radius_one : radius 1 = initialRadius
incomingSigma_one : incomingSigma 1 = initialIncomingSigma
radius_pos : ∀ k : ℕ, 1 ≤ k → 0 < radius k
constraintResidual_spec :
∀ k : ℕ, 1 ≤ k →
constraintResidual k = constraintResidualAt (iterate k)
gradient_spec :
∀ k : ℕ, 1 ≤ k →
gradient k = gradientAt (iterate k)
constraintJacobian_spec :
∀ k : ℕ, 1 ≤ k →
constraintJacobian k = constraintJacobianAt (iterate k)
nullSpaceBasis_spec :
∀ k : ℕ, 1 ≤ k →
IsNullSpaceBasisFor (constraintJacobian k) (nullSpaceBasis k)
aPseudoInverse_spec :
∀ k : ℕ, 1 ≤ k →
aPseudoInverse k = (constraintJacobian k)⁺
stageSigma_eq_incoming_of_stepTwoAccepts :
∀ k : ℕ, 1 ≤ k →
¬ (nullSpaceStoppingResidual
(constraintResidual k)
(nullSpaceBasis k)
(gradient k) ≤ ε) →
nullSpaceStepTwoAcceptanceCondition
(incomingSigma k)
(aPseudoInverse k)
(gradient k)
(hessianApproximation k)
(dHat k)
ρ →
stageSigma k = incomingSigma k
stageSigma_eq_reset_of_not_stepTwoAccepts :
∀ k : ℕ, 1 ≤ k →
¬ (nullSpaceStoppingResidual
(constraintResidual k)
(nullSpaceBasis k)
(gradient k) ≤ ε) →
¬ nullSpaceStepTwoAcceptanceCondition
(incomingSigma k)
(aPseudoInverse k)
(gradient k)
(hessianApproximation k)
(dHat k)
ρ →
stageSigma k =
nullSpacePenaltyUpdate
(aPseudoInverse k)
(gradient k)
(hessianApproximation k)
(dHat k)
ρ
trialStepCondition_of_not_terminated :
∀ k : ℕ, 1 ≤ k →
¬ (nullSpaceStoppingResidual
(constraintResidual k)
(nullSpaceBasis k)
(gradient k) ≤ ε) →
nullSpaceTrialStepCondition
(nullSpacePredictedReduction
(predictedModel k)
(trialStep k))
ρ₁
ρ₂
(constraintResidual k)
(nullSpaceBasis k)
(gradient k)
(radius k)
(aPseudoInverse k)
(hessianApproximation k)
(dHat k)
actualReduction_spec_of_not_terminated :
∀ k : ℕ, 1 ≤ k →
¬ (nullSpaceStoppingResidual
(constraintResidual k)
(nullSpaceBasis k)
(gradient k) ≤ ε) →
actualReduction k =
TrustRegionSubproblem.actualReduction
(iterate k)
penaltyFunction
(trialStep k)
predictedReduction_spec_of_not_terminated :
∀ k : ℕ, 1 ≤ k →
¬ (nullSpaceStoppingResidual
(constraintResidual k)
(nullSpaceBasis k)
(gradient k) ≤ ε) →
predictedReduction k =
nullSpacePredictedReduction
(predictedModel k)
(trialStep k)
ratio_eq_of_not_terminated :
∀ k : ℕ, 1 ≤ k →
¬ (nullSpaceStoppingResidual
(constraintResidual k)
(nullSpaceBasis k)
(gradient k) ≤ ε) →
ratio k = actualReduction k / predictedReduction k
iterate_succ_of_not_terminated :
∀ k : ℕ, 1 ≤ k →
¬ (nullSpaceStoppingResidual
(constraintResidual k)
(nullSpaceBasis k)
(gradient k) ≤ ε) →
iterate (k + 1) =
nullSpaceAcceptedPoint
β₀
(iterate k)
(trialStep k)
(ratio k)
radius_succ_spec_of_not_terminated :
∀ k : ℕ, 1 ≤ k →
¬ (nullSpaceStoppingResidual
(constraintResidual k)
(nullSpaceBasis k)
(gradient k) ≤ ε) →
nullSpaceRadiusUpdateCondition
β₁
β₂
β₃
β₄
(radius k)
(trialStep k)
(ratio k)
(radius (k + 1))
incomingSigma_succ_of_not_terminated :
∀ k : ℕ, 1 ≤ k →
¬ (nullSpaceStoppingResidual
(constraintResidual k)
(nullSpaceBasis k)
(gradient k) ≤ ε) →
incomingSigma (k + 1) = stageSigma k
Lemma 13.4.2
— source only (outside the published documentation root) (Lean source)
Lean contributors (project-level attribution): Chenyi Li, Wanli Ma, Zichen Wang.
Chapter13 Lemma 13.4.2: if the predicted reduction dominates the two Step-3 lower bounds, then it also dominates their maximum. The trust-region guard ‖dHat‖ ≤ Δ belongs to the owner-level condition (13.4.27), but this scalar max consequence uses only the two lower-bound inequalities themselves.
open scoped Matrix.Norms.L2Operator
variable {ambientDim constraintDim tangentDim : ℕ}
local notation "Point" => EuclideanSpace ℝ (Fin ambientDim)
local notation "ConstraintPoint" => EuclideanSpace ℝ (Fin constraintDim)
local notation "HessianMatrix" => Matrix (Fin ambientDim) (Fin ambientDim) ℝ
local notation "NullSpaceMatrix" => Matrix (Fin ambientDim) (Fin tangentDim) ℝ
local notation "PseudoInverseMatrix" => Matrix (Fin constraintDim) (Fin ambientDim) ℝ
theorem nullSpacePredictedReductionLowerBound
(predictedReduction ρ₁ ρ₂ : ℝ)
(c : ConstraintPoint)
(Z : NullSpaceMatrix)
(g : Point)
(trustRegionRadius : ℝ)
(APlus : PseudoInverseMatrix)
(B : HessianMatrix)
(dHat : Point)
(h_constraint :
(if ‖APlus‖₂ = 0 then
ρ₁ * ‖c‖
else
ρ₁ * min ‖c‖ (trustRegionRadius / ‖APlus‖₂)) ≤
predictedReduction)
(h_gradient :
ρ₂ * min ‖nullSpaceReducedGradient Z g‖ 1 *
min
(Real.sqrt (trustRegionRadius ^ (2 : ℕ) - ‖dHat‖ ^ (2 : ℕ)))
(‖nullSpaceReducedGradient Z g‖ / (1 + ‖B‖₂)) ≤
predictedReduction) :
max
(if ‖APlus‖₂ = 0 then
ρ₁ * ‖c‖
else
ρ₁ * min ‖c‖ (trustRegionRadius / ‖APlus‖₂))
(ρ₂ * min ‖nullSpaceReducedGradient Z g‖ 1 *
min
(Real.sqrt (trustRegionRadius ^ (2 : ℕ) - ‖dHat‖ ^ (2 : ℕ)))
(‖nullSpaceReducedGradient Z g‖ / (1 + ‖B‖₂))) ≤
predictedReduction
Lemma 13.4.3
— source only (outside the published documentation root) (Lean source)
Lean contributors (project-level attribution): Chenyi Li, Wanli Ma, Zichen Wang.
Chapter13 Lemma 13.4.3: assume f : Point → ℝ is C², the recorded gradient map method.gradientAt agrees with gradient f, the recorded constraint map method.constraintResidualAt is C² with Jacobian method.constraintJacobianAt, fix a uniform bound aBound for the stagewise Jacobian norms ‖A_k‖₂, and fix δ > 0 such that δ ≤ ‖c_k‖₂ + ‖Z_kᵀ g_k‖₂ at every book index k ≥ 1 where the Step-2 stopping test fails. Then there exists β₅ > 0 such that β₅ / M_k ≤ ‖d_k‖₂ for all such k ≥ 1, where M_k = method.hessianNormEnvelope k = max_{1 ≤ i ≤ k} ‖B_i‖₂ + 1.
open scoped Matrix.Norms.L2Operator
variable {ambientDim constraintDim tangentDim : ℕ}
local notation "Point" => EuclideanSpace ℝ (Fin ambientDim)
namespace NullSpaceTrustRegionMethod
theorem exists_trialStepNormLowerBound
(f : Point → ℝ)
(method : NullSpaceTrustRegionMethod ambientDim constraintDim tangentDim)
(h_objective_contDiff : ContDiff ℝ 2 f)
(h_gradient_eq : ∀ x : Point, _root_.gradient f x = method.gradientAt x)
(h_constraint_contDiff : ContDiff ℝ 2 method.constraintResidualAt)
(h_constraintJacobian_is_fderiv :
∀ x : Point,
fderiv ℝ method.constraintResidualAt x =
(Matrix.toEuclideanLin (method.constraintJacobianAt x).transpose).toContinuousLinearMap)
(aBound : ℝ)
(hA_bounded : ∀ k : ℕ, 1 ≤ k → ‖method.constraintJacobian k‖₂ ≤ aBound)
(δ : ℝ)
(hδ_pos : 0 < δ)
(h_residual_lb :
∀ k : ℕ, 1 ≤ k →
¬ method.terminatedAt k →
δ ≤
nullSpaceStoppingResidual
(method.constraintResidual k)
(method.nullSpaceBasis k)
(method.gradient k)) :
∃ β₅ : ℝ, 0 < β₅ ∧
∀ k : ℕ, 1 ≤ k → ¬ method.terminatedAt k →
β₅ / method.hessianNormEnvelope k ≤ ‖method.trialStep k‖
Lemma 13.4.4
Lean contributors (project-level attribution): Chenyi Li, Wanli Ma, Zichen Wang.
Chapter13 Lemma 13.4.4: let Δ and M be positive real sequences. Assume there are positive constants τ, β₁, and β₄ with β₄ ∈ (0, 1) and a subset I of indices such that Δ contracts by the factor β₁ whenever the source index k + 1 lies in I, contracts by the factor β₄ when k + 1 ∉ I, Δ k is bounded below by τ / M k, M is nondecreasing, and the exceptional subseries ∑_{k + 1 ∈ I} 1 / M (k + 1) is summable. Then the full series ∑' k, 1 / M k is summable. The separate source assumptions 0 < β₁ and 0 < Δ k are redundant for this conclusion: 0 < Δ k already follows from hτ, hM_pos, and hτ_le, so the Lean API omits both while keeping the same mathematical content. This keeps the chapter's faithful ℕ-encoding of the source's 1-based exceptional indices.
theorem summable_reciprocals_of_split_decay_and_exceptional_subseries
(Δ M : ℕ → ℝ)
(τ β₁ β₄ : ℝ)
(I : Set ℕ)
(hM_pos : ∀ k : ℕ, 0 < M k)
(hτ : 0 < τ)
(hβ₄ : β₄ ∈ Set.Ioo (0 : ℝ) 1)
(hΔ_on : ∀ k : ℕ, k + 1 ∈ I → Δ (k + 1) ≤ β₁ * Δ k)
(hΔ_off : ∀ k : ℕ, k + 1 ∉ I → Δ (k + 1) ≤ β₄ * Δ k)
(hτ_le : ∀ k : ℕ, τ / M k ≤ Δ k)
(hM_mono : ∀ k : ℕ, M k ≤ M (k + 1))
(hsummable_I : Summable (fun k : {k : ℕ // k + 1 ∈ I} ↦ 1 / M (k + 1))) :
Summable (fun k : ℕ ↦ 1 / M k)Theorem 13.4.5
— source only (outside the published documentation root) (Lean source)
Lean contributors (project-level attribution): Chenyi Li, Wanli Ma, Zichen Wang.
Chapter13 Theorem 13.4.5 (1): assume the objective f and the recorded constraint map of method are C² on an open set S containing every book-index iterate x_k with k ≥ 1, the recorded gradient map method.gradientAt, its derivative, the recorded Jacobian map method.constraintJacobianAt, and its derivative are uniformly bounded on S, and the gradient and Jacobian-identification hypotheses hold for x ∈ S; the stagewise penalty parameters σ_k recorded as method.stageSigma k eventually stabilize, the recorded penalty function is bounded below along the iterates, the stagewise Jacobians A_k and pseudoinverses A_k⁺ are uniformly bounded, and the source partial sums (13.4.63) ∑ 1 / M_k diverge via method.hessianApproximationReciprocalEnvelopePartialSum. Then the shifted Step-2 residual sequence k ↦ method.stoppingResidual (k + 1) has liminf equal to 0.
open Filter
open scoped BigOperators Matrix.Norms.L2Operator
variable {ambientDim constraintDim tangentDim : ℕ}
local notation "Point" => EuclideanSpace ℝ (Fin ambientDim)
local notation "ConstraintPoint" => EuclideanSpace ℝ (Fin constraintDim)
local notation "Method" =>
NullSpaceTrustRegionMethod ambientDim constraintDim tangentDim
-- Semantic recall: `Algorithm_13_4_1` owns the null-space trust-region method and its Step-2/3/4
-- surfaces, while `Lemma_13_4_3` owns the source denominator `method.hessianNormEnvelope`.
-- This file keeps only the Theorem 13.4.5 boundedness and partial-sum layer built on that API.
namespace NullSpaceTrustRegionMethod
variable
(f : Point → ℝ)
(S : Set Point)
(method : Method)
(h_objective_contDiff : ContDiffOn ℝ 2 f S)
(h_gradient_eq : ∀ x : Point, x ∈ S → _root_.gradient f x = method.gradientAt x)
(h_constraint_contDiff : ContDiffOn ℝ 2 method.constraintResidualAt S)
(h_constraintJacobian_is_fderiv :
∀ x : Point, x ∈ S →
fderiv ℝ method.constraintResidualAt x = method.constraintJacobianLinearization x)
(hS_open : IsOpen S)
(h_iterates_mem : ∀ k : ℕ, 1 ≤ k → method.iterate k ∈ S)
(h_gradient_bounded : Bornology.IsBounded (method.gradientAt '' S))
(h_hessian_bounded : Bornology.IsBounded ((fun x : Point ↦ fderiv ℝ method.gradientAt x) '' S))
(h_jacobian_bounded : Bornology.IsBounded (method.constraintJacobianAt '' S))
(h_jacobianDerivative_bounded :
Bornology.IsBounded
((fun x : Point ↦ fderiv ℝ method.constraintJacobianLinearization x) '' S))
(h_stageSigma_eventually_constant :
∃ σBar : ℝ, ∃ N : ℕ, ∀ k : ℕ, N ≤ k → method.stageSigma k = σBar)
(h_penalty_bounded_below :
∃ pLower : ℝ, ∀ k : ℕ, 1 ≤ k → pLower ≤ method.penaltyFunction (method.iterate k))
(h_jacobian_stages_bounded :
Bornology.IsBounded (Set.range fun k : ℕ ↦ method.constraintJacobian (k + 1)))
(h_pseudoinverse_stages_bounded :
Bornology.IsBounded (Set.range fun k : ℕ ↦ method.aPseudoInverse (k + 1)))
(h_hessianApproximation_reciprocalEnvelopePartialSum_diverges :
Tendsto method.hessianApproximationReciprocalEnvelopePartialSum atTop atTop)
theorem liminf_stoppingResidual_eq_zero_of_eventually_constant_stageSigma
: liminf (fun k : ℕ ↦ method.stoppingResidual (k + 1)) atTop = 0
13.5 — CDT Subproblem
Theorem 13.5.1
Lean contributors (project-level attribution): Chenyi Li, Wanli Ma, Zichen Wang.
Chapter13 Theorem 13.5.1 (1): let dStar be a global solution of the CDT subproblem min cdtObjective B g d on cdtFeasibleSet Δ ξ c A. Under the source assumption (13.5.10), formalized here as cdtXiMin Δ c A < ξ, there exist nonnegative multipliers lambdaStar and muStar satisfying the stationarity equation (B + lambdaStar I + muStar A Aᵀ) dStar = -(g + muStar A c) and the complementarity relations lambdaStar * (Δ - ‖dStar‖) = 0 and muStar * (ξ - ‖cdtConstraintResidual c A dStar‖) = 0.
open Matrix
variable {m n : ℕ}
local notation "StepVector" => EuclideanSpace ℝ (Fin n)
local notation "ConstraintVector" => EuclideanSpace ℝ (Fin m)
local notation "MatrixN" => Matrix (Fin n) (Fin n) ℝ
local notation "JacobianMatrix" => Matrix (Fin n) (Fin m) ℝ
theorem existsCdtOptimalityMultipliers
{B : MatrixN} {g : StepVector} {A : JacobianMatrix} {c : ConstraintVector}
{Δ ξ : ℝ} {dStar : StepVector} (hB : B.IsSymm)
(hConstraintQualification : cdtXiMin Δ c A < ξ)
(hSolution : IsCdtSolution B g A c Δ ξ dStar) :
∃ lambdaStar muStar : ℝ, IsCdtOptimalityPair B g A c Δ ξ dStar lambdaStar muStarTheorem 13.5.2
Lean contributors (project-level attribution): Chenyi Li, Wanli Ma, Zichen Wang.
Chapter13 Theorem 13.5.2: let dStar be a feasible point of the CDT subproblem with objective cdtObjective B g and feasible set cdtFeasibleSet Δ ξ c A. If there exist nonnegative multipliers lambdaStar and muStar satisfying the optimality conditions (13.5.11)-(13.5.13), and the shifted Hessian cdtShiftedHessian B A lambdaStar muStar = B + lambdaStar I + muStar A Aᵀ is positive semidefinite, then dStar is a global solution of the CDT subproblem.
variable {m n : ℕ}
local notation "StepVector" => EuclideanSpace ℝ (Fin n)
local notation "ConstraintVector" => EuclideanSpace ℝ (Fin m)
local notation "MatrixN" => Matrix (Fin n) (Fin n) ℝ
local notation "JacobianMatrix" => Matrix (Fin n) (Fin m) ℝ
theorem cdtGlobalSolution_of_optimalityPair_and_posSemidef
{B : MatrixN} {g : StepVector} {A : JacobianMatrix} {c : ConstraintVector}
{Δ ξ : ℝ} {dStar : StepVector} {lambdaStar muStar : ℝ}
(hFeasible : dStar ∈ cdtFeasibleSet Δ ξ c A)
(hOptimality : IsCdtOptimalityPair B g A c Δ ξ dStar lambdaStar muStar)
(hPosSemidef : (cdtShiftedHessian B A lambdaStar muStar).PosSemidef) :
IsCdtSolution B g A c Δ ξ dStarCorollary 13.5.3
Lean contributors (project-level attribution): Chenyi Li, Wanli Ma, Zichen Wang.
Chapter13 Corollary 13.5.3: under the source standing assumption (13.5.10), formalized as cdtXiMin Δ c A < ξ, and assuming that B is positive semidefinite, a step dStar is a global solution of the CDT subproblem (13.5.1)-(13.5.3) if and only if it is feasible and there exist nonnegative multipliers lambdaStar and muStar such that the optimality conditions (13.5.11)-(13.5.13) hold, formalized by IsCdtOptimalityPair B g A c Δ ξ dStar lambdaStar muStar. In this chapter's owner API, primal feasibility is part of IsCdtSolution and is not bundled into IsCdtOptimalityPair.
variable {m n : ℕ}
local notation "StepVector" => EuclideanSpace ℝ (Fin n)
local notation "ConstraintVector" => EuclideanSpace ℝ (Fin m)
local notation "MatrixN" => Matrix (Fin n) (Fin n) ℝ
local notation "JacobianMatrix" => Matrix (Fin n) (Fin m) ℝ
theorem cdtGlobalSolution_iff_exists_optimalityPair_of_posSemidef
{B : MatrixN} {g : StepVector} {A : JacobianMatrix} {c : ConstraintVector}
{Δ ξ : ℝ} {dStar : StepVector}
(hConstraintQualification : cdtXiMin Δ c A < ξ)
(hB : B.PosSemidef) :
IsCdtSolution B g A c Δ ξ dStar ↔
dStar ∈ cdtFeasibleSet Δ ξ c A ∧
∃ lambdaStar muStar : ℝ, IsCdtOptimalityPair B g A c Δ ξ dStar lambdaStar muStarLemma 13.5.4
Lean contributors (project-level attribution): Chenyi Li, Wanli Ma, Zichen Wang.
Chapter13 Lemma 13.5.4: under the standing assumption (13.5.10), formalized as cdtXiMin Δ c A < ξ, and assuming B is positive definite, the Euclidean-space step cdtMultiplierStep B g A c lambdaStar muStar, formalizing d(λ, μ) from (13.5.20), is a solution of the CDT subproblem (13.5.1)-(13.5.3), in the canonical owner sense IsCdtSolution, if and only if it is feasible for (13.5.2)-(13.5.3) and one of the four source multiplier cases holds.
open Matrix
variable {m n : ℕ}
local notation "StepVector" => EuclideanSpace ℝ (Fin n)
local notation "ConstraintVector" => EuclideanSpace ℝ (Fin m)
local notation "MatrixN" => Matrix (Fin n) (Fin n) ℝ
local notation "JacobianMatrix" => Matrix (Fin n) (Fin m) ℝ
theorem cdtMultiplierStep_isCdtSolution_iff_feasible_and_case_of_posDef
{B : MatrixN} {g : StepVector} {A : JacobianMatrix} {c : ConstraintVector}
{Δ ξ : ℝ} {lambdaStar muStar : ℝ}
(hConstraintQualification : cdtXiMin Δ c A < ξ)
(hB : B.PosDef) :
IsCdtSolution
B
g
A
c
Δ
ξ
(cdtMultiplierStep B g A c lambdaStar muStar) ↔
cdtMultiplierStep B g A c lambdaStar muStar ∈ cdtFeasibleSet Δ ξ c A ∧
IsCdtMultiplierCase
A
c
Δ
ξ
(cdtMultiplierStep B g A c lambdaStar muStar)
lambdaStar
muStarAlgorithm 13.5.5
Lean contributors (project-level attribution): Chenyi Li, Wanli Ma, Zichen Wang.
Algorithm 13.5.5 enters Step 3 exactly when d(0, 0) is infeasible and lies outside the trust region, so the source Step-2 test does not branch directly to Step 4.
open Matrix
variable {m n : ℕ}
local notation "StepVector" => EuclideanSpace ℝ (Fin n)
local notation "ConstraintVector" => EuclideanSpace ℝ (Fin m)
local notation "MatrixN" => Matrix (Fin n) (Fin n) ℝ
local notation "JacobianMatrix" => Matrix (Fin n) (Fin m) ℝ
-- Semantic recall: `Theorem_13_5_1` owns the CDT model, feasible set, residual threshold, and
-- shifted Hessian, while `Lemma_13_5_4` owns the multiplier-generated step `d(λ, μ)`. This file
-- therefore stays at the source-facing algorithm layer and keeps only the branch logic and
-- stopping data explicit.
--
-- Domain-style sampling for this algorithm:
-- * primary domain: CDT trust-region subproblems with linearized-constraint bounds and the
-- multiplier-generated step search of Algorithm 13.5.5;
-- * sampled owner declarations:
-- `cdtFeasibleSet`, `cdtConstraintResidual`, and `cdtXiMin` from `Theorem_13_5_1`,
-- `cdtMultiplierStep` and `IsCdtMultiplierCase` from `Lemma_13_5_4`,
-- `IsCdtSolution` from `Theorem_13_5_1`;
-- * owner choice:
-- `Theorem_13_5_1` remains the source-facing CDT subproblem owner,
-- `Lemma_13_5_4` remains the bridge/view owner for the explicit step `d(λ, μ)`,
-- and this file keeps only the source-facing branch predicates and terminal stop data of
-- Algorithm 13.5.5;
-- * primitive vs derived split:
-- the primitive data here are the Step-3/4/5 branch conditions and the selected terminal
-- multipliers,
-- while feasibility of a candidate step is derived directly from
-- `cdtMultiplierStep B g A c lambdaStar muStar ∈ cdtFeasibleSet Δ ξ c A` and should not be
-- duplicated as a second owner.
def cdtAlgorithm1355EntersStep3
(B : MatrixN) (g : StepVector) (A : JacobianMatrix) (c : ConstraintVector)
(Δ ξ : ℝ) : Prop :=
cdtMultiplierStep B g A c 0 0 ∉ cdtFeasibleSet Δ ξ c A ∧
Δ < ‖cdtMultiplierStep B g A c 0 0‖13.6 — Powell-Yuan Algorithm
Algorithm 13.6.1
— source only (outside the published documentation root) (Lean source)
Lean contributors (project-level attribution): Chenyi Li, Wanli Ma, Zichen Wang.
Chapter13 Algorithm 13.6.1: the Powell-Yuan trust-region method for constrained problems. The method records an initial point x₁, an initial radius Δ₁ > 0, a tolerance ε > 0, and parameters τ₀, τ₁, τ₂, τ₃, τ₄ satisfying 0 < τ₃ < τ₄ < 1 < τ₁ and 0 ≤ τ₀ ≤ τ₂ < 1 with 0 < τ₂. At each stage k ≥ 1, if powellYuanStoppingResidual c_k g_k A_k λ_k ≤ ε then the method stops. Otherwise the recorded state data satisfy c_k = c (x_k), g_k = g (x_k), and A_k = A (x_k) for the fixed problem maps carried by the structure, while λ_k is recorded as stagewise algorithmic data, the recorded direction d_k is a global minimizer of the Chapter 13 CDT owner cdtObjective on cdtFeasibleSet, and hence feasible for the source subproblem (13.6.1)-(13.6.3) with the recorded linearized-constraint bound ξ_k, the candidate and final predicted reductions are the explicit formula powellYuanPredictedReduction from (13.6.7), Step 3 tests powellYuanStep3AcceptanceCondition from (13.6.10) and replaces the incoming penalty parameter by powellYuanSigmaUpdate from (13.6.11) when that test fails, the ratio is Ared_k / Pred_k with Pred_k ≠ 0, the next iterate uses the acceptance threshold τ₀ from (13.6.12), the next radius uses the recorded parameters τ₁, τ₂, τ₃, τ₄ in (13.6.13), B_(k+1) satisfies the recorded update rule, sigmaCandidate (k + 1) = σ_k, and σ_(k+1) = σ_k.
open scoped Matrix Matrix.Norms.L2Operator
variable {m n : ℕ}
local notation "Point" => EuclideanSpace ℝ (Fin n)
local notation "ConstraintPoint" => EuclideanSpace ℝ (Fin m)
local notation "Multiplier" => EuclideanSpace ℝ (Fin m)
local notation "Jacobian" => Matrix (Fin n) (Fin m) ℝ
local notation "HessianApproximation" => Matrix (Fin n) (Fin n) ℝ
-- Semantic recall: Chapter 13 already uses `cdtConstraintResidual`, `cdtObjective`,
-- `cdtFeasibleSet`, and `IsCdtSolution` as the owner layer for the CDT subproblem. This file
-- keeps only the Powell-Yuan-specific residual, penalty, reduction, and update data explicit,
-- and reuses that earlier CDT owner for Step 2.
structure PowellYuanTrustRegionMethod where
hessianUpdateRule (k : ℕ) (B BNext : HessianApproximation) : Prop
tolerance : ℝ
tau0 : ℝ
tau1 : ℝ
tau2 : ℝ
tau3 : ℝ
tau4 : ℝ
initialPoint : Point
initialRadius : ℝ
constraintResidualAt : Point → ConstraintPoint
gradientAt : Point → Point
constraintJacobianAt : Point → Jacobian
iterate : ℕ → Point
constraintResidual : ℕ → ConstraintPoint
gradient : ℕ → Point
constraintJacobian : ℕ → Jacobian
multiplier : ℕ → Multiplier
trialMultiplier : ℕ → Multiplier
hessianApproximation : ℕ → HessianApproximation
radius : ℕ → ℝ
constraintBound : ℕ → ℝ
sigmaCandidate : ℕ → ℝ
sigma : ℕ → ℝ
direction : ℕ → Point
projectedDirection : ℕ → Point
predictedReductionCandidate : ℕ → ℝ
predictedReduction : ℕ → ℝ
actualReduction : ℕ → ℝ
ratio : ℕ → ℝ
tolerance_pos : 0 < tolerance
tau3_pos : 0 < tau3
tau3_lt_tau4 : tau3 < tau4
tau4_lt_one : tau4 < 1
tau1_gt_one : 1 < tau1
tau0_nonneg : 0 ≤ tau0
tau0_le_tau2 : tau0 ≤ tau2
tau2_pos : 0 < tau2
tau2_lt_one : tau2 < 1
initialRadius_pos : 0 < initialRadius
iterate_one : iterate 1 = initialPoint
radius_one : radius 1 = initialRadius
radius_pos (k : ℕ) (_ : 1 ≤ k) : 0 < radius k
constraintResidual_spec (k : ℕ) (_ : 1 ≤ k) :
constraintResidual k = constraintResidualAt (iterate k)
gradient_spec (k : ℕ) (_ : 1 ≤ k) :
gradient k = gradientAt (iterate k)
constraintJacobian_spec (k : ℕ) (_ : 1 ≤ k) :
constraintJacobian k = constraintJacobianAt (iterate k)
direction_subproblem
(k : ℕ)
(_ : 1 ≤ k)
(h_not_term : ¬ powellYuanTerminated
tolerance
(constraintResidual k)
(gradient k)
(constraintJacobian k)
(multiplier k)) :
IsCdtSolution
(hessianApproximation k)
(gradient k)
(constraintJacobian k)
(constraintResidual k)
(radius k)
(constraintBound k)
(direction k)
predictedReductionCandidate_spec
(k : ℕ)
(_ : 1 ≤ k)
(h_not_term : ¬ powellYuanTerminated
tolerance
(constraintResidual k)
(gradient k)
(constraintJacobian k)
(multiplier k)) :
predictedReductionCandidate k =
powellYuanPredictedReduction
(gradient k)
(hessianApproximation k)
(constraintJacobian k)
(constraintResidual k)
(multiplier k)
(trialMultiplier k)
(sigmaCandidate k)
(direction k)
(projectedDirection k)
sigma_eq_candidate_of_step3
(k : ℕ)
(_ : 1 ≤ k)
(h_not_term : ¬ powellYuanTerminated
tolerance
(constraintResidual k)
(gradient k)
(constraintJacobian k)
(multiplier k))
(h_step3 : powellYuanStep3AcceptanceCondition
(sigmaCandidate k)
(predictedReductionCandidate k)
(constraintResidual k)
(constraintJacobian k)
(direction k)) :
sigma k = sigmaCandidate k
sigmaUpdateDenominator_ne_zero_of_not_step3
(k : ℕ)
(_ : 1 ≤ k)
(h_not_term : ¬ powellYuanTerminated
tolerance
(constraintResidual k)
(gradient k)
(constraintJacobian k)
(multiplier k))
(h_not_step3 : ¬ powellYuanStep3AcceptanceCondition
(sigmaCandidate k)
(predictedReductionCandidate k)
(constraintResidual k)
(constraintJacobian k)
(direction k)) :
powellYuanSigmaUpdateDenominator
(constraintResidual k)
(constraintJacobian k)
(direction k) ≠ 0
sigma_eq_update_of_not_step3
(k : ℕ)
(_ : 1 ≤ k)
(h_not_term : ¬ powellYuanTerminated
tolerance
(constraintResidual k)
(gradient k)
(constraintJacobian k)
(multiplier k))
(h_not_step3 : ¬ powellYuanStep3AcceptanceCondition
(sigmaCandidate k)
(predictedReductionCandidate k)
(constraintResidual k)
(constraintJacobian k)
(direction k)) :
sigma k =
powellYuanSigmaUpdate
(sigmaCandidate k)
(predictedReductionCandidate k)
(constraintResidual k)
(constraintJacobian k)
(direction k)
predictedReduction_spec
(k : ℕ)
(_ : 1 ≤ k)
(h_not_term : ¬ powellYuanTerminated
tolerance
(constraintResidual k)
(gradient k)
(constraintJacobian k)
(multiplier k)) :
predictedReduction k =
powellYuanPredictedReduction
(gradient k)
(hessianApproximation k)
(constraintJacobian k)
(constraintResidual k)
(multiplier k)
(trialMultiplier k)
(sigma k)
(direction k)
(projectedDirection k)
predictedReduction_ne_zero_of_not_terminated
(k : ℕ)
(_ : 1 ≤ k)
(h_not_term : ¬ powellYuanTerminated
tolerance
(constraintResidual k)
(gradient k)
(constraintJacobian k)
(multiplier k)) :
predictedReduction k ≠ 0
ratio_eq
(k : ℕ)
(_ : 1 ≤ k)
(h_not_term : ¬ powellYuanTerminated
tolerance
(constraintResidual k)
(gradient k)
(constraintJacobian k)
(multiplier k)) :
ratio k = powellYuanReductionRatio (actualReduction k) (predictedReduction k)
iterate_next_of_not_terminated
(k : ℕ)
(_ : 1 ≤ k)
(h_not_term : ¬ powellYuanTerminated
tolerance
(constraintResidual k)
(gradient k)
(constraintJacobian k)
(multiplier k)) :
iterate (k + 1) =
powellYuanAcceptedPoint
tau0
(iterate k)
(direction k)
(ratio k)
radius_next_of_not_terminated
(k : ℕ)
(_ : 1 ≤ k)
(h_not_term : ¬ powellYuanTerminated
tolerance
(constraintResidual k)
(gradient k)
(constraintJacobian k)
(multiplier k)) :
radius (k + 1) =
powellYuanRadiusUpdate
tau1
tau2
tau3
tau4
(radius k)
(ratio k)
(direction k)
sigmaCandidate_next_of_not_terminated
(k : ℕ)
(_ : 1 ≤ k)
(h_not_term : ¬ powellYuanTerminated
tolerance
(constraintResidual k)
(gradient k)
(constraintJacobian k)
(multiplier k)) :
sigmaCandidate (k + 1) = sigma k
sigma_next_of_not_terminated
(k : ℕ)
(_ : 1 ≤ k)
(h_not_term : ¬ powellYuanTerminated
tolerance
(constraintResidual k)
(gradient k)
(constraintJacobian k)
(multiplier k)) :
sigma (k + 1) = sigma k
hessian_next_of_not_terminated
(k : ℕ)
(_ : 1 ≤ k)
(h_not_term : ¬ powellYuanTerminated
tolerance
(constraintResidual k)
(gradient k)
(constraintJacobian k)
(multiplier k)) :
hessianUpdateRule
k
(hessianApproximation k)
(hessianApproximation (k + 1))
Assumption 13.6.2
Lean contributors (project-level attribution): Chenyi Li, Wanli Ma, Zichen Wang.
Chapter13 Assumption 13.6.2: the Powell-Yuan iterates x k, trial points x k + d k, the Jacobian models A y, and the Hessian approximations B k satisfy the source assumptions that there is a bounded convex closed set omega : Set Point containing every stage iterate x k and trial point x k + d k for book indices k ≥ 1, that A y has full column rank for every y ∈ omega, and that the matrix sequence B k is uniformly bounded on book indices k ≥ 1, expressed through the equivalent finite-coordinate family fun i j ↦ (B k) i j.
open scoped Matrix.Norms.L2Operator
variable {n m : ℕ}
local notation "Point" => EuclideanSpace ℝ (Fin n)
local notation "ConstraintMatrix" => Matrix (Fin n) (Fin m) ℝ
local notation "MatrixN" => Matrix (Fin n) (Fin n) ℝ
-- Domain sampling for this refine pass:
-- * primary domain: bounded Euclidean trust-region stage data for Powell-Yuan Chapter 13;
-- * sampled owner declarations:
-- `Bornology.IsBounded`,
-- `Matrix.rank`,
-- `HasQuasiNewtonGlobalConvergenceAssumptions`;
-- * best owner abstraction here: the source-facing Chapter 13 assumption package itself, with
-- `Bornology.IsBounded` reused for the geometric set `omega`, `Matrix.rank` reused for the
-- full-rank clause, and the Hessian boundedness expressed through the bounded range of the
-- shifted finite-coordinate family `k ↦ (fun i j ↦ B (k + 1) i j)`.
-- Primitive data vs derived API:
-- * primitive data: the distinguished set `omega`, iterate/trial-point containment, Jacobian
-- full-column rank on `omega`, and the bounded range of the Hessian approximations along the
-- book indices `k ≥ 1`;
-- * derived API: membership in the distinguished set `omega`.
structure PowellYuanAssumption1362
(x : ℕ → Point) (d : ℕ → Point) (A : Point → ConstraintMatrix) (B : ℕ → MatrixN) where
omega : Set Point
omega_bounded : Bornology.IsBounded omega
omega_convex : Convex ℝ omega
omega_closed : IsClosed omega
iterate_mem_omega (k : ℕ) (_ : 1 ≤ k) : x k ∈ omega
trialPoint_mem_omega (k : ℕ) (_ : 1 ≤ k) : x k + d k ∈ omega
jacobian_fullColumnRank (y : Point) (_ : y ∈ omega) : Matrix.rank (A y) = m
matrix_bounded :
Bornology.IsBounded
(Set.range fun k : ℕ ↦ (fun i j ↦ B (k + 1) i j : Fin n → Fin n → ℝ))Lemma 13.6.3
— source only (outside the published documentation root) (Lean source)
Lean contributors (project-level attribution): Chenyi Li, Wanli Ma, Zichen Wang.
Chapter13 Lemma 13.6.3: if the Section 13.3 estimate (13.3.25) holds for the stage data (ck, Ak, ξk, Δ_k, b₂) via the source-facing owner powellYuanSection13325 on the canonical Moore-Penrose pseudoinverse A_k⁺ = (A_k)⁺, the Chapter 13 standing full-column-rank condition from Assumption 13.6.2 is available for Ak, and the Step-2 constraint condition gives ‖c_k + A_kᵀ d_k‖₂ ≤ ξ_k, then the constraint residual decrease is bounded below by the source quantity (13.6.14), written using the canonical Chapter 13 residual owner cdtConstraintResidual and the canonical pseudoinverse norm ‖(A_k)⁺‖.
open scoped Matrix Matrix.Norms.L2Operator
open LinearMap
variable {m n : ℕ}
theorem powellYuanConstraintResidualDecreaseLowerBound
(ck : EuclideanSpace ℝ (Fin m))
(Ak : Matrix (Fin n) (Fin m) ℝ)
(dk : EuclideanSpace ℝ (Fin n))
(trustRegionRadius ξk b2 : ℝ)
(h_b2 : 0 ≤ b2)
(h_trustRegionRadius : 0 ≤ trustRegionRadius)
(h_Ak_fullColumnRank : Matrix.rank Ak = m)
(h_section13325 : powellYuanSection13325 ck Ak trustRegionRadius ξk b2)
(h_constraint_condition :
‖cdtConstraintResidual ck Ak dk‖ ≤ ξk) :
‖ck‖ - ‖cdtConstraintResidual ck Ak dk‖ ≥
min ‖ck‖ ((b2 * trustRegionRadius) / ‖Ak⁺‖)
Lemma 13.6.4
— source only (outside the published documentation root) (Lean source)
Lean contributors (project-level attribution): Chenyi Li, Wanli Ma, Zichen Wang.
Chapter13 Lemma 13.6.4: there exists a positive constant δ₁ such that the source predicted-reduction lower bound holds at every book index k ≥ 1 for the canonical Powell-Yuan predicted reduction powellYuanPredictedReduction from (13.6.7), written using the source-facing projector owner powellYuanProjector, under the Chapter13 Assumption 13.6.2 stage setup, the source Section 13.3 branch hypothesis together with the Step-2 solution data that feed Lemma 13.6.3 for the residual-decrease constant b₂, and the uniform multiplier/product bounds used in the proof of the lemma, with the canonical pseudoinverse owner A_k⁺ = (A_k)⁺ used directly.
open scoped Matrix Matrix.Norms.L2Operator
variable {m n : ℕ}
local notation "Point" => EuclideanSpace ℝ (Fin n)
local notation "ConstraintPoint" => EuclideanSpace ℝ (Fin m)
local notation "Multiplier" => EuclideanSpace ℝ (Fin m)
local notation "Jacobian" => Matrix (Fin n) (Fin m) ℝ
local notation "HessianApproximation" => Matrix (Fin n) (Fin n) ℝ
-- Domain sampling for this refine pass:
-- * primary domain: Chapter 13 Powell-Yuan trust-region stage data on the canonical Euclidean
-- `ℓ2` surface;
-- * sampled owner declarations:
-- `Matrix.pseudoinverse` / `A⁺`,
-- `powellYuanSection13325`,
-- `powellYuanConstraintResidualDecreaseLowerBound`,
-- `IsCdtSolution`,
-- `powellYuanPredictedReduction`,
-- `powellYuanUniformProductBound`;
-- * best owner abstraction: this lemma is the source-facing owner for the explicit Powell-Yuan
-- projector `P̄ = I - A A⁺`, while reusing the canonical pseudoinverse owner `A⁺` together
-- with the source-facing Section 13.3 branch owner `powellYuanSection13325` and the
-- Chapter 13 CDT/algorithm owners for the Step-2 solution predicate, predicted reduction,
-- hat direction, and sequence-level uniform bounds;
-- the later method-level projector in `Theorem_13_6_8` is a bridge/view that specializes to
-- the canonical pseudoinverse `A_k⁺ = (A_k)⁺`.
-- Primitive data vs derived API:
-- * primitive data here: the projector owner `powellYuanProjector`, the shifted gradient owner
-- `powellYuanBarGradient`, the source projected quantity `powellYuanProjectedBarGradient`, and
-- the reduced radius owner `powellYuanReducedTrustRegionRadius`;
-- * derived API reused from upstream: `cdtConstraintResidual`, `cdtObjective`, `IsCdtSolution`,
-- `powellYuanSection13325`, `powellYuanConstraintResidualDecreaseLowerBound`,
-- `powellYuanHatDirection`,
-- `powellYuanSigmaUpdateDenominator`,
-- `powellYuanPredictedReduction`, `powellYuanMultiplierVariationBound`, and
-- `powellYuanUniformProductBound`.
open scoped PowellYuan1364
theorem powellYuanPredictedReductionLowerBound
(sigma : ℕ → ℝ)
(c : ℕ → ConstraintPoint)
(jacobian : Point → Jacobian)
(x d : ℕ → Point)
(g : ℕ → Point)
(lam lamTrial : ℕ → Multiplier)
(B : ℕ → HessianApproximation)
(Δ : ℕ → ℝ)
(b2 : ℝ)
(h1362 : PowellYuanAssumption1362 x d jacobian B)
(h_b2 : 0 ≤ b2)
(h_sigma : ∀ k : ℕ, 1 ≤ k → 0 ≤ sigma k)
(h_residualDecreaseSource :
∀ k : ℕ, 1 ≤ k →
∃ ξk : ℝ,
IsCdtSolution
(B k)
(g k)
(jacobian (x k))
(c k)
(Δ k)
ξk
(d k) ∧
powellYuanSection13325 (c k) (jacobian (x k)) (Δ k) ξk b2)
(h_multiplierVariation : powellYuanMultiplierVariationBound lam lamTrial d)
(h_uniformProduct : powellYuanUniformProductBound (jacobian ∘ x) B) :
∃ delta1 : ℝ, 0 < delta1 ∧
∀ k : ℕ, 1 ≤ k →
(1 / 4 : ℝ) *
‖P̄ḡ[g k, B k, jacobian (x k), d k]‖ *
min
(Δ̄[Δ k, jacobian (x k), d k])
(‖P̄ḡ[g k, B k, jacobian (x k), d k]‖ /
(2 * ‖B k‖)) +
(sigma k / 2 : ℝ) * ‖c k‖ * min ‖c k‖ ((b2 * Δ k) / ‖(jacobian (x k))⁺‖) ≤
(powellYuanPredictedReduction
(g k)
(B k)
(jacobian (x k))
(c k)
(lam k)
(lamTrial k)
(sigma k)
(d k)
(powellYuanHatDirection
(P̄[jacobian (x k)])
(d k))) -
(sigma k / 2 : ℝ) *
powellYuanSigmaUpdateDenominator
(c k)
(jacobian (x k))
(d k) +
delta1 * ‖d k‖ * ‖c k‖
Corollary 13.6.5
— source only (outside the published documentation root) (Lean source)
Lean contributors (project-level attribution): Chenyi Li, Wanli Ma, Zichen Wang.
Chapter13 Corollary 13.6.5: under the standing Chapter13 Assumption 13.6.2 stage setup plus the Lemma 13.6.4 residual-decrease source data with the explicit constant b₂ ≥ 0, the Section 13.3 branch hypothesis (13.3.25), the multiplier-variation bound, and the canonical pseudoinverse-product bound, there is a positive threshold δ₃ with a positive constant δ₄ such that every stage satisfying (13.6.31) at a book index k ≥ 1 also satisfies (13.6.32), written directly on the canonical Step-3 denominator owner powellYuanSigmaUpdateDenominator and the stage predicted-reduction owner powellYuanPredictedReduction.
open scoped Matrix.Norms.L2Operator PowellYuan1364
variable {m n : ℕ}
local notation "Point" => EuclideanSpace ℝ (Fin n)
local notation "ConstraintPoint" => EuclideanSpace ℝ (Fin m)
local notation "Multiplier" => EuclideanSpace ℝ (Fin m)
local notation "Jacobian" => Matrix (Fin n) (Fin m) ℝ
local notation "HessianApproximation" => Matrix (Fin n) (Fin n) ℝ
-- Domain sampling for this refine pass:
-- * primary domain: the Chapter 13 sequence-level corollary layer built on the
-- `powellYuanPredictedReductionLowerBound` machinery from Lemma 13.6.4;
-- * inspected owner declarations:
-- `powellYuanSection13325` from `Lemma_13_6_3`,
-- `IsCdtSolution` and `cdtConstraintResidual` from `Theorem_13_5_1`,
-- `powellYuanSigmaUpdateDenominator` and `powellYuanPredictedReduction` from
-- `Algorithm_13_6_1`,
-- `powellYuanPredictedReductionLowerBound` together with the projector/radius owners from
-- `Lemma_13_6_4`,
-- and the later downstream bridge `PowellYuanCorollary1365Regime` from `Lemma_13_6_6`;
-- * source/core/bridge triage:
-- - source-facing: the corollary's direct existential lower-bound statement
-- - core/canonical: the CDT residual owner and Step-3 denominator/predicted-reduction owners
-- - bridge/view: the later regime packaging in `Lemma_13_6_6`, which adds eventual-smallness
-- data not present in Corollary 13.6.5 itself;
-- * primitive data vs derived API:
-- - primitive data here: the source constant `b₂` and the Section 13.3 branch hypothesis
-- `powellYuanSection13325` attached to the Step-2 solution witness `ξ_k`
-- - derived API: the owner theorem `powellYuanPredictedReductionLowerBound`, whose full
-- hypothesis shape this corollary should reuse rather than weakening into a parallel local
-- surrogate.
theorem powellYuanPredictedReductionLowerBound_of_smallConstraintResidual
(sigma : ℕ → ℝ)
(c : ℕ → ConstraintPoint)
(jacobian : Point → Jacobian)
(x d : ℕ → Point)
(g : ℕ → Point)
(lam lamTrial : ℕ → Multiplier)
(B : ℕ → HessianApproximation)
(Δ : ℕ → ℝ)
(b2 : ℝ)
(h1362 : PowellYuanAssumption1362 x d jacobian B)
(h_b2 : 0 ≤ b2)
(h_sigma : ∀ k : ℕ, 1 ≤ k → 0 ≤ sigma k)
(h_residualDecreaseSource :
∀ k : ℕ, 1 ≤ k →
∃ ξk : ℝ,
IsCdtSolution
(B k)
(g k)
(jacobian (x k))
(c k)
(Δ k)
ξk
(d k) ∧
powellYuanSection13325
(c k)
(jacobian (x k))
(Δ k)
ξk
b2)
(h_multiplierVariation : powellYuanMultiplierVariationBound lam lamTrial d)
(h_uniformProduct : powellYuanUniformProductBound (jacobian ∘ x) B) :
∃ delta3 : ℝ,
0 < delta3 ∧
∃ delta4 : ℝ,
0 < delta4 ∧
∀ k : ℕ, 1 ≤ k →
‖c k‖ ≤ delta3 * Δ k →
(sigma k / 2 : ℝ) *
powellYuanSigmaUpdateDenominator
(c k)
(jacobian (x k))
(d k) +
delta4 * Δ k ≤
powellYuanPredictedReduction
(g k)
(B k)
(jacobian (x k))
(c k)
(lam k)
(lamTrial k)
(sigma k)
(d k)
(powellYuanHatDirection
(P̄[jacobian (x k)])
(d k))
Lemma 13.6.6
— source only (outside the published documentation root) (Lean source)
Lean contributors (project-level attribution): Chenyi Li, Wanli Ma, Zichen Wang.
Chapter13 Lemma 13.6.6: for a Powell-Yuan trust-region run that does not terminate finitely, if the recorded projected directions are the canonical d̂_k, the Corollary 13.6.5 lower bound holds for explicit constants δ₃ and nonnegative δ₄, and the small-residual tail hypothesis holds with the same δ₃, then the incoming Step-3 penalty parameters σ_k, represented by method.sigmaCandidate k, are eventually constant. By Filter.eventuallyConst_atTop_nat, this is equivalent to the tail identity σ_(k+1) = σ_k for all sufficiently large indices.
open Filter
variable {m n : ℕ}
-- Domain sampling for this refine pass:
-- * primary domain: Chapter 13 Powell-Yuan algorithmic stabilization of the Step-3 penalty
-- sequence;
-- * inspected owner declarations:
-- `Filter.EventuallyConst` and `Filter.eventuallyConst_atTop_nat` from mathlib,
-- `PowellYuanTrustRegionMethod.step3AcceptsAt`,
-- `PowellYuanTrustRegionMethod.sigmaCandidate_succ_eq`,
-- `PowellYuanTrustRegionMethod.sigma_eq_candidate_of_step3`, and
-- `PowellYuanTrustRegionMethod.constraintJacobian_eq_at` from `Algorithm_13_6_1`,
-- `powellYuanPredictedReductionLowerBound_of_smallConstraintResidual` from
-- `Corollary_13_6_5`;
-- * owner abstraction: the Chapter 13 method owner `PowellYuanTrustRegionMethod`;
-- * source/core/bridge triage:
-- - source-facing: eventual constancy of the recorded incoming Step-3 penalty parameters
-- `method.sigmaCandidate`
-- - core/canonical: `PowellYuanTrustRegionMethod`,
-- `powellYuanPredictedReductionLowerBound_of_smallConstraintResidual`, and
-- `Filter.EventuallyConst`
-- - bridge/view: direct reuse of Corollary 13.6.5 on the recorded method data when a
-- lower-bound witness is needed;
-- * primitive data vs derived API:
-- - primitive data: the recorded method fields, the Section 13.3 branch hypothesis, and the
-- identification of the recorded projected direction with the canonical `d̂_k`
-- - derived API: `terminatedAt`, `finitelyTerminates`, `step3AcceptsAt`, and the Corollary
-- 13.6.5 lower-bound theorem reused on the method owner.
namespace PowellYuanTrustRegionMethod
local notation "Method" => @PowellYuanTrustRegionMethod m n
theorem penaltyParameters_eventuallyConstant
(method : Method)
(delta3 delta4 : ℝ)
(hNoTerminate : ¬ method.finitelyTerminates)
(h_projectedDirection :
∀ k : ℕ, 1 ≤ k →
method.projectedDirection k =
powellYuanHatDirection
(powellYuanProjector (method.constraintJacobian k))
(method.direction k))
(h_delta4 : 0 ≤ delta4)
(h_lowerBound :
∀ k : ℕ, 1 ≤ k →
‖method.constraintResidual k‖ ≤ delta3 * method.radius k →
(method.sigmaCandidate k / 2 : ℝ) *
powellYuanSigmaUpdateDenominator
(method.constraintResidual k)
(method.constraintJacobianAt (method.iterate k))
(method.direction k) +
delta4 * method.radius k ≤
powellYuanPredictedReduction
(method.gradient k)
(method.hessianApproximation k)
(method.constraintJacobianAt (method.iterate k))
(method.constraintResidual k)
(method.multiplier k)
(method.trialMultiplier k)
(method.sigmaCandidate k)
(method.direction k)
(powellYuanHatDirection
(powellYuanProjector
(method.constraintJacobianAt (method.iterate k)))
(method.direction k)))
(h_smallResidual :
∀ᶠ k in atTop,
‖method.constraintResidual k‖ ≤ delta3 * method.radius k) :
Filter.EventuallyConst method.sigmaCandidate atTop
Lemma 13.6.7
— source only (outside the published documentation root) (Lean source)
Lean contributors (project-level attribution): Chenyi Li, Wanli Ma, Zichen Wang.
Chapter13 Lemma 13.6.7 (1): under Chapter13 Assumption 13.6.2, if the Powell-Yuan algorithm does not terminate finitely, then the trust-region radii Δ_k converge to 0, encoded on the shifted sequence k ↦ method.radius (k + 1).
open Filter
variable {m n : ℕ}
-- Domain sampling pass:
-- * primary domain: Powell-Yuan trust-region local convergence under Chapter 13 Assumption
-- 13.6.2
-- * inspected project declarations:
-- `PowellYuanTrustRegionMethod` from `Algorithm_13_6_1`
-- `PowellYuanTrustRegionMethod.satisfiesAssumption1362`
-- `PowellYuanTrustRegionMethod.finitelyTerminates`
-- `powellYuanPenaltyParameters_eventuallyConstant` from `Lemma_13_6_6`
-- `NullSpaceTrustRegionMethod.tendsto_stoppingResidual_zero_of_bounded_hessianApproximation`
-- from `Theorem_13_4_5`
-- * owner abstraction: `PowellYuanTrustRegionMethod`
-- * source/core/bridge triage:
-- - source-facing: the two local-convergence clauses of Lemma 13.6.7
-- - core/canonical: the Chapter 13 method owner `PowellYuanTrustRegionMethod`
-- - bridge/view: the Chapter 13 penalty-stabilization and stopping-residual convergence
-- machinery from `Lemma_13_6_6` and `Theorem_13_4_5`
-- * primitive data vs derived API:
-- - primitive data: the recorded run data in `PowellYuanTrustRegionMethod`
-- - derived API: `terminatedAt`, `finitelyTerminates`, and `satisfiesAssumption1362`
namespace PowellYuanTrustRegionMethod
variable (method : @_root_.PowellYuanTrustRegionMethod m n)
theorem tendsto_radius_zero_of_not_finitelyTerminates
(h1362 : method.satisfiesAssumption1362)
(hNoTerminate : ¬ method.finitelyTerminates)
:
Tendsto (fun k : ℕ ↦ method.radius (k + 1)) atTop (nhds 0)
Theorem 13.6.8
— source only (outside the published documentation root) (Lean source)
Lean contributors (project-level attribution): Chenyi Li, Wanli Ma, Zichen Wang.
Chapter13 Theorem 13.6.8: under Chapter13 Assumption 13.6.2, either the Powell-Yuan direction vanishes at some stage k ≥ 1 or the source residual from (13.6.58), with the canonical projector P̄_k = I - A_k (A_k)⁺, satisfies liminf_(k → ∞) (‖c_k‖ + ‖P̄_k g_k‖) = 0, encoded on the shifted sequence k ↦ method.projectedGradientResidualAt (k + 1).
open Filter
open scoped Matrix PowellYuan1364
variable {m n : ℕ}
local notation "Point" => EuclideanSpace ℝ (Fin n)
local notation "ConstraintPoint" => EuclideanSpace ℝ (Fin m)
local notation "Jacobian" => Matrix (Fin n) (Fin m) ℝ
local notation "HessianApproximation" => Matrix (Fin n) (Fin n) ℝ
local notation "Method" => @PowellYuanTrustRegionMethod m n
-- Domain sampling pass:
-- * primary domain: Powell-Yuan global convergence alternatives in Chapter 13
-- * inspected declarations:
-- `PowellYuanTrustRegionMethod` from `Algorithm_13_6_1`
-- `PowellYuanTrustRegionMethod.satisfiesAssumption1362`
-- `PowellYuanTrustRegionMethod.finitelyTerminates`
-- `powellYuanProjector` from `Lemma_13_6_4`
-- * owner abstraction: `PowellYuanTrustRegionMethod`
-- * source/core/bridge triage:
-- - source-facing: the projected-gradient residual alternative of Theorem 13.6.8
-- - core/canonical: the method owner `PowellYuanTrustRegionMethod`
-- - bridge/view: the stagewise specialization of the canonical projector owner
-- `powellYuanProjector`
-- * primitive data vs derived API:
-- - primitive data: the recorded method run
-- - derived API: the stagewise bridge `projectedGradientProjectorAt`, the source residual
-- `projectedGradientResidualAt`, and the convergence/termination theorems
namespace PowellYuanTrustRegionMethod
theorem direction_zero_or_liminf_projectedGradientResidual_eq_zero_of_satisfiesAssumption1362
(method : Method)
(h1362 : method.satisfiesAssumption1362) :
(∃ k : ℕ, 1 ≤ k ∧ method.direction k = 0) ∨
Filter.liminf
(fun k : ℕ ↦ method.projectedGradientResidualAt (k + 1))
Filter.atTop = 0
Supporting modules
These source modules support the indexed items and are listed separately so the chapter inventory remains complete.
-
Lemma_13_6_3/Section13325.lean(Documentation unavailable) (Lean source)
Lean contributors (project-level attribution): Chenyi Li, Wanli Ma, Zichen Wang.
-
LinearTrustRegion.lean(Documentation) (Lean source)
Lean contributors (project-level attribution): Chenyi Li, Wanli Ma, Zichen Wang.
-
PowellYuanPseudoInverse.lean(Documentation) (Lean source)
Lean contributors (project-level attribution): Chenyi Li, Wanli Ma, Zichen Wang.