Theorem 3.1 — for 0 < ρ < 2r, the modified dual algorithm converges strongly to (v*, Av*) and λⁿ stays bounded
ProvedGabayMercier.DualAlgorithm.theorem_3_1Let be real Hilbert spaces, continuous linear, , and where
- is convex and continuously differentiable with strongly monotone gradient: for some (2.3);
- is proper, convex and lower semicontinuous;
- for some (2.5);
- some lies in the interior of (qualification).
Let be the solution of : . Let and let the stepsize satisfy
Then every sequence produced by the modified dual algorithm (3.4), from any start (Step 1: for all ; Step 2: ; Step 3: ), satisfies
and the multipliers stay bounded in .
This is the convergence theorem for the alternating direction method of multipliers in Hilbert space, for any stepsize below twice the penalty parameter. The solution exists and is unique (Proposition 2.1), so the hypothesis on can be met; the multipliers need not converge because the multiplier need not be unique.
Formalization Note. Strong convergence in is stated as the two norm limits. enters through the hypothesis IsSolution (finite value and minimal). The statement quantifies over every run of the algorithm; the algorithm's well-posedness (Remark 1, p. 15) is not used. Two departures from the printed text, both explained in the definition file: Step 1 carries (the paper prints , which makes the algorithm solve (𝒫) with ; for , , , , the printed iteration converges to while ); and the paper's qualification (2.4), , is strengthened to . Under (2.4) alone the multipliers can be unbounded: in the example of Theorem 2.1 (converse) (, , , the indicator of the disc of centre and radius , ), no saddle point exists, and the conclusion of Theorem 3.1 fails for : if and , a bounded would have a weak cluster point with by Step 1 and by Step 2, which forces (numerically, after iterations and still decreasing).
import Mathlib import Definitions.Def_InertialFB_IFB_ConvexAnalysis import Definitions.Def_GabayMercier_DualAlgorithm_Model open Filter Topology InertialFB.IFB
namespace GabayMercier.DualAlgorithm
variable {V Y : Type*} [NormedAddCommGroup V] [InnerProductSpace ℝ V] [CompleteSpace V]
[NormedAddCommGroup Y] [InnerProductSpace ℝ Y] [CompleteSpace Y]
/-- Theorem 3.1, p. 19: for every stepsize `0 < ρ < 2r`, every run of the modified dual algorithm
(3.4) converges strongly in `V × Y` to `(v*, Av*)`, where `v*` is the solution of (𝒫), and the
multipliers `λⁿ` stay bounded. The qualification hypothesis strengthens the paper's (2.4). -/
theorem theorem_3_1 (A : V →L[ℝ] Y) (f₁ : Y → ℝ) (f₁' : Y → Y) (f₂ : Y → EReal)
(b : StrongDual ℝ V) (γ α : ℝ) (h : StandingHyp A f₁ f₁' f₂ γ α)
(hq : Qualification A f₂) (r ρ : ℝ) (hr : 0 < r) (hρ : 0 < ρ) (hρr : ρ < 2 * r)
(v : ℕ → V) (y lam : ℕ → Y) (hrun : IsModifiedDualRun A f₁' f₂ b r ρ v y lam)
(vs : V) (hvs : IsSolution A f₁ f₂ b vs) :
Tendsto v atTop (𝓝 vs) ∧ Tendsto y atTop (𝓝 (A vs)) ∧
Bornology.IsBounded (Set.range lam) := by sorry
end GabayMercier.DualAlgorithm
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.