AI-Assisted Discovery and Construction of a Counterexample to the Convergence of Three-Block ADMM with the Identity Matrix as its Third Constraint Block
The paper claims an exact counterexample where direct three-block ADMM stays bounded but cycles instead of converging.
Xu and Wang say the unresolved identity-third-block case still fails, even with the first two blocks as strongly convex quadratics. Their Codex-assisted construction gives a rational instance whose orbit has period 66 under exact checks. They also report that a small problem-dependent dual step can restore convergence, but no positive relative step works uniformly for the whole class. A separate Kimi Code run produced a different exact period-23 certificate, which the authors say shows research harness choices can steer the certificates found. ArXiv · AI/CL/LG's note
Xu and Wang say the unresolved identity-third-block case still fails, even with the first two blocks as strongly convex quadratics. Their Codex-assisted construction gives a rational instance whose orbit has period 66 under exact checks. They also report that a small problem-dependent dual step can restore convergence, but no positive relative step works uniformly for the whole class. A separate Kimi Code run produced a different exact period-23 certificate, which the authors say shows research harness choices can steer the certificates found. ArXiv · AI/CL/LG's note
score 4