🔢 mathematics

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

This paper resolves the open question of whether three-block ADMM converges when the third constraint block is the identity matrix by using AI-assisted workflows to construct explicit rational counterexamples demonstrating non-convergence, while also analyzing the conditions under which convergence can be restored through multiplier relaxation.

Original authors: Kenan Xu, Xiangfeng Wang

Published 2026-08-17

📖 4 min read🧠 Deep dive

CC BY 4.0

Original authors: Kenan Xu, Xiangfeng Wang

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine a world where computers are constantly trying to solve massive, messy puzzles. These puzzles are called "optimization problems," and they show up everywhere: from figuring out the most efficient route for a delivery truck to balancing a complex electrical grid. To solve them, scientists use a famous tool called ADMM (Alternating Direction Method of Multipliers). Think of ADMM as a team of three friends trying to agree on a single answer. They take turns making a guess, checking their work, and passing the baton to the next person. For a long time, everyone knew that if there were only two friends, this team would almost always reach a perfect agreement. But when a third friend joined the team, things got tricky. Sometimes, instead of agreeing, the three friends would start running in circles, never quite settling on a solution.

For years, mathematicians have been hunting for the "smoking gun"—a specific example where this three-person team fails. They knew it could happen with complicated rules, but there was one specific, simple scenario that remained a mystery: What if the third friend's rule was the simplest possible one (just a straight line, or an "identity" rule)? Most people hoped that this simplicity would save the day and force the team to converge. This paper steps into that mystery, using a very special kind of AI assistant to build a mathematical trap. The researchers wanted to see if the three-person team could still get stuck in an endless loop even when the rules were as simple as they could be.

The paper delivers a surprising "no" to that hope. The researchers, working with AI tools, successfully constructed a specific mathematical puzzle where the three-block ADMM algorithm fails to converge, even when the third block is the simplest identity matrix possible. They didn't just guess this; they built a rigorous, exact proof. They found a scenario where the algorithm gets stuck in a perfect, repeating loop of 66 steps. It's like a dancer who performs a routine that repeats exactly every 66 beats, never stopping, never finishing, and never reaching the "KKT point" (the mathematical term for the perfect solution). This proves that the simplicity of the third rule is not enough to guarantee the team will ever agree.

To find this, the authors used AI not just to crunch numbers, but to act as a creative partner in discovery. They guided the AI to look for a specific pattern of "switching" behaviors in the algorithm's steps. The AI helped them design a problem where the algorithm's path looks like a near-perfect circle that gets reset every few turns, creating a cycle that never breaks. They verified this with "exact rational arithmetic," meaning they didn't rely on computer approximations that might have rounding errors; they used precise fractions to prove the loop is real and unbreakable.

The paper also explores a "what if" scenario: Could we fix this broken team by just slowing them down? They tested changing the "step size" (how aggressively the algorithm updates its guess). They found that for this specific broken puzzle, slowing down the update (using a smaller step) does fix the problem and makes the team converge. However, they also proved that there is no single "magic speed" that works for every possible puzzle of this type. You have to tune the speed specifically for each problem; a one-size-fits-all solution doesn't exist.

In a second, independent experiment, a different AI setup found an even stranger loop: a cycle of 23 steps that is "attracting." This means that if you start the algorithm anywhere near this loop, it will get sucked into the cycle and stay there forever. This confirms that the failure isn't just a fluke of one specific starting point; it's a stable trap that can catch many different attempts.

Ultimately, this paper shows that even in the simplest-looking mathematical setups, complex algorithms can get stuck in endless loops. It uses AI to not only find these traps but to understand exactly why they happen and how to potentially fix them. The researchers emphasize that this wasn't just a computer guessing; it was a human-guided process where AI helped design the puzzle, and humans verified the proof with absolute mathematical certainty. The result is a clear warning: just because a rule looks simple doesn't mean the algorithm will behave nicely, and we need to be careful about assuming these methods will always work without checking the specific details of the problem.

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

1. Problem Statement

The paper addresses a specific open problem in the convergence theory of the Alternating Direction Method of Multipliers (ADMM). While the two-block ADMM is known to converge under standard assumptions, its direct extension to three blocks is generally known to fail. However, the specific case where the third constraint block is the identity matrix ( $A_3 = I_m$ ) remained unresolved. This configuration arises naturally from inequality-constrained convex programs via the introduction of nonnegative slack variables.

The central question is: Does the direct three-block ADMM converge when the third block is the identity matrix, even if the first two blocks are strongly convex quadratics? Existing literature provided neither a general convergence proof nor a counterexample for this specific subclass.

2. Methodology: AI-Assisted Research Workflow

The authors employ an AI-assisted research process to discover and verify counterexamples. The methodology distinguishes between numerical exploration and rigorous mathematical certification:

