Chapter 04 — Conjugate Gradient Method

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

Exercise 4.1

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

Source header · Attribution source

Chapter04 Exercise 4.1: if G is a symmetric positive definite real matrix and p : Fin n → Fin n → ℝ is linearly independent, then the family obtained from the textbook recurrence d₁ = p₁ and d_{k+1} = p_{k+1} - ∑_{i=1}^k ((p_{k+1}ᵀ G d_i) / (d_iᵀ G d_i)) • d_i is G-conjugate.

open scoped BigOperators variable {n : ℕ} local notation "Vector" => Fin n → ℝ theorem chapter04Exercise41_isConjugateFamily (G : Matrix (Fin n) (Fin n) ℝ) (hG : G.PosDef) (p : Fin n → Vector) (hp : LinearIndependent ℝ p) : G.IsConjugateFamily (chapter04Exercise41Directions G p)

Exercise 4.2

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

Source header · Attribution source

Chapter04 Exercise 4.2 (1): for f x = x 0 ^ 2 + 2 * x 1 ^ 2 - 2 * x 0 * x 1 + 2 * x 1 + 2, the Fletcher-Reeves conjugate-gradient run from (0, 0)ᵀ reaches !₂[-1, -1] after the two explicit exact line-search steps recorded above, and that point is a global minimizer.

open Filter Topology

-- Chapter 4 already owns the canonical conjugate-gradient iterative-scheme record and the
-- Fletcher-Reeves coefficient used by its update rule. This exercise keeps its explicit objective
-- functions and bridges the quartic run to that owner, while retaining the source exercise's
-- concrete iterate and convergence statements.
local notation "Point" => EuclideanSpace ℝ (Fin 2)
theorem quadraticFletcherReevesReachesMinimizerFromOrigin :
    exercise42QuadraticSecondIterate = exercise42QuadraticMinimizer ∧
      IsMinOn exercise42QuadraticObjective Set.univ exercise42QuadraticMinimizer

Exercise 4.3

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

Source header · Attribution source

Chapter04 Exercise 4.3: using the Fletcher-Reeves conjugate-gradient method, minimize rosenbrockFunction from Appendix 1.1; using the Polak-Ribiere-Polyak conjugate-gradient method, minimize extendedRosenbrockFunction from Appendix 1.2.

open scoped BigOperators -- Domain sampling: -- * source-facing owner upstream: `Chapter03.Exercise_3_4.rosenbrockFunction` -- * heavier project packaging: `OptimizationProblem` -- * nearby concrete-objective style: `Chapter04.Exercise_4_2` -- The present exercise only names benchmark objectives, so the right public surface is the -- objective functions themselves, not a packaged optimization problem or public point aliases. #check rosenbrockFunction

Exercise 4.4

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

Source header · Attribution source

Chapter04 Exercise 4.4 (2): for a quadratic objective with positive-definite Hessian G, if the first n stages of a Dixon-CG run are nonstationary, then the first n search directions form a G-conjugate family.

open Matrix
variable {n : ℕ}
local notation "Point" => ConjugateGradientPoint n
namespace ConjugateGradientRun.Dixon
theorem quadraticDirections_isConjugateFamily
    {G : Matrix (Fin n) (Fin n) ℝ} (hG : G.PosDef) {b : Point} {c : ℝ}
    {method : ConjugateGradientRun Point (quadraticObjective G b c)}
    (hDixon : method.Dixon)
    (h_nonstationary : ∀ k : ℕ, k < n → method.g k ≠ 0) :
    G.IsConjugateFamily (fun i : Fin n ↦ method.d i)

Exercise 4.5

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

Source header · Attribution source

Chapter04 Exercise 4.5 belongs to the recall layer: the stronger owner BealeThreeTermConjugateGradientMethod already provides the exact denominator and formula fields for (4.2.38) and the two branches of (4.2.39), so this file reuses those canonical declarations directly instead of restating them over the inherited generic run data.

#check BealeThreeTermConjugateGradientMethod.betaDenominatorNonzero

Exercise 4.6

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

Source header · Attribution source

Chapter04 Exercise 4.6 (1): for the quadratic objective x ↦ (1 / 2) * xᵀ G x - bᵀ x with positive-definite Hessian G, the exact line-search steplength at a nonterminal stage has the textbook form α_k = -(r_kᵀ d_k) / (d_kᵀ G d_k). The chapter owner uses the equivalent linear term -b for the same objective.

open Matrix
variable {n : ℕ}
local notation "Point" => ConjugateGradientPoint n

