AI-Assisted Discovery and Construction of a Counterexample to the Convergence of Three-Block ADMM with the Identity Matrix as its Third Constraint Block
本文通过利用人工智能辅助工作流构建显式的有理反例来证明不收敛性，同时也分析了可以通过乘子松弛来恢复收敛性的条件，从而解决了当第三个约束块为单位矩阵时三块 ADMM 是否收敛这一开放性问题。
原始论文采用 CC BY 4.0 许可（http://creativecommons.org/licenses/by/4.0/）。 这是对下方论文的AI生成解释。它不是由作者撰写或认可的。如需技术准确性，请参阅原始论文。 阅读完整免责声明
想象一个计算机不断试图解决大规模、混乱谜题的世界。这些谜题被称为“优化问题”，它们无处不在：从计算送货卡车最有效的路线，到平衡复杂的电网。为了解决这些问题，科学家们使用了一种著名的工具——ADMM（交替方向乘子法）。你可以把 ADMM 想象成一个由三位朋友组成的团队，他们正试图达成一个统一的答案。他们轮流做出猜测、检查工作，并将接力棒传递给下一个人。长期以来，大家都知道如果只有两位朋友，这个团队几乎总能达成完美的共识。但当第三位朋友加入时，情况变得棘手了。有时，这三位朋友并没有达成一致，而是开始原地打转，永远无法稳定在一个解上。
多年来，数学家们一直在寻找那个“确凿证据”——即一个能让这个三人团队失败的具体案例。他们知道在规则复杂的情况下这确实会发生，但有一个特定的简单场景一直是个谜：如果第三位朋友的规则是最简单的（仅仅是一条直线，或者说是一个“恒等”规则）会怎样？大多数人都希望这种简洁性能化险为夷，迫使团队收敛。这篇论文深入研究了这个谜团，利用一种非常特殊的 AI 助手来构建一个数学陷阱。研究人员想要看看，即使规则像能尽可能简单时，这个三人团队是否仍会陷入无尽的循环。
论文给出了一个令人惊讶的“不”字，否定了这种希望。研究人员在 AI 工具的辅助下，成功构建了一个特定的数学谜题，在这个谜题中，即使第三块是尽可能简单的恒等矩阵，三块 ADMM 算法仍然无法收敛。他们不仅仅是靠猜测，而是建立了一个严谨、精确的证明。他们发现了一个场景，算法会陷入一个完美的、重复的 66 步循环。这就像一位舞者表演一段每 66 拍就精确重复一次的舞步，永不停歇，永不结束，也永远无法达到“KKT 点”（数学术语，指完美解）。这证明了即便第三个规则足够简单，也并不足以保证团队最终能达成一致。
为了找到这一点，作者不仅利用 AI 进行数值计算，还将其作为发现过程中的创意伙伴。他们引导 AI 去寻找算法步骤中特定的“切换”行为模式。AI 帮助他们设计了一个问题，使得算法的路径看起来像一个每隔几回合就会重置的近乎完美的圆圈，从而创造出一个永不打破的循环。他们通过“精确有理算术”验证了这一点，这意味着他们没有依赖可能产生舍入误差的计算机近似值，而是使用了精确的分数来证明这个循环是真实且不可打破的。
论文还探讨了一个“如果……会怎样”的情景：我们能否通过仅仅降低速度来修复这个失灵的团队？他们测试了改变“步长”（即算法更新其猜测的激进程度）的情况。他们发现，对于这个特定的失效谜题，放慢更新速度（使用较小的步长）确实能解决问题并使团队收敛。然而，他们同时也证明了，不存在一个适用于此类所有可能问题的单一“魔力速度”；你必须针对每个问题专门调整速度，并不存在通用的解决方案。
在第二个独立的实验中，另一种 AI 设置发现了甚至更奇怪的一个循环：一个 23 步的“吸引子”循环。这意味着，如果你从这个循环附近的任何地方开始运行算法，它会被吸入这个循环并永远停留在那里。这证实了这种失败并非某个特定起始点的偶然现象；它是一个稳定的陷阱，可以捕捉许多不同的尝试。
最终，这篇论文表明，即使在看起来最简单的数学设置中，复杂的算法也可能会陷入无尽的循环。它利用 AI 不仅是为了寻找这些陷阱，也是为了理解它们究竟是如何发生的，以及如何潜在地修复它们。研究人员强调，这不仅仅是计算机在进行猜测，而是一个由人类引导的过程，其中 AI 帮助设计了谜题，而人类则用绝对的数学确定性验证了证明。结果是一个明确的警告：仅仅因为一个规则看起来很简单，并不意味着算法就会表现良好，我们需要谨慎对待，不要假设这些方法在没有检查问题具体细节的情况下总能奏效。
您所在领域的论文太多了？
获取与您研究关键词匹配的最新论文每日摘要——附技术摘要，使用您的语言。