Chapter 06 — Trust-Region Methods and Conic Model Methods
Proofs omitted. Hover over highlighted terms to see their Lean types.
Exercise 6.1
Lean contributors (project-level attribution): Chenyi Li, Wanli Ma, Zichen Wang.
Chapter06 Exercise 6.1: for f(x) = x 0 ^ 4 + x 0 ^ 2 + x 1 ^ 2, current iterate x^(k) = (1, 1)ᵀ, and trust-region radius Δ_k = 1 / 2, the double-dogleg method gives x^(k+1) = (17 / 32 + √15 / 160, 27 / 32 - 3 * √15 / 160)ᵀ.
local notation "Point" => EuclideanSpace ℝ (Fin 2)
open TrustRegionSubproblem
theorem chapter06Exercise61DoubleDoglegNextIterate :
chapter06Exercise61IsDoubleDoglegNextIterate chapter06Exercise61NextIterateExercise 6.2
— source only (outside the published documentation root) (Lean source)
Lean contributors (project-level attribution): Chenyi Li, Wanli Ma, Zichen Wang.
Chapter06 Exercise 6.2: for the quadratic objective f(x) = (1 / 2) * x 0 ^ 2 + x 1 ^ 2, starting point (1, 1)ᵀ, and initial trust-region radius Δ₀ = 5 / 4, the updated stage-one subproblem at the first double-dogleg iterate x^(1) = (4 / 9 - √5 / 18, -1 / 9 + √5 / 36)ᵀ has a feasible Newton step, and that Newton step sends x^(1) to x^(2) = (0, 0)ᵀ.
open scoped Matrix.Norms.L2Operator
-- Domain sampling for this refine pass:
-- * `TrustRegionSubproblem` is the Chapter 6 owner of the quadratic trust-region model and its
-- Cauchy-point data.
-- * `TrustRegionSubproblem.gradientBoundaryStep`, `cauchyPointScale`, and `cauchyPoint` already
-- define the steepest-descent boundary step and trust-region Cauchy point for this exercise.
-- * `TrustRegionSubproblem.newtonStep`, `doubleDoglegGamma`,
-- `doubleDoglegIntermediateNewtonStep`, and `doubleDoglegPath` are the chapter owners of the
-- Newton step and dogleg/double-dogleg bridge data for the fixed quadratic model, with the
-- double-dogleg objects living in the positive-definite Hessian context of Chapter 6.
-- Source/core/bridge triage for this file:
-- * source-facing: the concrete exercise data and the first/second iterate formulas.
-- * core/canonical: `TrustRegionSubproblem` and its Chapter 6 dogleg/double-dogleg owners.
-- * bridge/view: the concrete `ℝ²` formulas for the exercise iterates and translated
-- point-equalities `x^(i + 1) = x^(i) + s`.
-- The first-iterate statements use those explicit coordinate bridges, while the second-iterate
-- statements refine to the updated stage-one `TrustRegionSubproblem` and its owner-level
-- `newtonStep`/`feasibleSet` API.
local notation "Point" => EuclideanSpace ℝ (Fin 2)
local notation "Matrix2" => Matrix (Fin 2) (Fin 2) ℝ
theorem chapter06Exercise62DoubleDoglegX2DeltaFiveQuarters :
let P := chapter06Exercise62DoubleDoglegStageOneSubproblemDeltaFiveQuarters
let hP :=
chapter06Exercise62DoubleDoglegStageOneSubproblemDeltaFiveQuarters_hessianApprox_posDef
P.newtonStep (hP.isUnit) ∈ P.feasibleSet ∧
chapter06Exercise62DoubleDoglegX1DeltaFiveQuartersPoint +
P.newtonStep (hP.isUnit) =
chapter06Exercise62Origin
Exercise 6.3
Lean contributors (project-level attribution): Chenyi Li, Wanli Ma, Zichen Wang.
Chapter06 Exercise 6.3: if s_k satisfies the fraction-of-Cauchy-decrease condition, then there exists β ∈ (0, 1] such that q^(k) 0 - q^(k) (s_k) ≥ β * ‖g_k‖ * min {Δ_k, ‖g_k‖ / ‖B_k‖₂}. Here q^(k) is the quadratic model P, ‖B_k‖₂ is P.hessianOperatorNorm, and the source branch hypothesis is the canonical owner predicate P.hasFractionCauchyDecrease β₂ sk.
variable {n : ℕ}
local notation "Point" => EuclideanSpace ℝ (Fin n)
-- Domain sampling for this refine pass:
-- * primary domain: Chapter 6 trust-region predicted-reduction lower bounds;
-- * inspected project declarations:
-- `TrustRegionSubproblem.predictedReduction`,
-- `TrustRegionSubproblem.hasFractionCauchyDecrease`,
-- `TrustRegionSubproblem.cauchyPointPredictedReductionLowerBoundScaled`,
-- `TrustRegionSubproblem.predictedReductionLowerBound_of_hasFractionCauchyDecrease`;
-- * best owner abstraction: `TrustRegionSubproblem`;
-- * primitive data: the quadratic model, trust-region radius, gradient, and Hessian data owned
-- by `TrustRegionSubproblem`, together with the branch predicate
-- `P.hasFractionCauchyDecrease β₂ sk`;
-- * derived API: the source-facing existential constant extracted from the sharper owner-level
-- lower bound.
-- Source/core/bridge triage:
-- * source-facing: the exercise statement asserting existence of a reduction constant;
-- * core/canonical: `TrustRegionSubproblem` and
-- `predictedReductionLowerBound_of_hasFractionCauchyDecrease`;
-- * bridge/view: the existential reformulation proved here from the explicit owner-level bound.
namespace TrustRegionSubproblem
theorem exists_predictedReductionConstant_of_hasFractionCauchyDecrease
(P : TrustRegionSubproblem n) (β₂ : ℝ) (step : Point)
(hβ₂ : β₂ ∈ Set.Ioc (0 : ℝ) 1)
(hstep : P.hasFractionCauchyDecrease β₂ step) :
∃ β ∈ Set.Ioc (0 : ℝ) 1,
β * ‖P.gradient‖ * min P.radius (‖P.gradient‖ / P.hessianOperatorNorm) ≤
P.predictedReduction stepExercise 6.4
Lean contributors (project-level attribution): Chenyi Li, Wanli Ma, Zichen Wang.
Chapter06 Exercise 6.4: the attractive point of the trust-region method is that it adapts the trust-region radius by comparing actual reduction with predicted reduction. This adaptive update makes the method robust even when the local model is unreliable, and it underlies the strong global convergence behavior developed later in Chapter 6.
#check TrustRegionSubproblem.reductionRatioExercise 6.5
Lean contributors (project-level attribution): Chenyi Li, Wanli Ma, Zichen Wang.
Chapter06 Exercise 6.5: use the trust-region Newton method to minimize rosenbrockFunction from Appendix Problem 1.1.
#check rosenbrockFunctionExercise 6.6
Lean contributors (project-level attribution): Chenyi Li, Wanli Ma, Zichen Wang.
Chapter06 Exercise 6.6: use a trust-region quasi-Newton method to minimize extendedRosenbrockFunction from Appendix Problem 1.2.
#check extendedRosenbrockFunctionExercise 6.7
Lean contributors (project-level attribution): Chenyi Li, Wanli Ma, Zichen Wang.
Chapter06 Exercise 6.7: for the dogleg path s(τ) constructed from the trust-region Cauchy point and the Newton step of a positive-definite quadratic model, the norm ‖s(τ)‖ increases monotonically along the path on the standard parameter interval τ ∈ [0, 2].
variable {n : ℕ}
local notation "Point" => EuclideanSpace ℝ (Fin n)
-- Domain sampling for this refine pass:
-- * Primary domain: Chapter 6 trust-region step geometry on the owner
-- `TrustRegionSubproblem`.
-- * Inspected owner/data declarations:
-- `TrustRegionSubproblem.gradientCurvature`,
-- `TrustRegionSubproblem.cauchyPoint`,
-- `Matrix.PosDef.isUnit`,
-- and `IsUnit.invertible`.
-- * Core/canonical owner: `TrustRegionSubproblem`; primitive data is the quadratic model,
-- trust-region radius, and Hessian approximation.
-- * Derived API: the dogleg Newton step needs only the explicit Hessian-unit bridge, while the
-- monotonicity theorem keeps the positive-definite regime. The first dogleg breakpoint is
-- already canonically owned upstream by
-- `TrustRegionSubproblem.cauchyPoint`.
-- * This file therefore keeps only the source-facing dogleg path and its monotonicity theorem.
-- It reuses the upstream Cauchy-point owner instead of a parallel local Cauchy-step
-- definition.
namespace TrustRegionSubproblem
theorem norm_doglegPath_monotoneOn
(P : TrustRegionSubproblem n) (h_hessianApprox_posDef : P.hessianApprox.PosDef) :
MonotoneOn (fun τ : ℝ ↦ ‖P.doglegPath h_hessianApprox_posDef.isUnit τ‖)
(Set.Icc (0 : ℝ) 2)Exercise 6.8
Lean contributors (project-level attribution): Chenyi Li, Wanli Ma, Zichen Wang.
Chapter06 Exercise 6.8 (1): if g_k ≠ 0 and g_kᵀ B_k g_k ≤ 0, then the Cauchy point is the boundary steepest-descent step -(Δ_k / ‖g_k‖) • g_k.
namespace TrustRegionSubproblem
variable {n : ℕ}
theorem cauchyPoint_eq_of_nonpos_curvature
(P : TrustRegionSubproblem n) (h_grad : P.gradient ≠ 0)
(h_curv : P.gradientCurvature ≤ 0) :
P.cauchyPoint = -(P.radius / ‖P.gradient‖) • P.gradientExercise 6.9
Lean contributors (project-level attribution): Chenyi Li, Wanli Ma, Zichen Wang.
Chapter06 Exercise 6.9 (4): when g_k ≠ 0, the generalized Cauchy-point parameter τ_k is given by the piecewise formula τ_k = 1 if g_kᵀ (Dᵀ D)⁻¹ B_k (Dᵀ D)⁻¹ g_k ≤ 0, and otherwise τ_k = min (‖D⁻ᵀ g_k‖₂^3 / (Δ_k (g_kᵀ (Dᵀ D)⁻¹ B_k (Dᵀ D)⁻¹ g_k))) 1. Under symmetry of D, this is the source formula (6.3.68).
namespace GeneralizedTrustRegionSubproblem
variable {n : ℕ}
local notation "Point" => EuclideanSpace ℝ (Fin n)
local notation "MatrixN" => Matrix (Fin n) (Fin n) ℝ
variable (P : GeneralizedTrustRegionSubproblem n)
theorem generalizedCauchyScale_eq_piecewise
{τk : ℝ} (h_gradient : P.gradient ≠ 0) (h_tau : P.IsGeneralizedCauchyScale τk) :
τk =
if P.generalizedGradientCurvature ≤ 0 then 1
else
min
((‖P.inverseTransposeScaledGradient‖ ^ (3 : ℕ)) /
(P.radius * P.generalizedGradientCurvature))
1Exercise 6.10
Lean contributors (project-level attribution): Chenyi Li, Wanli Ma, Zichen Wang.
Chapter06 Exercise 6.10: a step sStar solves the generalized trust-region subproblem min f + gᵀ s + (1 / 2) sᵀ B s subject to ‖D s‖₂ ≤ Δ if and only if there is an multiplier λStar satisfying the weighted trust-region KKT conditions.
variable {n : ℕ}
local notation "Point" => EuclideanSpace ℝ (Fin n)
local notation "MatrixN" => Matrix (Fin n) (Fin n) ℝ
theorem GeneralizedTrustRegionSubproblem.isSolution_iff_exists_multiplier
(P : GeneralizedTrustRegionSubproblem n) (sStar : Point) :
P.IsSolution sStar ↔
∃ lambdaStar : ℝ,
0 ≤ lambdaStar ∧
(P.shiftedHessian lambdaStar).mulVec sStar = -P.gradient ∧
P.weightedNorm sStar ≤ P.radius ∧
lambdaStar * (P.radius - P.weightedNorm sStar) = 0 ∧
(P.shiftedHessian lambdaStar).PosSemidefExercise 6.11
Lean contributors (project-level attribution): Chenyi Li, Wanli Ma, Zichen Wang.
Chapter06 Exercise 6.11: the Steihaug-CG program is already recorded canonically by the owner SteihaugCGAlgorithm. Its source-facing pseudocode clauses are realized by the following primitive fields and companion update lemmas: - Step 0 input and initialization: initialGradient, hessianApprox, weightMatrix, ε, Δ, stepZero, preconditionedGradientZero, searchDirectionZero. - Initial stopping clause: initialStop. - Negative-curvature boundary exit: activeIteration_branch, negativeCurvatureTauPos, negativeCurvatureBoundary, negativeCurvatureReturnedStep. - Step 2 update and trust-region boundary exit: alphaUpdate, step_next_eq, boundaryTauPos, boundaryOnSphere, boundaryReturnedStep. - Step 3 update and residual stopping clause: gradient_next_eq, residualStop. - Step 4 update and loop continuation: preconditionedGradient_next_eq, betaUpdate, searchDirection_next_eq, nextIterationActive.
#check SteihaugCGAlgorithmExercise 6.12
— source only (outside the published documentation root) (Lean source)
Lean contributors (project-level attribution): Chenyi Li, Wanli Ma, Zichen Wang.
Chapter06 Exercise 6.12 compares the canonical Chapter 6 owner surfaces for the trust-region quadratic model, the conic model, the collinear-scaling rewrite, and the tensor/quadratic trial point transition. Primary domain sampling for this refine pass: - source-facing/core owner: TrustRegionSubproblem for the quadratic trust-region model. - source-facing/core owner: ConicTrustRegionSubproblem for the conic trust-region model. - bridge/view: ConicTrustRegionSubproblem.CollinearScalingRewrite for the s = J w / (1 + hᵀ w) reformulation and its admissible-set/objective comparison API. - source-facing/core owner: TensorMethodTransition for the Step 3-8 tensor/quadratic trial point transition. Primitive data stay in those owners; this exercise recalls only their derived public API rather than introducing a second wrapper layer. - TrustRegionSubproblem.quadraticModel is the standard trust-region quadratic model q^(k) (s) = f(x_k) + g_kᵀ s + (1 / 2) sᵀ B_k s. - ConicTrustRegionSubproblem.objective is the conic model ψ(s) = f + (gᵀ s) / (1 - aᵀ s) + (1 / 2) (sᵀ A s) / (1 - aᵀ s)^2 on admissible steps s ∈ P.admissibleSet. - ConicTrustRegionSubproblem.CollinearScalingRewrite.step records the collinear-scaling substitution s = J w / (1 + hᵀ w). - ConicTrustRegionSubproblem.CollinearScalingRewrite.exists_parameter_of_mem_admissibleSet records the reverse representation of every admissible conic step by some parameter w. - ConicTrustRegionSubproblem.CollinearScalingRewrite.objective_eq_of_pos records the side-conditioned comparison turning the conic objective into a quadratic objective in w. - TensorMethodTransition.xNext_eq_choose records the Step 7 comparison between the tensor-model and quadratic-model trial points.
#check TrustRegionSubproblem.quadraticModel
Exercise 6.13
Lean contributors (project-level attribution): Chenyi Li, Wanli Ma, Zichen Wang.
Chapter06 Exercise 6.13: if the collinear scaling formula s = w / (1 + hᵀ w) is applied to a quasi-Newton image w = Hnext.mulVec y, then Hnext satisfies the canonical generalized quasi-Newton equation with right-hand side (1 + hᵀ w) • s.
variable {n : ℕ}
local notation "Point" => EuclideanSpace ℝ (Fin n)
local notation "MatrixN" => Matrix (Fin n) (Fin n) ℝ
-- Semantic recall: Chapter 5 already uses the inverse-form generalized quasi-Newton surface
-- `Hnext.mulVec y = ρ • s`. This item derives the same relation from the Chapter 6 collinear
-- scaling formula on the local concrete `EuclideanSpace`/matrix layer.
theorem collinearScaling_satisfiesGeneralizedQuasiNewtonEquation
(Hnext : MatrixN) (h y s w : Point) (hw : w = Hnext.mulVec y)
(hdenom : 1 + dotProduct h w ≠ 0)
(hs : s = (1 + dotProduct h w)⁻¹ • w) :
satisfiesQuasiNewtonEquation Hnext.toEuclideanLin y ((1 + dotProduct h w) • s)Exercise 6.14
— source only (outside the published documentation root) (Lean source)
Lean contributors (project-level attribution): Chenyi Li, Wanli Ma, Zichen Wang.
Chapter06 Exercise 6.14 (1): the compact collinear scaling BFGS formula writes collinearScalingBFGSMatrixUpdate γ C s y as γ^2 times the Chapter 5 inverse-BFGS update.
variable {n : ℕ}
local notation "Point" => EuclideanSpace ℝ (Fin n)
local notation "MatrixN" => Matrix (Fin n) (Fin n) ℝ
theorem collinearScalingBFGSMatrixUpdate_eq_scaledBfgsInverseUpdate
(γ : ℝ) (C : MatrixN) (s y : Point) :
collinearScalingBFGSMatrixUpdate γ C s y = γ ^ 2 • bfgsInverseUpdate C s y
6.1 — Trust-Region Methods
Algorithm 6.1.1
Lean contributors (project-level attribution): Chenyi Li, Wanli Ma, Zichen Wang.
Chapter06 Algorithm 6.1.1: a trust-region algorithm on ℝ^n consists of an objective f, an initial point x₀, an overall radius bound ΔMax, an initial trust-region radius Δ0 ∈ (0, ΔMax), parameters ε ≥ 0, 0 < η1 ≤ η2 < 1, and 0 < γ1 < 1 < γ2, together with a uniform β₂ ∈ Set.Ioc (0 : ℝ) 1, explicit sequences of iterates x k, trial steps s k, gradients g k, model matrices B k, ratios r k, and radii Δ k. At every active iteration with ε < ‖g k‖, the structure records the source-faithful Step 3 condition `(subproblem k).isApproximateSolution β₂ (s k)for the trust-region subproblem built fromf (x k), g k, B k, and Δ k`, and fixes r k to be the usual actual-to-predicted reduction ratio. Positivity of the predicted reduction on active iterations is derived later from Lemma 6.1.5 on the canonical subproblem owner. The quadratic model q^(k) is treated as the derived function view of (subproblem k), while x k enters the ratio only through the actual-reduction bridge. The stopping test ‖g k‖ ≤ ε, accepted-iterate update, and the total source radius-update rule are primitive algorithm data; the separate shrink/keep/expand cases are derived later from that single owner-level rule.
open scoped Matrix.Norms.L2Operator
variable {n : ℕ}
local notation "Point" => EuclideanSpace ℝ (Fin n)
structure TrustRegionAlgorithm (n : ℕ) (f : EuclideanSpace ℝ (Fin n) → ℝ) where
ε : ℝ
η1 : ℝ
η2 : ℝ
γ1 : ℝ
γ2 : ℝ
β₂ : ℝ
x0 : EuclideanSpace ℝ (Fin n)
ΔMax : ℝ
Δ0 : ℝ
x : ℕ → EuclideanSpace ℝ (Fin n)
s : ℕ → EuclideanSpace ℝ (Fin n)
g : ℕ → EuclideanSpace ℝ (Fin n)
B : ℕ → Matrix (Fin n) (Fin n) ℝ
r : ℕ → ℝ
Δ : ℕ → ℝ
epsilon_nonneg : 0 ≤ ε
eta1_pos : 0 < η1
eta1_le_eta2 : η1 ≤ η2
eta2_lt_one : η2 < 1
gamma1_mem : γ1 ∈ Set.Ioo (0 : ℝ) 1
gamma2_gt_one : 1 < γ2
beta2_mem : β₂ ∈ Set.Ioc (0 : ℝ) 1
deltaMax_pos : 0 < ΔMax
delta0_mem : Δ0 ∈ Set.Ioo (0 : ℝ) ΔMax
x_zero : x 0 = x0
delta_zero : Δ 0 = Δ0
delta_mem (k : ℕ) : Δ k ∈ Set.Ioc (0 : ℝ) ΔMax
hasGradientAt (k : ℕ) : HasGradientAt f (g k) (x k)
B_symm (k : ℕ) : (B k).IsSymm
step_isApproximateSolution (k : ℕ) (_ : ε < ‖g k‖) :
({
fAtCenter := f (x k)
gradient := g k
hessianApprox := B k
hessianApprox_symm := B_symm k
radius := Δ k
radius_pos := (delta_mem k).1
} : TrustRegionSubproblem n).isApproximateSolution β₂ (s k)
ratio_eq (k : ℕ) (_ : ε < ‖g k‖) :
r k =
({
fAtCenter := f (x k)
gradient := g k
hessianApprox := B k
hessianApprox_symm := B_symm k
radius := Δ k
radius_pos := (delta_mem k).1
} : TrustRegionSubproblem n).reductionRatio (x k) f (s k)
iterate_update (k : ℕ) (_ : ε < ‖g k‖) :
x (k + 1) = if η1 ≤ r k then x k + s k else x k
radius_update (k : ℕ) (_ : ε < ‖g k‖) :
Δ (k + 1) ∈
trustRegionRadiusUpdateSet η1 η2 γ1 γ2 ΔMax (Δ k) (r k) ‖s k‖Theorem 6.1.2
Lean contributors (project-level attribution): Chenyi Li, Wanli Ma, Zichen Wang.
Chapter06 Theorem 6.1.2: a step sStar solves the trust-region subproblem if and only if it admits a nonnegative multiplier λ satisfying the source KKT conditions. The source-facing owner P.IsSolution sStar keeps the Chapter 6 notion of "solves the subproblem" while reusing the canonical minimizer API internally, and the feasibility clause is stated directly as the textbook trust-region inequality ‖sStar‖ ≤ Δ.
variable {n : ℕ}
local notation "Point" => EuclideanSpace ℝ (Fin n)
local notation "MatrixN" => Matrix (Fin n) (Fin n) ℝ
-- Domain sampling for this refine pass:
-- * `Chapter06.Definition_6_1_extra_1.TrustRegionSubproblem` is the Chapter 6 owner for the
-- quadratic model, feasible set, and solution predicate `TrustRegionSubproblem.IsSolution`.
-- * `IsMinOn` from `Mathlib.Order.Filter.Extr` remains the canonical minimizer API underneath
-- that owner.
-- Source/core/bridge triage:
-- * source-facing: `P.IsSolution sStar`, expressing that `sStar` solves the trust-region
-- subproblem.
-- * core/canonical: `IsMinOn P P.feasibleSet sStar`.
-- * bridge/view: `TrustRegionSubproblem.isSolution_iff_mem_feasibleSet_and_isMinOn` in the
-- owner file.
-- This file therefore keeps only the auxiliary shifted Hessian definition and states the source
-- KKT clauses directly on the theorem surface.
theorem TrustRegionSubproblem.isSolution_iff_exists_multiplier
(P : TrustRegionSubproblem n) (sStar : Point) :
P.IsSolution sStar ↔
∃ lambdaStar : ℝ,
0 ≤ lambdaStar ∧
(P.shiftedHessian lambdaStar).mulVec sStar = -P.gradient ∧
‖sStar‖ ≤ P.radius ∧
lambdaStar * (P.radius - ‖sStar‖) = 0 ∧
(P.shiftedHessian lambdaStar).PosSemidefLemma 6.1.3
Lean contributors (project-level attribution): Chenyi Li, Wanli Ma, Zichen Wang.
Chapter06 Lemma 6.1.3: if s_k solves the trust-region subproblem (6.1.1), expressed on the chapter-local owner surface P.IsSolution s_k, then the predicted reduction q^(k) 0 - q^(k) s_k is bounded below by the standard trust-region Cauchy decrease estimate. To avoid Lean's / 0 = 0 convention from silently weakening the source statement, the case ‖B_k‖₂ = 0 is stated explicitly, while the nonzero branch keeps the textbook quotient ‖g_k‖ / ‖B_k‖₂. Here q^(k) is the quadratic model P, and ‖B_k‖₂ is ‖P.hessianApprox‖, as identified by Matrix.l2_opNorm_def.
open scoped Matrix.Norms.L2Operator
variable {n : ℕ}
local notation "Point" => EuclideanSpace ℝ (Fin n)
-- Domain sampling for this refine pass:
-- * `Chapter06.Definition_6_1_extra_1.TrustRegionSubproblem` is the chapter-local owner for the
-- trust-region quadratic model, feasible set, and predicted reduction.
-- * `IsMinOn` / `isMinOn_iff` from `Mathlib.Order.Filter.Extr` is the canonical minimizer owner
-- for minimizing the quadratic model on the feasible set.
-- * the source proof compares the exact minimizer with an explicit feasible point on the
-- steepest-descent ray rather than with the later Cauchy-point construction.
-- Source/core/bridge triage:
-- * source-facing: the trust-region lower bound for a solution `sk` of the subproblem.
-- * core/canonical: `IsMinOn P P.feasibleSet sk`.
-- * bridge/view: `P.IsSolution sk`, the chapter-local owner that packages feasibility together
-- with the canonical minimizer predicate.
theorem TrustRegionSubproblem.predictedReductionLowerBound
(P : TrustRegionSubproblem n) (sk : Point)
(hsol : P.IsSolution sk) :
P.predictedReduction sk ≥
if hB : ‖P.hessianApprox‖ = 0 then
(1 / 2 : ℝ) * ‖P.gradient‖ * P.radius
else
(1 / 2 : ℝ) * ‖P.gradient‖ * min P.radius (‖P.gradient‖ / ‖P.hessianApprox‖)Lemma 6.1.4
Lean contributors (project-level attribution): Chenyi Li, Wanli Ma, Zichen Wang.
Chapter06 Lemma 6.1.4: the Cauchy point s_k^c satisfies the standard predicted-reduction lower bound. To avoid Lean's / 0 = 0 convention from silently weakening the source statement, the zero-operator-norm case is stated explicitly, while the positive-norm branch uses the textbook quotient ‖g_k‖ / ‖B_k‖₂. Here q^(k) is the quadratic model P, Pred_k (s) = P.predictedReduction s, s_k^c = P.cauchyPoint, and ‖B_k‖₂ = P.hessianOperatorNorm.
open scoped Matrix.Norms.L2Operator
variable {n : ℕ}
local notation "⟪" x ", " y "⟫" => inner ℝ x y
theorem TrustRegionSubproblem.cauchyPointPredictedReductionLowerBound
(P : TrustRegionSubproblem n) :
P.predictedReduction P.cauchyPoint ≥
if _ : P.hessianOperatorNorm = 0 then
(1 / 2 : ℝ) * ‖P.gradient‖ * P.radius
else
(1 / 2 : ℝ) * ‖P.gradient‖ *
min P.radius (‖P.gradient‖ / P.hessianOperatorNorm)Lemma 6.1.5
Lean contributors (project-level attribution): Chenyi Li, Wanli Ma, Zichen Wang.
Chapter06 Lemma 6.1.5: if step is an approximate solution of (6.1.1), then its predicted reduction satisfies Pred_k = q^(k) 0 - q^(k) step ≥ (1 / 2) * β₂ * ‖g_k‖ * min {Δ_k, ‖g_k‖ / ‖B_k‖₂}, where ‖B_k‖₂ is P.hessianOperatorNorm. To avoid Lean's / 0 = 0 convention from silently weakening the source statement, the ‖B_k‖₂ = 0 branch is stated explicitly as in Chapter06 Lemma 6.1.4.
open scoped Matrix.Norms.L2Operator
variable {n : ℕ}
namespace TrustRegionSubproblem
local notation "Point" => EuclideanSpace ℝ (Fin n)
theorem predictedReductionLowerBound_of_hasFractionCauchyDecrease
(P : TrustRegionSubproblem n) (β₂ : ℝ) (step : Point)
(hβ₂ : β₂ ∈ Set.Ioc (0 : ℝ) 1)
(hstep : P.hasFractionCauchyDecrease β₂ step) :
(1 / 2 : ℝ) * β₂ * ‖P.gradient‖ * min P.radius (‖P.gradient‖ / P.hessianOperatorNorm) ≤
P.predictedReduction stepLemma 6.1.6
— source only (outside the published documentation root) (Lean source)
Lean contributors (project-level attribution): Chenyi Li, Wanli Ma, Zichen Wang.
Chapter06 Lemma 6.1.6: under Assumption (A₀) for a Chapter 6 trust-region algorithm A, there exist hessianBound ≥ 0 and C : ℝ → ℝ with Filter.Tendsto C (nhds 0) (nhds 0) such that, at every active iteration k, the actual and predicted reductions of the canonical stage subproblem differ by at most (1 / 2) * hessianBound * ‖A.s k‖^2 + C ‖A.s k‖ * ‖A.s k‖. The active-iteration hypothesis is the canonical Chapter 6 owner-side condition under which the algorithm fixes the stage-k subproblem data and the Step 3 trial step.
open Filter
variable {n : ℕ}
local notation "Point" => EuclideanSpace ℝ (Fin n)
-- Domain-style sampling for this model-error lemma:
-- * `TrustRegionAlgorithm` in `Algorithm_6_1_1` is the Chapter 6 owner of the iteration data,
-- and the stage-`k` quadratic model is the derived owner `A.subproblem k`.
-- * `TrustRegionSubproblem.actualReduction` and `TrustRegionSubproblem.predictedReduction` in
-- `Definition_6_1_extra_1` are the canonical Chapter 6 owners for the trust-region agreement
-- numerator, so the model-error lemma should use that owner surface rather than a parallel
-- expanded difference `f (x_k + s_k) - q^(k) (s_k)`.
-- * `TrustRegionAssumptionA0` in `Assumption_6_1_extra_2` is the source-facing Chapter 6
-- regularity package, and `TrustRegionAssumptionA0.hessianBound_nonneg` is its canonical
-- derived API extracting the nonnegative uniform Hessian-operator-norm bound from `(A₀)`.
-- * The Chapter 1 / mathlib remainder owner relevant here is the first-order differentiability
-- remainder `HasFDerivAt.isLittleO`, not the convex-segment Hölder/Lipschitz owner used for
-- stronger remainder estimates on convex sets.
-- This theorem is therefore source-facing, with `TrustRegionAlgorithm` and the Chapter 6
-- reduction owners as the core owners and no parallel local wrapper around the quadratic model.
namespace TrustRegionAlgorithm
theorem trustRegionQuadraticModelErrorBound
{f : Point → ℝ} (A : TrustRegionAlgorithm n f)
[TrustRegionAssumptionA0 f A.x0 A.subproblem A.s] :
∃ hessianBound : ℝ,
0 ≤ hessianBound ∧
∃ C : ℝ → ℝ,
Tendsto C (nhds 0) (nhds 0) ∧
∀ ⦃k : ℕ⦄,
A.activeAt k →
Lemma 6.1.7
— source only (outside the published documentation root) (Lean source)
Lean contributors (project-level attribution): Chenyi Li, Wanli Ma, Zichen Wang.
Chapter06 Lemma 6.1.7: under Assumption (A₀) and a positive tolerance A.ε, there is a threshold Δ̃ > 0 such that every active iteration k with A.activeAt k and A.Δ k < Δ̃ is very successful and satisfies A.Δ k ≤ A.Δ (k + 1).
variable {n : ℕ}
local notation "Point" => EuclideanSpace ℝ (Fin n)
-- Domain-style sampling for this threshold lemma:
-- * `TrustRegionSubproblem` in `Definition_6_1_extra_1` is the Chapter 6 owner of the quadratic
-- trust-region model and its step-space data.
-- * `TrustRegionSubproblem.cauchyPoint` and related Cauchy-step API in
-- `Definition_6_1_extra_3` are derived subproblem data, not primitive fields of the algorithm.
-- * `TrustRegionSubproblem.isApproximateSolution` in `Lemma_6_1_5` is the canonical Step 3
-- predicate on a subproblem.
-- * `TrustRegionAlgorithm` in `Algorithm_6_1_1` is the Chapter 6 owner of the iteration data and
-- derives `q^(k)` from `subproblem k` instead of storing a parallel local wheel.
-- For this file, the source-facing item is the threshold theorem below; the core/canonical
-- owners are the existing Chapter 6 algorithm and subproblem declarations; there is no new
-- bridge/view data to package here.
namespace TrustRegionAlgorithm
theorem existsVerySuccessfulThreshold_ofTrustRegionAssumptionA0
{f : Point → ℝ} (A : TrustRegionAlgorithm n f)
[TrustRegionAssumptionA0 f A.x0 A.subproblem A.s]
(hε : 0 < A.ε) :
∃ deltaTilde > 0,
∀ k : ℕ,
A.activeAt k →
A.Δ k < deltaTilde →
A.verySuccessfulAt k ∧ A.Δ k ≤ A.Δ (k + 1)
Theorem 6.1.8
— source only (outside the published documentation root) (Lean source)
Lean contributors (project-level attribution): Chenyi Li, Wanli Ma, Zichen Wang.
Chapter06 Theorem 6.1.8: under Assumption (A₀), if the trust-region algorithm A has only finitely many active successful iterations, uses exact stopping A.ε = 0, and stutters after termination, then the iterate sequence converges to a first-order stationary point of f.
open Filter
variable {n : ℕ}
local notation "Point" => EuclideanSpace ℝ (Fin n)
theorem trustRegionAlgorithm_tendsto_stationary_of_finiteSuccessfulIterations
{f : Point → ℝ} (A : TrustRegionAlgorithm n f)
[TrustRegionAssumptionA0 f A.x0 A.subproblem A.s]
(hfinite : Set.Finite {k : ℕ | A.activeSuccessfulAt k})
(hε : A.ε = 0)
(hStutter : ∀ k : ℕ, A.terminatedAt k → A.x (k + 1) = A.x k) :
∃ xStar : Point, Tendsto A atTop (nhds xStar) ∧ IsStationaryPoint f xStar
Theorem 6.1.9
— source only (outside the published documentation root) (Lean source)
Lean contributors (project-level attribution): Chenyi Li, Wanli Ma, Zichen Wang.
Chapter06 Theorem 6.1.9: let Assumption (A₀) hold. If Algorithm 6.1.1 has infinitely many successful active iterations, then the gradient sequence of Algorithm 6.1.1 satisfies liminf_(k → ∞) ‖g_k‖ = 0, encoded through the owner companion A.gradientNormAt k = ‖A.g k‖ as liminf A.gradientNormAt atTop = 0.
open Filter
variable {n : ℕ}
local notation "Point" => EuclideanSpace ℝ (Fin n)
theorem trustRegionAlgorithm_liminf_gradientNorm_eq_zero
{f : Point → ℝ} (A : TrustRegionAlgorithm n f)
[TrustRegionAssumptionA0 f A.x0 A.subproblem A.s]
(hSuccessful : A.hasInfinitelyManySuccessfulIterations) :
liminf A.gradientNormAt atTop = 0
Theorem 6.1.10
— source only (outside the published documentation root) (Lean source)
Lean contributors (project-level attribution): Chenyi Li, Wanli Ma, Zichen Wang.
Chapter06 Theorem 6.1.10: suppose that Assumption (A₀) holds. Then the gradient sequence of Algorithm 6.1.1 converges to 0, encoded as Tendsto A.g atTop (nhds (0 : Point)). The book's infinite-sequence reading is recorded explicitly by the extra hypotheses hε : A.ε = 0 and hStutter : ∀ k, A.terminatedAt k → A.g (k + 1) = A.g k, rather than being hidden inside a stronger algorithm wrapper.
open Filter
variable {n : ℕ}
local notation "Point" => EuclideanSpace ℝ (Fin n)
namespace TrustRegionAlgorithm
theorem tendsto_gradient_zero
{f : Point → ℝ} (A : TrustRegionAlgorithm n f)
[TrustRegionAssumptionA0 f A.x0 A.subproblem A.s]
(hε : A.ε = 0)
(hStutter : ∀ k : ℕ, A.terminatedAt k → A.g (k + 1) = A.g k) :
Tendsto A.g atTop (nhds (0 : Point))
Theorem 6.1.11
Lean contributors (project-level attribution): Chenyi Li, Wanli Ma, Zichen Wang.
Chapter06 Theorem 6.1.11 (2): the trust-region quadratic model decreases monotonically along the full step-valued double-dogleg path on τ ∈ [0, 3].
variable {n : ℕ}
-- Local declaration justification (source-local notation): this item follows the book's fixed
-- trust-region step space `ℝ^n`, and keeping `Point` file-local avoids exporting a redundant
-- public alias solely for theorem readability.
local notation "Point" => EuclideanSpace ℝ (Fin n)
-- Domain sampling for this refine pass:
-- * Primary domain: step-space trust-region geometry for the Chapter 6 owner
-- `TrustRegionSubproblem`.
-- * Inspected owner/data declarations: `TrustRegionSubproblem.quadraticModel`,
-- `TrustRegionSubproblem.cauchyPoint`, `TrustRegionSubproblem.newtonStep`, and
-- `TrustRegionSubproblem.doglegPath`.
-- * Primitive owner data already lives in `TrustRegionSubproblem`; the Cauchy point and Newton
-- step are derived owner API.
-- * The reusable double-dogleg ratio/path and breakpoint API now lives in the item-owned
-- foundation module `Theorem_6_1_11.Path`.
-- * This file keeps only the source-facing monotonicity theorems and theorem-local proof helpers
-- in the positive-definite Hessian regime. Translated `xk + …` points remain bridge
-- expressions for source-facing distance statements.
namespace TrustRegionSubproblem
variable (P : TrustRegionSubproblem n) (h_hessianApprox_posDef : P.hessianApprox.PosDef) (η : ℝ)
variable (h_gamma_le_eta : P.doubleDoglegGamma h_hessianApprox_posDef.isUnit ≤ η)
variable (h_eta_le_one : η ≤ 1)
theorem quadraticModel_antitoneOn_doubleDoglegPath
(h_gamma_le_eta : P.doubleDoglegGamma h_hessianApprox_posDef.isUnit ≤ η)
(h_eta_le_one : η ≤ 1)
:
AntitoneOn (fun τ : ℝ ↦ P (P.doubleDoglegPath h_hessianApprox_posDef.isUnit η τ))
(Set.Icc (0 : ℝ) 3)Algorithm 6.1.12
Lean contributors (project-level attribution): Chenyi Li, Wanli Ma, Zichen Wang.
Chapter06 Algorithm 6.1.12: a Steihaug-CG algorithm for the trust-region subproblem. The owner stores explicit Step 0 data, both boundary exits, the Step 2-4 recurrences, loop-entry obligations, control-flow obligations, plus the returned step. The predicate activeIteration j means that iteration j has been reached. The predicate continuingIteration j means that iteration j enters Step 2 after the Step 1 negative-curvature test.
variable {n : ℕ}
notation:100 "‖" x "‖_" W:max => steihaugWeightedNorm W x
structure SteihaugCGAlgorithm (n : ℕ) where
initialGradient : Point n
hessianApprox : MatrixN n
weightMatrix : MatrixN n
weightMatrixInv : MatrixN n
ε : ℝ
Δ : ℝ
step : ℕ → Point n
gradient : ℕ → Point n
preconditionedGradient : ℕ → Point n
searchDirection : ℕ → Point n
α : ℕ → ℝ
β : ℕ → ℝ
τNegCurvature : ℕ → ℝ
τBoundary : ℕ → ℝ
returnedStep : Point n
epsilonPos : 0 < ε
radiusPos : 0 < Δ
weightMatrixPosDef : weightMatrix.PosDef
weightMatrixMulInv : weightMatrix * weightMatrixInv = 1
weightMatrixInvMul : weightMatrixInv * weightMatrix = 1
stepZero : step 0 = 0
gradientZero : gradient 0 = initialGradient
preconditionedGradientZero :
preconditionedGradient 0 = weightMatrixInv.mulVec (gradient 0)
searchDirectionZero : searchDirection 0 = -preconditionedGradient 0
initialStop :
steihaugInitialResidualNorm gradient preconditionedGradient <
steihaugResidualThreshold ε gradient preconditionedGradient →
returnedStep = step 0
activeIteration : ℕ → Prop
continuingIteration : ℕ → Prop
loopEntry :
steihaugResidualThreshold ε gradient preconditionedGradient ≤
steihaugInitialResidualNorm gradient preconditionedGradient →
activeIteration 0
continuingIteration_active :
∀ j : ℕ, continuingIteration j → activeIteration j
activeIteration_branch :
∀ j : ℕ, activeIteration j →
matrixQuadratic hessianApprox (searchDirection j) ≤ 0 ∨ continuingIteration j
negativeCurvatureTauPos :
∀ j : ℕ, activeIteration j → matrixQuadratic hessianApprox (searchDirection j) ≤ 0 →
0 < τNegCurvature j
negativeCurvatureBoundary :
∀ j : ℕ, activeIteration j → matrixQuadratic hessianApprox (searchDirection j) ≤ 0 →
‖step j + τNegCurvature j • searchDirection j‖_weightMatrix = Δ
negativeCurvatureReturnedStep :
∀ j : ℕ, activeIteration j → matrixQuadratic hessianApprox (searchDirection j) ≤ 0 →
returnedStep = step j + τNegCurvature j • searchDirection j
continuingCurvaturePos :
∀ j : ℕ, continuingIteration j →
0 < matrixQuadratic hessianApprox (searchDirection j)
alphaUpdate :
∀ j : ℕ, continuingIteration j →
α j =
steihaugResidualPairingAt gradient preconditionedGradient j /
matrixQuadratic hessianApprox (searchDirection j)
stepUpdate :
∀ j : ℕ, continuingIteration j → step (j + 1) = step j + α j • searchDirection j
boundaryTauPos :
∀ j : ℕ, continuingIteration j →
‖step (j + 1)‖_weightMatrix ≥ Δ →
0 < τBoundary j
boundaryOnSphere :
∀ j : ℕ, continuingIteration j →
‖step (j + 1)‖_weightMatrix ≥ Δ →
‖step j + τBoundary j • searchDirection j‖_weightMatrix = Δ
boundaryReturnedStep :
∀ j : ℕ, continuingIteration j →
‖step (j + 1)‖_weightMatrix ≥ Δ →
returnedStep = step j + τBoundary j • searchDirection j
gradientUpdate :
∀ j : ℕ, continuingIteration j →
‖step (j + 1)‖_weightMatrix < Δ →
gradient (j + 1) = gradient j + α j • hessianApprox.mulVec (searchDirection j)
preconditionedGradientUpdate :
∀ j : ℕ, continuingIteration j →
‖step (j + 1)‖_weightMatrix < Δ →
preconditionedGradient (j + 1) = weightMatrixInv.mulVec (gradient (j + 1))
residualStop :
∀ j : ℕ, continuingIteration j →
‖step (j + 1)‖_weightMatrix < Δ →
steihaugResidualNormAt gradient preconditionedGradient (j + 1) <
steihaugResidualThreshold ε gradient preconditionedGradient →
returnedStep = step (j + 1)
betaDenominatorNeZero :
∀ j : ℕ, continuingIteration j →
‖step (j + 1)‖_weightMatrix < Δ →
steihaugResidualThreshold ε gradient preconditionedGradient ≤
steihaugResidualNormAt gradient preconditionedGradient (j + 1) →
steihaugResidualPairingAt gradient preconditionedGradient j ≠ 0
betaUpdate :
∀ j : ℕ, continuingIteration j →
‖step (j + 1)‖_weightMatrix < Δ →
steihaugResidualThreshold ε gradient preconditionedGradient ≤
steihaugResidualNormAt gradient preconditionedGradient (j + 1) →
β j =
steihaugResidualPairingAt gradient preconditionedGradient (j + 1) /
steihaugResidualPairingAt gradient preconditionedGradient j
searchDirectionUpdate :
∀ j : ℕ, continuingIteration j →
‖step (j + 1)‖_weightMatrix < Δ →
steihaugResidualThreshold ε gradient preconditionedGradient ≤
steihaugResidualNormAt gradient preconditionedGradient (j + 1) →
searchDirection (j + 1) = -preconditionedGradient (j + 1) + β j • searchDirection j
nextIterationActive :
∀ j : ℕ, continuingIteration j →
‖step (j + 1)‖_weightMatrix < Δ →
steihaugResidualThreshold ε gradient preconditionedGradient ≤
steihaugResidualNormAt gradient preconditionedGradient (j + 1) →
activeIteration (j + 1)Lemma 6.1.13
Lean contributors (project-level attribution): Chenyi Li, Wanli Ma, Zichen Wang.
Chapter06 Lemma 6.1.13 (1): along a genuine Steihaug-CG history that continues through all earlier indices needed to reach j, stays inside the trust region, and does not trigger the residual stopping test on those earlier steps, if the Hessian approximation B is symmetric and i ≤ j, and d_iᵀ B d_i ≠ 0, then g_iᵀ d_j = -g_jᵀ v_j. This is the source identity (6.1.73).
variable {n : ℕ}
namespace SteihaugCGAlgorithm
theorem gradient_searchDirection_eq_neg_gradient_preconditionedGradient
(A : SteihaugCGAlgorithm n) {i j : ℕ} (hSymm : A.hessianApprox.IsSymm) (hij : i ≤ j)
(hContinue : ∀ k : ℕ, k < j → A.continuingIteration k)
(hInterior : ∀ k : ℕ, k < j → ‖A.step (k + 1)‖_A.weightMatrix < A.Δ)
(hResidual : ∀ k : ℕ, k < j → A.residualThreshold ≤ A.residualNorm (k + 1))
(hCurvatureNeZero :
matrixQuadratic A.hessianApprox (A.searchDirection i) ≠ 0) :
dotProduct (A.gradient i) (A.searchDirection j) =
-A.residualPairing jTheorem 6.1.14
Lean contributors (project-level attribution): Chenyi Li, Wanli Ma, Zichen Wang.
Chapter06 Theorem 6.1.14 (4): whenever the Steihaug-CG algorithm returns either from the initial residual stopping test or from one of the three terminal branches at stage j, the returned step remains feasible for the weighted trust region: ‖s‖_W ≤ Δ.
variable {n : ℕ}
namespace SteihaugCGAlgorithm
theorem returnedStep_le_radius
(A : SteihaugCGAlgorithm n) {j : ℕ}
(hTerminal : A.initialOrTerminalStopAt j) :
‖A.returnedStep‖_A.weightMatrix ≤ A.ΔDefinition 6.1.extra.1
Lean contributors (project-level attribution): Chenyi Li, Wanli Ma, Zichen Wang.
Chapter06 Definition 6.1-extra-1: a trust-region subproblem at iteration k is the quadratic model q^(k) (s) = f(x_k) + g_kᵀ s + (1 / 2) sᵀ B_k s together with a symmetric matrix B_k and a positive trust-region radius Δ_k. The iterate x_k itself is ambient data for the translated trust region and the actual-reduction formula, not primitive step-space data of the subproblem owner.
open scoped Matrix.Norms.L2Operator
variable {n : ℕ}
local notation "Point" => EuclideanSpace ℝ (Fin n)
-- Chapter 6 already treats `TrustRegionSubproblem` as the owner of the step-space quadratic
-- model, feasible set, and predicted reduction. This file keeps that owner shape and treats the
-- current iterate `x_k` only as bridge data for the translated trust region and actual reduction.
structure TrustRegionSubproblem (n : ℕ) where
fAtCenter : ℝ
gradient : EuclideanSpace ℝ (Fin n)
hessianApprox : Matrix (Fin n) (Fin n) ℝ
hessianApprox_symm : hessianApprox.IsSymm
radius : ℝ
radius_pos : 0 < radiusAssumption 6.1.extra.2
— source only (outside the published documentation root) (Lean source)
Lean contributors (project-level attribution): Chenyi Li, Wanli Ma, Zichen Wang.
Chapter06 Assumption 6.1-extra-2: the stage subproblems P_k have uniformly bounded Hessian operator norms ‖B_k‖₂ = P_k.hessianOperatorNorm, the level set {x | f x ≤ f x0} is bounded and f is continuously differentiable on it, and the approximate subproblem solutions satisfy ‖s_k‖ ≤ η̃ * Δ_k for a positive constant η̃, where Δ_k = P_k.radius. The source-side fact that s_k is an approximate solution of the already-fixed subproblem (6.1.1) remains ambient context, rather than part of the packaged assumptions (A₀) in Section 6.1.
open scoped Matrix.Norms.L2Operator
variable {n : ℕ}
local notation "Point" => EuclideanSpace ℝ (Fin n)
-- Domain sampling for this refine pass:
-- * primary domain: lower level sets and trust-region assumption packages on `ℝ^n`;
-- * inspected owner declarations in this domain:
-- - `lowerLevelSetOn` / `mem_lowerLevelSetOn` in Chapter 1 for the canonical lower-level-set
-- owner, with the `Set.univ` specialization handled directly by `simp`;
-- - `quasiNewtonLevelSet` in Chapter 5 as an example of a source-facing bridge to that owner.
-- * best owner abstraction: the Chapter 6 level set is not a new owner; it is exactly
-- `lowerLevelSetOn Set.univ f x0`.
-- * layer targeted here: `source-facing`, since `TrustRegionAssumptionA0` is the Chapter 6
-- assumption package, but its level-set fields should live directly over the canonical owner.
-- Primitive data vs derived API:
-- * primitive data: the subproblem sequence, its uniform Hessian-operator-norm bound,
-- boundedness and `ContDiffOn` on the canonical lower level set `lowerLevelSetOn Set.univ f x0`,
-- and the step-size bound `‖s_k‖ ≤ η̃ * Δ_k`;
-- * derived API: only genuinely new consequences of `(A₀)`, such as the nonnegative uniform
-- Hessian bound below; owner facts already provided by `TrustRegionSubproblem.radius_pos` and
-- the direct `Set.univ` lower-level-set simp facts, and exact field projections, should not
-- be restated here.
class TrustRegionAssumptionA0
(f : Point → ℝ) (x0 : Point) (subproblem : ℕ → TrustRegionSubproblem n)
(s : ℕ → Point) : Prop where
hessianOperatorNorm_bounded :
∃ hessianBound : ℝ, ∀ k : ℕ, (subproblem k).hessianOperatorNorm ≤ hessianBound
levelSet_bounded : Bornology.IsBounded (lowerLevelSetOn Set.univ f x0)
contDiffOn_levelSet : ContDiffOn ℝ 1 f (lowerLevelSetOn Set.univ f x0)
step_norm_bounded :
∃ etaTilde > 0, ∀ k : ℕ, ‖s k‖ ≤ etaTilde * (subproblem k).radius
Definition 6.1.extra.3
Lean contributors (project-level attribution): Chenyi Li, Wanli Ma, Zichen Wang.
The curvature term g_kᵀ B_k g_k along the steepest-descent ray.
open scoped Matrix.Norms.L2Operator
variable {n : ℕ}
local notation "Point" => EuclideanSpace ℝ (Fin n)
-- Chapter 6 already owns the trust-region quadratic model, feasible set, and predicted reduction
-- through `Definition_6_1_extra_1`.
-- Relevant minimizer style in this domain:
-- * `Mathlib.Order.Filter.Extr.IsMinOn` / `isMinOn_iff` is the canonical minimizer API.
-- * `TrustRegionSubproblem.isSolution_iff_mem_feasibleSet_and_isMinOn`
-- already uses that API for trust-region solutions.
-- This file therefore keeps the source-facing linearized and Cauchy-point predicates, but
-- organizes their minimization clauses around `IsMinOn` instead of a parallel `∀`-based owner.
def TrustRegionSubproblem.gradientCurvature (P : TrustRegionSubproblem n) : ℝ :=
dotProduct P.gradient (P.hessianApprox.mulVec P.gradient)6.2 — Conic Model and Collinear Scaling Algorithm
Algorithm 6.2.1
Lean contributors (project-level attribution): Chenyi Li, Wanli Ma, Zichen Wang.
Chapter06 Algorithm 6.2.1: a one-dimensional conic-model algorithm for an objective f : ℝ → ℝ consists of initial data x1, s1 and sequences x, s, rho, and gamma indexed by ℕ, where the book's index k = 1, 2, ... is represented literally. The sampled objective values are f (x k), and the sampled derivative values are the canonical derivatives deriv f (x k), with explicit HasDerivAt hypotheses at the iterate points x k for k ≥ 1. Step 0 gives x 1 = x1 and s 1 = s1; Step k.1 gives x (k + 1) = x k + s k; Step k.3 gives the formulas for rho k and gamma k; and Step k.4 gives the formula for s (k + 1), together with the explicit side conditions making the displayed square root and divisions mathematically well-defined for k ≥ 1.
structure ConicModelOneDimensionalAlgorithm (f : ℝ → ℝ) where
x1 : ℝ
s1 : ℝ
x : ℕ → ℝ
s : ℕ → ℝ
rho : ℕ → ℝ
gamma : ℕ → ℝ
x_one : x 1 = x1
s_one : s 1 = s1
hasDerivAt : ∀ ⦃k : ℕ⦄, 1 ≤ k → HasDerivAt f (deriv f (x k)) (x k)
iterate_update : ∀ ⦃k : ℕ⦄, 1 ≤ k → x (k + 1) = x k + s k
rhoRadicand_nonneg :
∀ ⦃k : ℕ⦄, 1 ≤ k →
0 ≤
conicModelRhoRadicand
(f (x k))
(f (x (k + 1)))
(deriv f (x k))
(deriv f (x (k + 1)))
(s k)
rho_update :
∀ ⦃k : ℕ⦄, 1 ≤ k →
rho k =
conicModelRho
(f (x k))
(f (x (k + 1)))
(deriv f (x k))
(deriv f (x (k + 1)))
(s k)
gammaDenominator_ne_zero :
∀ ⦃k : ℕ⦄, 1 ≤ k →
conicModelGammaDenominator (f (x k)) (f (x (k + 1))) (rho k) ≠ 0
gamma_update :
∀ ⦃k : ℕ⦄, 1 ≤ k →
gamma k =
conicModelGamma
(f (x k))
(f (x (k + 1)))
(deriv f (x k))
(s k)
(rho k)
gamma_ne_zero : ∀ ⦃k : ℕ⦄, 1 ≤ k → gamma k ≠ 0
nextDeriv_ne_zero : ∀ ⦃k : ℕ⦄, 1 ≤ k → deriv f (x (k + 1)) ≠ 0
stepDenominator_ne_zero :
∀ ⦃k : ℕ⦄, 1 ≤ k →
conicModelStepDenominator (gamma k) (deriv f (x k)) (deriv f (x (k + 1))) ≠ 0
step_update :
∀ ⦃k : ℕ⦄, 1 ≤ k →
s (k + 1) =
conicModelNextStep (s k) (gamma k) (deriv f (x k)) (deriv f (x (k + 1)))Algorithm 6.2.2
Lean contributors (project-level attribution): Chenyi Li, Wanli Ma, Zichen Wang.
Chapter06 Algorithm 6.2.2: a collinear scaling BFGS algorithm on ℝ^n consists of an objective f, an initial positive-definite matrix C₀, an initial point x₀, an initial scalar δ₀ > 0, a maximum line-search bound αMax > 0, and explicit sequences of matrices C k, iterates x k, objective values fVal k, gradients g k, line-search parameters α k, steps s k, auxiliary scalars ρ k and γ k, vectors y k, and scaling parameters δ k. The source Step 2 bound ᾱ is recorded by collinearScalingAlphaUpperBound (δ k) αMax; the line-search step, iterate update, value and gradient evaluation, and the formula for ρ_k² with ρ_k > 0 are recorded explicitly; and Step 4 is recorded by the formulas for γ_k, y_k, C_{k+1}, and δ_{k+1} together with the source inequalities and nonvanishing hypotheses from which the displayed divisions are well-defined.
variable {n : ℕ}
-- Semantic recall: `lean_leansearch` surfaced `Matrix.PosDef` as the canonical owner for the
-- positive-definite matrix condition, and nearby Chapter 4/5/6 precedent records optimization
-- algorithms as explicit sequence data on the concrete `EuclideanSpace ℝ (Fin n)` matrix layer.
structure CollinearScalingBFGSAlgorithm
(n : ℕ) (f : EuclideanSpace ℝ (Fin n) → ℝ) where
C0 : Matrix (Fin n) (Fin n) ℝ
x0 : EuclideanSpace ℝ (Fin n)
δ0 : ℝ
αMax : ℝ
C : ℕ → Matrix (Fin n) (Fin n) ℝ
x : ℕ → EuclideanSpace ℝ (Fin n)
fVal : ℕ → ℝ
g : ℕ → EuclideanSpace ℝ (Fin n)
α : ℕ → ℝ
s : ℕ → EuclideanSpace ℝ (Fin n)
ρ : ℕ → ℝ
γ : ℕ → ℝ
y : ℕ → EuclideanSpace ℝ (Fin n)
δ : ℕ → ℝ
C0_posDef : C0.PosDef
δ0_pos : 0 < δ0
αMax_pos : 0 < αMax
C_zero : C 0 = C0
x_zero : x 0 = x0
δ_zero : δ 0 = δ0
value_eq : ∀ k : ℕ, fVal k = f (x k)
hasGradientAt : ∀ k : ℕ, HasGradientAt f (g k) (x k)
alpha_mem :
∀ k : ℕ, α k ∈ Set.Ioo (0 : ℝ) (collinearScalingAlphaUpperBound (δ k) αMax)
step_eq : ∀ k : ℕ, s k = collinearScalingStep (α k) (δ k) (C k) (g k)
iterate_eq : ∀ k : ℕ, x (k + 1) = x k + s k
rho_sq_eq :
∀ k : ℕ, ρ k ^ 2 = collinearScalingRhoSq (fVal k) (fVal (k + 1)) (g (k + 1)) (g k) (s k)
rho_pos : ∀ k : ℕ, 0 < ρ k
value_strict_decrease : ∀ k : ℕ, fVal (k + 1) < fVal k
gamma_eq :
∀ k : ℕ, γ k = collinearScalingGamma (g k) (s k) (fVal k) (fVal (k + 1)) (ρ k)
directionalDerivative_ne_zero : ∀ k : ℕ, dotProduct (g k) (s k) ≠ 0
y_eq : ∀ k : ℕ, y k = collinearScalingYVector (γ k) (g k) (g (k + 1))
secant_pairing_ne_zero : ∀ k : ℕ, dotProduct (s k) (y k) ≠ 0
matrix_update_eq :
∀ k : ℕ, C (k + 1) = collinearScalingBFGSMatrixUpdate (γ k) (C k) (s k) (y k)
delta_update_eq :
∀ k : ℕ, δ (k + 1) = collinearScalingDeltaUpdate (γ k) (g k) (s k) (C (k + 1)) (g (k + 1))Definition 6.2.extra.1
— source only (outside the published documentation root) (Lean source)
Lean contributors (project-level attribution): Chenyi Li, Wanli Ma, Zichen Wang.
The quadratic function x ↦ xᵀ A x + bᵀ x + c on Point n = ℝ^n.
variable {n : ℕ}
-- Domain sampling for this item:
-- - primary domain: quadratic-over-affine conic models on Euclidean space;
-- - sampled project owner declarations: `quadraticFunction`,
-- `ConicTrustRegionSubproblem.admissibleSet`, `ConicTrustRegionSubproblem.objective`;
-- - sampled mathlib declarations: `AffineMap`, `Set.EqOn`, `ContDiffOn.div`;
-- - best owner abstraction: the conic ratio together with its admissible nonvanishing-denominator
-- domain, with domain-restricted recognition predicates derived from that owner;
-- - primitive data: the quadratic numerator coefficients `A`, `b`, `c` and the affine
-- denominator `a`;
-- - derived API: the admissible domain, the ambient conic ratio, and the domain-local predicate
-- `IsConicOn`.
-- Semantic recall: `lean_leansearch` surfaced only the homogeneous `QuadraticMap` API and
-- matrix conversions, while nearby repository precedent uses the explicit matrix/vector/scalar
-- formula for general quadratic functions. The source-facing notion therefore stays on that
-- concrete `ℝ^n` layer.
def quadraticFunction (A : MatrixN n) (b : Point n) (c : ℝ) (x : Point n) : ℝ :=
matrixQuadratic A x + dotProduct b x + c
Definition 6.2.extra.2
Lean contributors (project-level attribution): Chenyi Li, Wanli Ma, Zichen Wang.
Chapter06 Definition 6.2-extra-2 (1): a conic trust-region subproblem on ℝ^n records the step-space model data: the scalar f = f(x) at the current approximation x, the gradient g = ∇ f(x), the Hessian approximation A, the horizontal vector a, the scaling matrix D, and the trust-region radius Δ for the model ψ(s) = f + (gᵀ s) / (1 - aᵀ s) + (1 / 2) (sᵀ A s) / (1 - aᵀ s)^2 under the constraint ‖D s‖ ≤ Δ, with 0 ≤ Δ. The iterate x itself is ambient bridge data for later translated statements, not primitive data of this owner.
variable {n : ℕ}
structure ConicTrustRegionSubproblem (n : ℕ) where
fAtCenter : ℝ
gradient : EuclideanSpace ℝ (Fin n)
hessianApprox : Matrix (Fin n) (Fin n) ℝ
horizontalVector : EuclideanSpace ℝ (Fin n)
scalingMatrix : Matrix (Fin n) (Fin n) ℝ
radius : ℝ
radius_nonneg : 0 ≤ radius6.3 — Tensor Methods
Definition 6.3.1
— source only (outside the published documentation root) (Lean source)
Lean contributors (project-level attribution): Chenyi Li, Wanli Ma, Zichen Wang.
Chapter06 Definition 6.3.1: a third-order tensor on ℝ^n is represented by its coordinate entries T i j k : ℝ, equivalently by its n horizontal faces indexed by i : Fin n.
open scoped BigOperators
variable {n : ℕ}
local notation "Point" => EuclideanSpace ℝ (Fin n)
-- Semantic recall: `lean_leansearch` surfaced abstract tensor-product contraction APIs, but
-- this item is a coordinate definition on `ℝ^n`, and nearby Chapter 6 files use the explicit
-- `EuclideanSpace ℝ (Fin n)` / matrix surface for finite-dimensional data.
abbrev ThirdOrderTensor (n : ℕ) := Fin n → Fin n → Fin n → ℝ
Definition 6.3.2
— source only (outside the published documentation root) (Lean source)
Lean contributors (project-level attribution): Chenyi Li, Wanli Ma, Zichen Wang.
Chapter06 Definition 6.3.2 (1): the third-order rank-one tensor u ⊗ v ⊗ w is the tensor with entries T i j k = u i * v j * w k.
variable {n : ℕ}
local notation "Point" => EuclideanSpace ℝ (Fin n)
-- Semantic recall: `lean_leansearch` surfaced `Matrix.vecMulVec` and
-- `Matrix.rank_vecMulVec_le` as the canonical rank-one matrix API. This file keeps the source's
-- third-order tensor as the concrete owner from Definition 6.3.1 and expresses its horizontal
-- faces through `Matrix.vecMulVec`.
namespace ThirdOrderTensor
def rankOne (u v w : Point) : ThirdOrderTensor n :=
fun i j k ↦ u i * v j * w k
Theorem 6.3.3
— source only (outside the published documentation root) (Lean source)
Lean contributors (project-level attribution): Chenyi Li, Wanli Ma, Zichen Wang.
Chapter06 Theorem 6.3.3 (2): if s : Fin p → ℝ^n is linearly independent and z : Fin p → ℝ^n, then the least-Frobenius-norm solution of the interpolation problem T s_k s_k = z_k is the explicit tensor Tc = tensorGramInverseCombination s z = ∑ k, a_k ⊗ s_k ⊗ s_k, where a_k is the k-th column of the coefficient matrix tensorGramInverseCoefficientMatrix s z = Z M⁻¹. As in part (1), the source's side condition p ≤ n is redundant once s is linearly independent, and the objective is the full coordinate Frobenius norm owner T.fullFrobeniusNorm, matching the source ‖T_c‖_F on all tensor entries.
open scoped BigOperators
open scoped ThirdOrderTensor
variable {n p : ℕ}
theorem tensorLeastNormSolution_isMinOn
(s : Fin p → EuclideanSpace ℝ (Fin n)) (z : Fin p → EuclideanSpace ℝ (Fin n))
(hlin : LinearIndependent ℝ s) :
let Tc := tensorGramInverseCombination s z
Tc ∈ tensorLeastNormFeasibleSet s z ∧
IsMinOn (fun T ↦ T.fullFrobeniusNorm) (tensorLeastNormFeasibleSet s z) Tc
Theorem 6.3.4
Lean contributors (project-level attribution): Chenyi Li, Wanli Ma, Zichen Wang.
Chapter06 Theorem 6.3.4: let p ≤ n, let s : Fin p → ℝⁿ be linearly independent, and let β : ℝᵖ. If M[i,j] = ((s i)ᵀ (s j))^4 and γ = M⁻¹ β, then the solution of (6.3.41) is V_c = ∑ k, γ[k] (s k ⊗ s k ⊗ s k ⊗ s k). As in Theorem 6.3.3, the source side condition p ≤ n is redundant once s is linearly independent, so the Lean statement packages the solution claim as feasibility plus least-Frobenius-norm optimality for the explicit tensor quarticTensorGramInverseCombination s β.
open scoped BigOperators
variable {n p : ℕ}
local notation "Point" => EuclideanSpace ℝ (Fin n)
-- Domain sampling for this file:
-- * `Chapter06.Tensor4`: source-facing fourth-order tensor vocabulary now lives in the reusable
-- chapter owner file as coordinate tensors with the intended Frobenius/Hilbert norm.
-- * `Chapter06.Definition_6_3_1`: `ThirdOrderTensor` is the chapter's matching source-facing
-- tensor owner pattern, so the quartic owner should stay at the same coordinate level.
-- * `Mathlib.Analysis.InnerProductSpace.PiL2`: `PiLp 2` / `WithLp.toLp 2` is the core/canonical
-- Hilbert-space owner for finite coordinate arrays, which induces the tensor Frobenius norm.
-- * `Tensor4.rankOne`, `Tensor4.apply`, `Tensor4.frobeniusNorm`, and `Tensor4.IsSymmetric` are
-- derived API on that owner, so this theorem file only keeps the quartic interpolation data.
open scoped Tensor4
theorem quarticTensorLeastNormSolution_isMinOn
(s : Fin p → Point) (β : EuclideanSpace ℝ (Fin p))
(hlin : LinearIndependent ℝ s) :
let Vc := quarticTensorGramInverseCombination s β
Vc ∈ quarticTensorFeasibleSet s β ∧
IsMinOn (fun V ↦ V.frobeniusNorm) (quarticTensorFeasibleSet s β) VcTheorem 6.3.5
— source only (outside the published documentation root) (Lean source)
Lean contributors (project-level attribution): Chenyi Li, Wanli Ma, Zichen Wang.
Chapter06 Theorem 6.3.5: if s : Fin p → ℝ^n is linearly independent and a : Fin p → ℝ^n, then the symmetric least-Frobenius-norm solution of problem (6.3.43) is the explicit tensor symmetricThirdTensorLeastNormSolution s a hlin = symmetricThirdTensorCombination s (b), where b = symmetricThirdTensorLeastNormCoefficients s a hlin is the uniquely determined coefficient family satisfying the interpolation equations. The companion coefficient uniqueness statement is recorded separately via existsUnique_symmetricThirdTensorLeastNormCoefficients. The source's side condition p ≤ n is redundant once s is linearly independent and is therefore omitted from the Lean statement.
open scoped BigOperators
open scoped ThirdOrderTensor
variable {n p : ℕ}
local notation "Point" => EuclideanSpace ℝ (Fin n)
local notation "Tensor3" => ThirdOrderTensor n
-- Semantic recall: Chapter 6 already owns the source-facing third-order tensor API through
-- `ThirdOrderTensor`, `⟪u, v, w⟫₃`, `ThirdOrderTensor.mulVecVec`,
-- `ThirdOrderTensor.fullFrobeniusNorm`,
-- and `tensorLeastNormFeasibleSet`. This file adds only the symmetric third-order interpolation
-- surface for Theorem 6.3.5.
theorem symmetricThirdTensorLeastNormSolution_spec
(s : Fin p → Point) (a : Fin p → Point) (hlin : LinearIndependent ℝ s) :
symmetricThirdTensorLeastNormSolution s a hlin =
symmetricThirdTensorCombination s (symmetricThirdTensorLeastNormCoefficients s a hlin) ∧
IsSymmetricThirdTensorLeastNormSolution s a
(symmetricThirdTensorLeastNormSolution s a hlin)
Algorithm 6.3.6
— source only (outside the published documentation root) (Lean source)
Lean contributors (project-level attribution): Chenyi Li, Wanli Ma, Zichen Wang.
Chapter06 Algorithm 6.3.6: a single non-stopping tensor-method transition on ℝ^n from the current state xc, together with the Nat.nthRoot 3 n most recent past points, to the Step 7-8 update determined by Steps 3-6. Step 3 selects p recent points; Step 4 supplies the interpolation right-hand sides from which the chapter's canonical tensors Tc and Vc are derived; Step 5 records the tensor-model trial data dT and ΔT; and Step 6 records the canonical quadratic trust-region subproblem together with its source-facing gradient and Hessian compatibility with f at xc, its trial step dN, and the updated radius ΔN. The next iterate, next radius, and next objective value are then derived from this source-facing data by the branch comparison in Step 7. The selected interpolation family is stored through its linear independence, and the distinctness of the selected indices is derived from that owner data rather than stored separately.
variable {n p : ℕ}
local notation "Point" => EuclideanSpace ℝ (Fin n)
local notation "MatrixN" => Matrix (Fin n) (Fin n) ℝ
local notation "Tensor3N" => ThirdOrderTensor n
local notation "Tensor4N" => _root_.Tensor4 n
structure TensorMethodTransition (n p : ℕ) where
f : EuclideanSpace ℝ (Fin n) → ℝ
xc : EuclideanSpace ℝ (Fin n)
quadraticSubproblem : TrustRegionSubproblem n
quadraticSubproblem_fAtCenter_eq : quadraticSubproblem.fAtCenter = f xc
hasGradientAt : HasGradientAt f quadraticSubproblem.gradient xc
hasHessianApproxAt : HasHessianMatrixAt f xc quadraticSubproblem.hessianApprox
recentPastPoint : Fin (Nat.nthRoot 3 n) → EuclideanSpace ℝ (Fin n)
selectedPastIndex : Fin p → Fin (Nat.nthRoot 3 n)
selectedPastPoint_linearIndependent :
LinearIndependent ℝ (fun i ↦ recentPastPoint (selectedPastIndex i))
tensorInterpolationData : Fin p → EuclideanSpace ℝ (Fin n)
quarticInterpolationData : EuclideanSpace ℝ (Fin p)
dT : EuclideanSpace ℝ (Fin n)
ΔT : ℝ
dN : EuclideanSpace ℝ (Fin n)
ΔN : ℝ
tensorRadius_pos : 0 < ΔT
quadraticRadius_pos : 0 < ΔN
quadraticStep_feasible :
dN ∈ (quadraticSubproblem.feasibleSet : Set (EuclideanSpace ℝ (Fin n)))
Supporting modules
These source modules support the indexed items and are listed separately so the chapter inventory remains complete.
-
Tensor4.lean(Documentation) (Lean source)
Lean contributors (project-level attribution): Chenyi Li, Wanli Ma, Zichen Wang.
-
Theorem_6_1_11/Path.lean(Documentation) (Lean source)
Lean contributors (project-level attribution): Chenyi Li, Wanli Ma, Zichen Wang.
-
Theorem_6_3_3/Frobenius.lean(Documentation unavailable) (Lean source)
Lean contributors (project-level attribution): Chenyi Li, Wanli Ma, Zichen Wang.
-
Theorem_6_3_3/Interpolation.lean(Documentation unavailable) (Lean source)
Lean contributors (project-level attribution): Chenyi Li, Wanli Ma, Zichen Wang.