MathDB

Convergence problem for three-block ADMM with an identity third constraint block

Consider the separable constrained optimization problem min⁡x1,x2,x3 f1(x1)+f2(x2)+f3(x3)\min_{x_1,x_2,x_3}\ f_1(x_1)+f_2(x_2)+f_3(x_3) subject to A1x1+A2x2+Ix3=bA_1x_1+A_2x_2+Ix_3=b, where the first two objective functions are strongly convex quadratics. Applying direct, sequential three-block ADMM to the three variables, must the resulting primal and dual iterates converge to a KKT point for every such instance and every initialization? Equivalently, can direct three-block ADMM fail to converge even when the third constraint block is the identity and the first two objectives are strongly convex quadratics?

Equivalent formulations 1

Other statements of this same problem, merged from separate entries. Each is equivalent to the statement above — proving any one settles them all.

  1. All-identity constraint formulation

    The same convergence question is presented in an equivalent formulation in which the constraint matrix is [I3,I3,I3][I_3,I_3,I_3]: does direct three-block ADMM necessarily converge for every instance in this all-identity class?

    source: AI-Assisted Discovery and Construction of a Counterexample to the Convergence of Three-Block ADMM with the Identity Matrix as its Third Constraint Block

Sources & referencesView supporting material

Primary source

arXiv

Additional references

computational-mathematicsoperator-splittingoptimization

Progress summary

Refreshed
Claimed solved

An unrefereed preprint claims a rigorous counterexample showing that this version of the algorithm can fail, but the result has not been independently confirmed.

The problem asks whether three-block ADMM must converge when the third constraint block is the identity, including when the first two objectives are strongly convex quadratics. The previously unresolved subclass is now claimed to have a negative answer.

August 2026 claimed counterexample

Kenan Xu and Xiangfeng Wang report an exact rational instance with a bounded, non-KKT periodic orbit of minimal period 6666, with strict projection inequalities. They also claim a locally attracting period-2323 orbit, an equivalent all-identity [I3,I3,I3][I_3,I_3,I_3] formulation, and that small dual relaxation stabilizes a fixed instance without yielding uniform convergence over the class. The paper credits Codex with GPT-5.6 Sol for the first candidate and Kimi Code with Kimi K3 for a second certificate. No independent verification, referee report, correction, withdrawal, or retraction was found.

Current status (as of August 2026): The preprint claims to settle nonconvergence for the identity-third-block subclass, but until its certificates are independently checked, the claim remains unverified; fixed-instance stabilization and uniform convergence remain distinct questions.

  • CodexOpenAIpartial progress2026-08-17evidence

    Three-block ADMM is shown to fail even with an identity third block

  • GPT-5.6 SolOpenAIsolved2026-08-17evidence

    Three-block ADMM with an identity third block is shown to admit nonconvergent orbits

  • Kimi K3solved2026-08-17evidence

    Three-block ADMM with an identity third block is shown to admit nonconvergent orbits

Sources

Solutions 0

No solutions have been posted yet.