Chapter 02 — Line Search

Proofs omitted. Hover over highlighted terms to see their Lean types.

Exercise 2.1

Lean contributors (project-level attribution): Chenyi Li, Wanli Ma, Zichen Wang.

Source header · Attribution source

Chapter02 Exercise 2.1: the objective x ↦ (Real.sin x)^6 * Real.tan (1 - x) * Real.exp (30 * x) attains its maximum on Icc (0 : ℝ) 1.

open Set theorem chapter02Exercise21_exists_isMaxOn_unitInterval : ∃ x ∈ Icc (0 : ℝ) 1, IsMaxOn chapter02Exercise21Objective (Icc (0 : ℝ) 1) x

Exercise 2.2

Lean contributors (project-level attribution): Chenyi Li, Wanli Ma, Zichen Wang.

Source header · Attribution source

Chapter02 Exercise 2.2 Recall-only entry: the source asks for the Fibonacci algorithm and its MATLAB/FORTRAN/C implementation. In Lean, the canonical specification is Nat.fib, the executable algorithm is Nat.fastFib, and Nat.fastFib_eq identifies the program with the specification.

#check Nat.fib

Exercise 2.3

Lean contributors (project-level attribution): Chenyi Li, Wanli Ma, Zichen Wang.

Source header · Attribution source

Chapter02 Exercise 2.3 (1): under the explicit tie convention that equal φ-values allow either candidate subinterval to be kept, a retained interval after the first 0.618 step for φ(t) = Real.exp (-t) + Real.exp t on [-1, 1] is exactly one of the two explicit subintervals determined by the trial points 2 - Real.sqrt 5 and Real.sqrt 5 - 2.

open Set
theorem chapter02Exercise23ZeroPointSixOneEightRetainedInterval_iff (I : Set ℝ) :
    ((chapter02Exercise23Objective chapter02Exercise23LeftTrialPoint ≤
          chapter02Exercise23Objective chapter02Exercise23RightTrialPoint ∧
        I = chapter02Exercise23LeftRetainedInterval) ∨
      (chapter02Exercise23Objective chapter02Exercise23RightTrialPoint ≤
          chapter02Exercise23Objective chapter02Exercise23LeftTrialPoint ∧
        I = chapter02Exercise23RightRetainedInterval)) ↔
      I = chapter02Exercise23LeftRetainedInterval ∨
        I = chapter02Exercise23RightRetainedInterval

Exercise 2.4

Lean contributors (project-level attribution): Chenyi Li, Wanli Ma, Zichen Wang.

Source header · Attribution source

Chapter02 Exercise 2.4. The function quadraticInterpolationExerciseObjective attains its minimum on Set.Icc (0 : ℝ) 1 at Real.sqrt 2 / 2.

theorem quadraticInterpolationExerciseObjective_isMinOn_unitInterval : IsMinOn quadraticInterpolationExerciseObjective (Set.Icc (0 : ℝ) 1) (Real.sqrt 2 / 2)

Exercise 2.5

Lean contributors (project-level attribution): Chenyi Li, Wanli Ma, Zichen Wang.

Source header · Attribution source

Chapter02 Exercise 2.5 (1): the initial trial step t₀ = 1 / 2 satisfies the Armijo sufficient-decrease inequality for φ(t) = -2 t^3 + 21 t^2 - 60 t + 50 with ρ = 1 / 10.

theorem chapter02Exercise25_armijoAcceptsInitialStep : goldsteinSufficientDecrease exercise25Phi (exercise25PhiDeriv 0) (1 / 10 : ℝ) (1 / 2 : ℝ)

Exercise 2.6

Lean contributors (project-level attribution): Chenyi Li, Wanli Ma, Zichen Wang.

Source header · Attribution source

Chapter02 Exercise 2.6 (1): the half-step α = 1 / 2 satisfies the Wolfe rule with ρ = 1 / 10 and σ = 1 / 2, and the resulting update point is (-1 / 2, 1 / 2).

local notation "Point" => EuclideanSpace ℝ (Fin 2) theorem chapter02Exercise26WolfeRuleProducesHalfStepUpdate : WolfePowellCondition chapter02Exercise26Phi chapter02Exercise26PhiDeriv (1 / 10 : ℝ) (1 / 2 : ℝ) (1 / 2 : ℝ) ∧ chapter02Exercise26CurrentPoint + (1 / 2 : ℝ) • chapter02Exercise26SearchDirection = chapter02Exercise26NextPoint

Exercise 2.7

Lean contributors (project-level attribution): Chenyi Li, Wanli Ma, Zichen Wang.

Source header · Attribution source

Chapter02 Exercise 2.7: there exists a differentiable line-search profile φ : ℝ → ℝ for which no steplength satisfies the Wolfe rule with parameters ρ and σ, assuming the Wolfe-Powell parameters are admissible: 0 < ρ < σ < 1.

theorem existsLineSearchProfileWithoutWolfeStep (ρ σ : ℝ) (h_wolfe : WolfePowellParameters ρ σ) : ∃ φ : ℝ → ℝ, Differentiable ℝ φ ∧ ∀ α : ℝ, ¬ WolfePowellCondition φ (deriv φ) ρ σ α

Exercise 2.8

Lean contributors (project-level attribution): Chenyi Li, Wanli Ma, Zichen Wang.

Source header · Attribution source

Chapter02 Exercise 2.8 The source item is expository: it asks for the outline of Chapter02 Theorem 2.5.4 rather than for new source-facing mathematical data. The correct public layer is therefore the existing chapter theorem inexactLineSearch_globalConvergence, with InexactLineSearchAcceptance and InexactLineSearchMethod.stepSpec as the nearby source-facing Step 3 owners that unpack its accepted inexact line-search hypothesis.

#check InexactLineSearchAcceptance

Exercise 2.9

Lean contributors (project-level attribution): Chenyi Li, Wanli Ma, Zichen Wang.

Source header · Attribution source

Chapter02 Exercise 2.9: if f : E → ℝ on a real Hilbert space E is continuously differentiable and bounded below, gradient f is Lipschitz on the initial sublevel set initialSublevelSet f (x 0), and the iterates satisfy the Wolfe-Powell rule with parameters ρ, σ, then (inner ℝ (gradient f (x k)) (s k)) / ‖s k‖ → 0.

open Filter
open scoped Gradient
variable {E : Type*} [NormedAddCommGroup E] [InnerProductSpace ℝ E] [CompleteSpace E]

-- Domain sampling:
-- * project Wolfe-Powell owner for admissible parameters: `WolfePowellParameters`;
-- * project owner for the source-facing cosine-limit statement:
--   `wolfePowellLineSearch_gradientNorm_mul_cos_angle_tendsto_zero`;
-- * project bridge/view companion for the ratio-limit statement:
--   `wolfePowellLineSearch_gradientInner_div_searchDirectionNorm_tendsto_zero`;
-- * mathlib bridge from a Lipschitz-on-set hypothesis to the owner theorem's
--   uniform-continuity hypothesis: `LipschitzOnWith.uniformContinuousOn`.
-- Primitive data here are the iterate/update sequences, the descent inequality, the per-step
-- one-dimensional owner `WolfePowellCondition` on the canonical search-ray owner
-- `lineSearchObjective f (x k) (s k)`, and the Lipschitz-on-`initialSublevelSet f (x 0)`
-- hypothesis.
-- The limit conclusions are derived API obtained by reusing the Chapter 2 Wolfe-Powell owners,
-- so this file remains a bridge/view layer rather than a new owner abstraction.
theorem wolfePowell_gradientInner_div_searchDirectionNorm_tendsto_zero
    (f : E → ℝ) (x s : ℕ → E) (α : ℕ → ℝ) (ρ σ : ℝ)
    (h_contDiff : ContDiff ℝ 1 f)
    (h_bddBelow : BddBelow (Set.range f))
    (h_gradLipschitz :
      ∃ L : NNReal, LipschitzOnWith L (∇ f) (initialSublevelSet f (x 0)))
    (h_update : ∀ k, x (k + 1) = x k + α k • s k)
    (h_descent : ∀ k, inner ℝ (∇ f (x k)) (s k) < 0)
    (h_wolfeStep :
      ∀ k,
        WolfePowellCondition
          (lineSearchObjective f (x k) (s k))
          (deriv (lineSearchObjective f (x k) (s k)))
          ρ σ (α k)) :
    Tendsto (fun k : ℕ ↦ inner ℝ (∇ f (x k)) (s k) / ‖s k‖) atTop (nhds 0)

2.1 — Introduction

Definition 2.1.1

Lean contributors (project-level attribution): Chenyi Li, Wanli Ma, Zichen Wang.

Source header · Attribution source