-- Domain-style sampling summary:
-- * primary domain: finite-dimensional linear algebra for the linear conjugate-gradient method
--   on quadratic objectives;
-- * inspected owner declarations in the chapter domain:
--   `ConjugateGradientIterativeScheme`,
--   `LinearConjugateGradientMethod`,
--   `LinearConjugateGradientMethod.nonterminalStep`,
--   `posDefDistinctEigenvalueCount_le`;
-- * owner choice: `LinearConjugateGradientMethod` is the source-facing quadratic specialization,
--   built on top of the chapter owner `ConjugateGradientIterativeScheme`; the exercise formulas
--   below are thin bridge/view consequences of that owner;
-- * primitive data vs derived API: the run sequences and Fletcher-Reeves recurrence are
--   primitive in the imported owner, while exact line search, nonterminal-step identities,
--   conjugacy, and residual-direction relations are derived API and should not be duplicated
--   locally.
theorem chapter04Exercise46_linearConjugateGradientStepSizeFormula
    (G : Matrix (Fin n) (Fin n) ℝ) (hG : G.PosDef) (b : Point)
    (A : LinearConjugateGradientMethod G (-b)) {k : ℕ} (h_nonterminal : A.g k ≠ 0) :
    A.α k =
      -dotProduct (A.g k) (A.d k) /
        dotProduct (A.d k) (Matrix.toEuclideanLin G (A.d k))

Exercise 4.7

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

Source header · Attribution source

