Chapter 11 — Feasible Direction Methods
Proofs omitted. Hover over highlighted terms to see their Lean types.
Exercise 11.1
— source only (outside the published documentation root) (Lean source)
Lean contributors (project-level attribution): Chenyi Li, Wanli Ma, Zichen Wang.
Chapter11 Exercise 11.1 (1): the normalized feasible-direction search problem with feasible set linearlyConstrainedDirectionSearchFeasibleSet A b x and objective linearlyConstrainedDirectionSearchObjective f x is a convex program in the canonical Chapter 8 owner sense ConvexOn. The source feasibility and differentiability assumptions are not needed for this convexity statement itself.
variable {n m : ℕ}
local notation "Point" => EuclideanSpace ℝ (Fin n)
local notation "ConstraintPoint" => EuclideanSpace ℝ (Fin m)
local notation "ConstraintMatrix" => Matrix (Fin n) (Fin m) ℝ
-- Domain-style sampling:
-- * primary domain: linearly constrained feasible-direction search and its explicit dual
-- maximization problem in Euclidean space
-- * inspected owner declarations:
-- `OptimizationProblem` from Chapter 1,
-- `ConstrainedOptimizationProblem.IsDualSolution` from Chapter 8,
-- `QuadraticProgram.IsDualSolution` from Chapter 9,
-- and `IsFeasibleDescentDirection` from `Definition_11_1_extra_1`
-- * best owner abstraction: keep the source-facing feasible-set/objective data for the primal
-- direction search, and expose the dual directly by its multiplier feasible set and objective;
-- the Chapter 1 owner `OptimizationProblem` would add only a coordinate transport from
-- `EuclideanSpace ℝ (Fin m)` to `Fin m → ℝ`, so the dual optimality surface here should be the
-- canonical predicate `IsMaxOn` rather than a second local problem wrapper
-- * primitive data: the primal feasible set/objective and the dual feasible set/objective
-- * layer triage:
-- source-facing: `linearlyConstrainedDirectionSearchDualFeasibleSet` and
-- `linearlyConstrainedDirectionSearchDualObjective`
-- core/canonical: `ConvexOn` and `IsMaxOn`
-- bridge/view: the membership and evaluation simp lemmas
-- * derived API: convexity and feasible-descent certification
theorem linearlyConstrainedDirectionSearch_isConvexProgram
(f : Point → ℝ) (A : ConstraintMatrix) (b : ConstraintPoint) (x : Point) :
ConvexOn ℝ (linearlyConstrainedDirectionSearchFeasibleSet A b x)
(linearlyConstrainedDirectionSearchObjective f x)
Exercise 11.2
Lean contributors (project-level attribution): Chenyi Li, Wanli Ma, Zichen Wang.
Chapter11 Exercise 11.2 is the same nearest-point-on-an-ellipse problem already formalized in Chapter08 Exercise 8.9, so this file reuses the Chapter 8 source-facing owners directly instead of reintroducing parallel local definitions.
local notation "Point" => EuclideanSpace ℝ (Fin 3)
-- Domain sampling:
-- * mathlib owner: `IsMinOn`
-- * project source-facing owners: `exercise89FeasibleSet`, `exercise89SquaredDistanceToOrigin`,
-- and `exercise89NearestPoint`
-- Layer triage:
-- * source-facing: the explicit ellipse and squared-distance problem already formalized in
-- Chapter 8 Exercise 8.9
-- * core/canonical: `IsMinOn` on that feasible set
-- * bridge/view: the uniqueness theorem below, with the explicit feasibility hypothesis that
-- `IsMinOn` itself does not encode
#check exercise89NearestPoint_mem_feasibleSetExercise 11.3
— source only (outside the published documentation root) (Lean source)
Lean contributors (project-level attribution): Chenyi Li, Wanli Ma, Zichen Wang.
Exercise 11.3 as the linear equality-constrained problem with constraint x 0 + x 1 = 1.
local notation "Point" => EuclideanSpace ℝ (Fin 2) -- Primary domain: equality-constrained minimization in a finite-dimensional Euclidean space. -- Sampled owners: -- * `IsMinOn` is the canonical minimizer predicate. -- * `LinearEqualityConstrainedProblem` from Chapter 11 is the owner for affine equality -- constraints `Aᵀ x = b`, with `x ∈ problem` as the public feasible-point surface and -- `problem.feasibleSet` as the underlying set-valued minimization domain. -- The exercise-specific primitive data are the quartic objective and the eliminated -- one-variable quartic; the feasible-set API is derived from the Chapter 11 owner object. def chapter11Exercise113Problem : LinearEqualityConstrainedProblem 2 1
Exercise 11.4
— source only (outside the published documentation root) (Lean source)
Lean contributors (project-level attribution): Chenyi Li, Wanli Ma, Zichen Wang.
Chapter11 Exercise 11.4 (1): at the point (3, -2)ᵀ, the projected gradient of the reused constrained problem along the normalized null-space direction of x 0 + x 1 = 1 is 416 * √2.
local notation "Point" => EuclideanSpace ℝ (Fin 2)
local notation "projectedGradient114" =>
linearlyConstrainedDirectionSearchObjective chapter11Exercise113Objective
-- Source/core/bridge triage:
-- * source-facing: the scalar first-order and second-order data of the Exercise 11.3 objective
-- along the normalized null direction of the equality constraint.
-- * inspected owners: `linearlyConstrainedDirectionSearchObjective` from `Exercise_11_1`,
-- `hessianQuadraticAt` from `Chapter03.Definition_3_5_1`,
-- `projectedGradientReducedGradient` from `Algorithm_11_4_1`, and
-- `LinearEqualityConstrainedProblem.feasibleSet` from `Lemma_11_5_4`.
-- * core/canonical: `linearlyConstrainedDirectionSearchObjective` for the directional pairing and
-- `hessianQuadraticAt` for the second-order directional evaluation.
-- * bridge/view: the exercise-specific null direction used to evaluate those canonical owners.
theorem chapter11Exercise114_projectedGradient_testPoint :
projectedGradient114 chapter11Exercise114TestPoint chapter11Exercise114NullDirection =
416 * Real.sqrt 2
Exercise 11.5
Lean contributors (project-level attribution): Chenyi Li, Wanli Ma, Zichen Wang.
Chapter11 Exercise 11.5: the projected gradient algorithm for the box constrained problem min objective x subject to lowerBound ≤ x and x ≤ upperBound is the iterate sequence starting from x₁ = initialPoint and defined recursively by x_(k + 1) = P_[lowerBound, upperBound] (x_k - stepSize k • ∇ objective (x_k)) for k ≥ 1.
variable {n : ℕ}
local notation "Point" => EuclideanSpace ℝ (Fin n)
-- Semantic recall hits for this item: `Set.projIcc` and `Set.coe_projIcc` are the canonical
-- interval-projection owners in mathlib, so the box projection is modeled coordinatewise on
-- `EuclideanSpace ℝ (Fin n)` rather than through a wrapper around a generic nearest-point map.
variable (objective : Point → ℝ) (lowerBound upperBound : Point)
(h_bounds : ∀ i, lowerBound i ≤ upperBound i)
local notation "P_[" lowerBound ", " upperBound "]" =>
boxProjection lowerBound upperBound h_bounds
def boxProjectedGradientAlgorithm
(initialPoint : Point) (stepSize : ℕ → ℝ) : ℕ → Point :=
fun
| 0 => initialPoint
| 1 => initialPoint
| k + 2 =>
boxProjectedGradientStep objective lowerBound upperBound h_bounds
(stepSize (k + 1))
(boxProjectedGradientAlgorithm
objective lowerBound upperBound h_bounds initialPoint stepSize (k + 1))Exercise 11.6
— source only (outside the published documentation root) (Lean source)
Lean contributors (project-level attribution): Chenyi Li, Wanli Ma, Zichen Wang.
Chapter11 Exercise 11.6: direct recall of the source-facing generalized reduced-gradient method owner form of Chapter 11 Theorem 11.3.2.
open GeneralizedReducedGradientMethod #check tendsto_reducedGradientNorm_zero_or_objective_tendsto_atBot
Exercise 11.7
Lean contributors (project-level attribution): Chenyi Li, Wanli Ma, Zichen Wang.
Chapter11 Exercise 11.7 (1): if B is invertible, then the bordered matrix borderedMatrix B b β = [[B, b], [bᵀ, β]] is invertible if and only if the scalar Schur complement β - bᵀ B⁻¹ b is nonzero, i.e. formula (11.5.39). The symmetry assumption from the exercise is not needed for this invertibility criterion.
open Matrix
variable {n : ℕ}
local notation "VectorN" => EuclideanSpace ℝ (Fin n)
local notation "MatrixN" => Matrix (Fin n) (Fin n) ℝ
local notation "BorderedIndex" => Sum (Fin n) (Fin 1)
local notation "BorderedVectorN" => EuclideanSpace ℝ BorderedIndex
local notation "BorderedMatrixN" => Matrix BorderedIndex BorderedIndex ℝ
-- Semantic recall: `lean_leansearch` surfaced the Schur-complement block-matrix API in
-- `Mathlib.LinearAlgebra.Matrix.SchurComplement`, especially the `Matrix.fromBlocks`
-- nonsingularity criteria and inverse formulas. This item keeps the source bordered matrix
-- explicit and records the scalar Schur-complement and rank-one inverse conclusions directly.
theorem borderedMatrix_isUnit_iff_schurComplement_ne_zero
(B : MatrixN) (b : VectorN) (β : ℝ) (hB : IsUnit B) :
IsUnit (borderedMatrix B b β) ↔ borderedMatrixSchurComplement B b β ≠ 011.1 — Feasible Point Methods
Lemma 11.1.1
— source only (outside the published documentation root) (Lean source)
Lean contributors (project-level attribution): Chenyi Li, Wanli Ma, Zichen Wang.
Chapter11 Lemma 11.1.1 (1): if xk ∈ X, d satisfies (11.1.1) and (11.1.2), α is a feasible point Armijo step along d at xk, the doubled-step segment xk + (t * α) • d, t ∈ [0, 2], lies in an open set D on which f is C², the source maximum feasiblePointArmijoHessianBound f xk d α then induces the canonical Chapter 1 Hessian upper bound on that trace, and xk + (2 * α) • d ∈ X, then f (xk + α • d) satisfies the decrease estimate (11.1.5) with that source maximum.
variable {E : Type*} [NormedAddCommGroup E] [InnerProductSpace ℝ E] [CompleteSpace E]
-- Domain sampling for this item:
-- * primary domain: feasible-point Armijo decrease estimates in real-Hilbert-space smooth
-- constrained optimization
-- * owner abstractions inspected: `Metric.infDist`, `IsFeasiblePointArmijoStep`,
-- `HasHessianUpperBoundOn`, `lineTaylorFormula_withIntegralHessianRemainder`, and the
-- Chapter 3 Hessian owner `hessianAt`
-- * layer triage:
-- - `Metric.infDist x Xᶜ`: canonical distance owner for the source quantity `Γ(x)`
-- - `feasiblePointArmijoHessianBound`: source-facing scalar quantity for Lemma 11.1.1,
-- built from the canonical Hessian owner `hessianAt`
-- - `feasiblePointArmijoHessianBound_hasHessianUpperBoundOn`: bridge/view from the source
-- maximum to the canonical Chapter 1 setwise Hessian-bound owner
-- - the two decrease theorems: source-facing statements built on the Chapter 11 Armijo owner
-- * primitive data vs. derived API:
-- - primitive/source data: the Armijo step, the doubled-step feasibility branch, an open
-- set containing the traced segment from `xk` to `xk + (2 * α) • d`, and `ContDiffOn ℝ 2 f`
-- there
-- - derived API: the scalar source maximum `feasiblePointArmijoHessianBound f xk d α`,
-- expressed through the canonical owner `hessianAt`, together with the induced Chapter 1
-- setwise Hessian upper bound on the traced segment
theorem feasiblePointArmijoStep_decrease_of_double_mem
(f : E → ℝ) (X : Set E) (c1 : ℝ) (xk d : E) (α : ℝ) {D : Set E}
(hD : IsOpen D)
(h_segment : segment ℝ xk (xk + (2 * α) • d) ⊆ D)
(hC2 : ContDiffOn ℝ 2 f D)
(hα : IsFeasiblePointArmijoStep f X xk d c1 α)
(h_double_mem : xk + (2 * α) • d ∈ X) :
f (xk + α • d) ≤
f xk -
(c1 * (1 - c1) / feasiblePointArmijoHessianBound f xk d α) *
(inner ℝ d (gradient f xk) / ‖d‖) ^ (2 : ℕ)
Algorithm 11.1.2
— source only (outside the published documentation root) (Lean source)
Lean contributors (project-level attribution): Chenyi Li, Wanli Ma, Zichen Wang.
Chapter11 Algorithm 11.1.2 (1): Step 1 initializes the feasible-direction Armijo search at (α_max, α) = (+∞, 1).
variable {n : ℕ}
local notation "Point" => EuclideanSpace ℝ (Fin n)
-- Layer triage:
-- * source-facing: `FeasibleDirectionArmijoState`, `feasibleDirectionArmijoStep`
-- * core/canonical reused from earlier project owners: `feasiblePointArmijoAccepts`
-- * bridge/view: the branch-characterization lemmas for `feasibleDirectionArmijoStep`
def feasibleDirectionArmijoInitialState : FeasibleDirectionArmijoState
Lemma 11.1.3
— source only (outside the published documentation root) (Lean source)
Lean contributors (project-level attribution): Chenyi Li, Wanli Ma, Zichen Wang.
Chapter11 Lemma 11.1.3. Assume d ∈ FD(x, X) and αStar satisfies the source exact line-search condition (11.1.11) on the truncated step domain feasibleDirectionStepSet X x d = Set.Icc 0 (Metric.infDist x Xᶜ / ‖d‖), encoded as both αStar ∈ feasibleDirectionStepSet X x d and minimization of α ↦ f (x + α • d) on that set because IsMinOn itself does not enforce set membership. If M is the source maximum max_(t ≥ 0) ‖∇² f (x + t • d)‖₂ along the ray, with the needed along-ray differentiability bundled into IsFeasibleDirectionHessianRayMaximum, and 0 < M so the coefficient 1 / (2 * M) matches the source formula, then either the source quadratic-model decrease estimate (11.1.12) or the boundary-limited decrease estimate (11.1.13) holds.
variable {n : ℕ}
local notation "Point" => EuclideanSpace ℝ (Fin n)
-- Semantic recall: `lean_leansearch` surfaced the generic extremum/minimizer APIs and
-- `DifferentiableAt.hasGradientAt`, so the Hessian-max owner below records the along-ray
-- differentiability needed for `gradient f` and `fderiv ℝ (gradient f)` to denote the source
-- `∇ f` and `∇² f` data rather than their totalized Lean terms. The chapter already owns the
-- source feasible-direction predicate in `Chapter08.Definition_8_2_1` and the Chapter 11
-- use of the canonical distance owner `Metric.infDist x Xᶜ`, so this file keeps only the exact
-- line-search step domain and the Hessian-ray bound that are specific to Lemma 11.1.3.
theorem exactLineSearch_decrease_or_boundaryDecrease_of_feasibleDirection
(f : Point → ℝ) (X : Set Point) (x d : Point) (M αStar : ℝ)
(hd : d ∈ feasibleDirections x X)
(hM : IsFeasibleDirectionHessianRayMaximum f x d M)
(hM_pos : 0 < M)
(hαStar_mem : αStar ∈ feasibleDirectionStepSet X x d)
(hαStar :
IsMinOn (fun α : ℝ ↦ f (x + α • d))
(feasibleDirectionStepSet X x d) αStar) :
f x - f (x + αStar • d) ≥
(1 / (2 * M)) * (inner ℝ d (gradient f x) / ‖d‖) ^ (2 : ℕ) ∨
f x - f (x + αStar • d) ≥
-((Metric.infDist x Xᶜ) / (2 * ‖d‖)) * inner ℝ d (gradient f x)
Lemma 11.1.4
— source only (outside the published documentation root) (Lean source)
Lean contributors (project-level attribution): Chenyi Li, Wanli Ma, Zichen Wang.
Chapter11 Lemma 11.1.4: if x ∈ X, X is convex, f is convex on X, and f is differentiable at x, then there exists a feasible descent direction at x if and only if x is not a minimizer of f on X.
variable {E : Type*} [NormedAddCommGroup E] [InnerProductSpace ℝ E] [CompleteSpace E]
-- Layer triage:
-- * source-facing: existence of a feasible descent direction versus failure of `IsMinOn`
-- * core/canonical reused from earlier Chapter 11 owner: `IsFeasibleDescentDirection`
-- * bridge/view: the companion theorem phrased via `feasibleDescentDirections`
theorem exists_feasibleDescentDirection_iff_not_isMinOn_of_convexOn
(f : E → ℝ) {x : E} {X : Set E}
(hx : x ∈ X) (hX : Convex ℝ X) (hf : ConvexOn ℝ X f)
(hfdiff : DifferentiableAt ℝ f x) :
(∃ d, IsFeasibleDescentDirection f x X d) ↔ ¬ IsMinOn f X x
Algorithm 11.1.5
— source only (outside the published documentation root) (Lean source)
Lean contributors (project-level attribution): Chenyi Li, Wanli Ma, Zichen Wang.
Chapter11 Algorithm 11.1.5: a feasible point method for minimizing objective on feasibleSet starts from x₁ ∈ feasibleSet. Step 2 stops when no vector satisfies the concrete conditions IsFeasibleDescentDirection objective x_k feasibleSet d; otherwise it chooses d_k with that property. Step 3 produces a positive feasible steplength stepSize k ∈ feasiblePointLineSearchDomain x_k d_k feasibleSet, and Step 4 updates x_(k + 1) = x_k + α_k • d_k. Here continues k means that Step 2 succeeds at stage k, so the method carries out Steps 3-4 from x_k; after that, stage k + 1 is continuing exactly when the new iterate x_(k + 1) again admits a Step-2 direction.
structure FeasiblePointMethod (n : ℕ) where
feasibleSet : Set (EuclideanSpace ℝ (Fin n))
objective : EuclideanSpace ℝ (Fin n) → ℝ
initialPoint : EuclideanSpace ℝ (Fin n)
continues : ℕ → Prop
iterate : ℕ → EuclideanSpace ℝ (Fin n)
direction : ℕ → EuclideanSpace ℝ (Fin n)
stepSize : ℕ → ℝ
initialPoint_mem : initialPoint ∈ feasibleSet
iterate_one : iterate 1 = initialPoint
continues_one_iff :
continues 1 ↔
∃ d : EuclideanSpace ℝ (Fin n),
IsFeasibleDescentDirection objective initialPoint feasibleSet d
feasible (k : ℕ) (hk : 1 ≤ k) (hcontinues : continues k) :
iterate k ∈ feasibleSet
direction_spec (k : ℕ) (hk : 1 ≤ k) (hcontinues : continues k) :
IsFeasibleDescentDirection objective (iterate k) feasibleSet (direction k)
step_search (k : ℕ) (hk : 1 ≤ k) (hcontinues : continues k) :
stepSize k ∈ feasiblePointLineSearchDomain (iterate k) (direction k) feasibleSet
iterate_succ (k : ℕ) (hk : 1 ≤ k) (hcontinues : continues k) :
iterate (k + 1) = iterate k + stepSize k • direction k
continues_succ_iff (k : ℕ) (hk : 1 ≤ k) :
continues (k + 1) ↔
continues k ∧
∃ d : EuclideanSpace ℝ (Fin n),
IsFeasibleDescentDirection objective (iterate (k + 1)) feasibleSet d
Lemma 11.1.6
— source only (outside the published documentation root) (Lean source)
Lean contributors (project-level attribution): Chenyi Li, Wanli Ma, Zichen Wang.
Chapter11 Lemma 11.1.6: for an unconstrained optimization problem on ℝ^n, let f : Point → ℝ be twice continuously differentiable and uniformly, equivalently strongly, convex on ℝ^n with modulus m > 0. Let x, d, and α be the iterates, search directions, and positive line-search step sizes of a method satisfying x (k + 1) = x k + α k • d k, and assume every d k is a descent direction at x k, formalized by the Chapter 1 owner IsDescentDirectionAt f (x k) (d k). The companion lemmas searchDirection_ne_of_descent and gradient_ne_of_descent record that this keeps both vectors in the source angle formula nonzero. If ∑' k, (Real.cos (InnerProductGeometry.angle (d k) (-gradient f (x k))))^2 is finite, i.e. ∑_{k=1}^∞ cos^2 θ_k < ∞ in the source notation up to the harmless finite initial-index convention difference between the source and Lean's ℕ indexing, then liminf ‖gradient f (x_k)‖ > 0.
open Filter
variable {n : ℕ}
local notation "Point" => EuclideanSpace ℝ (Fin n)
-- The source-facing layer here is the iterate-level convergence statement. The core reusable
-- owners are Chapter 1's `IsDescentDirectionAt` for descent directions and mathlib's canonical
-- angle owner `InnerProductGeometry.angle` for the angle between the search direction and the
-- negative gradient. The companion API
-- `IsDescentDirectionAt.direction_ne` / `IsDescentDirectionAt.gradient_ne` keeps the angle term
-- on its intended nondegenerate domain without duplicating separate public nonzero hypotheses.
theorem liminf_gradientNorm_pos_of_summable_cos_angle_sq_of_strongConvex
(f : Point → ℝ) (m : ℝ) (x d : ℕ → Point) (α : ℕ → ℝ)
(hC2 : ContDiff ℝ 2 f)
(hm : 0 < m)
(hStrong : StrongConvexOn Set.univ m f)
(h_update : ∀ k : ℕ, x (k + 1) = x k + α k • d k)
(h_alpha_pos : ∀ k : ℕ, 0 < α k)
(h_descent : ∀ k : ℕ, IsDescentDirectionAt f (x k) (d k))
(h_summable :
Summable
(fun k : ℕ ↦
(Real.cos (InnerProductGeometry.angle (d k) (-gradient f (x k)))) ^ (2 : ℕ))) :
0 < liminf (fun k : ℕ ↦ ‖gradient f (x k)‖) atTop
Definition 11.1.7
Lean contributors (project-level attribution): Chenyi Li, Wanli Ma, Zichen Wang.
Chapter11 Definition 11.1.7: a vector d is a feasible steepest descent direction at x when f is differentiable at x, d ≠ 0, d belongs to the closure of the Chapter 8 feasible direction set FD(x, X), and its normalized gradient pairing is minimal among all feasible directions in FD(x, X).
variable {E : Type*} [NormedAddCommGroup E] [InnerProductSpace ℝ E] [CompleteSpace E]
-- Domain sampling:
-- * primary domain: first-order constrained optimization in a real Hilbert space
-- * owner abstractions inspected:
-- `IsFeasibleDirectionAt`, `feasibleDirections`, `IsDescentDirectionAt`
-- * source/core/bridge triage:
-- `source-facing`: `IsFeasibleSteepestDescentDirection`
-- `core/canonical`: Chapter 8's `IsFeasibleDirectionAt` / `feasibleDirections`
-- `bridge/view`: `isFeasibleSteepestDescentDirection_iff`
-- * primitive data here: differentiability at `x`, nonvanishing of the chosen direction `d`,
-- closure membership in the Chapter 8 feasible-direction set, and the minimization inequality
-- * derived API here: feasibility of the base point and the unpacked conjunction theorem
class IsFeasibleSteepestDescentDirection
(f : E → ℝ) (x : E) (X : Set E) (d : E) : Prop where
ne : d ≠ 0
differentiableAt : DifferentiableAt ℝ f x
mem_closure : d ∈ closure (feasibleDirections x X)
minimal (d' : E) (hd' : d' ∈ feasibleDirections x X) :
normalizedGradientPairing f x d ≤ normalizedGradientPairing f x d'Definition 11.1.extra.1
— source only (outside the published documentation root) (Lean source)
Lean contributors (project-level attribution): Chenyi Li, Wanli Ma, Zichen Wang.
IsFeasibleDescentDirection f xk X d records that d is a feasible direction of X at xk and a strict descent direction for f at xk.
variable {E : Type*} [NormedAddCommGroup E] [InnerProductSpace ℝ E] [CompleteSpace E]
-- Domain sampling:
-- * primary domain: first-order constrained optimization in a real Hilbert space
-- * owner abstractions inspected:
-- `IsFeasibleDirectionAt`, `feasibleDirections`, `descentDirections`,
-- `IsDescentDirectionAt`
-- * source-facing layer here: the combined notion of a feasible descent direction
-- * primitive data: feasible-direction data from Chapter 8 and descent-direction data from
-- Chapter 1
-- * derived API: feasibility of the base point, differentiability, and the set-valued view
class IsFeasibleDescentDirection
(f : E → ℝ) (xk : E) (X : Set E) (d : E) : Prop
extends IsFeasibleDirectionAt X xk d where
isDescentDirectionAt : IsDescentDirectionAt f xk d
Definition 11.1.extra.2
— source only (outside the published documentation root) (Lean source)
Lean contributors (project-level attribution): Chenyi Li, Wanli Ma, Zichen Wang.
The accepted-step condition in Definition 11.1-extra-2: the trial point is feasible and satisfies the canonical Chapter 2 Armijo sufficient-decrease test along d at xk.
variable {E : Type*} [NormedAddCommGroup E] [InnerProductSpace ℝ E] [CompleteSpace E]
-- Layer triage:
-- * source-facing: `IsFeasiblePointArmijoStep`
-- * core/canonical reused from earlier project owners:
-- `IsFeasibleDescentDirection`, `armijoBacktrackingAccepts`
-- * bridge/view: `feasiblePointArmijoAccepts`, `isFeasiblePointArmijoStep_iff`
-- Domain sampling:
-- * primitive feasible-direction owner: `IsFeasibleDirectionAt`
-- * primitive descent-direction owner: `IsDescentDirectionAt`
-- * combined Chapter 11 owner: `IsFeasibleDescentDirection`
-- * canonical Chapter 2 Armijo owner: `armijoBacktrackingAccepts`
-- Semantic recall: Chapter 11 already owns the feasible-descent notion in
-- `Definition_11_1_extra_1`, while Chapter 2 already owns the Armijo sufficient-decrease
-- predicate `armijoBacktrackingAccepts`. This file keeps the Chapter 11 feasible-step predicate
-- only as the constrained bridge: feasibility of the trial point plus the canonical Chapter 2
-- Armijo test with gradient witness `gradient f xk`.
def feasiblePointArmijoAccepts
(f : E → ℝ) (X : Set E)
(c1 : ℝ) (xk d : E) (α : ℝ) : Prop :=
xk + α • d ∈ X ∧
armijoBacktrackingAccepts f c1 xk (gradient f xk : E) d α
Definition 11.1.extra.3
Lean contributors (project-level attribution): Chenyi Li, Wanli Ma, Zichen Wang.
The positive feasible step sizes along the ray x + α • d.
variable {E : Type*} [AddCommGroup E] [Module ℝ E]
-- Layer triage:
-- * source-facing: `FeasiblePointExactLineSearch`
-- * core/canonical reused from Chapter 8: `IsFeasibleDirectionAt`
-- * bridge/view: `feasiblePointExactLineSearch_iff`
-- Semantic recall: Chapter 8 already owns the small-segment feasible-direction predicate.
-- This file keeps the source-facing exact line-search notion and only adds the chosen positive
-- feasible step and the canonical `IsMinOn` minimizer condition.
def feasiblePointLineSearchDomain (x d : E) (X : Set E) : Set ℝ :=
{α | 0 < α ∧ x + α • d ∈ X}11.2 — Generalized Elimination
Algorithm 11.2.1
— source only (outside the published documentation root) (Lean source)
Lean contributors (project-level attribution): Chenyi Li, Wanli Ma, Zichen Wang.
Chapter11 Algorithm 11.2.1: a variable elimination method is modeled on the split space x = (x_B, x_N) with objective f, equality-constraint map c, feasible set X, elimination map φ, tolerance ε ≥ 0, initial feasible point x₁ ∈ X, active-stage predicate, iterate sequence x_k, Step 2 Jacobian blocks A_B and A_N, multiplier sequence λ_k, reduced gradient sequence g̃_k, Step 3 descent directions d̄_k, and Step 4 step sizes α_k. At each active stage k ≥ 1, the equality constraints are solved exactly by the elimination graph x_B = φ x_N, the current iterate lies on that graph, the block A_B(k) is nonsingular, Step 2 satisfies the source formulas (11.2.12) and (11.2.11), the recorded reduced gradient g̃_k agrees with the canonical gradient of the reduced objective, the method continues to stage k + 1 exactly when ε < ‖g̃_k‖, every continuing stage uses a feasible descent direction for the reduced objective on the reduced feasible set determined by X, the chosen step size satisfies the exact reduced-space line-search condition from (11.2.17), and the next iterate is x_(k + 1) = (φ ((x_N)_k + α_k • d̄_k), (x_N)_k + α_k • d̄_k).
variable {basicDim nonbasicDim : ℕ}
local notation "BasicPoint" => EuclideanSpace ℝ (Fin basicDim)
local notation "NonbasicPoint" => EuclideanSpace ℝ (Fin nonbasicDim)
local notation "Point" => BasicPoint × NonbasicPoint
-- Semantic recall: `lean_leansearch` surfaced only generic gradient infrastructure and no
-- canonical mathlib owner for the variable-elimination iteration from Section 11.2. Following
-- nearby Chapter 11 algorithm files, this item keeps an explicit iteration-data owner. The
-- primitive split-space owner is the elimination graph point `x_N ↦ (φ x_N, x_N)`, from which
-- the reduced feasible set, reduced objective, and Step 4 update are derived.
structure VariableEliminationMethod where
objective : Point → ℝ
constraint : Point → BasicPoint
feasibleSet : Set Point
φ : NonbasicPoint → BasicPoint
ε : ℝ
x1 : Point
active : ℕ → Prop
iterate : ℕ → Point
basicJacobian : ℕ → Matrix (Fin basicDim) (Fin basicDim) ℝ
nonbasicJacobian : ℕ → Matrix (Fin nonbasicDim) (Fin basicDim) ℝ
multiplier : ℕ → BasicPoint
reducedGradient : ℕ → NonbasicPoint
direction : ℕ → NonbasicPoint
stepSize : ℕ → ℝ
constraint_eq_zero_iff_eq_phi (xB : BasicPoint) (xN : NonbasicPoint) :
constraint (xB, xN) = 0 ↔ xB = φ xN
epsilon_nonneg : 0 ≤ ε
initialPoint_mem : x1 ∈ feasibleSet
iterate_one : iterate 1 = x1
active_one : active 1
feasible (k : ℕ) (hk : 1 ≤ k) (hactive : active k) :
iterate k ∈ feasibleSet
iterate_compatible (k : ℕ) (hk : 1 ≤ k) (hactive : active k) :
(iterate k).1 = φ (iterate k).2
basicJacobian_nonsingular (k : ℕ) (hk : 1 ≤ k) (hactive : active k) :
IsUnit (Matrix.det (basicJacobian k))
stepTwoSpec (k : ℕ) (hk : 1 ≤ k) (hactive : active k) :
variableEliminationStepTwoSpec
objective
constraint
(iterate k)
(basicJacobian k)
(nonbasicJacobian k)
(multiplier k)
(reducedGradient k)
reducedGradient_eq_gradient (k : ℕ) (hk : 1 ≤ k) (hactive : active k) :
reducedGradient k =
gradient (variableEliminationReducedObjective objective φ) (iterate k).2
active_succ_iff (k : ℕ) (hk : 1 ≤ k) :
active (k + 1) ↔ active k ∧ ε < ‖reducedGradient k‖
direction_spec (k : ℕ) (hk : 1 ≤ k) (hactive : active (k + 1)) :
IsFeasibleDescentDirection
(variableEliminationReducedObjective objective φ)
(iterate k).2
(variableEliminationReducedFeasibleSet feasibleSet φ)
(direction k)
stepSize_spec (k : ℕ) (hk : 1 ≤ k) (hactive : active (k + 1)) :
FeasiblePointExactLineSearch
(variableEliminationReducedObjective objective φ)
(variableEliminationReducedFeasibleSet feasibleSet φ)
(iterate k).2
(direction k)
(stepSize k)
iterate_succ (k : ℕ) (hk : 1 ≤ k) (hactive : active (k + 1)) :
iterate (k + 1) =
variableEliminationUpdate φ (iterate k).2 (direction k) (stepSize k)
Theorem 11.2.2
— source only (outside the published documentation root) (Lean source)
Lean contributors (project-level attribution): Chenyi Li, Wanli Ma, Zichen Wang.
Chapter11 Theorem 11.2.2: assume that the objective f(x) and constraint map c(x) of a run of Algorithm 11.2.1 are twice continuously differentiable. If the inverse of ((∇ c(x)ᵀ)ᵀ) * ∇ c(x)ᵀ is uniformly bounded on the feasible set X, then Algorithm 11.2.1 with exact line searches, the divergence condition (11.2.24), and an infinite-run hypothesis that every stage k ≥ 1 remains active ensures that either the Step 2 stationarity residual ∇ f(x_k) - ∇ c(x_k)ᵀ λ_k built from the recorded Step 2 multiplier λ_k = method.multiplier k has liminf norm equal to 0, or the objective values satisfy f(x_k) → -∞.
open Filter
open scoped BigOperators Matrix.Norms.Frobenius
variable {basicDim nonbasicDim : ℕ}
local notation "BasicPoint" => EuclideanSpace ℝ (Fin basicDim)
local notation "NonbasicPoint" => EuclideanSpace ℝ (Fin nonbasicDim)
local notation "Point" => BasicPoint × NonbasicPoint
namespace VariableEliminationMethod
local notation "Method" => @_root_.VariableEliminationMethod basicDim nonbasicDim
theorem liminf_stationarityResidualNorm_eq_zero_or_objective_tendsto_atBot
(method : Method)
(hC2f : ContDiff ℝ 2 method.objective)
(hC2c : ContDiff ℝ 2 method.constraint)
(hBoundedInverse : method.uniformlyBoundedConstraintGramInverse)
(hActive : ∀ k, 1 ≤ k → method.active k)
(hCosine : method.reducedDirectionCosineSqPartialSumsDiverge) :
liminf (fun k : ℕ ↦ ‖method.stationarityResidualAt k‖) atTop = 0 ∨
Tendsto (fun k : ℕ ↦ method.objective (method.iterate k)) atTop atBot
Algorithm 11.2.3
— source only (outside the published documentation root) (Lean source)
Lean contributors (project-level attribution): Chenyi Li, Wanli Ma, Zichen Wang.
Chapter11 Algorithm 11.2.3: the general elimination method is the source-facing recursive algorithm built from a fixed ambient objective f, a fixed equality-constraint map c, a feasible set X, a tolerance ε ≥ 0, initial Step 2 data (M₁, (w₁)_N, λ₁), and the recursive families M_k, (w_k)_N, λ_k, d̄_k, and α_k. The current iterate x_k = S_B φ̄_k ((w_k)_N) + S_N (w_k)_N and the current reduced gradient ḡ_k are derived. Continuing stages are governed by the source stopping test ε < ‖ḡ_k‖, each continuing stage uses a feasible descent direction for the reduced objective on the reduced feasible set determined by M_k, the chosen step size satisfies the canonical exact reduced-space line search on that reduced-space bridge, and the next stage is required to realize the Step 4 trial point S_B φ̄_k ((w_k)_N + α_k d̄_k) + S_N ((w_k)_N + α_k d̄_k).
open GeneralizedEliminationMethod
variable {n m : ℕ}
local notation "Point" => EuclideanSpace ℝ (Fin n)
local notation "BasicPoint" => EuclideanSpace ℝ (Fin m)
local notation "NonbasicPoint" => EuclideanSpace ℝ (Fin (n - m))
local notation "ConstraintPoint" => EuclideanSpace ℝ (Fin m)
local notation "Elimination" => @_root_.GeneralizedEliminationMethod n m
-- Domain sampling:
-- * source-facing owner: `GeneralEliminationMethod`, whose primitive recursive families are the
-- stagewise generalized-elimination owners `M_k`, nonbasic variables `(w_k)_N`, multipliers
-- `λ_k`, directions `d̄_k`, and step sizes `α_k`.
-- * core/canonical owners: `GeneralizedEliminationMethod` for the elimination geometry and
-- `FeasiblePointExactLineSearch` for the reduced-space exact line search.
-- * bridge layer: `GeneralizedEliminationMethod.graphPoint` together with the Chapter 11
-- variable-elimination owner `variableEliminationReducedFeasibleSet`.
structure GeneralEliminationMethod where
objective : Point → ℝ
constraint : Point → ConstraintPoint
feasibleSet : Set Point
tolerance : ℝ
initialElimination : Elimination
initialReducedVariable : NonbasicPoint
initialMultiplier : ConstraintPoint
active : ℕ → Prop
elimination : ℕ → Elimination
reducedVariable : ℕ → NonbasicPoint
multiplier : ℕ → ConstraintPoint
direction : ℕ → NonbasicPoint
stepSize : ℕ → ℝ
tolerance_nonneg : 0 ≤ tolerance
active_one : active 1
elimination_one : elimination 1 = initialElimination
reducedVariable_one : reducedVariable 1 = initialReducedVariable
multiplier_one : multiplier 1 = initialMultiplier
/-- Every feasible point `x ∈ X` satisfies the equality constraint equation `c x = 0`. -/
feasibleSet_constraint_eq_zero :
∀ {x : Point}, x ∈ feasibleSet → constraint x = 0
elimination_constraint :
∀ k, 1 ≤ k → active k → (elimination k).constraint = constraint
stage_spec :
∀ k, 1 ≤ k → active k →
GeneralEliminationStageValid
objective
feasibleSet
(elimination k)
(reducedVariable k)
(multiplier k)
active_succ_iff (k : ℕ) (hk : 1 ≤ k) :
active (k + 1) ↔
active k ∧
tolerance <
‖(elimination k).reducedGradient objective (reducedVariable k)‖
direction_spec :
∀ k, 1 ≤ k → active (k + 1) →
IsFeasibleDescentDirection
((elimination k).reducedObjective objective)
(reducedVariable k)
((elimination k).reducedFeasibleSet feasibleSet)
(direction k)
stepSize_spec :
∀ k, 1 ≤ k → active (k + 1) →
FeasiblePointExactLineSearch
((elimination k).reducedObjective objective)
((elimination k).reducedFeasibleSet feasibleSet)
(reducedVariable k)
(direction k)
(stepSize k)
iterate_succ_eq_trialPoint_spec :
∀ k, 1 ≤ k → active (k + 1) →
(elimination (k + 1)).graphPoint (reducedVariable (k + 1)) =
(elimination k).graphPoint
(reducedVariable k + stepSize k • direction k)
Definition 11.2.extra.1
— source only (outside the published documentation root) (Lean source)
Lean contributors (project-level attribution): Chenyi Li, Wanli Ma, Zichen Wang.
The x_B-partial gradient of f.
variable {nB nN : ℕ}
local notation "PointB" => EuclideanSpace ℝ (Fin nB)
local notation "PointN" => EuclideanSpace ℝ (Fin nN)
-- Domain sampling:
-- * source-facing layer: the reduced-space Lagrangian and reduced-gradient formulas in split
-- coordinates.
-- * core/canonical layer: mathlib's `gradient`, `fderiv`, `LinearMap.toMatrix`, and
-- `Matrix.toEuclideanLin`.
-- * bridge/view layer: the partial gradients and Jacobian blocks on the basic/nonbasic split.
abbrev partialGradientB
(f : PointB → PointN → ℝ) (xB : PointB) (xN : PointN) : PointB :=
gradient (fun yB : PointB ↦ f yB xN) xB
Definition 11.2.extra.2
— source only (outside the published documentation root) (Lean source)
Lean contributors (project-level attribution): Chenyi Li, Wanli Ma, Zichen Wang.
The standard Euclidean basis on the ambient point space.
variable {n m : ℕ}
local notation "Point" => EuclideanSpace ℝ (Fin n)
local notation "BasicPoint" => EuclideanSpace ℝ (Fin m)
local notation "NonbasicPoint" => EuclideanSpace ℝ (Fin (n - m))
local notation "ConstraintPoint" => EuclideanSpace ℝ (Fin m)
abbrev pointBasis :=
(EuclideanSpace.basisFun (Fin n) ℝ).toBasis
11.3 — Generalized Reduced Gradient Method
Algorithm 11.3.1
— source only (outside the published documentation root) (Lean source)
Lean contributors (project-level attribution): Chenyi Li, Wanli Ma, Zichen Wang.
Algorithm 11.3.1 is terminated at stage k when the Step 3 stopping test ‖g̃_k‖ ≤ ε holds at x_k.
open Filter
open scoped Matrix.Norms.Frobenius
variable {basicDim nonbasicDim : ℕ}
local notation "BasicPoint" => EuclideanSpace ℝ (Fin basicDim)
local notation "NonbasicPoint" => EuclideanSpace ℝ (Fin nonbasicDim)
local notation "Point" => BasicPoint × NonbasicPoint
-- Semantic recall: `lean_leansearch` surfaced no reusable mathlib owner for the generalized
-- reduced-gradient method. Following the neighboring Chapter 11 algorithm files, this item is
-- formalized as explicit split-coordinate iteration data with concrete Step 4 and Step 5 updates.
namespace GeneralizedReducedGradientMethod
local notation "Method" =>
@_root_.GeneralizedReducedGradientMethod basicDim nonbasicDim
def terminatedAt (method : Method) (k : ℕ) : Prop :=
‖method.reducedGradient k‖ ≤ method.ε
Theorem 11.3.2
— source only (outside the published documentation root) (Lean source)
Lean contributors (project-level attribution): Chenyi Li, Wanli Ma, Zichen Wang.
Chapter11 Theorem 11.3.2: assume that the objective f(x) and constraint map c(x) of a generalized reduced-gradient run equipped with the modified Step 7 sufficient-decrease search data on equality-feasible iterates are twice continuously differentiable, that the inherited Step 2 inverse-block bound of GeneralizedReducedGradientRun.uniformlyBoundedBasicJacobianInverse holds, and that the Step 3 initial steplengths α_k⁽⁰⁾ stay positive and have reciprocals (α_k⁽⁰⁾)⁻¹ uniformly bounded above on continuing stages, and that the modified Step 7 rule (11.3.5) admits one positive stage-uniform acceptance threshold for sufficiently small products αₖ,ₗ * ‖g̃ₖ‖. This source-facing method owner keeps the Step 6 backtracking data tying the accepted steplength to α_k⁽⁰⁾, and it records the replacement of Step 7 by (11.3.5) at the search level rather than only as an extra inequality on the already accepted trial point. If method.ε = 0 and the algorithm does not terminate, then either the reduced-gradient norms satisfy ‖g̃_k‖ → 0 or the objective values satisfy f(x_k) → -∞.
open Filter
open scoped Matrix.Norms.Frobenius
variable {basicDim nonbasicDim : ℕ}
variable {β : ℝ}
namespace GeneralizedReducedGradientMethod
theorem tendsto_reducedGradientNorm_zero_or_objective_tendsto_atBot
(β : ℝ)
(method : @_root_.GeneralizedReducedGradientSufficientDecreaseMethod basicDim nonbasicDim β)
(hC2f : ContDiff ℝ 2 method.objective)
(hC2c : ContDiff ℝ 2 method.constraint)
(hBoundedABInv :
GeneralizedReducedGradientRun.uniformlyBoundedBasicJacobianInverse
(GeneralizedReducedGradientSufficientDecreaseMethod.toRun method))
(hBoundedAlpha0Inv :
∃ C ∈ Set.Ici (0 : ℝ),
∀ k, 1 ≤ k → method.active (k + 1) → ‖(method.initialStepSize k)⁻¹‖ ≤ C)
(hUniformAcceptanceThreshold : method.HasUniformAcceptanceThreshold)
(hβ : β ∈ Set.Ioo (0 : ℝ) 1)
(hε : method.ε = 0)
(hNonterminating : ∀ k, 1 ≤ k → method.active k) :
Tendsto (fun k : ℕ ↦ ‖method.reducedGradient k‖) atTop (nhds (0 : ℝ)) ∨
Tendsto (fun k : ℕ ↦ method.objective (method.iterate k)) atTop atBot
Theorem 11.3.3
— source only (outside the published documentation root) (Lean source)
Lean contributors (project-level attribution): Chenyi Li, Wanli Ma, Zichen Wang.
Chapter11 Theorem 11.3.3: assume that f(x) and c(x) are twice continuously differentiable for a generalized reduced-gradient accepted-step run run : GeneralizedReducedGradientAcceptedStepRun, that the inherited Step 2 inverse blocks A_B(x_k)⁻¹ are uniformly bounded above on active stages, and that the Step 3 initial steplengths α_k⁽⁰⁾ satisfy (11.3.6) and (11.3.7). This canonical accepted-step owner keeps the Step 7 decrease and iterate-update data needed to connect the Step 3 steplength hypotheses to the actual evolution of x_k. If run.ε = 0 and the algorithm does not terminate, then either the reduced-gradient norms satisfy ‖g̃_k‖ → 0, or the objective values satisfy f(x_k) → -∞.
open Filter
open scoped Matrix.Norms.Frobenius
variable {basicDim nonbasicDim : ℕ}
local notation "AcceptedStepRun" =>
@_root_.GeneralizedReducedGradientAcceptedStepRun basicDim nonbasicDim
namespace GeneralizedReducedGradientAcceptedStepRun
theorem reducedGradientNorm_tendsto_zero_or_objective_tendsto_atBot_of_step3Hypotheses
(run : AcceptedStepRun)
(hC2f : ContDiff ℝ 2 run.objective)
(hC2c : ContDiff ℝ 2 run.constraint)
(hBoundedInverse :
run.toGeneralizedReducedGradientRun.uniformlyBoundedBasicJacobianInverse)
(h1136 :
run.toGeneralizedReducedGradientRun.initialStepSizeLowerBoundByReducedGradient)
(h1137 :
run.toGeneralizedReducedGradientRun.initialStepSizeOverReducedGradientNormPartialSumsDiverge)
(hε : run.ε = 0)
(hNonterminating : ∀ k, 1 ≤ k → run.active k) :
Tendsto (fun k : ℕ ↦ ‖run.reducedGradient k‖) atTop (nhds (0 : ℝ)) ∨
Tendsto (fun k : ℕ ↦ run.objective (run.iterate k)) atTop atBot
11.4 — Projected Gradient Method
Algorithm 11.4.1
Lean contributors (project-level attribution): Chenyi Li, Wanli Ma, Zichen Wang.
Chapter11 Algorithm 11.4.1: a projected gradient method on ℝ^ambientDim with constraint map C : ℝ^ambientDim → ℝ^constraintDim records a feasible initial point x₁ ∈ X, tolerances ε ≥ 0 and ε̄ > 0, a positive integer bound N for the Step-4 correction loop, and for each active stage k ≥ 1 concrete QR data Y_k, Z_k, R_k, reduced gradient ḡ_k, search direction d_k, initial trial step α_k^(0), dyadic backtracking count, accepted step size α_k, accepted correction count, and accepted trial point y_k. The feasible set is the zero set of constraint, the QR data satisfy ∇ C(x_k)ᵀ = Y_k R_k, R_k is upper triangular, and [Y_k Z_k] forms an orthogonal block decomposition via orthonormality, cross-orthogonality, and the identity decomposition Y_k Y_kᵀ + Z_k Z_kᵀ = 1; active stages carry explicit DifferentiableAt hypotheses for objective and constraint at x_k; Step 2 computes ḡ_k = Z_kᵀ ∇ f(x_k) and, on continuing stages, d_k = -Z_k ḡ_k; the active stages satisfy active (k + 1) ↔ active k ∧ ε < ‖ḡ_k‖; Step 4 uses the explicit nonsingularity of R_k for the correction map, and accepts y_k after a positive number of explicit correction steps bounded by N, with failure of all earlier correction iterates; and every earlier dyadic backtracking exponent fails to yield any accepted Step-4 outcome, with x_(k + 1) = y_k.
variable {ambientDim constraintDim tangentDim : ℕ}
local notation "Point" => EuclideanSpace ℝ (Fin ambientDim)
local notation "ConstraintPoint" => EuclideanSpace ℝ (Fin constraintDim)
local notation "TangentPoint" => EuclideanSpace ℝ (Fin tangentDim)
-- Semantic recall: `lean_leansearch` surfaced only generic orthogonal-projection and
-- decomposition APIs, not a canonical projected-gradient owner with the textbook QR and
-- correction-loop data. Following nearby Chapter 11 algorithm files, this item is formalized as
-- explicit stagewise Euclidean, matrix, reduced-gradient, and backtracking data.
structure ProjectedGradientMethod (ambientDim constraintDim tangentDim : ℕ) where
objective : EuclideanSpace ℝ (Fin ambientDim) → ℝ
constraint : EuclideanSpace ℝ (Fin ambientDim) → EuclideanSpace ℝ (Fin constraintDim)
tolerance : ℝ
correctionTolerance : ℝ
maxCorrectionSteps : ℕ
initialPoint : EuclideanSpace ℝ (Fin ambientDim)
active : ℕ → Prop
iterate : ℕ → EuclideanSpace ℝ (Fin ambientDim)
yFactor : ℕ → Matrix (Fin ambientDim) (Fin constraintDim) ℝ
zFactor : ℕ → Matrix (Fin ambientDim) (Fin tangentDim) ℝ
rFactor : ℕ → Matrix (Fin constraintDim) (Fin constraintDim) ℝ
reducedGradient : ℕ → EuclideanSpace ℝ (Fin tangentDim)
direction : ℕ → EuclideanSpace ℝ (Fin ambientDim)
initialStep : ℕ → ℝ
backtrackingCount : ℕ → ℕ
stepSize : ℕ → ℝ
correctionCount : ℕ → ℕ
acceptedTrial : ℕ → EuclideanSpace ℝ (Fin ambientDim)
qrBlockSize : constraintDim + tangentDim = ambientDim
tolerance_nonneg : 0 ≤ tolerance
correctionTolerance_pos : 0 < correctionTolerance
maxCorrectionSteps_pos : 0 < maxCorrectionSteps
initialPoint_mem : initialPoint ∈ projectedGradientFeasibleSet constraint
active_one : active 1
iterate_one : iterate 1 = initialPoint
active_succ_iff :
∀ k, 1 ≤ k →
(active (k + 1) ↔ active k ∧ tolerance < ‖reducedGradient k‖)
objectiveDifferentiableAt :
∀ k, 1 ≤ k → active k → DifferentiableAt ℝ objective (iterate k)
constraintDifferentiableAt :
∀ k, 1 ≤ k → active k → DifferentiableAt ℝ constraint (iterate k)
qrFactorization :
∀ k, 1 ≤ k → active k →
constraintJacobianTranspose constraint (iterate k) =
yFactor k * rFactor k
rFactor_upperTriangular :
∀ k, 1 ≤ k → active k →
(rFactor k).BlockTriangular id
yFactor_orthonormal :
∀ k, 1 ≤ k → active k →
(yFactor k).transpose * yFactor k = 1
yz_orthogonal :
∀ k, 1 ≤ k → active k →
(yFactor k).transpose * zFactor k = 0
zFactor_orthonormal :
∀ k, 1 ≤ k → active k →
(zFactor k).transpose * zFactor k = 1
orthogonalDecomposition :
∀ k, 1 ≤ k → active k →
yFactor k * (yFactor k).transpose +
zFactor k * (zFactor k).transpose =
1
rFactor_nonsingular :
∀ k, 1 ≤ k → active k →
IsUnit (Matrix.det (rFactor k))
reducedGradient_eq :
∀ k, 1 ≤ k → active k →
reducedGradient k =
projectedGradientReducedGradient
(zFactor k)
(gradient objective (iterate k))
direction_eq :
∀ k, 1 ≤ k → active (k + 1) →
direction k =
projectedGradientDirection (zFactor k) (reducedGradient k)
initialStep_pos :
∀ k, 1 ≤ k → active (k + 1) → 0 < initialStep k
stepSize_eq :
∀ k, 1 ≤ k → active (k + 1) →
stepSize k = initialStep k / (2 : ℝ) ^ backtrackingCount k
earlierBacktrackingRejected :
∀ k, 1 ≤ k → active k → active (k + 1) →
∀ b, b < backtrackingCount k →
∀ i, i ≤ maxCorrectionSteps →
∀ y,
¬ IsProjectedGradientAcceptedTrial
objective
constraint
correctionTolerance
maxCorrectionSteps
(yFactor k)
(rFactor k)
(iterate k)
(direction k)
(initialStep k / (2 : ℝ) ^ b)
i
y
acceptedTrial_spec :
∀ k, 1 ≤ k → active k → active (k + 1) →
IsProjectedGradientAcceptedTrial
objective
constraint
correctionTolerance
maxCorrectionSteps
(yFactor k)
(rFactor k)
(iterate k)
(direction k)
(stepSize k)
(correctionCount k)
(acceptedTrial k)
iterate_succ :
∀ k, 1 ≤ k → active (k + 1) →
iterate (k + 1) = acceptedTrial k11.5 — Linearly Constrained Problems
Algorithm 11.5.1
Lean contributors (project-level attribution): Chenyi Li, Wanli Ma, Zichen Wang.
Chapter11 Algorithm 11.5.1: the null-space projected-gradient method for the linearly constrained problem Aᵀ x = b starts from a feasible point x₁, fixes a matrix Z satisfying Aᵀ Z = 0 and rank Z = n - m under the dimension side condition m ≤ n, assumes that the objective has the genuine gradient ∇f(x_k) at each stage k ≥ 1, sets d_k = -Z Zᵀ ∇f(x_k), stops exactly when ‖d_k‖ ≤ ε, and otherwise updates x_(k + 1) = x_k + α_k • d_k with a positive line-search step size α_k.
variable {n m : ℕ}
local notation "Point" => EuclideanSpace ℝ (Fin n)
-- Semantic recall hits verified for this item: `linearlyConstrainedFeasibleSet` is already the
-- Chapter 11 owner for the equality-constrained feasible set in `Algorithm_11_5_2`, while
-- `projectedGradientReducedGradient` and `projectedGradientDirection` in
-- `Algorithm_11_4_1` already own the null-space projected-gradient construction
-- `-Z (Zᵀ ∇f(x))`. The stagewise Algorithm 11.5.1 data therefore stays explicit here, but the
-- duplicate local direction owner is removed.
structure NullSpaceProjectedGradientMethod (n m : ℕ) where
objective : EuclideanSpace ℝ (Fin n) → ℝ
constraintMatrix : Matrix (Fin n) (Fin m) ℝ
constraintTarget : EuclideanSpace ℝ (Fin m)
nullMatrix : Matrix (Fin n) (Fin (n - m)) ℝ
tolerance : ℝ
initialPoint : EuclideanSpace ℝ (Fin n)
active : ℕ → Prop
iterate : ℕ → EuclideanSpace ℝ (Fin n)
stepSize : ℕ → ℝ
hmn : m ≤ n
tolerance_nonneg : 0 ≤ tolerance
initialPoint_mem : initialPoint ∈ linearlyConstrainedFeasibleSet constraintMatrix constraintTarget
nullMatrix_spec : constraintMatrix.transpose * nullMatrix = 0 ∧ Matrix.rank nullMatrix = n - m
iterate_one : iterate 1 = initialPoint
objective_hasGradientAt (k : ℕ) (_ : 1 ≤ k) :
HasGradientAt objective (gradient objective (iterate k)) (iterate k)
feasible (k : ℕ) (_ : 1 ≤ k) :
active k → iterate k ∈ linearlyConstrainedFeasibleSet constraintMatrix constraintTarget
active_iff (k : ℕ) (_ : 1 ≤ k) :
active k ↔
tolerance <
‖projectedGradientDirection nullMatrix
(projectedGradientReducedGradient nullMatrix (gradient objective (iterate k)))‖
stepSize_pos (k : ℕ) (_ : 1 ≤ k) : active k → 0 < stepSize k
iterate_succ (k : ℕ) (_ : 1 ≤ k) :
active k →
iterate (k + 1) =
iterate k + stepSize k •
projectedGradientDirection nullMatrix
(projectedGradientReducedGradient nullMatrix (gradient objective (iterate k)))Algorithm 11.5.2
Lean contributors (project-level attribution): Chenyi Li, Wanli Ma, Zichen Wang.
Chapter11 Algorithm 11.5.2: for the linear equality-constrained feasible set linearlyConstrainedFeasibleSet constraintMatrix constraintTarget, a feasible initial point x₁ ∈ linearlyConstrainedFeasibleSet constraintMatrix constraintTarget, parameters μ ∈ (0, 1) and γ > 0, stagewise trial paths x_k(α) based at the current iterate via x_k(0) = x_k, and a stagewise acceptance predicate encoding condition (11.5.13) as a condition on μ, the trial step α, and the trial point x_k(α), the algorithm fixes α₀ = 1. At each stage k ≥ 1, Step 2 forms the trial seed max {2 * α_(k-1), γ}, Step 3 repeatedly divides it by 4 until (11.5.13) holds, and Step 4 sets x_(k + 1) = x_k(α_k).
open Matrix
variable {ambientDim constraintDim : ℕ}
local notation "Point" => EuclideanSpace ℝ (Fin ambientDim)
local notation "ConstraintPoint" => EuclideanSpace ℝ (Fin constraintDim)
local notation "ConstraintMatrix" => Matrix (Fin ambientDim) (Fin constraintDim) ℝ
-- Semantic recall: `lean_leansearch` did not surface a canonical mathlib owner for this
-- quartering line-search loop. Following nearby Chapter 11 algorithm files, the public surface
-- keeps the stagewise trial map `x_k(α)`, the Step `(11.5.13)` acceptance predicate, and the
-- accepted quartering count explicit.
structure LinearlyConstrainedQuarteringSearchMethod (ambientDim constraintDim : ℕ) where
constraintMatrix : Matrix (Fin ambientDim) (Fin constraintDim) ℝ
constraintTarget : EuclideanSpace ℝ (Fin constraintDim)
μ : ℝ
γ : ℝ
initialPoint : EuclideanSpace ℝ (Fin ambientDim)
trialPoint : ℕ → ℝ → EuclideanSpace ℝ (Fin ambientDim)
accepts : ℝ → ℕ → ℝ → EuclideanSpace ℝ (Fin ambientDim) → Prop
iterate : ℕ → EuclideanSpace ℝ (Fin ambientDim)
stepSize : ℕ → ℝ
quarteringCount : ℕ → ℕ
mu_mem : μ ∈ Set.Ioo (0 : ℝ) 1
gamma_pos : 0 < γ
initialPoint_mem :
initialPoint ∈ linearlyConstrainedFeasibleSet constraintMatrix constraintTarget
iterate_one : iterate 1 = initialPoint
trialPoint_zero :
∀ k, 1 ≤ k → trialPoint k 0 = iterate k
step_zero : stepSize 0 = 1
step_spec :
∀ k, 1 ≤ k →
IsLinearlyConstrainedQuarteringAcceptedStep
(fun α ↦ accepts μ k α (trialPoint k α))
γ
(stepSize (k - 1))
(stepSize k)
(quarteringCount k)
iterate_succ :
∀ k, 1 ≤ k →
iterate (k + 1) = trialPoint k (stepSize k)Lemma 11.5.3
— source only (outside the published documentation root) (Lean source)
Lean contributors (project-level attribution): Chenyi Li, Wanli Ma, Zichen Wang.
Chapter11 Lemma 11.5.3: assume f is continuously differentiable and bounded below on the feasible set method.feasibleSet. If gradient f is uniformly continuous on that feasible set, and the stagewise trial path of the Algorithm 11.5.2 owner method is the projected path IsLinearlyConstrainedProjectedTrialPath f method, and the Step-3 predicate method.acceptedAt k α is exactly the source acceptance test linearlyConstrainedAcceptanceCondition11513 f method k α, then the iterates generated by Algorithm 11.5.2 satisfy ‖x_(k + 1) - x_k‖ / α_k ⟶ 0 as k ⟶ ∞.
open Filter
variable {n m : ℕ}
local notation "Point" => EuclideanSpace ℝ (Fin n)
local notation "ConstraintPoint" => EuclideanSpace ℝ (Fin m)
local notation "ConstraintMatrix" => Matrix (Fin n) (Fin m) ℝ
-- Domain sampling for this item:
-- * source-facing owner for arbitrary complete convex-set projection in this chapter:
-- `nearestPointProjection`.
-- * source-facing owners for the constraint geometry and quartering search method are reused from
-- `Algorithm_11_5_2`.
-- * canonical feasible-set completeness/convexity owners are reused from `Lemma_11_5_4`.
-- * bridge/view layer in this file: the projected trial path and acceptance predicate obtained by
-- specializing `nearestPointProjection` to the feasible set recorded by that method.
-- Primitive data here are the canonical feasible-set owner and the quartering-search method; the
-- projection point itself is derived from the chapter owner instead of being redefined locally.
theorem linearlyConstrainedQuarteringSearchMethod_tendsto_norm_sub_div_stepSize_to_zero
(f : Point → ℝ)
(method : LinearlyConstrainedQuarteringSearchMethod n m)
(h_contDiffOn : ContDiffOn ℝ 1 f method.feasibleSet)
(h_bddBelow : BddBelow (f '' method.feasibleSet))
(h_uniformContinuousOn : UniformContinuousOn (gradient f) method.feasibleSet)
(h_projectedTrialPath : IsLinearlyConstrainedProjectedTrialPath f method)
(h_accepts_eq_11513 :
∀ k α, 1 ≤ k →
method.acceptedAt k α ↔
linearlyConstrainedAcceptanceCondition11513 f method k α) :
Tendsto
(fun k : ℕ ↦ ‖method.iterate (k + 1) - method.iterate k‖ / method.stepSize k)
atTop
(nhds 0)
Lemma 11.5.4
— source only (outside the published documentation root) (Lean source)
Lean contributors (project-level attribution): Chenyi Li, Wanli Ma, Zichen Wang.
Chapter11 Lemma 11.5.4: for a feasible point xStar of a linearly equality-constrained problem with problem.objective differentiable at xStar, there exists a multiplier vector such that ∇ f(xStar) = A λ if and only if there exists δBar > 0 such that the nearest-point projection of xStar - α • ∇ f(xStar) onto the feasible set of problem is again xStar for every α ∈ [0, δBar].
open Matrix
variable {n m : ℕ}
local notation "Point" => EuclideanSpace ℝ (Fin n)
local notation "ConstraintPoint" => EuclideanSpace ℝ (Fin m)
local notation "Multiplier" => EuclideanSpace ℝ (Fin m)
local notation "ConstraintMatrix" => Matrix (Fin n) (Fin m) ℝ
-- Domain sampling for this item:
-- * source-facing layer: the Chapter 11 KKT characterization for a linear equality-constrained
-- problem.
-- * core/canonical owners already in this chapter: `linearlyConstrainedFeasibleSet` and
-- `nearestPointProjection`.
-- * bridge/view layer here: the equality-only Chapter 8 constrained-optimization view of the
-- Chapter 11 problem owner.
-- * derived API here: the problem owner together with its feasible-set owner, the source-facing
-- multiplier characterization, and the bridge to `ConstrainedOptimizationProblem.IsKKTPoint`;
-- the projection side is stated directly with the canonical `nearestPointProjection`.
namespace LinearEqualityConstrainedProblem
theorem exists_multiplier_iff_projection_fixedPoint
(problem : LinearEqualityConstrainedProblem n m) (xStar : Point)
(hxStar : xStar ∈ problem)
(hDiff : DifferentiableAt ℝ problem.objective xStar) :
(∃ multiplier : Multiplier,
gradient problem.objective xStar = problem.constraintMatrix.mulVec multiplier) ↔
∃ δBar : ℝ,
0 < δBar ∧
∀ α ∈ Set.Icc (0 : ℝ) δBar,
nearestPointProjection
problem.feasibleSet
⟨xStar, hxStar⟩
problem.isComplete_feasibleSet
problem.convex_feasibleSet
(xStar - α • gradient problem.objective xStar) = xStar
Theorem 11.5.5
— source only (outside the published documentation root) (Lean source)
Lean contributors (project-level attribution): Chenyi Li, Wanli Ma, Zichen Wang.
Chapter11 Theorem 11.5.5: assume f is continuously differentiable on the feasible set method.feasibleSet in the ambient sense, namely f is differentiable at each feasible point and the ambient gradient field gradient f is continuous on method.feasibleSet. If method is the Algorithm 11.5.2 sequence for the projected trial path and the Step (11.5.13) acceptance test determined by f, then any accumulation point of the iterate sequence {x_k}, encoded by a strictly monotone subsequence of the source stages k ≥ 1 converging to xStar, admits a multiplier vector making xStar a Chapter 8 KKT point of the equality-only constrained-problem bridge attached to f and the constraint system of method.
open Filter
variable {n m : ℕ}
local notation "Point" => EuclideanSpace ℝ (Fin n)
local notation "Multiplier" => EuclideanSpace ℝ (Fin m)
-- Domain sampling:
-- * source-facing layer: the accumulation-point KKT conclusion for Algorithm 11.5.2.
-- * current-chapter owners reused here:
-- `LinearlyConstrainedQuarteringSearchMethod`,
-- `IsLinearlyConstrainedProjectedTrialPath`,
-- `linearlyConstrainedAcceptanceCondition11513`, and
-- `LinearEqualityConstrainedProblem`.
-- * bridge/view layer reused here from `Theorem_11_5_5.Comparison`: the problem attached to a
-- method and objective, together with the Chapter 8 KKT view already exported by
-- `LinearEqualityConstrainedProblem`.
theorem linearlyConstrainedQuarteringSearchMethod_accumulationPoint_isKKTPoint
(f : Point → ℝ)
(method : LinearlyConstrainedQuarteringSearchMethod n m)
(h_diffAt_feasible : ∀ x ∈ method.feasibleSet, DifferentiableAt ℝ f x)
(h_gradientContinuousOn : ContinuousOn (gradient f) method.feasibleSet)
(h_projectedTrialPath : IsLinearlyConstrainedProjectedTrialPath f method)
(h_accepts_eq_11513 :
∀ k α, 1 ≤ k →
method.acceptedAt k α ↔
linearlyConstrainedAcceptanceCondition11513 f method k α)
{xStar : Point} {φ : ℕ → ℕ}
(hφ : StrictMono φ)
(hxStar : Tendsto (fun k : ℕ ↦ method.iterate (φ k + 1)) atTop (nhds xStar)) :
∃ multiplier : Multiplier,
(method.toLinearEqualityConstrainedProblem f).toConstrainedOptimizationProblem.IsKKTPoint
xStar.ofLp multiplier.ofLp
Definition 11.5.extra.1
Lean contributors (project-level attribution): Chenyi Li, Wanli Ma, Zichen Wang.
Chapter11 Definition 11.5-extra-1: the nearest-point projection map x ↦ P(x) = arg min {‖z - x‖ | z ∈ X} on a nonempty complete convex set X.
variable {F : Type*} [NormedAddCommGroup F] [InnerProductSpace ℝ F]
-- Primary domain: nearest-point projections onto complete convex sets in real inner product
-- spaces.
-- Owner sampling:
-- * `exists_norm_eq_iInf_of_complete_convex` in mathlib supplies the primitive existence theorem.
-- * `norm_eq_iInf_iff_real_inner_le_zero` in mathlib is the canonical minimizer characterization.
-- * Chapter 1 already establishes uniqueness for this same minimizer notion, so the public owner
-- here keeps only the primitive data `X`, `X.Nonempty`, `IsComplete X`, and `Convex ℝ X`.
-- Membership and distance-minimizing properties are derived API.
def nearestPointProjection
(X : Set F) (hX_nonempty : X.Nonempty) (hX_complete : IsComplete X)
(hX_convex : Convex ℝ X) :
F → F :=
fun x ↦
Classical.choose <|
exists_norm_eq_iInf_of_complete_convex hX_nonempty hX_complete hX_convex xSupporting modules
These source modules support the indexed items and are listed separately so the chapter inventory remains complete.
-
Theorem_11_5_5/Comparison.lean(Documentation unavailable) (Lean source)
Lean contributors (project-level attribution): Chenyi Li, Wanli Ma, Zichen Wang.