Lemma 5(a) — variational inequality for the step under block-separability
ProvedTsengCGD.Linear.lemma5_aConsider problem (1): with , proper, convex, lower semicontinuous and continuously differentiable on an open set containing . Let , , nonempty, the direction (6), , and ; put .
Suppose is block-separable with respect to , . Then for every , every and ,
This inequality compares a partial step with an arbitrary point on the block ; it is the per-block estimate that the linear convergence proof of Theorem 2(b) sums over a Gauss–Seidel cycle.
Formalization Note The left side involves the particular summand , so the statement holds for every decomposition (20) of ; a decomposition is given by two proper convex lsc functions on , one depending only on (with its own effective domain), the other only on . When the left side is and the inequality is empty, so ranges over . is any minimizer of (6) (it is unique). Coordinates are 0-based; is the quadratic form of the matrix .
import Mathlib import Definitions.Def_TsengCGD_Linear_Basic open Filter Topology Finset Matrix open scoped RealInnerProductSpace
namespace TsengCGD.Linear
theorem lemma5_a {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) (x : TsengCGD.Global.Vec n) (hx : x ∈ D) (H : Matrix (Fin n) (Fin n) ℝ)
(hH : H.PosDef) (J : Finset (Fin n)) (hJ : J.Nonempty) (d : TsengCGD.Global.Vec n)
(hd : TsengCGD.Global.IsDir f D P c H x J d) (γ : ℝ) (hγ0 : 0 ≤ γ) (hγ1 : γ < 1)
(DJ : Set (TsengCGD.Global.Vec n)) (PJ : TsengCGD.Global.Vec n → ℝ) (DJC : Set (TsengCGD.Global.Vec n)) (PJC : TsengCGD.Global.Vec n → ℝ)
(hw : TsengCGD.Global.IsBlockSepWitness D P J DJ PJ DJC PJC)
(xbar : TsengCGD.Global.Vec n) (hxbar : xbar ∈ DJ) (α : ℝ) (hα0 : 0 < α) (hα1 : α ≤ 1) :
(∑ j ∈ J, (gradient f x j + (H *ᵥ WithLp.ofLp d) j) * ((x + α • d) j - xbar j))
+ c * PJ (x + α • d) - c * PJ xbar
≤ (α - 1) * ((1 - γ) * TsengCGD.Global.qf H d + TsengCGD.Global.Delta f P c γ H x d) := by sorry
end TsengCGD.Linear
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.