Theorem 3.1, p. 14 — on the instance (3.10), the direct extension of ADMM diverges for every β > 0 from an open half of a 3-dimensional subspace of starting points
ProvedExtADMM.Diverge.theorem_3_1Consider the three-block problem (1.1) given by the linear system
with null objective, and (example (3.10)). Then:
- this instance satisfies the standing assumptions of (1.1) (closed convex sets, convex objectives, nonempty solution set);
- there are a three-dimensional real subspace of and a nonzero linear functional on such that, for every penalty parameter and every starting point with
the direct extension of ADMM (1.5) with penalty has a run starting from , and no run from that starting point converges: the sequence has no limit.
This is the paper's main theorem. It answers negatively the question whether the direct extension of the two-block ADMM to three blocks converges for convex problems: even on a nonsingular linear system with zero objective, for every and from an open half of a three-dimensional subspace of starting points, the iteration diverges.
Formalization Note. "There is an example" is witnessed by the paper's own instance (3.10). The paper's "continuously dense half space of dimension 3" is in the coordinates with of (3.12)–(3.13); in these coordinates the set does not depend on , so and are chosen before . "Divergent" is read as "does not converge" (in the product topology of ), and the existence of a run is asserted so that the claim is not vacuous. is not used by (1.5).
import Mathlib import Definitions.Def_ExtADMM_Diverge_Setting open Matrix Filter Topology
namespace ExtADMM.Diverge
/-- Theorem 3.1, p. 14. The instance (3.10) of problem (1.1) satisfies the standing
assumptions, and there are a 3-dimensional subspace `S` of the space of starting points
`(x₂⁰, x₃⁰, λ⁰/β)` and a nonzero linear functional `φ` on `S` such that, for every penalty
`β > 0` and every starting point `(x₂⁰, x₃⁰, λ⁰)` with `(x₂⁰, x₃⁰, λ⁰/β)` in the open half
`{z ∈ S | φ z > 0}`, the direct extension of ADMM (1.5) has a run from that point, and no
run from that point converges. -/
theorem theorem_3_1 :
example310.Standing ∧
∃ S : Submodule ℝ (Fin 5 → ℝ), Module.finrank ℝ S = 3 ∧ ∃ φ : S →ₗ[ℝ] ℝ, φ ≠ 0 ∧
∀ β : ℝ, 0 < β → ∀ (x20 x30 : Fin 1 → ℝ) (lam0 : Fin 3 → ℝ)
(hz : stateVec β x20 x30 lam0 ∈ S), 0 < φ ⟨_, hz⟩ →
(∃ (x1 x2 x3 : ℕ → Fin 1 → ℝ) (lam : ℕ → Fin 3 → ℝ),
example310.IsRun15 β x1 x2 x3 lam ∧ x2 0 = x20 ∧ x3 0 = x30 ∧ lam 0 = lam0) ∧
∀ (x1 x2 x3 : ℕ → Fin 1 → ℝ) (lam : ℕ → Fin 3 → ℝ),
example310.IsRun15 β 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.Diverge
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.