Lemma 3.1 — with and (2.17), , the directions are descent directions satisfying (3.2)
ProvedNonlinCG.FRBound.lemma_3_1Let satisfy Assumptions 2.1 at . Consider a method of the form (1.2)–(1.3), , (), with , in which every satisfies
and every steplength satisfies condition (2.17), , with . Suppose no gradient vanishes. Then every is a descent direction, , and for every
At all three terms equal . Since , the upper bound gives the sufficient descent condition (2.18), and the two bounds control the growth of in the proof of Theorem 3.2.
Formalization Note The paper does not state ; it divides by in (3.2) and calls a descent direction, which is impossible when , so we assume for all . Only condition (2.17) is assumed, as in the paper ("the Wolfe condition (2.17)"), with the range from (2.17). The paper's standing assumption (1.1) "f is smooth" is taken as global . Indices start at ; is a sum over . The finite-dimensional real inner product space and positive steplengths are as in the definition file.
import Mathlib import Definitions.Def_NonlinCG_FRBound_Setting
namespace NonlinCG.FRBound
/-- Lemma 3.1 (Gilbert–Nocedal, INRIA RR-1268, p. 7): for a method (1.2)–(1.3) with
`|β_k| ≤ β_k^{FR}` (3.1) for `k ≥ 2` and steplengths satisfying (2.17) with `0 < σ₂ < 1/2`, every
`d_k` is a descent direction and
`−Σ_{j=0}^{k−1} σ₂^j ≤ ⟨g_k, d_k⟩/‖g_k‖² ≤ −2 + Σ_{j=0}^{k−1} σ₂^j` for `k ≥ 1` (3.2).
The hypothesis `g_k ≠ 0` is implicit in the paper, which divides by `‖g_k‖²`. -/
theorem lemma_3_1 {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) :
∀ k ≥ 1, inner ℝ (g f x k) (d k) < 0 ∧
-(∑ j ∈ Finset.range k, σ₂ ^ j) ≤ inner ℝ (g f x k) (d k) / ‖g f x k‖ ^ 2 ∧
inner ℝ (g f x k) (d k) / ‖g f x k‖ ^ 2 ≤ -2 + ∑ j ∈ Finset.range k, σ₂ ^ j := by sorry
end NonlinCG.FRBound
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.