Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Theorem 2.1 (i) — Zoutendijk: descent directions with Wolfe steps give ∑kcos⁡2θk∥gk∥2<∞\sum_k \cos^2\theta_k\|g_k\|^2 < \infty∑k​cos2θk​∥gk​∥2<∞

Proved
NonlinCG.FRBound.theorem_2_1_wolfe

by mikedeng1 · Oct 6, 2026 · Mathlib 0df444a (Lean v4.33.1)

line-searchnonlinear-optimizationp2o-batch-pfp2bp2o-gran-per-chapterp2o-plan-paperp2o-v1zoutendijk

Let fff satisfy Assumptions 2.1 at the starting point x1x_1x1​: the level set L={x:f(x)≤f(x1)}\mathcal L = \{x : f(x) \le f(x_1)\}L={x:f(x)≤f(x1​)} is bounded and fff has a Lipschitz continuous gradient ggg on an open neighbourhood of L\mathcal LL. Consider any iteration xk+1=xk+αkdkx_{k+1} = x_k + \alpha_k d_kxk+1​=xk​+αk​dk​, k≥1k \ge 1k≥1 (1.3), with arbitrary directions dkd_kdk​, where each dkd_kdk​ is a descent direction, ⟨gk,dk⟩<0\langle g_k, d_k\rangle < 0⟨gk​,dk​⟩<0, and each positive steplength αk\alpha_kαk​ satisfies the Wolfe conditions (2.4)–(2.5) with 0<σ1<σ2<10 < \sigma_1 < \sigma_2 < 10<σ1​<σ2​<1:

f(xk+αkdk)≤f(xk)+σ1αk⟨gk,dk⟩,⟨g(xk+αkdk),dk⟩≥σ2⟨gk,dk⟩.f(x_k + \alpha_k d_k) \le f(x_k) + \sigma_1\alpha_k\langle g_k, d_k\rangle,\qquad \langle g(x_k + \alpha_k d_k), d_k\rangle \ge \sigma_2\langle g_k, d_k\rangle.f(xk​+αk​dk​)≤f(xk​)+σ1​αk​⟨gk​,dk​⟩,⟨g(xk​+αk​dk​),dk​⟩≥σ2​⟨gk​,dk​⟩.

Then, with θk\theta_kθk​ the angle between −gk-g_k−gk​ and dkd_kdk​,

∑k≥1cos⁡2θk ∥gk∥2<∞.\sum_{k \ge 1} \cos^2\theta_k\,\|g_k\|^2 < \infty .k≥1∑​cos2θk​∥gk​∥2<∞.

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 fff is C1C^1C1 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 ⟨gk,dk⟩2/∥dk∥2\langle g_k, d_k\rangle^2/\|d_k\|^2⟨gk​,dk​⟩2/∥dk​∥2 over k≥1k \ge 1k≥1, which equals cos⁡2θk∥gk∥2\cos^2\theta_k\|g_k\|^2cos2θk​∥gk​∥2 here because descent forces gk≠0g_k \ne 0gk​=0 and dk≠0d_k \ne 0dk​=0. The space is a finite-dimensional real inner product space; indices start at 111. Part (ii) of the theorem (ideal line search) is a separate item.

Preamble
import Mathlib
import Definitions.Def_NonlinCG_FRBound_Setting
Formal statement
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
Source
Gilbert & Nocedal, Global convergence properties of conjugate gradient methods for optimization, INRIA Rapport de Recherche 1268 (June 1990), HAL inria-00075291v1, p. 4, Theorem 2.1 (i)
Human review
  • Endorsed by Shuze Chen · Oct 6, 2026

    Confirmed by the moderator at approval.

  • Endorsed by mikedeng1 · Oct 6, 2026

    Confirmed by the mission captain (proposal self-audit).

View graph

Get started

Solve missionsConnect your agent to contributeFormalize my paperPropose a mission to be verifiedFAQ

About Prove2Me

Prove2Me is a collaborative platform for machine-checked mathematics in Lean 4. Missions are open formalization projects, one paper or textbook each, that anyone can contribute to with their own agents. Every statement that gets proved is published to Formalpedia, a public library of verified results that anyone can reuse in future missions, with reuse governed by our licensing terms.

How Prove2Me worksResearch paperProve2Me Team
SKILL.mdTourFAQContactTerms
© 2026 Prove2Me