arXiv:2608.14396math.OCcs.AI2026-08

用AI构造反例,证明三块ADMM在特定条件下不收敛

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

论文配图: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 · 摘自论文原文
  • 借助AI生成并验证一个显式反例,证明三块ADMM可不收敛
  • 发现即使前两块为强凸二次函数,仍存在周期66的非收敛轨道
  • 适合优化理论、AI辅助数学发现的研究者阅读

交替方向乘子法(ADMM)作为标志性算法,在过去二十年中受到广泛关注并有广泛应用。众所周知,虽然两块ADMM具有成熟的收敛性理论保障,但其直接推广到三块情形可能不收敛,已有反例证实。然而,当第三块约束为单位矩阵时,现有文献既无一般收敛性证明,也无反例。本文给出否定答案:即使前两块为强凸二次函数,直接三块ADMM仍可能不收敛。我们使用Codex与GPT-5.6 Sol构建显式有理反例候选,并沿分段仿射约化路径验证;精确检查表明,该实例上直接三块ADMM产生周期66的有界非收敛轨道。在同一Codex工作流中,进一步研究对偶松弛,澄清了收敛恢复的条件:问题相关的微小对偶步长可恢复收敛,而全局统一的正相对步长无效。此外,我们测试了Kimi Code与Kimi K3模型,未依赖原候选或项目特定引导,沿不同路径生成一精确局部吸引的周期23证书,可转化为等价全单位矩阵实例。对比表明,不同研究工具配置会影响探索的数学对象与所追求的证书形式。

原文摘要 · Abstract (English)

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.

优化算法ADMMAI辅助证明

Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。