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

Kenan Xu; Xiangfeng Wang

math.OCAug 14, 2026

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

Authors: Kenan Xu, Xiangfeng Wang

Organizations: School of Mathematical Sciences, East China Normal University, Shanghai 200241, P.R. China. · Key Laboratory of Mathematics and Engineering Applications (MoE) and School of Mathematical Sciences, East China Normal University, Shanghai 200241, P.R. China.

Abstract

The alternating direction method of multipliers (ADMM), as a landmark algorithm, has attracted tremendous research attention and extensive practical applications over the past two decades. It is well known that, although the two-block ADMM enjoys well-established theoretical convergence guarantees, its direct extension to the three-block case may fail to converge, as demonstrated by existing counterexamples [5]. However, to the best of our knowledge, the case in which the third constraint block is the identity remains unresolved: the existing literature gives neither a general convergence proof nor a counterexample for this subclass. In this paper, we give a negative answer: direct three-block ADMM may fail even when the first two blocks are strongly convex quadratics. Using Codex with GPT-5.6 Sol, we construct an explicit rational counterexample candidate and verify it along a piecewise-affine reduction path; exact checks show that direct three-block ADMM on this instance produces a bounded nonconvergent orbit of period 66. Within the same Codex workflow, we further guide a study of multiplier relaxation and clarify when convergence can be restored at the fixed-instance and class levels: a problem-dependent small dual step can restore convergence, whereas no positive relative step works uniformly over the whole class. Furthermore, we also test the recent Kimi Code with Kimi K3 model without the Codex candidate or project-specific route guidance; along a different path it produces an exact locally attracting period-23 certificate, convertible to an equivalent all-identity instance. The comparison suggests that different research-harness configurations can shape the mathematical objects explored and the certificates pursued.

Figures & tables

Figure 1: Decimal visualization of the exact rational period-

66

sequence. Red squares mark the two

00

iterates; the remaining iterates have pattern

01

. The KKT coordinate

q^{\star}=(-1,1)

is not on the periodic sequence.

Figure 2: Certified dual-step ranges for the fixed rational instance: pointwise local attraction on the strict

D_{01}

branch, a uniform common-Lyapunov interval, and convergence of the initialization in Theorem 2.1 .

Figure 3: Kimi period- $23$ certificate: projection word and margin; invariant-ellipsoid slice; spectrum of $M_{\rm per}$ .

Panel of Figure 4 — Figure 4: Candidate-generation and claim-promotion workflow shared by the two AI-assisted research routes. Models may propose representations, search objects, and candidates in the exploration stage, but only conclusions that pass exact verification and a human claim-scope audit enter the final mathematical record. The two routes share the same mathematical question and evidence principles, but use different harness configurations.

Aspect	Codex / GPT-5.6 Sol route	Kimi Code / Kimi K3 route
Harness configuration	Long-running project workspace; project-specific ADMM skill and experiment toolchain; persistent research artifacts; iterative human steering	Frozen blind workspace; generic research skills with shell/Python tools; isolated route state; few continue-search instructions
Main search object	Resolvent parameters $(M,N)$ and realizable active-set itinerary $(00)^{2}(01)^{64}$	KKT-compatible QP data and projection itinerary $\mathcal{W}_{23}$
Reduced state	$s=(y,q)\in\mathbb{R}^{4}$ , $q=z+\lambda$ ; direct $m=2$ all-identity model	$v=(y,t)\in\mathbb{R}^{6}$ , $t=z+\lambda$ ; $m=3$ model, equivalently convertible to all-identity form
Construction style	Mechanism-driven: state reduction, branch-spectrum analysis, and near-rotation/reset itinerary design	Inverse design: jointly synthesize problem data, projection itinerary, and return-map fixed point
Main certificate	Exact period closure, strict branch checks, raw ADMM replay, and minimal-period verification	Exact period closure, strict projection checks, discrete Lyapunov inequality, and invariant ellipsoid
Dynamical conclusion	Minimal period- $66$ non-KKT orbit; exposes active-set switching instability	Minimal period- $23$ locally attracting non-KKT orbit; certified open attracting basin

Table 1: Comparison of the two realized AI-assisted research routes.

Appendix figures & tables1 asset

Supplementary material from the paper’s appendix.

Appendix

