(3.16)–(3.17), p. 181 — if ‖g_k‖ ≥ c > 0 for all k, then ‖d_k‖²/(g_kᵀd_k)² ≤ k/c² and Σ (g_kᵀd_k)²/‖d_k‖² = ∞
ProvedDaiYuanCG.Conv.eq_3_17conjugate-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 ). Suppose there is a constant with for all (this is (3.15)). Then
This is the contrapositive half of the proof of Theorem 3.3: gradients bounded away from zero force the Zoutendijk series to diverge, contradicting Lemma 3.2.
Formalization Note Assumption 3.1 and are not used and are dropped. Since the terms are nonnegative, "" is stated as non-summability of over , i.e. of the paper's series over .
Preamble
import Mathlib import Definitions.Def_DaiYuanCG_Conv_Setting
Formal statement
namespace DaiYuanCG.Conv
theorem eq_3_17 {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)
(c : ℝ) (hc : 0 < c) (hgc : ∀ k, 1 ≤ k → c ≤ ‖gradient f (x k)‖) :
(∀ k, 1 ≤ k → ‖d k‖ ^ 2 / inner ℝ (gradient f (x k)) (d k) ^ 2 ≤ (k : ℝ) / c ^ 2) ∧
¬ Summable (fun k : ℕ =>
inner ℝ (gradient f (x (k + 1))) (d (k + 1)) ^ 2 / ‖d (k + 1)‖ ^ 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), pp. 180–181, (3.15)–(3.17), proof of Theorem 3.3
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.