Chapter02 Definition 2.1.1. For the one-dimensional minimization problem min_{α ≥ 0} φ α, a closed interval Icc a b is a search interval when αStar is a minimizer of φ on Ici 0, αStar ∈ Icc a b, and Icc a b ⊆ Ici 0. The same interval is also called an interval of uncertainty.

open Set def IsSearchInterval (φ : ℝ → ℝ) (αStar a b : ℝ) : Prop := IsMinOn φ (Ici 0) αStar ∧ αStar ∈ Icc a b ∧ Icc a b ⊆ Ici (0 : ℝ)

Algorithm 2.1.2

Lean contributors (project-level attribution): Chenyi Li, Wanli Ma, Zichen Wang.

Source header · Attribution source

Chapter02 Algorithm 2.1.2: under the natural output facts for the forward-backward method, the textbook bracket formed from stage k is a search interval in the sense of Chapter02 Definition 2.1.1.

namespace ForwardBackward theorem isSearchInterval_of_between {φ : ℝ → ℝ} {α0 h0 t αStar : ℝ} {k : ℕ} (hk : 0 < k) (hmin : IsMinOn φ (Set.Ici 0) αStar) (hbetween : previousPoint φ α0 h0 t k hk ≤ αStar ∧ αStar ≤ trialPoint φ α0 h0 t k ∨ trialPoint φ α0 h0 t k ≤ αStar ∧ αStar ≤ previousPoint φ α0 h0 t k hk) (hprevious : 0 ≤ previousPoint φ α0 h0 t k hk) (htrial : 0 ≤ trialPoint φ α0 h0 t k) : IsSearchInterval φ αStar (lowerEndpoint φ α0 h0 t k hk) (upperEndpoint φ α0 h0 t k hk)

Definition 2.1.3

Lean contributors (project-level attribution): Chenyi Li, Wanli Ma, Zichen Wang.

Source header · Attribution source

Chapter02 Definition 2.1.3. A function φ : α → β is unimodal on the interval Set.Icc a b if there exists αStar ∈ Set.Icc a b such that φ is strictly decreasing on Set.Icc a αStar and strictly increasing on Set.Icc αStar b. Such an interval Set.Icc a b is then called a unimodal interval related to φ.

universe u v variable {α : Type u} {β : Type v} [Preorder α] [Preorder β] def unimodalOn (φ : α → β) (a b : α) : Prop := ∃ αStar ∈ Set.Icc a b, StrictAntiOn φ (Set.Icc a αStar) ∧ StrictMonoOn φ (Set.Icc αStar b)

Definition 2.1.4

Lean contributors (project-level attribution): Chenyi Li, Wanli Ma, Zichen Wang.

Source header · Attribution source

Chapter02 Definition 2.1.4. If there exists αStar : Set.Icc a b satisfying TurningPointOrderCondition φ a b αStar, then φ is unimodal on Set.Icc a b.

theorem unimodalOn_of_existsTurningPointOrderCondition {φ : ℝ → ℝ} {a b : ℝ} (h : ∃ αStar : Set.Icc a b, TurningPointOrderCondition φ a b αStar) : unimodalOn φ a b

Theorem 2.1.5

Lean contributors (project-level attribution): Chenyi Li, Wanli Ma, Zichen Wang.

Source header · Attribution source

Chapter02 Theorem 2.1.5 (1). Assume φ is unimodal on Icc a b. Let α₁, α₂ ∈ Icc a b satisfy α₁ < α₂ and φ α₁ ≤ φ α₂. Then Icc a α₂ is a unimodal interval related to φ.

open Set universe u v variable {α : Type u} {β : Type v} [LinearOrder α] [Preorder β] theorem unimodalOn_left_of_apply_le {φ : α → β} {a b α₁ α₂ : α} (h : unimodalOn φ a b) (hα₁ : α₁ ∈ Icc a b) (hα₂ : α₂ ∈ Icc a b) (hα : α₁ < α₂) (hφ : φ α₁ ≤ φ α₂) : unimodalOn φ a α₂

Definition 2.1.extra.1

Lean contributors (project-level attribution): Chenyi Li, Wanli Ma, Zichen Wang.

Source header · Attribution source

Chapter02 Definition 2.1-extra-1 (1): the one-dimensional objective associated to the search ray from x in direction d is the function α ↦ f (x + α • d).

universe u

-- `IsMinOn` is the canonical mathlib minimizer owner for line-search subproblems.
-- For the search ray itself, the source-facing Chapter 2 owner stays at the weaker
-- `Add`/`SMul` level rather than specializing to an affine-map API that would
-- require stronger subtraction data.
variable {E : Type u}
def lineSearchObjective [Add E] [SMul ℝ E] (f : E → ℝ) (x d : E) : ℝ → ℝ :=
  fun α ↦ f (x + α • d)

2.2 — Convergence Theory for Exact Line Search

Algorithm 2.2.1

Lean contributors (project-level attribution): Chenyi Li, Wanli Ma, Zichen Wang.

Source header · Attribution source

Chapter02 Algorithm 2.2.1: a general exact-line-search method for unconstrained optimization in ℝ^n starts from x0, uses a tolerance ε ≥ 0, computes a descent direction d k from the current gradient data g k, chooses α k so that a ↦ f (x k + a • d k) attains its minimum on Set.Ici 0 at α k, and updates by x (k + 1) = x k + α k • d k. The textbook stopping test after the k-th update is ‖g (k + 1)‖ ≤ ε, where g k is a gradient of f at x k.

variable {n : ℕ} variable {f : EuclideanSpace ℝ (Fin n) → ℝ} local notation "Point" => EuclideanSpace ℝ (Fin n) -- Semantic recall: `lean_leansearch` surfaced the canonical minimizer owner `IsMinOn`, -- and nearby repository precedent for optimization algorithms records one concrete run -- through explicit iterate, gradient, direction, and step-size sequences. structure GeneralUnconstrainedOptimizationMethod (n : ℕ) (f : EuclideanSpace ℝ (Fin n) → ℝ) where ε : ℝ x0 : EuclideanSpace ℝ (Fin n) x : ℕ → EuclideanSpace ℝ (Fin n) g : ℕ → EuclideanSpace ℝ (Fin n) d : ℕ → EuclideanSpace ℝ (Fin n) α : ℕ → ℝ epsilon_nonneg : 0 ≤ ε x_zero : x 0 = x0 hasGradientAt : ∀ k : ℕ, HasGradientAt f (g k) (x k) descentDirection : ∀ k : ℕ, inner ℝ (g k) (d k) < 0 exactLineSearch : ∀ k : ℕ, IsMinOn (fun a : ℝ ↦ f (x k + a • d k)) (Set.Ici 0) (α k) update : ∀ k : ℕ, x (k + 1) = x k + α k • d k

Theorem 2.2.2

Lean contributors (project-level attribution): Chenyi Li, Wanli Ma, Zichen Wang.

Source header · Attribution source

Chapter02 Theorem 2.2.2: if αk solves the exact line-search problem on the nonnegative ray from xk in the descent direction dk, the traced segment from xk to xk + αk • dk lies in an open set D on which f is C², and the Hessian operator fderiv ℝ (∇ f) z has norm bounded by the positive constant M for every z ∈ D, then the achieved decrease is bounded below by `(1 / (2 * M)) * ‖∇ f xk‖^2 * (Real.cos (InnerProductGeometry.angle dk (-(∇ f xk))))^2`.

open Filter InnerProductSpace
open scoped Gradient

-- Domain sampling:
-- * source-facing owners: Chapter01 `IsDescentDirectionAt` for the descent-direction
--   hypothesis and Chapter02 `lineSearchObjective` /
--   `IsExactLineSearchStepOnNonnegativeRay` for one-dimensional exact line search;
-- * core/canonical regularity owners in nearby Chapter 2 files: local `ContDiffOn ℝ 2 f D`
--   on a set containing the traced segment and the derived Hessian operator `fderiv ℝ (∇ f)`;
-- * bridge/view: Chapter02 `cos_angle_searchDirection_negGradient` rewrites the cosine term
--   into the dot-product form when needed.
-- Primitive data are therefore the descent direction at `xk`, the exact line-search step, a
-- local domain `D` containing the traced segment from `xk` to `xk + αk • dk`, `C²` regularity
-- on `D`, and the Hessian norm bound on `D`; the pointwise `HasGradientAt`/`HasFDerivAt` facts
-- along the ray are derived API from that owner abstraction rather than primitive public
-- assumptions here.
variable {Point : Type*} [NormedAddCommGroup Point] [InnerProductSpace ℝ Point]
  [CompleteSpace Point]
