Proof of Theorem 4.1(c), pp. 482–483 — unique block minima force z¹ = z² = ⋯ = z^{T−1}
ProvedTsengBCD.Stationary.part_c_windows_eqblock-coordinate-descentcoordinatewise-minimump2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1unique-minimum
Let , , and let be points and blocks such that:
- has at most one minimum in for ;
- for ;
- (7) for all , , and for all , ;
- (8) for all , .
Then
so .
In the proof of Theorem 4.1(c), (7) and (8) say that attains its minimum both at and at ; uniqueness of the minimum point collapses the window, and the cluster point is then a coordinatewise minimum point.
Formalization Note. Stated about the points and blocks alone, with (7), (8) as hypotheses; limit_chain produces them from a BCD run. A minimum point of a block section is a point of its effective domain (see the definitions item), which is why is a hypothesis here; in the theorem it follows from (6).
Preamble
import Mathlib import Definitions.Def_TsengBCD_Stationary_Setting
Formal statement
namespace TsengBCD.Stationary
open Filter Topology
theorem part_c_windows_eq {N : ℕ} {n : Fin N → ℕ} (f : X n → EReal) (T : ℕ)
(zs : ℕ → X n) (ss : ℕ → Fin N)
(huniq : ∀ j, 2 ≤ j → j ≤ T - 1 → AtMostOneMinIn f (ss j))
(hfin : ∀ j, 1 ≤ j → j ≤ T → f (zs j) ≠ ⊤)
(h7 : ∀ j, 1 ≤ j → j ≤ T → ∀ d : EuclideanSpace ℝ (Fin (n (ss j))),
f (zs j) ≤ f (zs j + Pi.single (ss j) d))
(h7' : ∀ j, 2 ≤ j → j ≤ T → ∀ k : Fin N, k ≠ ss j → zs j k = zs (j - 1) k)
(h8 : ∀ j, 2 ≤ j → j ≤ T → ∀ d : EuclideanSpace ℝ (Fin (n (ss j))),
f (zs (j - 1)) ≤ f (zs (j - 1) + Pi.single (ss j) d)) :
∀ j, 2 ≤ j → j ≤ T - 1 → zs (j - 1) = zs j := by sorry
end TsengBCD.Stationary
Source
Tseng, Convergence of a block coordinate descent method for nondifferentiable minimization, J. Optim. Theory Appl. 109 (2001), pp. 482–483, proof of Theorem 4.1(c)
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.