§2 after (10) — negative descent quantity and Armijo trial existence
ProvedTsengCGD.Global.armijo_existscomposite-optimizationcoordinate-descentnonsmooth-optimizationp2o-batch-pfp2bp2o-gran-per-chapterp2o-plan-paperp2o-v1
Under the standing assumptions, take , a nonempty block , a positive-definite matrix , and the exact direction . Let , , and let be an initial trial step. With , the paper's claim after (10) includes
There is some for which passes the Armijo test. This establishes that the backtracking rule has a positive accepted trial, including when .
Formalization Note The little- remainder is explicit and the tested point must belong to . The strict inequality is conditional on ; at a trial still exists.
Preamble
import Mathlib import Definitions.Def_TsengCGD_Global_Basic
Formal statement
namespace TsengCGD.Global
open Filter Topology Finset Matrix
open scoped RealInnerProductSpace
theorem armijo_exists {n : ℕ} (f : Vec n → ℝ) (D : Set (Vec n)) (P : Vec n → ℝ)
(c : ℝ) (hs : Standing f D P c)
(x : Vec n) (hx : x ∈ D) (J : Finset (Fin n)) (hJ : J.Nonempty)
(H : Matrix (Fin n) (Fin n) ℝ) (hH : H.PosDef)
(d : Vec n) (hd : IsDir f D P c H x J d)
(β σ γ a₀ : ℝ) (hparams : ArmijoParams β σ γ) (ha₀ : 0 < a₀) :
(∃ r : ℝ → ℝ, Tendsto (fun a => r a / a) (𝓝[>] (0 : ℝ)) (𝓝 0) ∧
∀ a ∈ Set.Ioc (0 : ℝ) 1,
x + a • d ∈ D ∧
Fc f P c (x + a • d) ≤ Fc f P c x + a * Delta f P c γ H x d + r a) ∧
Delta f P c γ H x d ≤ (γ - 1) * qf H d ∧
(d ≠ 0 → Delta f P c γ H x d < 0) ∧
∃ j : ℕ, ArmijoTest f D P c σ γ H x d (a₀ * β ^ j) := by sorry
end TsengCGD.Global
Source
Tseng and Yun, A coordinate gradient descent method for nonsmooth separable minimization, Math. Program. Ser. B 117 (2009), p. 392, §2, claim after equation (10), https://doi.org/10.1007/s10107-007-0170-0
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.