Exploration Phase: AI agents (specifically Codex with GPT-5.6 Sol and Kimi Code with Kimi K3) are used to generate candidate counterexamples, propose state reductions, and search for periodic orbits. Floating-point divergence or cycling serves only as a clue.
Certification Phase: All theoretical claims require exact rational certificates. The workflow involves:
1. Representation Discovery: Reducing the ADMM iteration to a lower-dimensional piecewise-affine dynamical system by eliminating variables and tracking active sets (projection signs).
2. Candidate Construction: Constructing explicit rational problem data (matrices $Q_1, Q_2$ , vectors $b$ , etc.) that satisfy the KKT conditions but exhibit non-convergent behavior.
3. Exact Verification: Using exact rational arithmetic to verify period closure, strict branch admissibility (ensuring projection inequalities are strictly satisfied), and minimal period.
4. Stability Analysis: Employing Lyapunov functions, Schur stability tests, and Sturm root counting to certify local attraction or structural persistence.

Two distinct research "harnesses" (configurations of tools, workspace history, and human guidance) were utilized to demonstrate how different AI setups shape mathematical discovery.

3. Key Contributions and Results

A. The Period-66 Counterexample (Codex Route)

Construction: The authors constructed an exact rational counterexample where $A_1 = A_2 = I_2$ , $A_3 = I_2$ , and the objective functions are strongly convex quadratics.
Dynamics: The ADMM iteration generates a bounded, non-KKT sequence with a minimal period of 66.
Mechanism: The orbit follows a specific projection-sign itinerary: $(00)^2(01)^{64}$ . This corresponds to a "near-rotational" phase (64 steps of pattern 01) followed by a "reset" phase (2 steps of pattern 00).
Certification: The existence of the cycle is proven by solving a fixed-point equation for the affine return map in exact rational arithmetic. The proof confirms that all projection inequalities are strict (margin $> 10^{-3}$ ), ensuring the cycle persists under small perturbations of the problem data.
Implication: This result provides a negative answer to the open problem: the identity third block does not guarantee unconditional global convergence.

B. Multiplier Relaxation Analysis

Problem-Dependent Convergence: The paper demonstrates that for the specific period-66 instance, convergence can be restored by reducing the dual step size $\tau$ (multiplier relaxation). A specific range $\tau \in [0.49, 0.51]$ ensures local Q-linear convergence to the KKT point.
No Class-Uniform Step: Conversely, the paper proves that no positive relative step size $\vartheta = \tau/\beta$ works uniformly for the entire class of such problems. For any $\vartheta \in (0, 80/119]$ , a counterexample can be constructed where the method fails to converge.
Adaptive Rule: An adaptive backtracking rule for the dual step is proposed, which guarantees global R-linear convergence for the noncompact slack-last model under strong convexity.

C. The Period-23 Attracting Cycle (Kimi Route)

Independent Discovery: Without access to the period-66 candidate or its specific guidance, the Kimi route discovered a distinct counterexample with a minimal period of 23 in a 3-dimensional setting ( $m=3$ ).
Local Attraction: Unlike the period-66 example which focuses on structural persistence, this certificate proves the existence of an open invariant ellipsoid of initializations that are attracted to the period-23 orbit.
Equivalence: Through a change of variables, this example is shown to be equivalent to an all-identity constraint block instance ( $[I_3, I_3, I_3]$ ), reinforcing the generality of the non-convergence result.

4. Significance and Claims

The paper claims significance in two primary dimensions:

Mathematical Resolution: It definitively settles the "identity-slack" open problem by proving that direct three-block ADMM can fail even with strongly convex objectives and identity constraints. It establishes that convergence cannot be guaranteed by the identity structure alone, nor by a uniform relative step size across the problem class.
AI for Optimization (Theory Discovery): The paper positions itself as a case study in using AI not just for solving optimization problems, but for discovering optimization theory.
- It demonstrates that AI agents can assist in representation discovery (reducing complex iterations to piecewise-affine systems), structured construction (designing instances with prescribed dynamical behaviors like periodicity), and exact certification (generating rigorous proofs via symbolic computation).
- It highlights that the "research harness" (the combination of model, workspace history, tools, and human guidance) significantly influences the mathematical objects discovered. The Codex route focused on mechanism-driven state reduction and itinerary design, while the Kimi route focused on inverse design and basin stability.
- The authors emphasize that their results are not a ranking of base model capabilities but a demonstration of how different research configurations shape the exploration of mathematical spaces.

5. Limitations and Future Directions

The authors modestly note that:

The certificates rely on exact rational arithmetic and symbolic derivation but have not yet been fully formalized in a proof assistant (e.g., Lean or Isabelle).
The comparison between the two AI routes is based on realized runs with different configurations, not a controlled ablation study isolating specific variables (model vs. workspace vs. human steering).
Open questions remain regarding shorter counterexamples in lower dimensions, quantitative conditions for excluding active-set switching, and the transferability of these discovery patterns to other splitting methods (e.g., Douglas–Rachford).