theorem exactLineSearch_decrease_ge_half_inv_hessianBound_mul_gradientNormSq_mul_cosSq
    {D : Set Point} (f : Point → ℝ) (xk dk : Point) (αk M : ℝ)
    (hM : 0 < M)
    (h_descent : IsDescentDirectionAt f xk dk)
    (h_exactLineSearch : IsExactLineSearchStepOnNonnegativeRay f xk dk αk)
    (hD : IsOpen D)
    (h_segment : segment ℝ xk (xk + αk • dk) ⊆ D)
    (hC2 : ContDiffOn ℝ 2 f D)
    (h_hessianBound : ∀ z ∈ D, ‖fderiv ℝ (∇ f) z‖ ≤ M) :
    f xk - f (xk + αk • dk) ≥
      (1 / (2 * M)) * ‖∇ f xk‖ ^ (2 : ℕ) *
        (Real.cos (InnerProductGeometry.angle dk (-(∇ f xk)))) ^ (2 : ℕ)

Theorem 2.2.3

Lean contributors (project-level attribution): Chenyi Li, Wanli Ma, Zichen Wang.

Source header · Attribution source

Chapter02 Theorem 2.2.3: under the C² hypothesis, the limiting direction is orthogonal to ∇ f xBar and has nonnegative second-order directional curvature at xBar.

open Filter
open scoped Gradient
variable {n : ℕ}
local notation "Point" => EuclideanSpace ℝ (Fin n)

-- Source/core/bridge:
-- * source-facing owners: the two accumulation-direction theorems below;
-- * core/canonical local ingredient: the Chapter 2 exact-line-search owner
--   `IsExactLineSearchStepOnNonnegativeRay`, built from `lineSearchObjective`, together with
--   subsequence convergence via `Tendsto`;
-- The source theorem stays stated on explicit iterate, direction, and step-size sequences.
-- The iterate-update equation from Algorithm 2.2.1 is part of the source semantics and must stay
-- explicit: the exact-line-search stationarity equations live at `x k + α k • d k`, while the
-- theorem concludes about accumulation points extracted from a subsequence of the iterates `x`.
theorem exactLineSearch_accumulationDirection_firstAndSecondOrderConditions
    {D : Set Point} (f : Point → ℝ) (x d : ℕ → Point) (α : ℕ → ℝ)
    (hD : IsOpen D)
    (hC2 : ContDiffOn ℝ 2 f D)
    (h_iterates : ∀ k : ℕ, x k ∈ D)
    (h_exactLineSearch :
      ∀ k : ℕ, IsExactLineSearchStepOnNonnegativeRay f (x k) (d k) (α k))
    (h_update : ∀ k : ℕ, x (k + 1) = x k + α k • d k)
    (h_gradientDirection_nonpos : ∀ k : ℕ, inner ℝ (∇ f (x k)) (d k) ≤ 0)
    {xBar dBar : Point} {φ : ℕ → ℕ}
    (hφ : StrictMono φ)
    (hxBar : xBar ∈ D)
    (hx_tendsto : Tendsto (x ∘ φ) atTop (nhds xBar))
    (hd_tendsto : Tendsto (d ∘ φ) atTop (nhds dBar)) :
    inner ℝ (∇ f xBar) dBar = 0 ∧
      0 ≤ inner ℝ dBar ((fderiv ℝ (∇ f) xBar) dBar)

Theorem 2.2.4

Lean contributors (project-level attribution): Chenyi Li, Wanli Ma, Zichen Wang.

Source header · Attribution source

Chapter02 Theorem 2.2.4: let x, d, and α be generated by the exact-line-search scheme of Chapter02 Algorithm 2.2.1 for f : Point → ℝ, meaning that on each nonstationary iterate x k the direction d k is a descent direction in the canonical Chapter 1 sense IsDescentDirectionAt f (x k) (d k), the steplength α k is an exact line-search step on the nonnegative ray from x k along d k, and the next iterate satisfies x (k + 1) = x k + α k • d k. Assume ∇ f is uniformly continuous on the initial sublevel set initialSublevelSet f (x 0) = {y | f y ≤ f (x 0)}, and that the displayed field ∇ f is the genuine gradient of f at every ambient point of Point. Assume further that the angle between d k and -gradient f (x k) is uniformly bounded away from π / 2 on every nonstationary iterate, i.e. there exists μ > 0 such that InnerProductGeometry.angle (d k) (-(∇ f (x k))) ≤ Real.pi / 2 - μ whenever ∇ f (x k) ≠ 0. Then either ∇ f (x k) = 0 for some k, or f (x k) ⟶ -∞, or ∇ f (x k) ⟶ 0.

open Filter
open scoped Gradient
variable {n : ℕ}
local notation "Point" => EuclideanSpace ℝ (Fin n)

-- Domain sampling:
-- * source-facing layer: this theorem is the textbook global-convergence statement for the
--   exact-line-search iterate, direction, and steplength sequences of Algorithm 2.2.1;
-- * core/canonical candidates inspected upstream in the chapter:
--   `GeneralUnconstrainedOptimizationMethod` from `Algorithm_2_2_1` and
--   `IsExactLineSearchStepOnNonnegativeRay` from
--   `Definition_2_2_extra_1`;
-- * bridge/view pattern inspected nearby: `InexactLineSearchMethod` records step data only on
--   nonstationary iterates, which matches the source semantics better than forcing a descent
--   direction at every iterate.
-- The best owner abstraction available for this file is therefore the one-step exact line-search
-- owner `IsExactLineSearchStepOnNonnegativeRay`; the theorem itself stays source-facing because
-- the current chapter-wide method packages are stronger than the source statement. The initial
-- sublevel-set owner is therefore recorded canonically as `initialSublevelSet f (x 0)` rather
-- than through a redundant separate starting-point parameter. The labeled theorem follows the
-- book by exposing the ambient Euclidean gradient regularity needed to interpret `∇ f`, together
-- with level-set uniform continuity and angle hypotheses on that canonical sublevel-set owner.
theorem exactLineSearch_globalConvergence
    (f : Point → ℝ)
    (x d : ℕ → Point)
    (α : ℕ → ℝ)
    (μ : ℝ)
    (h_descent : ∀ k : ℕ, ∇ f (x k) ≠ 0 → IsDescentDirectionAt f (x k) (d k))
    (h_exactLineSearch :
      ∀ k : ℕ, ∇ f (x k) ≠ 0 → IsExactLineSearchStepOnNonnegativeRay f (x k) (d k) (α k))
    (h_update : ∀ k : ℕ, ∇ f (x k) ≠ 0 → x (k + 1) = x k + α k • d k)
    (h_hasGradient : ∀ y : Point, HasGradientAt f (∇ f y) y)
    (h_gradUniform :
      UniformContinuousOn (∇ f) (initialSublevelSet f (x 0)))
    (hμ : 0 < μ)
    (h_angle :
      ∀ k : ℕ, ∇ f (x k) ≠ 0 →
        InnerProductGeometry.angle (d k) (-(∇ f (x k))) ≤ Real.pi / 2 - μ) :
    (∃ k : ℕ, ∇ f (x k) = 0) ∨
      Tendsto (fun k : ℕ ↦ f (x k)) atTop atBot ∨
      Tendsto (fun k : ℕ ↦ ∇ f (x k)) atTop (nhds 0)

Lemma 2.2.5

Lean contributors (project-level attribution): Chenyi Li, Wanli Ma, Zichen Wang.

Source header · Attribution source

Chapter02 Lemma 2.2.5. If φ : ℝ → ℝ is twice continuously differentiable on Set.Icc 0 b, deriv φ 0 < 0, αStar ∈ Set.Ioo 0 b is a minimizer of φ on Set.Icc 0 b, and iteratedDeriv 2 φ α ≤ M for every α ∈ Set.Icc 0 b with 0 < M, then -deriv φ 0 / M ≤ αStar.

open Filter -- Declarations for this item will be appended below by the statement pipeline. -- Semantic recall: `lean_leansearch` surfaced the local-extremum derivative-zero API; -- this item keeps the book's exact lower-bound statement with the canonical `IsMinOn` owner. theorem lineSearch_minimizer_ge_neg_deriv_div_secondDerivBound {φ : ℝ → ℝ} {b M αStar : ℝ} (hC2 : ContDiffOn ℝ 2 φ (Set.Icc (0 : ℝ) b)) (h_deriv0 : deriv φ 0 < 0) (hM : 0 < M) (h_secondDeriv : ∀ α ∈ Set.Icc (0 : ℝ) b, iteratedDeriv 2 φ α ≤ M) (hαStar : αStar ∈ Set.Ioo (0 : ℝ) b) (h_min : IsMinOn φ (Set.Icc (0 : ℝ) b) αStar) : -deriv φ 0 / M ≤ αStar

Lemma 2.2.6

Lean contributors (project-level attribution): Chenyi Li, Wanli Ma, Zichen Wang.

Source header · Attribution source

