(3.9)–(3.10), p. 180 — along a non-terminating run of Algorithm 2.1, g_kᵀd_k < 0 and d_kᵀy_k ≥ (σ − 1)d_kᵀg_k > 0
ProvedDaiYuanCG.Conv.descent_3_9conjugate-gradientdai-yuandescent-directionp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1wolfe-conditions
Let , , and let be a run of Algorithm 2.1 (the Dai–Yuan iteration , , , , with every satisfying the standard Wolfe conditions (1.7) and (1.10) with constants ). Suppose the algorithm does not terminate, i.e. for all . Then for every
All search directions are therefore descent directions, and the denominator of is positive, so is well defined at every iteration. This is the first step of the proof of Theorem 3.3.
Formalization Note Neither Assumption 3.1 nor the bound is used by this step, so they are dropped; only and the run are assumed. Non-termination is the hypothesis for all , which is (3.8).
Preamble
import Mathlib import Definitions.Def_DaiYuanCG_Conv_Setting
Formal statement
namespace DaiYuanCG.Conv
theorem descent_3_9 {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 → inner ℝ (gradient f (x k)) (d k) < 0 ∧
(σ - 1) * inner ℝ (d k) (gradient f (x k)) ≤
inner ℝ (d k) (gradient f (x (k + 1)) - gradient f (x k)) ∧
0 < inner ℝ (d k) (gradient f (x (k + 1)) - gradient f (x 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. 180, (3.9)–(3.10), proof of Theorem 3.3
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.