Stage	Human input	AI output	Promotion condition
Problem setup	Identity-slack question; evidence requirements	Proof and counterexample route proposals	Correct literature boundary
State-space reduction	Request for a certifiable representation	Signed reduced state $s=(y,q)$ , $q=z+\lambda$ (jointly refined)	Equivalence to raw ADMM
Candidate screening	Requirement that fixed-branch instability alone is insufficient	Fixed-branch spectra; near-rotation heuristic	Projection itinerary must be realizable
Period search	Requirement of a strict exact counterexample	Rational data ( 2.3 )–( 2.5 ) and word $(00)^{2}(01)^{64}$	Exact rational closure and strict signs ( $G_{1}$ – $G_{7}$ )
Relaxation extension	Frozen QP and initialization; vary only $\tau$ ; quantifier gates	Parameterized branch maps; candidate step regimes; certificate routes	Quantifier audit and exact certificates

Appendix

Table 2: Recorded stages of the Codex route, with the promotion condition that gated each stage.

AI-Assisted Mathematical Discovery

See all 18 papers

Second-Order KKT Guarantees for Bregman ADMM in Nonconvex and Non-Lipschitz Optimization
Jun 26, 2026Shuang Li, Zhihui Zhu, Qiuwei LiOptimization Convergence Analysis Distributed Optimization
Department of Electrical and Computer Engineering, Iowa State University, Ames, Iowa 50014, USA · Department of Computer Science and Engineering, Ohio State University, Columbus, Ohio 43210, USA · DAMO Academy, Alibaba Group US, Bellevue, Washington 98004, USA
Learning Over-Relaxation Policies for ADMM with Convergence Guarantees
Apr 29, 2026Junan Lin, Paul J. Goulart, Luca FurieriLearning to Optimize Alternating Direction Method of Multipliers
Department of Engineering Science, University of Oxford, OX1 3PJ Oxford, UK
Adam symmetry theorem: characterization of the convergence of the stochastic Adam optimizer
Nov 10, 2025Steffen Dereich, Thang Do, Arnulf Jentzen +1Stochastic Optimization Stochastic Optimization Convergence
Institute for Mathematical Stochastics, Faculty of Mathematics and Computer Science, University of Münster, Germany · School of Data Science, The Chinese University of Hong Kong, Shenzhen (CUHK-Shenzhen), China · School of Data Science and School of Artificial Intelligence, The Chinese University of Hong Kong, Shenzhen (CUHK-Shenzhen), China +1

Jun 26, 2026J/K move · Enter open · S save

Second-Order KKT Guarantees for Bregman ADMM in Nonconvex and Non-Lipschitz Optimization

Shuang Li, Zhihui Zhu, Qiuwei Li

Department of Electrical and Computer Engineering, Iowa State University, Ames, Iowa 50014, USA · Department of Computer Science and Engineering, Ohio State University, Columbus, Ohio 43210, USA · DAMO Academy, Alibaba Group US, Bellevue, Washington 98004, USA

Optimization Convergence Analysis Distributed Optimization Alternating Direction Method of Multipliers Nonconvex Optimization

Open paper AskPDF arXiv

We analyze Bregman ADMM for nonconvex linearly constrained problems under two-sided relative smoothness, a condition that replaces the standard Lipschitz gradient assumption with a Hessian comparison relative to a Bregman kernel. This setting covers polynomial objectives arising in matrix and tensor models for which a global Lipschitz-gradient constant need not exist. We show that on an invariant open state-space domain, one iteration of Bregman ADMM defines a smooth primal--dual fixed-point map whose strict-saddle KKT points are unstable fixed points; consequently, from random initialization the iterates converge to a strict saddle with probability zero. Combined with existing first-order convergence results, this yields almost-sure second-order stationarity of limiting KKT points. We extend the analysis to a multi-block star consensus formulation for distributed optimization. The technical novelty lies in a determinant reduction with a Bregman-specific symmetrization and scaling step in the two block spectral argument, together with a null space cancellation exploiting the star graph structure in the consensus case. Numerical experiments on distributed matrix factorization illustrate the theory, and a symmetric tensor factorization example demonstrates the broader Bregman proximal splitting idea beyond the separable consensus setting.

Abstract

AI-Assisted Mathematical Discovery

Explore similar work

Second-Order KKT Guarantees for Bregman ADMM in Nonconvex and Non-Lipschitz Optimization

Learning Over-Relaxation Policies for ADMM with Convergence Guarantees

Adam symmetry theorem: characterization of the convergence of the stochastic Adam optimizer