Chapter02 Lemma 2.2.6: if f : Point → ℝ is twice continuously differentiable on an open set D containing the segment from x to x + α • d, then the line-search objective lineSearchObjective f x d admits the second-order integral expansion `lineSearchObjective f x d α = f x + α * ⟪∇ f x, d⟫ + α ^ (2 : ℕ) * ∫ t in 0..1, (1 - t) * ⟪d, (fderiv ℝ (∇ f) (x + (t * α) • d)) d⟫`. This keeps the source-facing Chapter 2 owner lineSearchObjective for the search ray while recasting the regularity hypothesis as a local ContDiffOn bridge to mathlib's one-variable Taylor integral remainder theorem, rather than as a global ContDiff assumption on all of Point.

open Filter InnerProductSpace
open scoped Gradient
variable {Point : Type*} [NormedAddCommGroup Point] [InnerProductSpace ℝ Point]
  [CompleteSpace Point]
theorem lineTaylorFormula_withIntegralHessianRemainder
    {D : Set Point} (f : Point → ℝ) (x d : Point) (α : ℝ)
    (hD : IsOpen D)
    (h_segment : segment ℝ x (x + α • d) ⊆ D)
    (hC2 : ContDiffOn ℝ 2 f D) :
    lineSearchObjective f x d α =
      f x + α * inner ℝ (∇ f x) d +
        α ^ (2 : ℕ) * ∫ t in 0..1,
          (1 - t) * inner ℝ d ((fderiv ℝ (∇ f) (x + (t * α) • d)) d)

Lemma 2.2.7

Lean contributors (project-level attribution): Chenyi Li, Wanli Ma, Zichen Wang.

Source header · Attribution source

Chapter02 Lemma 2.2.7 (1): if xStar is a local minimizer of f, f is twice continuously differentiable on Metric.ball xStar ε, and the Hessian quadratic form satisfies m * ‖y‖ ^ 2 ≤ inner ℝ y ((fderiv ℝ (∇ f) z) y) for every z ∈ Metric.ball xStar ε and y, then every x ∈ Metric.ball xStar ε satisfies (1 / 2 : ℝ) * m * ‖x - xStar‖ ^ 2 ≤ f x - f xStar.

open Filter InnerProductSpace
open scoped Gradient
variable {Point : Type*} [NormedAddCommGroup Point] [InnerProductSpace ℝ Point]
  [CompleteSpace Point]

-- Domain sampling:
-- * core/canonical mathlib owners: `IsLocalMin`, `ContDiffOn ℝ 2 f s`, and
--   `StrongConvexOn s m f` for second-order convexity data on a set;
-- * nearby Chapter 2 bridge owner: `lineTaylorFormula_withIntegralHessianRemainder`, which uses
--   the same Hessian operator surface `fderiv ℝ (∇ f)` for local second-order estimates.
-- Primitive data here are the local minimizer, the local `C²` ball regularity, and the
-- one-sided Hessian quadratic bound needed for each estimate. The coordinate model `ℝⁿ`, the
-- positivity of `ε`, and the unused opposite-side Hessian bound are not primitive for these
-- three conclusions, so the public API is stated over the canonical real Hilbert-space owner
-- and only keeps the needed hypotheses.
variable (f : Point → ℝ) (xStar : Point) (ε : ℝ)
local notation "B" => Metric.ball xStar ε
theorem minimizerValue_lowerBound_of_hessianQuadratic_bounds
    (hMin : IsLocalMin f xStar)
    (hC2 : ContDiffOn ℝ 2 f B)
    (x : Point) (m : ℝ)
    (hLower :
      ∀ z ∈ B, ∀ y : Point,
        m * ‖y‖ ^ 2 ≤ inner ℝ y ((fderiv ℝ (∇ f) z) y))
    (hx : x ∈ B) :
    (1 / 2 : ℝ) * m * ‖x - xStar‖ ^ 2 ≤ f x - f xStar

Theorem 2.2.8

Lean contributors (project-level attribution): Chenyi Li, Wanli Ma, Zichen Wang.

Source header · Attribution source

Chapter02 Theorem 2.2.8: let x be an iterate sequence generated by the exact-line-search scheme of Chapter02 Algorithm 2.2.1 for f : Point → ℝ, with search directions d and exact line-search steps α on the nonnegative ray, updates x (k + 1) = x k + α k • d k, and HasGradientAt f (∇ f (x k)) (x k) along the iterates. Assume x ⟶ xStar, where xStar is a local minimizer of f, and suppose the angle between d k and -∇ f (x k) is uniformly bounded away from π / 2 on every nonstationary iterate. If f is C² on Metric.ball xStar ε, and the Hessian quadratic form is bounded below by m > 0 and above by M on that ball, then the iterates converge to xStar at least linearly, expressed by the Chapter 1 owner rAtLeastLinearConvergenceTo. This matches the source proof's geometric-majorant conclusion and still allows the finite-termination and superlinear-tail cases that the stricter Chapter 1 R-linear predicate excludes. The Chapter 3 contraction owners are stronger derived API and are not the source-facing main conclusion here.

open Filter
open scoped Gradient
variable {Point : Type*} [NormedAddCommGroup Point] [InnerProductSpace ℝ Point]
  [CompleteSpace Point]

-- Domain sampling:
-- * primary domain: local linear convergence for exact line-search iterates near a local
--   minimizer;
-- * owner declarations inspected in this domain:
--   `IsExactLineSearchStepOnNonnegativeRay` from Chapter 2,
--   the local minimizer owner `IsLocalMin` used by `Lemma_2_2_7`,
--   the Chapter 3 convergence owners `HasEventuallyLinearConvergenceTo`,
--   `HasLinearConvergenceTo`,
--   and the Chapter 1 rate owners `rAtLeastLinearConvergenceTo`,
--   `IsNonnegErrorMajorant`, `HasQLinearConvergenceTo`,
--   `rLinearConvergenceTo`, `rLinearConvergenceTo_iff_exists_nonneg_qLinearMajorant`;
-- * triage:
--   * source-facing data: the iterate, direction, and step sequences with the local minimizer,
--     uniform angle bound, and local regularity/Hessian hypotheses;
--   * core/canonical owner for the source conclusion "at least linearly": the Chapter 1 owner
--     `rAtLeastLinearConvergenceTo`;
--   * stricter derived companions only: the global contraction owner
--     `HasLinearConvergenceTo`, and the Chapter 1 rate owner `rLinearConvergenceTo` together
--     with its equivalent nonnegative `Q`-linear majorant witness; these require stronger
--     data than the source-facing local hypotheses alone;
-- * primitive data are the iterate, direction, and step sequences together with the local
--   minimizer, uniform angle bound, and local regularity/Hessian hypotheses. The scalar majorant
--   witness and the strict `R`-linear rate are derived API beyond the source-facing
--   at-least-`R`-linear owner and should not be the primary public theorem surface here.
variable (f : Point → ℝ) (x d : ℕ → Point) (α : ℕ → ℝ) (xStar : Point) (ε m M μ : ℝ)
variable
  (h_descent : ∀ k : ℕ, ∇ f (x k) ≠ 0 → IsDescentDirectionAt f (x k) (d k))
  (h_exactLineSearch : ∀ k : ℕ, IsExactLineSearchStepOnNonnegativeRay f (x k) (d k) (α k))
  (h_update : ∀ k : ℕ, x (k + 1) = x k + α k • d k)
  (h_hasGradientAt : ∀ k : ℕ, HasGradientAt f (∇ f (x k)) (x k))
  (h_tendsto : Tendsto x atTop (nhds xStar))
  (h_localMin : IsLocalMin f xStar)
  (hμ : 0 < μ)
  (h_angle :
    ∀ k : ℕ, ∇ f (x k) ≠ 0 →
      InnerProductGeometry.angle (d k) (-(∇ f (x k))) ≤ Real.pi / 2 - μ)
  (hε : 0 < ε)
  (hC2 : ContDiffOn ℝ 2 f (Metric.ball xStar ε))
  (hm : 0 < m)
  (h_hessianLower :
    ∀ ⦃z : Point⦄, z ∈ Metric.ball xStar ε → ∀ y : Point,
      m * ‖y‖ ^ (2 : ℕ) ≤ inner ℝ y ((fderiv ℝ (∇ f) z) y))
  (h_hessianUpper :
    ∀ ⦃z : Point⦄, z ∈ Metric.ball xStar ε → ∀ y : Point,
      inner ℝ y ((fderiv ℝ (∇ f) z) y) ≤ M * ‖y‖ ^ (2 : ℕ))
include f x d α xStar ε m M μ h_descent h_exactLineSearch h_update h_hasGradientAt h_tendsto
  h_localMin hμ h_angle hε hC2 hm h_hessianLower h_hessianUpper
