Proof of Theorem 4.1, p. 481 — the BCD iterates decrease f, stay in X⁰ and are bounded
ProvedTsengBCD.Stationary.run_mem_levelSetblock-coordinate-descentdescent-methodlevel-setp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1
Let , let satisfy , and assume the level set is compact. Let be any sequence generated by the BCD method (2)–(3) from with any choice of blocks. Then for every
and the sequence is bounded.
This is the first step of the proof of Theorem 4.1: the method is a descent method, so its iterates are confined to the compact level set.
Formalization Note. Blocks are 0-based and s r is the block chosen at iteration . Continuity of is not needed for this step and is not assumed; the existence half (" is defined") is the separate item argmin_attained.
Preamble
import Mathlib import Definitions.Def_TsengBCD_Stationary_Setting
Formal statement
namespace TsengBCD.Stationary
open Filter Topology
theorem run_mem_levelSet {N : ℕ} {n : Fin N → ℕ} (f : X n → EReal) (x0 : X n)
(hx0 : f x0 ≠ ⊤) (hcpt : IsCompact (levelSet f x0))
(s : ℕ → Fin N) (x : ℕ → X n) (hx : x 0 = x0) (hrun : IsBCDRun f s x) :
(∀ r, f (x (r + 1)) ≤ f (x r) ∧ x (r + 1) ∈ levelSet f x0) ∧
Bornology.IsBounded (Set.range x) := by sorry
end TsengBCD.Stationary
Source
Tseng, Convergence of a block coordinate descent method for nondifferentiable minimization, J. Optim. Theory Appl. 109 (2001), p. 481, proof of Theorem 4.1, first two sentences
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.