Proof of Theorem 4.8, p. 17 — |u^{k+1} − p| = |1 − λ/(1+γσ)| |uᵏ − p| once uᵏ, u^{k+1} > 1
ProvedNonconvexDRS.Tight.thm_4_8_identitycounterexampledouglas-rachfordnonconvex-optimizationp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1relaxation
Let , , , and . Let be the function (4.12) with , let , and let be a DRS run on with stepsize and relaxation . If is such that and , then
and if moreover , then .
Verbatim (p. 17): ", where the identity was used, cf. (4.13). Therefore, , where the inequality is due to the fact that ."
This is the expansion step of the paper's counterexample for over-relaxation.
Formalization Note The page uses the identity under "eventually "; it is needed at both and (the second branch of (4.13) at ), so both are hypotheses. The bound is written .
Preamble
import Mathlib import Definitions.Def_NonconvexDRS_Tight_Setting open Filter Topology
Formal statement
namespace NonconvexDRS.Tight
theorem thm_4_8_identity (L σ γ lam p : ℝ) (hL : 0 < L) (hσ : -L ≤ σ ∧ σ ≤ L) (hp : 1 < p)
(hγ : 0 < γ) (hγL : γ * L < 1) (hlam : 0 < lam)
(s u v : ℕ → ℝ) (hrun : IsDRSRun (phi1Ex L σ 1) (indic ({p} : Set ℝ)) γ lam s u v)
(k : ℕ) (hk : 1 < u k) (hk1 : 1 < u (k + 1)) :
|u (k + 1) - p| = |1 - lam / (1 + γ * σ)| * |u k - p| ∧
(2 * (1 + γ * σ) ≤ lam → |u k - p| ≤ |u (k + 1) - p|) := by sorry
end NonconvexDRS.Tight
Source
Themelis & Patrinos, Douglas-Rachford splitting and ADMM for nonconvex optimization: tight convergence results, arXiv:1709.05747v4, p. 17, proof of Theorem 4.8, the displayed identity and inequality
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.