theorem exactLineSearch_atLeastLinearConvergenceTo_of_tendsto_isLocalMin_of_angleBound
    : rAtLeastLinearConvergenceTo x xStar

Theorem 2.2.9

Lean contributors (project-level attribution): Chenyi Li, Wanli Ma, Zichen Wang.

Source header · Attribution source

Chapter02 Theorem 2.2.9: if αk is an exact line-search step from xk along dk on the nonnegative ray in the Chapter 2 sense IsExactLineSearchStepOnNonnegativeRay f xk dk αk, equivalently when lineSearchObjective f xk dk attains its minimum on Set.Ici 0 at αk, and f has a globally η-strongly monotone gradient in the sense that inner ℝ (x - z) (∇ f x - ∇ f z) ≥ η * ‖x - z‖^2 for all x, z, then the exact line-search decrease is bounded below by (η / 2) * ‖αk • dk‖^2.

open MeasureTheory
open scoped Gradient RealInnerProductSpace

-- Semantic recall: the canonical owner for the companion theorem is
-- `StrongConvexOn Set.univ η f`, while the source theorem itself is phrased through a
-- strong-monotonicity inequality for `∇ f`. This file keeps the source-facing Chapter 2
-- exact-line-search owner `IsExactLineSearchStepOnNonnegativeRay`, whose objective profile is
-- `lineSearchObjective`.
variable {Point : Type*} [NormedAddCommGroup Point] [InnerProductSpace ℝ Point]
  [CompleteSpace Point]
theorem exactLineSearch_decrease_ge_half_mul_eta_mul_stepNormSq_of_gradient_strongMonotone
    (f : Point → ℝ) (xk dk : Point) (αk η : ℝ)
    (h_exactLineSearch : IsExactLineSearchStepOnNonnegativeRay f xk dk αk)
    (h_hasGradient : ∀ x : Point, HasGradientAt f (∇ f x) x)
    (h_gradientStrongMonotone :
      ∀ x z : Point,
        inner ℝ (x - z) (∇ f x - ∇ f z) ≥ η * ‖x - z‖ ^ 2) :
    f xk - f (xk + αk • dk) ≥ (η / 2) * ‖αk • dk‖ ^ 2

Definition 2.2.extra.1

Lean contributors (project-level attribution): Chenyi Li, Wanli Ma, Zichen Wang.

Source header · Attribution source

Chapter02 Definition 2.2-extra-1 (2): an exact line-search step along d from x is a point αk ∈ Set.Ici 0 where lineSearchObjective f x d attains its minimum on the nonnegative ray. This uses the canonical minimizer owner IsMinOn, with the domain condition recorded as membership in Set.Ici 0.

universe u
variable {E : Type u} [Add E] [SMul ℝ E]
class IsExactLineSearchStepOnNonnegativeRay (f : E → ℝ) (x d : E) (αk : ℝ) : Prop where
  mem_Ici : αk ∈ Set.Ici 0
  isMinOn : IsMinOn (lineSearchObjective f x d) (Set.Ici 0) αk

2.3 — Section Methods

Algorithm 2.3.1

Lean contributors (project-level attribution): Chenyi Li, Wanli Ma, Zichen Wang.

Source header · Attribution source

Chapter02 Algorithm 2.3.1: a terminated golden section search run for a one-dimensional objective φ. The data consist of a precision δ > 0, interval endpoints a k, b k, interior observations lam k, mu k, and the cached function values phiLam k = φ (lam k) and phiMu k = φ (mu k). At k = 1, the observations are placed using the exact golden-section weights 1 - Real.goldenRatio⁻¹ and Real.goldenRatio⁻¹, whose decimal approximations are 0.382 and 0.618. For each k < terminalIndex, the method compares phiLam k and phiMu k: if phiLam k > phiMu k, then the right-case update of Step 3 is used and the nonterminal condition is δ < b k - lam k; if phiLam k ≤ phiMu k, then the left-case update of Step 4 is used and the nonterminal condition is δ < mu k - a k. At terminalIndex, the run stops with output mu terminalIndex in the right branch and lam terminalIndex in the left branch.

structure GoldenSectionMethod (φ : ℝ → ℝ) where δ : ℝ terminalIndex : ℕ a : ℕ → ℝ b : ℕ → ℝ lam : ℕ → ℝ mu : ℕ → ℝ phiLam : ℕ → ℝ phiMu : ℕ → ℝ output : ℝ delta_pos : 0 < δ one_le_terminalIndex : 1 ≤ terminalIndex initialInterval : a 1 ≤ b 1 initialLam : lam 1 = a 1 + (1 - Real.goldenRatio⁻¹) * (b 1 - a 1) initialMu : mu 1 = a 1 + Real.goldenRatio⁻¹ * (b 1 - a 1) phiLam_eval : ∀ k : ℕ, 1 ≤ k → k ≤ terminalIndex → phiLam k = φ (lam k) phiMu_eval : ∀ k : ℕ, 1 ≤ k → k ≤ terminalIndex → phiMu k = φ (mu k) rightCaseStep : ∀ k : ℕ, 1 ≤ k → k < terminalIndex → phiLam k > phiMu k → GoldenSectionMethod.RightCaseUpdate φ δ a b lam mu phiLam phiMu k leftCaseStep : ∀ k : ℕ, 1 ≤ k → k < terminalIndex → phiLam k ≤ phiMu k → GoldenSectionMethod.LeftCaseUpdate φ δ a b lam mu phiLam phiMu k rightCaseStop : phiLam terminalIndex > phiMu terminalIndex → GoldenSectionMethod.RightCaseStop δ output b lam mu terminalIndex leftCaseStop : phiLam terminalIndex ≤ phiMu terminalIndex → GoldenSectionMethod.LeftCaseStop δ output a lam mu terminalIndex

Definition 2.3.extra.1

Lean contributors (project-level attribution): Chenyi Li, Wanli Ma, Zichen Wang.

Source header · Attribution source

Chapter02 Definition 2.3-extra-1: the Fibonacci sequence from the text is the shifted canonical sequence k ↦ Nat.fib (k + 1), so that fibonacciSequence 0 = 1 and fibonacciSequence 1 = 1.

abbrev fibonacciSequence (k : ℕ) : ℕ := Nat.fib (k + 1)

2.4 — Interpolation Method

Theorem 2.4.1

Lean contributors (project-level attribution): Chenyi Li, Wanli Ma, Zichen Wang.

Source header · Attribution source

Chapter02 Theorem 2.4.1: if φ : ℝ → ℝ is ContDiffAt ℝ 3 at αStar and αStar is a nondegenerate stationary point of φ, then there is a positive neighborhood of αStar such that the recursively generated interpolation-secant sequence from any initial pair in that neighborhood converges to αStar with Q-order Real.goldenRatio = (1 + √5) / 2, provided each secant denominator is nonzero.

theorem interpolationSecant_hasQOrderConvergenceTo_goldenRatio (φ : ℝ → ℝ) (αStar : ℝ) (h_smooth : ContDiffAt ℝ 3 φ αStar) (h_stationary : deriv φ αStar = 0) (h_nondegenerate : iteratedDeriv 2 φ αStar ≠ 0) : ∃ δ > 0, ∀ a₀ a₁ : ℝ, let α := interpolationSecantSequence φ a₀ a₁

Algorithm 2.4.2

Lean contributors (project-level attribution): Chenyi Li, Wanli Ma, Zichen Wang.

Source header · Attribution source

Chapter02 Algorithm 2.4.2 (Line Search Employing Quadratic Interpolation with Three Points). Given a positive tolerance ε > 0, a line-search objective φ, and a valid current bracket {α1, α2, α3}, Step 1 produces αbar = bracket.interpolationPoint by the quadratic-interpolation formula (2.4.25). If one also tracks a target minimizer αStar, the source hypothesis that it lies in the current bracket is αStar ∈ Set.Icc bracket.α1 bracket.α3. One textbook iteration: * retries when (αbar - α1) * (αbar - α3) ≥ 0, * stops when αbar lies between α1 and α3 and |αbar - α2| < ε, * otherwise continues with the Step 3 bracket computed from α1, α2, α3, and αbar.

namespace QuadraticInterpolationThreePointBracket noncomputable def step (bracket : QuadraticInterpolationThreePointBracket φ) (ε : ℝ) (hε : 0 < ε) : QuadraticInterpolationThreePointStepResult φ

Theorem 2.4.3

Lean contributors (project-level attribution): Chenyi Li, Wanli Ma, Zichen Wang.

Source header · Attribution source

Chapter02 Theorem 2.4.3: if φ : ℝ → ℝ is ContDiffAt ℝ 4 at αStar and αStar is a nondegenerate stationary point of φ, then there is a positive neighborhood of αStar such that every valid quadratic-interpolation sequence generated from an initial triple in that neighborhood converges to αStar with Q-order quadraticInterpolationOrder.

