← All papers
First page of The multiplier step size in classical two-block ADMM: convergence and counterexamples

The multiplier step size in classical two-block ADMM: convergence and counterexamples

Benqi Liu, Qiming Dai, Zaiwen Wen

math.OC Nov 6, 2026 · v1
Results on ADMM multiplier step-size convergence and counterexamples are accompanied by a Lean 4 formalization hosted in the ReasBook project.
How large can the multiplier step be in the classical two-block alternating direction method of multipliers (ADMM)? We keep the penalty fixed and use the usual primal updates. We consider finite-dimensional problems with closed proper convex objectives. We assume that a Karush-Kuhn-Tucker point exists and that each block subproblem attains its minimum at every step. Under these assumptions, the constraint images and the multiplier converge for a range of factors that extends beyond the golden ratio. The constraint matrices may be rank deficient. For larger steps, we construct two fixed compact polytopes and give an explicit threshold below two. The polytopes admit an infeasible periodic orbit for every factor at or above this threshold. At that threshold, ADMM can cycle even for smooth strongly convex objectives. This gives a negative answer to Glowinski's question about the full interval from zero to two. A different pair of piecewise-quadratic objectives gives geometrically growing residuals. For the general convex class, we locate the endpoint of the uniform convergence interval near 1.88688256. A convergence certificate on the unit circle gives the lower bound, while a separate periodic orbit gives the upper bound. Exact arithmetic verifies that the two bounds differ by less than 0.000000174.

How large can the multiplier step factor be in classical two-block ADMM for general closed proper convex problems? Glowinski asked whether the full interval (0,2) is admissible, as it is for some structured problems.

Convergence is proved by reducing the iteration to the constraint images using closed biconjugate image functions and a Lyapunov-type argument, combined with a certificate on the unit circle. Counterexamples are built in R^96 by prescribing periodic multiplier sequences and checking support inequalities, so that the primal updates are projections onto fixed polytopes. A perturbation and an interpolation argument extend these cycles to smooth strongly convex and piecewise-quadratic objectives. A Lean 4 formalization accompanies the work.

For factors up to L≈1.88688247, the constraint images converge, the residuals vanish, and the multipliers converge. Period-48 infeasible orbits exist for all factors at or above about 1.886957, including at that threshold for smooth strongly convex objectives, which answers Glowinski's question negatively. The uniform convergence endpoint lies between L and U, and exact arithmetic shows U−L≈1.74×10^-7.