Theorem 2.1 (i) — Zoutendijk: descent directions with Wolfe steps give
ProvedNonlinCG.FRBound.theorem_2_1_wolfeLet satisfy Assumptions 2.1 at the starting point : the level set is bounded and has a Lipschitz continuous gradient on an open neighbourhood of . Consider any iteration , (1.3), with arbitrary directions , where each is a descent direction, , and each positive steplength satisfies the Wolfe conditions (2.4)–(2.5) with :
Then, with the angle between and ,
This is the Zoutendijk condition (2.7), the basic tool of the paper's global convergence analysis: it is the only consequence of the line search that the proof of Theorem 3.2 uses besides the descent bounds.
Formalization Note The paper states (1.1) "f is smooth"; we assume is on the whole space, in addition to Assumptions 2.1. The steplengths are positive, as in the paper's definition of the Wolfe line search (p. 4). The sum is stated as summability of over , which equals here because descent forces and . The space is a finite-dimensional real inner product space; indices start at . Part (ii) of the theorem (ideal line search) is a separate item.
import Mathlib import Definitions.Def_NonlinCG_FRBound_Setting
namespace NonlinCG.FRBound
/-- Theorem 2.1 (i) (Gilbert–Nocedal, INRIA RR-1268, p. 4): under Assumptions 2.1, any iteration
`x_{k+1} = x_k + α_k d_k` (1.3) with positive steplengths, descent directions `d_k` and
steplengths satisfying the Wolfe conditions (2.4)–(2.5) with `0 < σ₁ < σ₂ < 1` satisfies the
Zoutendijk condition (2.7). The directions `d_k` are arbitrary, not necessarily (1.2). -/
theorem theorem_2_1_wolfe {E : Type*} [NormedAddCommGroup E] [InnerProductSpace ℝ E]
[FiniteDimensional ℝ E] (f : E → ℝ) (hf : ContDiff ℝ 1 f) (α : ℕ → ℝ) (x d : ℕ → E)
(σ₁ σ₂ : ℝ) (hA : Assumptions21 f (x 1))
(hσ : 0 < σ₁ ∧ σ₁ < σ₂ ∧ σ₂ < 1)
(hiter : ∀ k ≥ 1, 0 < α k ∧ x (k + 1) = x k + α k • d k)
(hdesc : ∀ k ≥ 1, inner ℝ (g f x k) (d k) < 0)
(hls : ∀ k ≥ 1, WolfeStep f σ₁ σ₂ (x k) (d k) (α k)) :
ZoutendijkCondition f x d := by sorry
end NonlinCG.FRBound
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.