open Filter -- This file keeps only the convergence-order constant and the Chapter 2 bridge from the -- source-facing recursive owner `quadraticInterpolationSequence` to the Chapter 1 owner -- `HasQOrderConvergenceTo`. theorem quadraticInterpolation_hasQOrderConvergenceTo (φ : ℝ → ℝ) (αStar : ℝ) (h_smooth : ContDiffAt ℝ 4 φ αStar) (h_stationary : deriv φ αStar = 0) (h_nondegenerate : iteratedDeriv 2 φ αStar ≠ 0) : ∃ δ > 0, ∀ a₀ a₁ a₂ : ℝ, let α := quadraticInterpolationSequence φ a₀ a₁ a₂

Definition 2.4.extra.1

Lean contributors (project-level attribution): Chenyi Li, Wanli Ma, Zichen Wang.

Source header · Attribution source

Chapter02 Definition 2.4-extra-1: a polynomial p interpolates the line-search objective at the sampled step sizes samplePoints when p.eval α = lineSearchObjective f x d α for every sampled α.

universe u

-- Polynomial interpolation adds a source-facing bridge between the existing
-- line-search objective owner `lineSearchObjective` and the canonical
-- polynomial/minimizer APIs. The minimizer surface itself remains the
-- canonical `IsMinOn` owner from mathlib.
variable {E : Type u}
def InterpolatesLineSearchOn [Add E] [SMul ℝ E] (f : E → ℝ) (x d : E)
    (p : Polynomial ℝ) (samplePoints : Finset ℝ) : Prop :=
  ∀ ⦃α : ℝ⦄, α ∈ samplePoints → p.eval α = lineSearchObjective f x d α

Definition 2.4.extra.2

Lean contributors (project-level attribution): Chenyi Li, Wanli Ma, Zichen Wang.

Source header · Attribution source

Chapter02 Definition 2.4-extra-2. The local interpolation-convergence results in Section 2.4 reuse the Chapter 1 owner HasQOrderConvergenceTo and its textbook quotient map qErrorRatio directly.

#check qErrorRatio

2.5 — Inexact Line Search Techniques

Algorithm 2.5.1

Lean contributors (project-level attribution): Chenyi Li, Wanli Ma, Zichen Wang.

Source header · Attribution source

Chapter02 Algorithm 2.5.1 (Inexact Line Search with Goldstein Rule): the accepted terminal step in a Goldstein line-search run satisfies the Goldstein rule.

theorem GoldsteinLineSearchRun.terminal_goldsteinCondition {φ : ℝ → ℝ} (run : GoldsteinLineSearchRun φ) : goldsteinCondition φ run.φPrime0 run.ρ (run.state run.terminalIndex).trial

Algorithm 2.5.2

Lean contributors (project-level attribution): Chenyi Li, Wanli Ma, Zichen Wang.

Source header · Attribution source

Chapter02 Algorithm 2.5.2: a successful backtracking Armijo step uses parameters ρ ∈ (0, 1 / 2) and 0 < l < u < 1, starts from α = 1, multiplies by recorded shrink factors ω ∈ [l, u], accepts the final recorded trial, and rejects every earlier recorded trial. The generic backtracking owner is derived from this finite source-facing trace.

variable {E : Type*} [NormedAddCommGroup E] [InnerProductSpace ℝ E]

-- Source/core/bridge triage:
-- * source-facing: a successful Armijo backtracking step with shrink factors in `[l, u]`,
--   recorded by its finite accepted/rejected trial trace;
-- * core/canonical: `lineSearchObjective` and `IsBacktrackingLineSearchStep`;
-- * bridge/view: the derived theorem `toIsBacktrackingLineSearchStep` packaging the finite
--   Armijo trace as the canonical least-index backtracking owner.
class IsBacktrackingArmijoLineSearchStep
    (f : E → ℝ) (xk gk dk : E) (ρ l u : ℝ) (ωs : List ℝ) : Prop where
  rho_mem : ρ ∈ Set.Ioo (0 : ℝ) (1 / 2 : ℝ)
  l_pos : 0 < l
  l_lt_u : l < u
  u_lt_one : u < 1
  shrinkFactors_mem : ∀ ω ∈ ωs, ω ∈ Set.Icc l u
  accepted :
    armijoBacktrackingAccepts f ρ xk gk dk (backtrackingArmijoStepSizes l ωs ωs.length)
  rejectedBefore :
    ∀ n < ωs.length,
      ¬ armijoBacktrackingAccepts f ρ xk gk dk (backtrackingArmijoStepSizes l ωs n)

Algorithm 2.5.3

Lean contributors (project-level attribution): Chenyi Li, Wanli Ma, Zichen Wang.

Source header · Attribution source

Chapter02 Algorithm 2.5.3 reuses the Chapter 1 gradient-vector owner HasGradientVectorAt; on a complete inner-product space this is exactly mathlib's HasGradientAt.

variable {Point : Type*} [NormedAddCommGroup Point] [InnerProductSpace ℝ Point]
variable {f : Point → ℝ}
theorem hasGradientVectorAt_iff_hasGradientAt
    [CompleteSpace Point]
    {g x : Point} :
    HasGradientVectorAt f g x ↔ HasGradientAt f g x

Theorem 2.5.4

Lean contributors (project-level attribution): Chenyi Li, Wanli Ma, Zichen Wang.

Source header · Attribution source

Chapter02 Theorem 2.5.4: let A : InexactLineSearchMethod f g be generated by Chapter02 Algorithm 2.5.3 with zero stopping tolerance. Thus A 0 = A.x0; each nonstationary iterate satisfies A (k + 1) = A k + A.α k • A.d k; each steplength satisfies the Step 3 inexact line-search acceptance condition from Chapter02 Algorithm 2.5.3; the chosen gradient field g is the genuine gradient of f on initialSublevelSet f A.x0; g is uniformly continuous there; (2.5.17) holds for some μ > 0. Then either g (A k) = 0 for some k, or f (A k) ⟶ -∞, or g (A k) ⟶ 0.

open Filter
variable {E : Type*} [NormedAddCommGroup E] [InnerProductSpace ℝ E]
variable {f : E → ℝ}
variable {g : E → E}

-- Domain sampling:
-- * source-facing: the global-convergence trichotomy for the Chapter 2 inexact-line-search run;
-- * core/canonical owners inspected in the local chapter API: `InexactLineSearchMethod`,
--   `InexactLineSearchAcceptance`, and the chapter support owner `initialSublevelSet`;
-- * adjacent convergence surfaces checked for statement shape: `exactLineSearch_globalConvergence`
--   in `Theorem_2_2_4` and `wolfePowellLineSearch_globalConvergence` in `Theorem_2_5_7`.
-- Primitive algorithm data belong to the owner object `A : InexactLineSearchMethod f g`; the
-- theorem-specific regularity hypotheses on the initial sublevel set remain external.
theorem inexactLineSearch_globalConvergence
    (A : InexactLineSearchMethod f g)
    (μ : ℝ)
    (hε : A.ε = 0)
    (h_hasGradient :
      ∀ y ∈ initialSublevelSet f A.x0, HasGradientVectorAt f (g y) y)
    (h_gradUniform : UniformContinuousOn g (initialSublevelSet f A.x0))
    (hμ : 0 < μ)
    (h_angle :
      ∀ k : ℕ, g (A k) ≠ 0 →
        InnerProductGeometry.angle (A.d k) (-(g (A k))) ≤ Real.pi / 2 - μ) :
    (∃ k : ℕ, g (A k) = 0) ∨
      Tendsto (fun k : ℕ ↦ f (A k)) atTop atBot ∨
      Tendsto (fun k : ℕ ↦ g (A k)) atTop (nhds 0)

Theorem 2.5.5

Lean contributors (project-level attribution): Chenyi Li, Wanli Ma, Zichen Wang.

Source header · Attribution source

Chapter02 Theorem 2.5.5: let f : E → ℝ on a real Hilbert space E be bounded below, and assume ∇ f y is the genuine gradient of f at each y in the initial sublevel set initialSublevelSet f (x 0) = {y | f y ≤ f (x 0)} and that ∇ f is uniformly continuous there. If the iterate sequence x, search directions s, and steplengths α satisfy the Wolfe-Powell rule from Chapter02 Algorithm 2.5.3, then the source-facing cosine formulation ‖∇ f (x k)‖ * cos θ k ⟶ 0, written with θ k = InnerProductGeometry.angle (s k) (-∇ f (x k)), holds.

open Filter
open scoped Gradient
variable {E : Type*} [NormedAddCommGroup E] [InnerProductSpace ℝ E] [CompleteSpace E]

