§3.2.1 — under Assumptions 1–2, ADMM residuals and
ProvedBoydADMM.Convergence.admm_convergenceConsider problem (3.1), minimize subject to , with optimal value . Assume
- (Assumption 1) and are closed, proper and convex;
- (Assumption 2) the Lagrangian has a saddle point ;
and let . Then every ADMM run , i.e. any sequences satisfying (3.2)–(3.4), satisfies, as ,
These are residual convergence (the iterates approach feasibility), objective convergence (the objective approaches the optimal value) and convergence of the dual residual. No rank condition on or is assumed, and the iterates themselves need not converge.
Formalization Note The run is any triple of sequences satisfying (3.2)–(3.4) exactly; it is never constructed (the book's claim that Assumption 1 alone makes the subproblems solvable is false). is the infimum optVal, not by definition. The dual residual sequence is written as , a shift that does not change the limit; the first term of each sequence (which involves the unused ) does not affect the limits either. The book also lists dual variable convergence in §3.2.1; Appendix A does not prove it and it is not part of this statement.
Retired 2026-10-27: a Lean-vs-paper fidelity audit found this statement weaker than, or narrower than, the cited result. A corrected statement will be resubmitted.
import Mathlib import Definitions.Def_BoydADMM_Convergence_Model
namespace BoydADMM.Convergence
/-- §3.2.1, p. 17, as proved in Appendix A (p. 106): under Assumptions 1 and 2, every ADMM
run satisfies residual convergence `r^k → 0`, objective convergence `f(x^k) + g(z^k) → p⋆`, and
dual residual convergence `s^k = ρAᵀB(z^k − z^{k−1}) → 0`. -/
theorem admm_convergence
{n m p : ℕ} (P : Problem n m p) (hA1 : P.Assumption1) {ρ : ℝ} (hρ : 0 < ρ)
{xs : EuclideanSpace ℝ (Fin n)} {zs : EuclideanSpace ℝ (Fin m)}
{ys : EuclideanSpace ℝ (Fin p)} (hsp : P.IsSaddlePoint xs zs ys)
{x : ℕ → EuclideanSpace ℝ (Fin n)} {z : ℕ → EuclideanSpace ℝ (Fin m)}
{y : ℕ → EuclideanSpace ℝ (Fin p)} (hrun : P.IsADMMSeq ρ x z y) :
Filter.Tendsto (fun k => P.resid (x k) (z k)) Filter.atTop (nhds 0) ∧
Filter.Tendsto (fun k => P.f (x k) + P.g (z k)) Filter.atTop (nhds P.optVal) ∧
Filter.Tendsto (fun k => P.dualResid ρ (z k) (z (k + 1))) Filter.atTop (nhds 0) := by sorry
end BoydADMM.Convergence
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.