(32), p. 17 — an Armijo backtracking index exists
ProvedBSUMConv.BSCA.eq_32armijodescent-directionline-searchp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1
Let be continuously differentiable, a point, and a strict descent direction, . For , and , there is a nonnegative integer such that satisfies
Thus geometric backtracking has an acceptable index whenever the direction gives strict descent.
Formalization Note The claim is stated at one point and direction, the form used at every BSCA iteration. The paper's condition is strict negativity here because (31) gives nonpositivity.
Preamble
import Mathlib import Definitions.Def_BSUMConv_BSCA_Setting
Formal statement
namespace BSUMConv.BSCA
/-- Display (32), p. 17: backtracking reaches an Armijo-admissible step along a strict descent direction. -/
theorem eq_32 {N : ℕ} {n : Fin N → ℕ}
(f : TsengBCD.Stationary.X n → ℝ) (hf : ContDiff ℝ 1 f)
(x d : TsengBCD.Stationary.X n)
(σ β αinit : ℝ) (hσ0 : 0 < σ) (hσ1 : σ < 1)
(hβ0 : 0 < β) (hβ1 : β < 1) (hα : 0 < αinit)
(hdesc : fderiv ℝ f x d < 0) :
∃ j : ℕ,
let α := αinit * β ^ j
f x - f (x + α • d) ≥ -σ * α * fderiv ℝ f x d := by sorry
end BSUMConv.BSCA
Source
Razaviyayn, Hong & Luo, arXiv:1209.2385v1, p. 17, (32)
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.