§3, (3.5) — for methods with
ProvedNonlinCG.FRBound.cos_theta_boundsUnder the hypotheses of Lemma 3.1 — Assumptions 2.1, a method of the form (1.2)–(1.3) with for , steplengths satisfying (2.17) with , and no vanishing gradient — there are positive constants and such that for every
where (2.1).
Thus, for the Fletcher–Reeves method or any method with , is proportional to . The left inequality, combined with the Zoutendijk condition, is what turns a bound on the growth of into convergence in Theorem 3.2.
Formalization Note The paper states existence of ; its derivation from (2.1) and (3.2) gives and , but the statement asserts existence only. The constants may depend on but are uniform in . The hypothesis is that of Lemma 3.1 (the paper divides by ). Global from (1.1), finite-dimensional real inner product space, indices from , positive steplengths, as in the definition file.
import Mathlib import Definitions.Def_NonlinCG_FRBound_Setting
namespace NonlinCG.FRBound
/-- Display (3.5) (Gilbert–Nocedal, INRIA RR-1268, §3, p. 7): under the hypotheses of Lemma 3.1
there are positive constants `c₁, c₂` with `c₁ ‖g_k‖/‖d_k‖ ≤ cos θ_k ≤ c₂ ‖g_k‖/‖d_k‖` for all
`k ≥ 1`. -/
theorem cos_theta_bounds {E : Type*} [NormedAddCommGroup E] [InnerProductSpace ℝ E]
[FiniteDimensional ℝ E] (f : E → ℝ) (hf : ContDiff ℝ 1 f) (β α : ℕ → ℝ) (x d : ℕ → E)
(σ₂ : ℝ) (hA : Assumptions21 f (x 1)) (hrun : IsCGRun f β α x d)
(hβ : ∀ k ≥ 2, |β k| ≤ betaFR f x k)
(hσ : 0 < σ₂ ∧ σ₂ < 1 / 2)
(hls : ∀ k ≥ 1,
|inner ℝ (gradient f (x k + α k • d k)) (d k)| ≤ -σ₂ * inner ℝ (g f x k) (d k))
(hg : ∀ k ≥ 1, g f x k ≠ 0) :
∃ c₁ c₂ : ℝ, 0 < c₁ ∧ 0 < c₂ ∧ ∀ k ≥ 1,
c₁ * (‖g f x k‖ / ‖d k‖) ≤ cosTheta f x d k ∧
cosTheta f x d k ≤ c₂ * (‖g f x k‖ / ‖d k‖) := by sorry
end NonlinCG.FRBound
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.