Theorem 2(b) — under Assumption 2, CGD with the restricted Gauss–Seidel rule and Armijo steps: or Q-/R-linear convergence along
ProvedTsengCGD.Linear.theorem2_bConsider problem (1): minimize with , proper, convex and lower semicontinuous, and continuously differentiable on an open set containing . Assume that is -Lipschitz on for some (22).
Let be generated by the CGD method under Assumption 1 (, ), where is chosen by the restricted Gauss–Seidel rule (12) with . Suppose further that
- satisfies Assumption 2: the local Lipschitzian error bound (35) on each level set near , with the set of stationary points, and the proper separation of the isocost surfaces of on ;
- is block-separable with respect to for all ;
- is chosen by the Armijo rule with and .
Then either decreases to , or
This is the paper's linear convergence theorem for the CGD method with cyclic (Gauss–Seidel-type) coordinate selection; it requires neither convexity of nor strong convexity, only the error bound and the separation property of Assumption 2 (§6 of the paper gives sufficient conditions for the error bound).
Formalization Note "" is stated as: the values are nonincreasing and tend to . The rates are along , i.e. for the sequences and . Q-linear convergence includes convergence to a limit and eventually with ; R-linear convergence is for some , and . "" is for all , "" a positive lower bound. In Assumption 2, is Metric.infDist and "for any " is "for every real ". is the pair (effective domain, finite values); coordinates are 0-based.
import Mathlib import Definitions.Def_TsengCGD_Linear_Basic open Filter Topology Finset Matrix open scoped RealInnerProductSpace
namespace TsengCGD.Linear
theorem theorem2_b {n : ℕ} (f : TsengCGD.Global.Vec n → ℝ) (D : Set (TsengCGD.Global.Vec n)) (P : TsengCGD.Global.Vec n → ℝ) (c : ℝ)
(hs : TsengCGD.Global.Standing f D P c) (J : ℕ → Finset (Fin n)) (H : ℕ → Matrix (Fin n) (Fin n) ℝ)
(x d : ℕ → TsengCGD.Global.Vec n) (α : ℕ → ℝ) (hrun : TsengCGD.Global.IsCGDRun f D P c J H x d α)
(lam lamBar : ℝ) (hA1 : TsengCGD.Global.Assumption1 H lam lamBar)
(L : ℝ) (hL : GradLipOn f D L)
(t : ℕ → ℕ) (hRGS : RestrictedGaussSeidel J t)
(hA2a : Assumption2a f D P c) (hA2b : Assumption2b f D P c)
(hsep : ∀ k, TsengCGD.Global.BlockSeparable D P (J k))
(β σ γ : ℝ) (αinit : ℕ → ℝ) (harm : TsengCGD.Global.IsArmijo f D P c β σ γ αinit H x d α)
(hinit1 : ∀ k, αinit k ≤ 1) (hinit : ∃ a > 0, ∀ k, a ≤ αinit k) :
(Antitone (fun k => TsengCGD.Global.Fc f P c (x k)) ∧ Tendsto (fun k => TsengCGD.Global.Fc f P c (x k)) atTop atBot) ∨
(QLinear (fun i => TsengCGD.Global.Fc f P c (x (t i))) ∧ RLinear (fun i => x (t i))) := by sorry
end TsengCGD.Linear
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.