Chapter04 Exercise 4.7: using the linear conjugate gradient method, minimize quadraticObjective (hilbertMatrix n) (hilbertConjugateGradientOffset n) 0 with initial point hilbertInitialPoint n; equivalently, solve hilbertMatrix n.mulVec x + hilbertConjugateGradientOffset n = 0` in the concrete cases n ∈ hilbertExerciseDimensions.

variable (n : ℕ)
#check hilbertMatrix 5

4.1 — Conjugate Direction Methods

Definition 4.1.1

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

Source header · Attribution source

Chapter04 Definition 4.1.1 (1): for a symmetric positive definite real matrix G, a family d : Fin m → Fin n → ℝ is G-conjugate when every d i is nonzero and d iᵀ G d j = 0 for all i ≠ j.

namespace Matrix variable {m n : ℕ} class IsConjugateFamily (G : Matrix (Fin n) (Fin n) ℝ) (d : Fin m → Fin n → ℝ) : Prop where nonzero : ∀ i, d i ≠ 0 iIsOrtho : G.toBilin'.iIsOrtho d

Algorithm 4.1.2

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

Source header · Attribution source

Chapter04 Algorithm 4.1.2: a nonterminal step uses exact line search, the iterate update, and a nonzero G-conjugate next direction.

open Matrix
theorem GeneralConjugateDirectionMethod.nonterminalStep {n : ℕ}
    {f : ConjugateDirectionPoint n → ℝ}
    (A : GeneralConjugateDirectionMethod n f) {k : ℕ}
    (hNotStopped : A.ε < ‖A.g k‖) :
    IsExactLineSearchStepOnNonnegativeRay f (A.x k) (A.d k) (A.α k) ∧
      A.x (k + 1) = A.x k + A.α k • A.d k ∧
      A.d (k + 1) ≠ 0 ∧
      ∀ j : ℕ, j ≤ k →
        dotProduct (A.d (k + 1)) (A.G.mulVec (A.d j)) = 0

Theorem 4.1.3

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

Source header · Attribution source

Chapter04 Theorem 4.1.3 (1): for a quadratic objective with positive-definite Hessian G, the conjugate direction method has terminated by stage n, and the iterate A n is a global minimizer after the first n exact line searches.

open Matrix
open scoped BigOperators
variable {n : ℕ}
local notation "Vector" => ConjugateDirectionPoint n
theorem conjugateDirectionMethod_terminates
    (G : Matrix (Fin n) (Fin n) ℝ) (b : Vector) (c : ℝ)
    (A : GeneralConjugateDirectionMethod n (quadraticObjective G b c))
    (hMethod : IsQuadraticConjugateDirectionMethod G b c A) :
    A.terminatedAt n ∧ IsMinOn (quadraticObjective G b c) Set.univ (A n)

4.2 — Conjugate Gradient Method

Theorem 4.2.1

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

Source header · Attribution source

Chapter04 Theorem 4.2.1 (1): for a positive-definite quadratic function, the linear conjugate-gradient recurrence terminates by the canonical bound m := posDefDistinctEigenvalueCount hG, where m is the number of distinct eigenvalues of G.

open Matrix
variable {n : ℕ}
local notation "Point" => ConjugateGradientPoint n
theorem linearConjugateGradient_terminatesBy_distinctEigenvalueCount
    (G : Matrix (Fin n) (Fin n) ℝ) (hG : G.PosDef) (b : Point)
    (A : LinearConjugateGradientMethod G b) :
    ∃ k : ℕ, k ≤ posDefDistinctEigenvalueCount hG ∧ A.IsFirstTerminatingIndex k

Algorithm 4.2.2

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

Source header · Attribution source

Chapter04 Algorithm 4.2.2 is the r = n specialization of the reusable restart-period owner PeriodicRestartFRConjugateGradientMethod.

abbrev RestartFRConjugateGradientMethod (n : ℕ)
    (f : ConjugateGradientPoint n → ℝ) :=
  PeriodicRestartFRConjugateGradientMethod n n f

Algorithm 4.2.3

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

Source header · Attribution source

Chapter04 Algorithm 4.2.3: Beale's three-term conjugate-gradient method on ℝ^n extends the generic nonlinear conjugate-gradient run data in ConjugateGradientRun by adding the stopping tolerance ε, the Beale coefficients β and γ, the tentative Step 7 directions, and the restart bookkeeping from Steps 5, 8, and 9. The inherited fields provide the common initial point, iterates, explicit gradients, search directions, step sizes, and gradient-at-iterate specification. The Beale-specific fields record that the initialization satisfies d 0 = -g 0 whenever the initial gradient is nonterminal, every nonterminal step uses exact line search and the iterate update, the Step 5 restart test chooses restartIndexBeforeFallback, Step 7 forms directionBeforeFallback using (4.2.37), Step 8 preserves a recent restart, Step 9 either accepts that tentative direction or falls back to d k = -g k + β k • d (k - 1), and the textbook formulas (4.2.38) and (4.2.39) hold whenever their denominators are required.

structure BealeThreeTermConjugateGradientMethod (n : ℕ)
    (f : ConjugateGradientPoint n → ℝ)
    extends ConjugateGradientRun n f where
  ε : ℝ
  β : ℕ → ℝ
  γ : ℕ → ℝ
  directionBeforeFallback : ℕ → ConjugateGradientPoint n
  restartIndexBeforeFallback : ℕ → ℕ
  t : ℕ → ℕ
  eps_pos : 0 < ε
  restartIndexBeforeFallback_zero : restartIndexBeforeFallback 0 = 0
  t_zero : t 0 = 0
  initialDirection (hactive : ε < ‖g 0‖) : d 0 = -g 0
  exactLineSearch (k : ℕ) (hactive : ε < ‖g k‖) :
    IsExactLineSearchStepOnNonnegativeRay f (x k) (d k) (α k)
  update (k : ℕ) (hactive : ε < ‖g k‖) : x (k + 1) = x k + α k • d k
  restartIndexBeforeFallback_of_restartCriterion
      (k : ℕ) (hactive : ε < ‖g k‖)
      (hrestart : BealeThreeTermRestartCriterion g t k) :
      restartIndexBeforeFallback k = k - 1
  restartIndexBeforeFallback_of_not_restartCriterion
      (k : ℕ) (hk : 0 < k) (hactive : ε < ‖g k‖)
      (hnotRestart : ¬ BealeThreeTermRestartCriterion g t k) :
      restartIndexBeforeFallback k = t (k - 1)
  directionBeforeFallbackFormula
      (k : ℕ) (hk : 0 < k) (hactive : ε < ‖g k‖) :
      directionBeforeFallback k = -g k + β k • d (k - 1) +
        γ k • d (restartIndexBeforeFallback k)
  finalRestartIndex_of_recentRestart
      (k : ℕ) (hk : 0 < k) (hactive : ε < ‖g k‖)
      (hrecent : k ≤ restartIndexBeforeFallback k + 1) :
      t k = restartIndexBeforeFallback k
  finalRestartIndex_of_acceptedDirection
      (k : ℕ) (hk : 0 < k) (hactive : ε < ‖g k‖)
      (hstrict : restartIndexBeforeFallback k + 1 < k)
      (haccepted : BealeThreeTermAcceptedDirectionTest g directionBeforeFallback k) :
      t k = restartIndexBeforeFallback k
  finalRestartIndex_of_stepNineFallback
      (k : ℕ) (hk : 0 < k) (hactive : ε < ‖g k‖)
      (hstrict : restartIndexBeforeFallback k + 1 < k)
      (hreject : ¬ BealeThreeTermAcceptedDirectionTest g directionBeforeFallback k) :
      t k = k - 1
  finalDirection_of_recentRestart
      (k : ℕ) (hk : 0 < k) (hactive : ε < ‖g k‖)
      (hrecent : k ≤ restartIndexBeforeFallback k + 1) :
      d k = directionBeforeFallback k
  finalDirection_of_acceptedDirection
      (k : ℕ) (hk : 0 < k) (hactive : ε < ‖g k‖)
      (hstrict : restartIndexBeforeFallback k + 1 < k)
      (haccepted : BealeThreeTermAcceptedDirectionTest g directionBeforeFallback k) :
      d k = directionBeforeFallback k
  finalDirection_of_stepNineFallback
      (k : ℕ) (hk : 0 < k) (hactive : ε < ‖g k‖)
      (hstrict : restartIndexBeforeFallback k + 1 < k)
      (hreject : ¬ BealeThreeTermAcceptedDirectionTest g directionBeforeFallback k) :
      d k = -g k + β k • d (k - 1)
  betaDenominatorNonzero
      (k : ℕ) (hk : 0 < k) (hactive : ε < ‖g k‖) :
      BealeThreeTermBetaDenominatorNonzero g d k
  betaFormula
      (k : ℕ) (hk : 0 < k) (hactive : ε < ‖g k‖) :
      β k = bealeThreeTermBeta (g (k - 1)) (g k) (d (k - 1))
  gammaFormula_of_recentRestart
      (k : ℕ) (hk : 0 < k) (hactive : ε < ‖g k‖)
      (hrecent : k = restartIndexBeforeFallback k + 1) :
      γ k = 0
  gammaDenominatorNonzero
      (k : ℕ) (hk : 0 < k) (hactive : ε < ‖g k‖)
      (hstrict : restartIndexBeforeFallback k + 1 < k) :
      BealeThreeTermGammaDenominatorNonzero g d (restartIndexBeforeFallback k)
  gammaFormula
      (k : ℕ) (hk : 0 < k) (hactive : ε < ‖g k‖)
      (hstrict : restartIndexBeforeFallback k + 1 < k) :
      γ k = bealeThreeTermGamma g d (restartIndexBeforeFallback k) k

Algorithm 4.2.extra.1

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

Source header · Attribution source

The ambient Euclidean space ℝ^n for the conjugate-gradient iterative scheme.

abbrev ConjugateGradientPoint (n : ℕ) := EuclideanSpace ℝ (Fin n)

Algorithm 4.2.extra.2

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

Source header · Attribution source

Chapter04 Algorithm 4.2-extra-2 is already owned by LinearConjugateGradientMethod in Theorem_4_2_1.lean. This file therefore stays at the recall layer and reuses that owner directly, rather than restating its fields as a second conjunction-style specification theorem.

#check LinearConjugateGradientMethod

Algorithm 4.2.extra.3

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

Source header · Attribution source

Chapter04 Algorithm 4.2-extra-3: a preconditioned conjugate gradient method for the linear system G.mulVec x + b = 0 with preconditioner W and initial point x0 consists of iterates x k, residuals/gradients r k, preconditioned residuals v k, search directions d k, step sizes α k, and recurrence coefficients β k. The initialization is x 0 = x0, r 0 = G.mulVec x0 + b, v k = W⁻¹.mulVec (r k), and d 0 = -v 0. For every k, the step size, iterate, residual, recurrence coefficient, and next direction satisfy the explicit preconditioned conjugate-gradient recurrences from the textbook at each nonterminal stage r k ≠ 0, while a terminating stage propagates the zero residual, zero direction, and stationary iterate thereafter. The denominator conditions record that the fractions defining α k and β k are well-defined on nonterminal steps. The field preconditioner_isUnit records the source's use of W⁻¹.

variable {n : ℕ} local notation "Vector" => Fin n → ℝ structure PreconditionedConjugateGradientMethod (G W : Matrix (Fin n) (Fin n) ℝ) (b x0 : Vector) where x : ℕ → Vector r : ℕ → Vector v : ℕ → Vector d : ℕ → Vector α : ℕ → ℝ β : ℕ → ℝ preconditioner_isUnit : IsUnit W x_zero : x 0 = x0 residual_zero : r 0 = G.mulVec x0 + b preconditionedResidual_eq : ∀ k : ℕ, v k = W⁻¹.mulVec (r k) direction_zero : d 0 = -v 0 stepSize_denom_ne_zero : ∀ k : ℕ, r k ≠ 0 → dotProduct (d k) (G.mulVec (d k)) ≠ 0 stepSize_eq : ∀ k : ℕ, r k ≠ 0 → α k = dotProduct (r k) (v k) / dotProduct (d k) (G.mulVec (d k)) iterate_eq : ∀ k : ℕ, r k ≠ 0 → x (k + 1) = x k + α k • d k residual_eq : ∀ k : ℕ, r k ≠ 0 → r (k + 1) = r k + α k • G.mulVec (d k) beta_denom_ne_zero : ∀ k : ℕ, r k ≠ 0 → dotProduct (r k) (v k) ≠ 0 beta_eq : ∀ k : ℕ, r k ≠ 0 → β k = dotProduct (r (k + 1)) (v (k + 1)) / dotProduct (r k) (v k) direction_eq : ∀ k : ℕ, r k ≠ 0 → d (k + 1) = -v (k + 1) + β k • d k residual_stationary : ∀ k t : ℕ, r k = 0 → k ≤ t → r t = 0 direction_zero_of_terminated : ∀ k t : ℕ, r k = 0 → k ≤ t → d t = 0 iterate_stationary : ∀ k t : ℕ, r k = 0 → k ≤ t → x t = x k

Algorithm 4.2.extra.4

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

Source header · Attribution source

The Polak-Ribiere-Polyak coefficient β_k = ⟪g_(k + 1), g_(k + 1) - g_k⟫ / ⟪g_k, g_k⟫.

variable {E : Type*} [NormedAddCommGroup E] [InnerProductSpace ℝ E]
def polakRibierePolyakBeta (gPrev gNext : E) : ℝ :=
  inner ℝ gNext (gNext - gPrev) / inner ℝ gPrev gPrev

4.3 — Convergence of Conjugate Gradient Methods

Theorem 4.3.1

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

Source header · Attribution source

Chapter04 Theorem 4.3.1 (1): if a Fletcher-Reeves sequence encoded as FletcherReevesMethod Point f terminates at stage k, then the final point A.x k is a stationary point of f. This is the exact owner theorem FletcherReevesMethod.isStationaryPoint_of_terminatedAt, so the file stays at the recall layer for clause (1) instead of keeping a parallel local wrapper.

open Filter

-- Domain sampling pass:
-- * primary domain: nonlinear conjugate-gradient runs on `ℝ^n` with exact line search;
-- * inspected chapter owners in this domain:
--   - `FletcherReevesMethod` from `Algorithm_4_2_extra_1` for the source-facing owner that
--     bundles the recurrence together with post-termination constancy;
--   - `FletcherReevesMethod.x_mem_lowerLevelSetOn_univ` from `Algorithm_4_2_extra_1` for the
--     exact-line-search lower-level-set invariance already attached to the source-facing owner;
--   - `FletcherReevesMethod.hasStationaryContinuation` from `Algorithm_4_2_extra_1` for the
--     owner-level bridge from the bundled post-termination field to the generic run API;
--   - `IsStationaryPoint` from `Chapter01.Definition_1_4_7` for the canonical stationary-point
--     owner that bundles vanishing gradient with differentiability.
--   - `Bornology.IsBounded.isCompact_closure` together with `IsCompact.tendsto_subseq` from
--     mathlib for the canonical bounded-sequence subsequence-extraction route in Euclidean space;
--   - `mem_closure_of_tendsto` together with `ContDiffOn.contDiffAt` from mathlib for the
--     set-neighborhood-to-pointwise-regularity bridge at an accumulation point
-- * best owner abstraction here: `ConjugateGradientRun` for primitive run data, with
--   `FletcherReevesMethod` as the source-facing exact-line-search owner and
--   `IsStationaryPoint` as the core stationary-point owner.
-- * source/core/bridge triage:
--   - `source-facing`: the numbered Fletcher-Reeves termination and accumulation-point results;
--   - `core/canonical`: `IsStationaryPoint`;
--   - `bridge/view`: the passage from `ContDiffOn` regularity on an open neighborhood of
--     `closure LevelSet` to the pointwise `ContDiffAt` input used by the stationary conclusion.
-- Primitive data vs derived API:
-- * primitive data: `x0`, `x`, `g`, `d`, `α`, and the `HasGradientAt` witnesses already owned
--   by `ConjugateGradientRun`;
-- * derived API here: the source-facing stationary and accumulation-point consequences that use
--   the owner-level lower-level-set invariance together with
--   `Bornology.IsBounded.isCompact_closure` and `IsCompact.tendsto_subseq`.
variable {n : ℕ}
local notation "Point" => ConjugateGradientPoint n
variable {f : Point → ℝ} (A : FletcherReevesMethod Point f)
local notation "LevelSet" => lowerLevelSetOn Set.univ f A.x0
#check fun (A : FletcherReevesMethod Point f) {k : ℕ} (hk : A.terminatedAt k) ↦
  (A.isStationaryPoint_of_terminatedAt hk : IsStationaryPoint f (A.x k))

Theorem 4.3.2

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

Source header · Attribution source

Chapter04 Theorem 4.3.2 (stationary accumulation point for the Crowder-Wolfe conjugate-gradient method): let method be the restart Fletcher-Reeves / Crowder-Wolfe method from Algorithm 4.2.2. If the initial lower level set LevelSet is bounded, f is C¹ on that level set, and gradient f is Lipschitz there, then the iterate sequence (method k).x has a convergent subsequence whose limit is stationary, packaged by RestartFRConjugateGradientStationaryAccumulationPoint f method.

open Filter
variable {n : ℕ}
local notation "Point" => ConjugateGradientPoint n
variable (f : Point → ℝ) (method : RestartFRConjugateGradientMethod n f)
local notation "LevelSet" => lowerLevelSetOn Set.univ f method.x0

-- Domain sampling pass:
-- * primary domain: restart Fletcher-Reeves / Crowder-Wolfe nonlinear conjugate-gradient
--   methods on `ℝ^n` with exact line search;
-- * inspected owner declarations in this domain:
--   - `RestartFRConjugateGradientMethod` from `Algorithm_4_2_2` for the source-facing
--     Crowder-Wolfe restart method data;
--   - `PeriodicRestartFRConjugateGradientMethod` from `Algorithm_4_2_2` for the reusable
--     period-`r` owner that specializes to the source threshold `r = n`;
--   - `RestartFRRestartStep` / `RestartFRContinueStep` from `Algorithm_4_2_2` for the
--     canonical restart-vs-continue branch data already attached to that owner;
--   - `lowerLevelSetOn` from `Chapter01.Theorem_1_3_19` for the canonical lower-level-set
--     owner used by nearby Chapter 4 convergence theorems.
-- * best owner abstraction here: the source-facing owner
--   `RestartFRConjugateGradientMethod n f`;
-- * layer targeted by the rewrite: `source-facing`, because Algorithm 4.2.2 already owns the
--   Crowder-Wolfe restart data and no extra wrapper is mathematically needed.
-- Primitive data vs derived API:
-- * primitive data: the initial point `x0`, restart states `method k`, exact line search,
--   iterate updates, gradients, and restart/continuation branch laws already owned by
--   `RestartFRConjugateGradientMethod`;
-- * derived API here: only the accumulation-point existence and stationarity conclusion under
--   bounded lower-level-set and local smoothness assumptions on that canonical owner.
theorem crowderWolfeConjugateGradient_exists_stationaryAccumulationPoint
    (hLevelSetBounded : Bornology.IsBounded LevelSet)
    (hC1 : ContDiffOn ℝ 1 f LevelSet)
    (hGradLipschitz : ∃ L : NNReal, LipschitzOnWith L (gradient f) LevelSet) :
    Nonempty (RestartFRConjugateGradientStationaryAccumulationPoint f method)

Theorem 4.3.3

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

Source header · Attribution source

Chapter04 Theorem 4.3.3: let f : ℝ^n → ℝ be twice continuously differentiable, let method be a Polak-Ribiere-Polyak conjugate-gradient run with exact line search, and assume the source stationary-step condition x (k + 1) = x k whenever g k = 0. Assume there is a constant m > 0 such that the Hessian quadratic form has the canonical lower-level-set bound HasLowerLevelHessianLowerBound Set.univ f method.x0 m on lowerLevelSetOn Set.univ f method.x0 = {x | f x ≤ f method.x0}. Then the generated sequence converges to a global minimizer xStar of f, and every global minimizer of f coincides with xStar. The boundedness clause in the source assumptions is redundant once this lower Hessian bound is imposed on the canonical lower level set.

open Filter
variable {n : ℕ}
local notation "Point" => ConjugateGradientPoint n
theorem polakRibierePolyakConjugateGradient_tendsto_uniqueGlobalMinimizer
    (f : Point → ℝ)
    (hC2 : ContDiff ℝ 2 f)
    (method : PolakRibierePolyakConjugateGradientMethod n f)
    (hStationaryUpdate : ∀ k : ℕ, method.g k = 0 → method.x (k + 1) = method.x k)
    (hLevelHessian : ∃ m > 0, HasLowerLevelHessianLowerBound Set.univ f method.x0 m) :
    ∃ xStar : Point,
      IsMinOn f Set.univ xStar ∧
        Tendsto method.x atTop (nhds xStar) ∧
        ∀ y : Point, IsMinOn f Set.univ y → y = xStar

Theorem 4.3.4

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

Source header · Attribution source

Chapter04 Theorem 4.3.4 (1): for a Fletcher-Reeves conjugate-gradient run whose step sizes satisfy the strong Wolfe-Powell rule, the estimate `-∑ j in Finset.range (k + 1), hWolfe.σ ^ j ≤ method.directionRatio k ≤ -2 + ∑ j in Finset.range (k + 1), hWolfe.σ ^ j` holds at each nonterminated stage k; the nontermination side condition is made explicit because method.directionRatio k uses ‖method.g k‖² in the denominator.

open scoped BigOperators
variable {E : Type*} [NormedAddCommGroup E] [InnerProductSpace ℝ E] [CompleteSpace E]
variable {f : E → ℝ}

-- Domain sampling pass:
-- * source-facing owner for the Fletcher-Reeves recurrence:
--   `ConjugateGradientIterativeScheme E` from `Algorithm_4_2_extra_1`
-- * core/canonical owners reused here:
--   `ConjugateGradientRun E` for the generic nonlinear conjugate-gradient run data,
--   `lineSearchObjective` together with `deriv_lineSearchObjective_apply` for the accepted
--   one-dimensional profile and its canonical derivative, and
--   `StrongWolfeCondition`, `WolfePowellCondition`, and `WolfePowellParameters` from Chapter 2
--   for the accepted inexact-line-search rules
-- * bridge/view added here: `ConjugateGradientRun.WolfePowell` and
--   `ConjugateGradientRun.StrongWolfePowell`, which record the weak and strong
--   Wolfe-Powell rules on a generic run together with the iterate update, leaving the
--   Fletcher-Reeves-specific `β` recurrence in `ConjugateGradientIterativeScheme`
-- Primitive run data remain the iterate, gradient, direction, and step-size sequences together
-- with `HasGradientAt`; the weak- and strong-Wolfe acceptance data are run-level bridges built
-- on the canonical derivative of `lineSearchObjective`, while the
-- normalized direction-ratio API below remains theorem-specific derived data.
theorem fletcherReeves_directionRatio_bounds
    (method : ConjugateGradientIterativeScheme E f)
    (hWolfe : ConjugateGradientRun.StrongWolfePowell f method.toConjugateGradientRun) (k : ℕ)
    (hk : ¬ method.terminatedAt k) :
    -(Finset.sum (Finset.range (k + 1)) fun j ↦ hWolfe.σ ^ j) ≤
      method.toConjugateGradientRun.directionRatio k ∧
      method.toConjugateGradientRun.directionRatio k ≤
        -2 + Finset.sum (Finset.range (k + 1)) (fun j ↦ hWolfe.σ ^ j)

Theorem 4.3.5

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

Source header · Attribution source

Chapter04 Theorem 4.3.5: let f : ℝ^n → ℝ be twice continuously differentiable, assume the initial lower level set lowerLevelSetOn Set.univ f method.x0 is bounded, and assume method is a Fletcher-Reeves conjugate-gradient run with strong Wolfe-Powell parameters 0 < ρ < σ < 1 / 2, allowing finite termination at a stationary point. Then the method is globally convergent in the source sense: liminf ‖gradient f (x_k)‖ = 0.

open Filter
variable {n : ℕ}
local notation "Point" => ConjugateGradientPoint n
theorem fletcherReevesConjugateGradient_liminf_gradientNorm_eq_zero
    (f : Point → ℝ) (hC2 : ContDiff ℝ 2 f)
    (method : ConjugateGradientIterativeScheme n f)
    (hWolfe : ConjugateGradientRun.StrongWolfePowell f method.toConjugateGradientRun)
    (hLevelSetBounded : Bornology.IsBounded (lowerLevelSetOn Set.univ f method.x0)) :
    liminf (fun k : ℕ ↦ ‖gradient f (method.x k)‖) atTop = 0

Theorem 4.3.6

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

Source header · Attribution source

Chapter04 Theorem 4.3.6 (1): in a Dai-Yuan conjugate-gradient run with Wolfe-Powell steps, every nonstationary search direction is a descent direction at the current iterate, expressed through the canonical owner IsDescentDirectionAt f (method.x k) (method.d k).

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

-- Domain sampling pass:
-- * primary domain: nonlinear conjugate-gradient runs on a real complete inner-product space
--   with Wolfe-Powell inexact line
--   search and Dai-Yuan direction updates
-- * inspected owner declarations in this domain:
--   - `ConjugateGradientRun E` from `Algorithm_4_2_extra_1` for the primitive nonlinear
--     conjugate-gradient run data and the `HasGradientAt`-backed gradient interface
--   - `ConjugateGradientRun.gradient_eq` from `Algorithm_4_2_extra_1` for the canonical bridge
--     from recorded gradients `method.g k` to the owner `gradient f (method.x k)`
--   - `ConjugateGradientRun.HasStationaryContinuation` from `Algorithm_4_2_extra_1` for the
--     canonical post-termination stationarity bridge on the infinite-sequence run owner
--   - `ConjugateGradientRun.WolfePowell` and `ConjugateGradientRun.StrongWolfePowell` from
--     `Theorem_4_3_4` as the run-level Wolfe bridges layered on the existing run owner
--   - `IsDescentDirectionAt` from `Chapter01.Definition_1_4_3` as the canonical owner of the
--     descent-direction notion used by the first theorem
--   - `WolfePowellParameters` from Chapter 2 as the canonical owner of the admissible
--     Wolfe-Powell parameter inequalities
-- * best owner abstraction here: the chapter owner `ConjugateGradientRun`, with a Dai-Yuan
--   bridge carrying only the Wolfe-Powell and Dai-Yuan-specific step laws
-- * layer targeted by the rewrite: `source-facing` theorem surfaces over the `bridge/view`
--   owner `ConjugateGradientRun.DaiYuan`
-- Primitive data vs derived API:
-- * primitive data: the initial point, iterate sequence, explicit gradient sequence, search
--   directions, step sizes, and `HasGradientAt` witnesses already owned by
--   `ConjugateGradientRun`
-- * derived API here: the canonical weak-Wolfe acceptance predicate on the accepted line-search
--   profile together with the canonical post-termination stationarity bridge, the nonvanishing
--   Dai-Yuan denominator, and the Dai-Yuan direction update
namespace ConjugateGradientRun.DaiYuan
variable {method : ConjugateGradientRun E f}
local notation "LevelSet" => lowerLevelSetOn Set.univ f method.x0
theorem descentDirection
    (hDaiYuan : DaiYuan f method) (k : ℕ) (hk : method.g k ≠ 0) :
    IsDescentDirectionAt f (method.x k) (method.d k)

Theorem 4.3.7

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

Source header · Attribution source

Chapter04 Theorem 4.3.7 (1): let method be a PRP-CG run, let xStar = x* be the source limit point, and package the source standing hypotheses into h : PolakRibierePolyakConjugateGradientMethod.HasRestartRateAssumptions method r xStar: restart every r > 0 steps, every iterate stays in the bounded lower level set lowerLevelSetOn Set.univ f method.x0 carrying the (A1)/(A2) Hessian bounds, the iterates converge to xStar, and xStar is stationary for f. Then the source n-step quadratic rate conclusion (4.3.42) is encoded canonically as a big-O statement for the error vector, with right-hand side the squared source error norm dist (x_(k r), x*)². This is equivalent to the displayed source norm formula ‖x_(k r + n) - x*‖ = O(‖x_(k r) - x*‖²).

open Filter
variable {n : ℕ}
local notation "Point" => ConjugateGradientPoint n

-- Domain sampling pass:
-- * primary domain: local asymptotic rate statements for nonlinear conjugate-gradient restart
--   methods on `ℝ^n`;
-- * inspected owner declarations in this domain:
--   - `PolakRibierePolyakConjugateGradientMethod` from `Algorithm_4_2_extra_4`;
--   - `PeriodicRestartFRConjugateGradientMethod` from `Algorithm_4_2_2`;
--   - `HasBoundedLowerLevelSetHessianBounds` from `Assumption_4_3_extra_1`;
--   - `IsStationaryPoint` from `Chapter01.Definition_1_4_7`;
-- * best owner abstraction: keep the four labeled rate theorems source-facing, but factor their
--   repeated standing hypotheses into small `Prop`-valued restart-rate assumption owners over
--   the existing chapter method owners;
-- * layer targeted here: `source-facing` theorem statements over those restart-rate owners, with
--   mathlib's asymptotic owners `=O[atTop]` and `=o[atTop]` used directly instead of local
--   witness wrappers;
-- * primitive data: the method, restart period, distinguished point `xStar`, lower-level-set
--   membership of the iterates, convergence to `xStar`, and stationarity of `xStar`;
-- * derived API here: the source quadratic and superquadratic asymptotic conclusions, together
--   with the boundedness companion inherited from the Hessian-bound assumption owner.
variable (f : Point → ℝ)
variable (method : PolakRibierePolyakConjugateGradientMethod n f)
variable (r : ℕ) (xStar : Point)
theorem polakRibierePolyakRestart_nStepQuadraticRate
    (h : PolakRibierePolyakConjugateGradientMethod.HasRestartRateAssumptions method r xStar) :
    ((fun k : ℕ ↦ (method.x (k * r + n) : Point) - xStar) : ℕ → Point) =O[atTop]
      ((fun k : ℕ ↦ dist (method.x (k * r)) xStar ^ (2 : ℕ)) : ℕ → ℝ)

Assumption 4.3.extra.1

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

Source header · Attribution source

On Set.univ, the canonical lower-level-set owner is exactly the usual set {x | f x ≤ f x0}.

variable {n : ℕ}
local notation "Point" => EuclideanSpace ℝ (Fin n)
@[simp] theorem mem_lowerLevelSetOn_univ
    (f : Point → ℝ) (x0 x : Point) :
    x ∈ lowerLevelSetOn Set.univ f x0 ↔ f x ≤ f x0