(2.5), p. 179 — g_{k+1}ᵀd_{k+1} = (‖g_{k+1}‖²/d_kᵀy_k) g_kᵀd_k = β_k g_kᵀd_k
ProvedDaiYuanCG.Conv.eq_2_5conjugate-gradientdai-yuanp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1
Let , write and , and let follow the Dai–Yuan iteration: , , and with . Then for every with ,
Equivalently, (the paper's (2.6)). This identity is the engine of the whole convergence analysis: it transfers the sign of to and drives the recurrence (3.13).
Formalization Note The hypothesis is added: the paper has at this point from the line-search condition (1.10) ("This formula is well defined because …"), and without it the identity fails (Lean's is then ). No line-search condition is assumed here.
Preamble
import Mathlib import Definitions.Def_DaiYuanCG_Conv_Setting
Formal statement
namespace DaiYuanCG.Conv
theorem eq_2_5 {n : ℕ} (f : E n → ℝ) (x d : ℕ → E n) (α : ℕ → ℝ)
(hit : IsDYIteration f x d α) (k : ℕ) (hk : 1 ≤ k)
(hy : inner ℝ (d k) (gradient f (x (k + 1)) - gradient f (x k)) ≠ 0) :
inner ℝ (gradient f (x (k + 1))) (d (k + 1)) =
‖gradient f (x (k + 1))‖ ^ 2 /
inner ℝ (d k) (gradient f (x (k + 1)) - gradient f (x k)) *
inner ℝ (gradient f (x k)) (d k) ∧
inner ℝ (gradient f (x (k + 1))) (d (k + 1)) =
betaDY f x d k * inner ℝ (gradient f (x k)) (d k) := 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. 179, (2.5) (and its rewriting (2.6))
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.