Math and TheoryA narrow interval for the universal multiplier step of two-block ADMM
Selected result in this collection
Problem and result
- Problem
- Glowinski's open question on the ADMM dual step size beyond the golden ratio
- Posed in
- Fortin and Glowinski proved convergence for 0 < τ < (1+√5)/2 (1983); Tao and Yuan, J. Optim. Theory Appl. 179 (2018), 163–196, call the general convex case Glowinski's open question
- Status
- Partially resolved
- Result
- Two-block ADMM with multiplier step τ converges for every 0 < τ ≤ 1.886795 on finite-dimensional convex problems with attained proximal steps and a saddle point; fixed polytopes in R^128 cycle for every τ ≥ 1.8868840…; scalar problems converge exactly for 0 < τ < 2
Abstract
Two-block ADMM with relaxation only in the multiplier update converges for every constant step 0 < τ ≤ 1.886795 on finite-dimensional convex problems whose proximal subproblems attain their minima and which have a saddle point. Both primal blocks, the multiplier and the objective values converge, with no smoothness, strong convexity or bounded-iterate assumption. Fixed compact polytopes in R¹²⁸ have a nonconstant periodic ADMM orbit for every τ ≥ 1.8868840…, so the largest step with universal convergence lies in an interval of width below 0.00009, about a tenth of the version 1.0 interval. For scalar problems the universal range is exactly 0 < τ < 2. Affine-constraint versions are also proved. The earlier assertion of convergence up to τ = 2 by Gao et al. (2022) is shown to be false.
Details
- Year
- 2026
- Discipline
- Mathematics
- Area
- Optimization
- Subject
- Optimization
- Result type
- Convergence theorem, periodic counterexample and reproducible proof package
- Formal proof
- Standalone Lean package
- Family
admm-multiplier-step- Keywords
- ADMM, alternating direction method of multipliers, dual step size, Glowinski golden ratio, multiplier relaxation, convergence threshold, Lyapunov certificate
Statement and scope
Formal scope. The consensus convergence theorem for 0 < τ ≤ 377359/200000, the arbitrary-rank and full-rank affine-constraint theorems, all seven finite-memory interval certificates and the periodic orbit in R^128 for τ ≥ 1.8868840… are formalized in 301 Lean modules. The scalar theorem, individual objective-value limits, the reduction from proper closed convex functions to proximal attainment, and penalty rescaling are conventional.
A Lean check establishes only the formal statement that is checked. It does not establish novelty, historical priority or a faithful transcription of an external source. Known gaps are listed in UNFINISHED.md; the authorship disclosure describes how the results were produced.
Manuscript
- PDF on this site
manuscript.pdf401 KB- PDF on GitHub
papers/mathematics/ admm-multiplier-step/ manuscript.pdf - LaTeX source
papers/mathematics/ admm-multiplier-step/ manuscript.tex
Formal proof
This result has a standalone Lean 4 package, separate from the shared library. Build it with the toolchain and instructions given in its README.
- Proof package
papers/mathematics/ admm-multiplier-step/ - Lean project
papers/303 Lean filesmathematics/ admm-multiplier-step/ lean/ - Lakefile
papers/mathematics/ admm-multiplier-step/ lean/ lakefile.lean - Toolchain
leanprover/lean4:v4.19.0 - Library roots
Reproduce
The commands below are quoted from papers/, which gives their context and working directory.
Lean
lake exe cache getLean
python3 ../verify_lean.py --dependency-project . --output-dir ../verification-replayExact arithmetic
python3 checks/check_exact_interval.py certificates/exact_175_188_m12.json
python3 checks/check_exact_interval.py certificates/exact_188_1886_m20.json
python3 checks/check_exact_interval.py certificates/exact_1886_188628_m20.json
python3 checks/check_exact_interval.py certificates/exact_188628_188632_m20.json
python3 checks/check_exact_interval.py certificates/exact_188632_18865_m20.json
python3 checks/check_exact_interval.py certificates/exact_18865_18867_m20.json
python3 checks/check_exact_interval.py certificates/exact_18867_1886795_m32.json
python3 checks/exact_circulant_cycle.py --check certificates/exact_cycle_1886884_K128.json
python3 checks/exact_circulant_cycle.py --check certificates/exact_cycle_18869_10000_K128.json- README
papers/mathematics/ admm-multiplier-step/ README.md - Verification guide
papers/mathematics/ admm-multiplier-step/ verification/ README.md - Verification record
papers/mathematics/ admm-multiplier-step/ VERIFICATION.md - Authorship
papers/mathematics/ admm-multiplier-step/ AUTHORSHIP.md - Repository guide
verification/README.md - Unfinished proofs
UNFINISHED.md
Source and prior work
Questions and answers
Does ADMM converge for dual step sizes beyond the golden ratio?
For finite-dimensional convex problems whose proximal subproblems attain their minima and which have a saddle point, this preprint proves convergence for every constant multiplier step 0 < τ ≤ 1.886795 = 377359/200000. Fixed compact polytopes in R^128 with zero objectives have a nonconstant periodic orbit for every τ ≥ 1.8868840…, so the exact universal threshold lies in an interval of width below 0.00009 and remains open.
Does multiplier-step ADMM converge for every τ up to 2?
Not in the general convex class: the periodic orbit contradicts the range 1 < τ ≤ 2 asserted by Gao et al. (2022). For scalar problems, however, the preprint proves convergence for every 0 < τ < 2, and τ = 2 fails already for zero objectives. The obstruction uses indicator objectives, so thresholds for smooth or strongly convex subclasses are not addressed.
Is the proof formally verified?
Largely. Lean 4 proves the consensus convergence theorem for 0 < τ ≤ 377359/200000 = 1.886795, the affine-constraint versions, all seven finite-memory certificates and the periodic orbit for τ ≥ 1.8868840…; the scalar theorem for 0 < τ < 2 has a conventional proof. The paper is an unrefereed preprint.
Cite
Citation file papers/. For the whole collection, use CITATION.cff or CITATION.bib.
@misc{goyal2026admmmultiplierstep,
author = {Goyal, Dev D.},
title = {A Narrow Interval for the Universal Multiplier Step of Two-Block {ADMM}},
year = {2026},
month = oct,
note = {Preprint, version 1.1. Fully autonomous agentic research; publication responsibility: Dev D. Goyal},
url = {https://github.com/dvgyl/math-and-theory/tree/main/papers/mathematics/admm-multiplier-step}
}