-- Domain sampling:
-- * source-facing: the sequential Wolfe-Powell line-search convergence statement for the iterates
--   `x`, directions `s`, and steplengths `α`;
-- * core/canonical: the chapter owners `lineSearchObjective`, `WolfePowellParameters`,
--   `WolfePowellCondition`, and the mathlib gradient owner `∇`;
-- * bridge/view: the derivative bridge `deriv (lineSearchObjective f (x k) (s k))`, identified
--   by `deriv_lineSearchObjective_apply`, the cosine-to-ratio bridge
--   `gradientNorm_mul_cos_angle_searchDirection_negGradient_eq_neg_gradientInner_div_norm`,
--   and the update relation `x (k + 1) = x k + α k • s k`.
-- Primitive data are therefore the iterate/update sequences, the parameter owner carried by each
-- `WolfePowellCondition`, the per-step Wolfe owner on the canonical search-ray profile, the
-- local gradient witnesses `HasGradientAt f (∇ f y) y` on `initialSublevelSet f (x 0)`, the
-- descent hypothesis, and the uniform continuity of `∇ f` on that same initial-sublevel-set
-- owner. The cosine formulation is the source-facing theorem surface; the ratio limit is a
-- bridge/view consequence.
theorem wolfePowellLineSearch_gradientNorm_mul_cos_angle_tendsto_zero
    (f : E → ℝ) (x s : ℕ → E) (α : ℕ → ℝ) (ρ σ : ℝ)
    (h_bddBelow : BddBelow (Set.range f))
    (h_hasGradient : ∀ y ∈ initialSublevelSet f (x 0), HasGradientAt f (∇ f y) y)
    (h_gradUniform : UniformContinuousOn (∇ f) (initialSublevelSet f (x 0)))
    (h_update : ∀ k, x (k + 1) = x k + α k • s k)
    (h_descent : ∀ k, inner ℝ (∇ f (x k)) (s k) < 0)
    (h_wolfeStep :
      ∀ k,
        WolfePowellCondition
          (lineSearchObjective f (x k) (s k))
          (deriv (lineSearchObjective f (x k) (s k)))
          ρ σ (α k)) :
    Tendsto
      (fun k : ℕ ↦
        ‖∇ f (x k)‖ * Real.cos (InnerProductGeometry.angle (s k) (-∇ f (x k))))
      atTop
      (nhds 0)

Lemma 2.5.6

Lean contributors (project-level attribution): Chenyi Li, Wanli Ma, Zichen Wang.

Source header · Attribution source

Chapter02 Lemma 2.5.6: let f : Point → ℝ be defined on a domain D, continuously differentiable on D, meaning that ∇ f y is the genuine gradient of f at each y ∈ D, and suppose this gradient is M-Lipschitz on D with M > 0. If xk ∈ D, the accepted trial point xk + αk • dk also lies in D, and αk satisfies the Wolfe-Powell rule (2.5.3), (2.5.7) along the descent direction dk, then `f xk - f (xk + αk • dk) ≥ ((ρ * (1 - σ)) / M) * ‖gradient f xk‖^2 * (Real.cos (InnerProductGeometry.angle dk (-gradient f xk)))^2`.

open scoped Gradient
variable {Point : Type*} [NormedAddCommGroup Point] [InnerProductSpace ℝ Point]
  [CompleteSpace Point]

-- Domain sampling: this is a source-facing single-step Wolfe-Powell decrease estimate in smooth
-- line search. The owner abstractions in this domain are the Chapter 2 ray profile
-- `lineSearchObjective`, the Chapter 2 one-dimensional Wolfe owner `WolfePowellCondition`,
-- mathlib's gradient predicate `HasGradientAt`, and mathlib's setwise Lipschitz owner
-- `LipschitzOnWith`. Primitive data for the present statement are the endpoint memberships in `D`,
-- the genuine-gradient witness for `∇ f` on `D`, the Lipschitz bound on `∇ f`, and the
-- descent/Wolfe inequalities; the derivative profile
-- `α ↦ inner ℝ (∇ f (xk + α • dk)) dk` is the bridge layer from the ambient function `f` to the
-- one-dimensional Wolfe condition.
theorem wolfePowellDecrease_ge_gradientNormSq_mul_cosSq
    (D : Set Point) (f : Point → ℝ)
    (xk dk : Point) (αk ρ σ M : ℝ)
    (hxk : xk ∈ D)
    (hxαk : xk + αk • dk ∈ D)
    (hM : 0 < M)
    (h_hasGradientOnD : ∀ y ∈ D, HasGradientAt f (∇ f y) y)
    (h_gradLipschitz : LipschitzOnWith ⟨M, le_of_lt hM⟩ (∇ f) D)
    (h_descent : inner ℝ (∇ f xk) dk < 0)
    (h_wolfe :
      WolfePowellCondition
        (lineSearchObjective f xk dk)
        (fun α ↦ inner ℝ (∇ f (xk + α • dk)) dk)
        ρ σ αk) :
    f xk - f (xk + αk • dk) ≥
      ((ρ * (1 - σ)) / M) * ‖∇ f xk‖ ^ (2 : ℕ) *
        (Real.cos (InnerProductGeometry.angle dk (-(∇ f xk)))) ^ (2 : ℕ)

Theorem 2.5.7

Lean contributors (project-level attribution): Chenyi Li, Wanli Ma, Zichen Wang.

Source header · Attribution source

Chapter02 Theorem 2.5.7 in source-facing gradient-field form: let g be a gradient field for f, meaning HasGradientVectorAt f (g y) y for every y, and assume g satisfies the Lipschitz bound ‖g x - g y‖ ≤ M * ‖x - y‖ for all x and y. Let x, s, and α be generated by Chapter02 Algorithm 2.5.3 in the Wolfe-Powell branch, so that on every nonstationary iterate x k the direction s k is a descent direction, the accepted steplength α k is positive, the update is x (k + 1) = x k + α k • s k, and the sufficient-decrease and curvature inequalities (2.5.3) and (2.5.7) hold. If the angle condition (2.5.17) is satisfied, here written as the existence of μ > 0 with InnerProductGeometry.angle (s k) (-(g (x k))) ≤ Real.pi / 2 - μ whenever g (x k) ≠ 0, then either g (x k) = 0 for some k, or f (x k) ⟶ -∞, or g (x k) ⟶ 0.

open Filter
open scoped Gradient
variable {E : Type*} [NormedAddCommGroup E] [InnerProductSpace ℝ E]

-- Domain sampling:
-- * source-facing: the Wolfe-Powell/Lipschitz specialization of Chapter 2 global convergence
--   stated with a chosen gradient field `g`;
-- * core/canonical: `HasGradientVectorAt`, `inexactLineSearch_globalConvergence`,
--   `InexactLineSearchAcceptance`, and `WolfePowellParameters`;
-- * bridge/view: `wolfePowellLineSearch_globalConvergence_of_uniformContinuousOn` packages the
--   explicit Wolfe-Powell iterate data into the canonical convergence owner, while the global
--   Lipschitz bound on `g` yields that bridge theorem's `UniformContinuousOn` hypothesis on the
--   initial sublevel set. The companion
--   `wolfePowellLineSearch_globalConvergence_of_contDiff` recovers the complete-space `∇ f`
--   formulation.
theorem wolfePowellLineSearch_globalConvergence
    (f : E → ℝ)
    (g : E → E)
    (x s : ℕ → E)
    (α : ℕ → ℝ)
    (ρ σ M μ : ℝ)
    (h_wolfe : WolfePowellParameters ρ σ)
    (h_hasGradient : ∀ y : E, HasGradientVectorAt f (g y) y)
    (h_gradLipschitz : ∀ x' y' : E, ‖g x' - g y'‖ ≤ M * ‖x' - y'‖)
    (h_alphaPos : ∀ k : ℕ, g (x k) ≠ 0 → 0 < α k)
    (h_update : ∀ k : ℕ, g (x k) ≠ 0 → x (k + 1) = x k + α k • s k)
    (h_descent : ∀ k : ℕ, g (x k) ≠ 0 → inner ℝ (g (x k)) (s k) < 0)
    (h_armijo :
      ∀ k : ℕ, g (x k) ≠ 0 →
        f (x k + α k • s k) ≤
          f (x k) + ρ * α k * inner ℝ (g (x k)) (s k))
    (h_curvature :
      ∀ k : ℕ, g (x k) ≠ 0 →
        σ * inner ℝ (g (x k)) (s k) ≤
          inner ℝ (g (x (k + 1))) (s k))
    (hμ : 0 < μ)
    (h_angle :
      ∀ k : ℕ, g (x k) ≠ 0 →
        InnerProductGeometry.angle (s k) (-(g (x k))) ≤ Real.pi / 2 - μ) :
    (∃ k : ℕ, g (x k) = 0) ∨
      Tendsto (fun k : ℕ ↦ f (x k)) atTop atBot ∨
      Tendsto (fun k : ℕ ↦ g (x k)) atTop (nhds 0)

