Theorem 4.1, p. 14 — with strongly convex θᵢ the direct extension of ADMM is not necessarily convergent for all β > 0 (diverges on (4.1) at β = 1)
ProvedExtADMM.StrongCvx.theorem_4_1Theorem 4.1. For the model (1.1) with strongly convex objective functions, the direct extension of ADMM (1.5) is not necessarily convergent for all .
Precisely: the strongly convex instance (4.1),
satisfies
- the standing assumptions of (1.1) (closed convex sets , convex , nonempty solution set);
- each is strongly convex with modulus ;
- there is a starting point such that the direct extension of ADMM (1.5) with has a run from it, and no run of (1.5) with from it converges: the sequence has no limit.
Hence strong convexity of the objective alone does not secure convergence of (1.5); the known convergence results for strongly convex need a restriction on that cannot simply be dropped.
Formalization Note "Not necessarily convergent for all " is read as "it is not the case that (1.5) converges for every ", witnessed by the explicit instance (4.1) at , the only value the paper computes. The stronger reading "for every there is a divergent run" is false for (4.1): the spectral radius of the iteration matrix is below for small (about at ). Strong convexity uses Mathlib's StrongConvexOn s m f ( convex), so has ; on Fin 1 → ℝ the norm is . "Converges" means convergence in the product topology; the existence of a run is asserted so that the non-convergence clause is not vacuous. The first block of a run is never read by (1.5).
import Mathlib import Definitions.Def_ExtADMM_StrongCvx_Setting import Definitions.Def_ExtADMM_StrongCvx_Example41
namespace ExtADMM.StrongCvx
open Matrix Filter Topology
/-- Theorem 4.1, p. 14: for the model (1.1) with strongly convex objective, the direct
extension of ADMM (1.5) is not necessarily convergent for all `β > 0`. Witness: the instance
(4.1), whose `θᵢ(x) = 0.05x²` are `(1/10)`-strongly convex, with `β = 1`: there is a starting
point `(x₂⁰, x₃⁰, λ⁰)` from which a run exists and no run converges. -/
theorem theorem_4_1 :
example41.Standing ∧
(StrongConvexOn Set.univ (1/10) example41.θ1 ∧ StrongConvexOn Set.univ (1/10) example41.θ2 ∧
StrongConvexOn Set.univ (1/10) example41.θ3) ∧
∃ (x20 x30 : Fin 1 → ℝ) (lam0 : Fin 3 → ℝ),
(∃ (x1 x2 x3 : ℕ → Fin 1 → ℝ) (lam : ℕ → Fin 3 → ℝ),
example41.IsRun15 1 x1 x2 x3 lam ∧ x2 0 = x20 ∧ x3 0 = x30 ∧ lam 0 = lam0) ∧
∀ (x1 x2 x3 : ℕ → Fin 1 → ℝ) (lam : ℕ → Fin 3 → ℝ),
example41.IsRun15 1 x1 x2 x3 lam → x2 0 = x20 → x3 0 = x30 → lam 0 = lam0 →
¬ ∃ w, Tendsto (fun k => (x1 k, x2 k, x3 k, lam k)) atTop (𝓝 w) := by sorry
end ExtADMM.StrongCvx
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.