(3.14), p. 180 — ‖d_k‖²/(g_kᵀd_k)² ≤ Σ_{i=1}^k 1/‖g_i‖²
ProvedDaiYuanCG.Conv.eq_3_14conjugate-gradientdai-yuanp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1
Let , , and let be a non-terminating run of Algorithm 2.1 (standard Wolfe steps with constants , and for every ). Then for every
It follows from the recurrence (3.13) together with . With gradients bounded away from zero, it bounds the reciprocal Zoutendijk terms linearly in .
Formalization Note Assumption 3.1 and are not used and are dropped. The quotients are Lean divisions with nonzero denominators along the run.
Preamble
import Mathlib import Definitions.Def_DaiYuanCG_Conv_Setting
Formal statement
namespace DaiYuanCG.Conv
theorem eq_3_14 {n : ℕ} (f : E n → ℝ) (δ σ : ℝ) (hσ1 : σ < 1)
(x d : ℕ → E n) (α : ℕ → ℝ) (hrun : IsDYRun f δ σ x d α)
(hnt : ∀ k, 1 ≤ k → gradient f (x k) ≠ 0) :
∀ k, 1 ≤ k → ‖d k‖ ^ 2 / inner ℝ (gradient f (x k)) (d k) ^ 2 ≤
∑ i ∈ Finset.Icc 1 k, 1 / ‖gradient f (x i)‖ ^ 2 := by sorry
end DaiYuanCG.Conv
Source
Dai and Yuan, A nonlinear conjugate gradient method with a strong global convergence property, SIAM J. Optim. 10 (1999), p. 180, (3.14), proof of Theorem 3.3
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.