(14), p. 10 — the BSUM objective values are non-increasing: f(x⁰) ≥ f(x¹) ≥ f(x²) ≥ …
ProvedBSUMConv.BSUM.eq_14block-coordinate-descentmonotonicityp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1successive-upper-bound-minimization
Let with each closed and convex, let be continuous on , and let the approximation functions satisfy Assumption 2 (B1)–(B4). Let be the iterates of the BSUM algorithm with the cyclic rule: , and is obtained from by replacing the scheduled block by a minimiser of over . Then
Monotonicity of the objective values is the first step of the convergence analysis of Theorem 2.
Formalization Note Stated as Antitone (fun r => f (x r)).
Preamble
import Mathlib import Definitions.Def_TsengBCD_Stationary_Setting import Definitions.Def_BSUMConv_BSUM_Setting
Formal statement
namespace BSUMConv.BSUM
open TsengBCD.Stationary Filter Topology
/-- (14), p. 10: the objective values of a cyclic BSUM run are non-increasing,
`f(x⁰) ≥ f(x¹) ≥ f(x²) ≥ ⋯`. -/
theorem eq_14 {N : ℕ} {n : Fin N → ℕ}
(Xs : (i : Fin N) → Set (EuclideanSpace ℝ (Fin (n i))))
(hXconv : ∀ i, Convex ℝ (Xs i)) (hXclosed : ∀ i, IsClosed (Xs i))
(f : X n → ℝ) (hf : ContinuousOn f (Xset Xs))
(u : (i : Fin N) → EuclideanSpace ℝ (Fin (n i)) → X n → ℝ) (hA2 : Assumption2 Xs f u)
(s : ℕ → Fin N) (hs : IsCyclic s) (x : ℕ → X n) (hx : IsBSUMRun Xs u s x) :
Antitone (fun r => f (x r)) := by sorry
end BSUMConv.BSUM
Source
Razaviyayn, Hong & Luo, arXiv:1209.2385v1, p. 10, proof of Theorem 2(a), display (14)
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.