Theorem 2.5.8

Lean contributors (project-level attribution): Chenyi Li, Wanli Ma, Zichen Wang.

Source header · Attribution source

Chapter02 Theorem 2.5.8: in the inexact line-search setting, if αk satisfies the sufficient-decrease condition (2.5.3) along a descent direction dk, formalized as armijoBacktrackingAccepts f ρ xk (∇ f xk) dk αk, ρ ∈ (0, 1 / 2), f is globally C², ∇ f satisfies the uniform-convexity lower bound (2.5.27) with constant η > 0, and the Hessian quadratic form of f, written via the canonical owner iteratedFDeriv ℝ 2 f, satisfies the two-sided bounds (2.5.28) with 0 < m < M, then the achieved decrease is bounded below by (ρ * η / (1 + Real.sqrt (M / m))) * ‖αk • dk‖^2, which is (2.5.29).

open scoped Gradient

-- Semantic recall: the Chapter 2 owner for the sufficient-decrease test is
-- `armijoBacktrackingAccepts`, and the existing bridge
-- `StrongConvexOn.gradientStrongMonotone_univ` already converts the canonical owner
-- `StrongConvexOn Set.univ η f` into the source-facing gradient strong-monotonicity
-- hypothesis used here. No mathlib theorem directly matches this inexact line-search
-- decrease estimate, so the main result stays source-facing while reusing those owners.
variable {Point : Type} [NormedAddCommGroup Point] [InnerProductSpace ℝ Point]
  [CompleteSpace Point]
theorem armijoDecrease_ge_rho_mul_eta_div_one_add_sqrt_hessianRatio_mul_stepNormSq
    (f : Point → ℝ) (xk dk : Point) (αk ρ η m M : ℝ)
    (hρ_pos : 0 < ρ)
    (hρ_lt_half : ρ < (1 / 2 : ℝ))
    (hη_pos : 0 < η)
    (hm_pos : 0 < m)
    (hm_lt_M : m < M)
    (hContDiff : ContDiff ℝ 2 f)
    (h_descent : inner ℝ (∇ f xk) dk < 0)
    (h_armijo :
      armijoBacktrackingAccepts f ρ xk (∇ f xk) dk αk)
    (h_gradientStrongMonotone :
      ∀ y z : Point,
        inner ℝ (y - z) (∇ f y - ∇ f z) ≥ η * ‖y - z‖ ^ 2)
    (h_hessianBounds :
      ∀ x y : Point,
        m * ‖y‖ ^ 2 ≤ (iteratedFDeriv ℝ 2 f x) ![y, y] ∧
          (iteratedFDeriv ℝ 2 f x) ![y, y] ≤ M * ‖y‖ ^ 2) :
    f xk - f (xk + αk • dk) ≥
      (ρ * η / (1 + Real.sqrt (M / m))) * ‖αk • dk‖ ^ 2

Theorem 2.5.9

Lean contributors (project-level attribution): Chenyi Li, Wanli Ma, Zichen Wang.

Source header · Attribution source

Chapter02 Theorem 2.5.9 (1): if x, d, and α satisfy the nonmonotone Armijo line-search update with parameters τ, σ, γ, and memory bound M, and if the search directions satisfy the descent bound inner ℝ (g k) (d k) ≤ -c1 * ‖g k‖^2 whenever x k ∈ initialSublevelSet f (x 0), then every iterate remains in initialSublevelSet f (x 0). This sublevel-invariance step uses only the update and accepted-step data of the nonmonotone Armijo run together with the descent inequality; compactness, gradient-regularity, and direction-norm hypotheses belong to later parts of the theorem, not to this part (1).

open Filter open scoped Gradient variable {E : Type*} [NormedAddCommGroup E] [InnerProductSpace ℝ E] [CompleteSpace E] variable (f : E → ℝ) (x g d : ℕ → E) (α : ℕ → ℝ) (τ σ γ c1 c2 : ℝ) (M : ℕ) (m exp : ℕ → ℕ) theorem nonmonotoneArmijoLineSearch_iterates_mem_initialSublevelSet (hc1 : 0 < c1) (h_descent : ∀ k, x k ∈ initialSublevelSet f (x 0) → inner ℝ (g k) (d k) ≤ -c1 * ‖g k‖ ^ (2 : ℕ)) (h_lineSearch : IsNonmonotoneArmijoLineSearch f x g d α τ σ γ M m exp) (k : ℕ) : x k ∈ initialSublevelSet f (x 0)

Definition 2.5.extra.1

Lean contributors (project-level attribution): Chenyi Li, Wanli Ma, Zichen Wang.

Source header · Attribution source

The admissible Armijo backtracking parameters satisfy 0 < β < 1, 0 < ρ < 1 / 2, and 0 < τ.

variable {E : Type} [NormedAddCommGroup E] [InnerProductSpace ℝ E]

-- Source/core/bridge triage:
-- * source-facing: admissible Armijo parameters and the first accepted exponent `mk`
--   for the geometric trial steps `τ, β * τ, β ^ 2 * τ, ...`;
-- * core/canonical: `armijoBacktrackingAccepts`, `IsBacktrackingLineSearchStep`, and
--   `IsBacktrackingStepSequence`;
-- * bridge/view: `armijoAcceptsAtExponent` records the textbook exponent-indexed view
--   by evaluating the canonical Armijo predicate on the geometric backtracking steps.
class ArmijoParameters (β ρ τ : ℝ) : Prop where
  beta_pos : 0 < β
  beta_lt_one : β < 1
  rho_pos : 0 < ρ
  rho_lt_half : ρ < (1 / 2 : ℝ)
  tau_pos : 0 < τ

Definition 2.5.extra.2

Lean contributors (project-level attribution): Chenyi Li, Wanli Ma, Zichen Wang.

Source header · Attribution source

Chapter02 Definition 2.5-extra-2 (1): a positive steplength α satisfies the Goldstein inexact line-search rule for the one-dimensional profile φ with stored slope datum φPrime0 when 0 < ρ < 1 / 2, 0 < α, and both Goldstein inequalities hold: φ α ≤ φ 0 + ρ * α * φPrime0 and φ 0 + (1 - ρ) * α * φPrime0 ≤ φ α.

class GoldsteinCondition (φ : ℝ → ℝ) (φPrime0 ρ α : ℝ) : Prop where parameters : GoldsteinParameters ρ step_pos : 0 < α core : goldsteinCondition φ φPrime0 ρ α

Definition 2.5.extra.3

Lean contributors (project-level attribution): Chenyi Li, Wanli Ma, Zichen Wang.

Source header · Attribution source

The admissible Wolfe-Powell parameters satisfy 0 < ρ < σ < 1.

class WolfePowellParameters (ρ σ : ℝ) : Prop where rho_pos : 0 < ρ rho_lt_sigma : ρ < σ sigma_lt_one : σ < 1

Definition 2.5.extra.4

Lean contributors (project-level attribution): Chenyi Li, Wanli Ma, Zichen Wang.

Source header · Attribution source

Chapter02 Definition 2.5-extra-4: a backtracking trial-step sequence starts from 1, stays positive, and strictly decreases at each backtracking step.

universe u -- Source/core/bridge triage: -- * source-facing: a successful backtracking line-search step, consisting of a -- backtracking trial-step sequence together with its first accepted index; -- * core/canonical: `IsLeast` on the acceptance set of trial indices; -- * bridge/view: the trial-point map `n ↦ x + α n • d`. class IsBacktrackingStepSequence (α : ℕ → ℝ) : Prop where start : α 0 = 1 step_pos (n : ℕ) : 0 < α n strictReduction (n : ℕ) : α (n + 1) < α n

Definition 2.5.extra.5

Lean contributors (project-level attribution): Chenyi Li, Wanli Ma, Zichen Wang.

Source header · Attribution source

The bounded recent-index window 0, 1, ..., min k mk used by the nonmonotone Armijo reference value at stage k.

variable {E : Type*} -- Source/core/bridge triage: -- * source-facing: the bounded recent-index window and the corresponding nonmonotone Armijo -- reference value formed from the recent objective values; -- * core/canonical: `Finset.Icc` for the window indices and `Finset.sup'` for the finite -- maximum; -- * bridge/view: the membership and unfolding lemmas exposing the explicit bounded-window -- formula from the source text. def nonmonotoneArmijoWindow (k mk : ℕ) : Finset ℕ := Finset.Icc 0 (Nat.min k mk)

Supporting modules

These source modules support the indexed items and are listed separately so the chapter inventory remains complete.

Lean contributors (project-level attribution): Chenyi Li, Wanli Ma, Zichen Wang.

Source header · Attribution source