🤖 AI

AI-Assisted Discovery of Convex Relaxations via Dual Agents

本文提出了一种利用双智能体进行 AI 辅助的框架，用于发现并严格认证非凸优化问题中改进的凸松弛，成功收紧了第一个自相关不等式和埃尔德什（Erdős）最小重叠常数的下界。

原作者： Sungyoon Kim, Mert Pilanci

发布于 2026-07-01

📖 1 分钟阅读☕ 轻松阅读

原作者： Sungyoon Kim, Mert Pilanci

原始论文采用 CC BY 4.0 许可（http://creativecommons.org/licenses/by/4.0/）。 ✨ 这是对下方论文的AI生成解释。它不是由作者撰写或认可的。如需技术准确性，请参阅原始论文。阅读完整免责声明

想象一下，你正试图为一个复杂的数学谜题寻找绝对的“最坏情况”。在数学世界中，有两种方法可以证明情况会变得多么糟糕：

“展示给我看”法（上界）： 你构建一个特定的、糟糕的例子，以此证明情况确实可以这么糟。这就像是找出一个具体的交通拥堵案例，以此证明“回家路上的交通可能需要2小时”。
“证明其不可能”法（下界）： 你必须证明，无论人们如何尝试，情况都不可能比某个点更好。这就像是证明“无论你怎么开车，回家的时间都不可能少于45分钟”。

这篇论文讨论的是第二种——也更难的一种方法。作者使用了一个由 AI 智能体组成的“超级聪明数学侦探小队”，来寻找更好的“不可能”证明。

团队：两个协同工作的 AI 智能体

作者并没有让一个 AI 尝试完成所有工作，而是建立了一个“双智能体”系统，就像一个创意作家和一个严厉编辑在循环中协作。

编码智能体（发明家）： 这个智能体是富有创造力的。它的任务是观察一个数学问题，然后说：“我认为如果我们增加这条新规则或约束，我们就能证明答案甚至更高。”它编写计算机代码来测试这条新规则。你可以把它想象成一位建筑师正在绘制一张更紧凑的新蓝图。
理论智能体（怀疑论者）： 这个智能体是严厉的编辑。它阅读新的蓝图，并询问：“这条规则对所有可能的情况都成立吗？还是说你犯了错误？”它试图通过寻找反例（即规则失效的具体情况）来推翻这条规则。
- 如果理论智能体发现了缺陷，它会将蓝图发回给编码智能体进行修复。
- 如果理论智能体确信这条规则是可靠的，它就会给出通行许可。

目标：收紧网格

他们处理的问题涉及自相关不等式（Autocorrelation Inequalities）。简单来说，这些是关于一个形状在移动时与自身重叠程度的规则。

想象你有一个模糊的云团（函数）。你想知道：“如果我让这个云团在自身上方滑动，无论我如何塑造这个云团，我能保证的最小重叠程度是多少？”

旧方法： 先前的研究人员拥有一个捕捉所有可能云团的“网”（数学松弛），但这个网有很多大洞。他们得到的答案有点宽松（例如，“重叠至少为 1.28”）。
新方法： AI 智能体通过协作来修补这些洞。它们增加了新的、经过数学验证的规则，使网变得更紧密。
- 对于第一个问题，他们收紧了网，足以证明重叠实际上至少为 1.2937（从 1.28 提升而来）。
- 对于第二个问题，他们证明了重叠至少为 0.37912（从 0.379005 提升而来）。

这些数字看起来很小，但在高深数学领域，即使是提高一个微小的常数也是一次巨大的胜利。这意味着他们找到了一个更精确的“底线”，即答案永远不会低于该值。

“金标准”检查

这篇论文最令人印象深刻的部分在于他们如何确保自己没有作弊。

当 AI 解决数学问题时，它通常使用的计算器会进行四舍五入，这可能会导致微小的误差。如果你向上取整，你可能会在无意中声称一个数字比实际情况更高。

为了解决这个问题，作者使用了一个对偶证书（Dual Certificate）。

可以把编码智能体想象成正在建造一座桥。
理论智能体负责检查数学逻辑。
但为了百分之百确定这座桥不会坍塌，他们使用了特殊的“区间算术（interval arithmetic）”检查。这就像是用一把自带微小误差范围的尺子来测量桥梁，确保即使在最坏的舍入情况下，桥梁依然安全。

他们不仅仅是说“计算机显示为 1.2937”。他们产生了一个特定的、可验证的数学“收据”（对偶可行点），这证明了在没有任何怀疑的情况下，答案确实至少有那么高。

总结

简而言之，这篇论文描述了一种将 AI 用于纯数学的新方法。他们并没有仅仅停留在猜测答案，而是创建了一个循环：一个 AI 发明新的数学规则，而另一个 AI 则进行严格测试以确保这些规则是正确的。通过这样做，他们成功地收紧了两个著名且长期存在的问题的数学“安全网”，证明了这些答案比之前任何人所认证的都要更高（也更精确）。

技术摘要：通过双智能体发现凸松弛的 AI 辅助研究

1. 问题陈述

本文探讨了提高泛函分析中锐利常数（sharp-constant）不等式认证下界（certified lower bounds）的挑战，特别关注非凸优化问题，其目标是在无限维的可容许函数空间中寻找评分（score）的下确界。

作者针对 Georgiev 等人 (2025) 研究的两个特定常数进行了研究：

第一自相关不等式 (C6.2)： 一个源于加性组合学中与 Sidon 集相关的常数，由以下不等式定义：
$\max_{-1/2 \le t \le 1/2} \int_{\mathbb{R}} f(t-x)f(x) \, dx \ge C_{6.2} \left( \int_{-1/4}^{1/4} f(x) \, dx \right)^2$
对于所有非负函数 $f: \mathbb{R} \to \mathbb{R}$ 均成立。
Erdős 最小重叠常数 (C6.5)： 一个控制最小重叠问题渐近性质的常数，由以下不等式定义：
$\sup_{x \in [-2, 2]} \int_{-1}^{1} f(t)g(x+t) \, dt \ge C_{6.5}$
其中对于满足 $f+g=1$ 且 $\int f = 1$ 的非负函数 $f, g: [-1, 1] \to [0, 1]$ 成立。

虽然近期由 AI 驱动的工作通过搜索极值构造（即违反某个界的特定函数）成功提高了上界（upper bounds），但提高下界（lower bounds）则是另一回事。一个下界必须对每一个可容许函数都成立，这需要证明不存在任何函数能使评分低于某个特定值。这通常通过求解原始非凸问题的凸松弛（convex relaxation）来实现。松弛越紧（即添加了越多的有效约束），下界就越强。

2. 方法论：双智能体循环

作者通过一个由两个专门的语言模型（LLM）智能体驱动的人机协同框架，实例化了一个自动研究范式（autoresearch paradigm）。该系统旨在迭代地发现并验证用于收紧凸松弛的有效约束。

智能体

编码智能体 (Coding Agent)：
- 角色： 为凸程序提出新的约束或强化现有约束。
- 输出： 生成修改后的凸优化程序以及一个“严格证明”（数学论证），用以证明该新约束对所有可容许函数均成立。
- 行动： 使用代码（利用 CVXPY）实现该约束，并求解该程序以产生候选下界。
理论智能体 (Theory Agent)：
- 角色： 作为验证器和反例搜索器。
- 行动： 阅读提议的约束及其证明。它批判性地分析逻辑，以确保约束是可容许条件（例如 $f \ge 0$ ）的必然结果。至关重要的是，它会主动寻找反例——即违反所提议约束的特定可容许函数。
- 决策： 如果证明是完备的且未发现反例，则接受该约束。如果发现缺陷或反例，则拒绝该提议，并指示编码智能体尝试不同的方法。

验证流水线

为了确保最终结果是经过认证的界（即经过数学证明，而非仅仅是数值估计），系统采用了严谨的双重认证过程：

对偶可行性： 系统构建凸程序的对偶程序。
区间算术： 它寻找一个对偶可行点 $\lambda$ ，并使用严谨的区间算术来验证其可行性和对偶目标值。这考虑了浮点舍入误差和无理数数据（如三角矩）的影响。
认证： 根据弱对偶性，一个具有目标值 $\beta$ 的有效对偶点 $\lambda$ 证明了原问题最优值（以及真实的常数）至少为 $\beta$ 。最终报告的界是经过验证的包络线的下端点。

人类角色

人类研究员进行最后的审查和紧凑化（compactification）。智能体循环往往会累积冗余约束。人类会对最终的程序进行审查，移除不必要的约束以创建一个最小且易读的公式，并在最终认证前验证数学论证。

3. 核心贡献

范式转移： 本文展示了将 AI 智能体应用于发现凸松纳（而非仅仅是搜索极值样本）的新颖应用。它解决了不等式中“下界”这一侧的问题，这需要证明全称量化（对所有函数均有效），而非存在量化（找到一个函数）。
双智能体框架： 它引入了一个特定的循环，其中编码智能体提出约束，而理论智能体验证有效性并搜寻反例，从而有效地实现了数学松弛的迭代细化自动化。
严谨认证： 通过集成区间算术和对偶可行性检查，确保了改进后的界是经过数学认证的，不受数值求解器浮点精度的影响。

4. 结果

该框架被应用于上述两个常数，提高了认证下界：

C6.2 (第一自相关不等式)：
- 此前最佳下界：1.28 (Cloninger & Steinerberger, 2017)。
- 新认证下界：1.2937。
- 注：此前不存在针对该问题的凸程序；智能体从零开始构建了一个。
C6.5 (Erdős 最小重叠常数)：
- 此前最佳下界：0.379005 (White, 2022)。
- 新认证下界：0.37912。
- 注：智能体从 White 现有的凸程序出发，基于 Bochner 定理发现了两个新的有效约束（即强制要求 $f$ 及其补函数 $g=1-f$ 的矩序列均可由非负测度实现）。

论文指出，虽然上界已通过搜索类方法（如 Together AI, 2026）得到提升，但下界自 2022 年以来一直停滞不前。本研究成功推动了下界的进展。

5. 意义与主张

作者声称这是首次使用自动研究风格的智能体循环来改进这些特定不等式的认证下界。其意义在于：

互补性： 它与现有的专注于寻找极值样本（上界）的 AI 研究形成互补，通过通过松弛来解决证明下界这一更难的问题。
发现的自主性： 智能体成功识别了之前的人类设计公式中所忽略或未能明确施加的数学属性（例如 $f$ 和 $1-f$ 的 Bochner 条件）。
通用性： 虽然在自相关不等式上进行了演示，但作者表示该框架并非针对这些特定问题。它适用于任何可以将下界表示为通过增加有效约束来收紧的凸松弛、并通过对偶进行认证的非凸优化问题（例如在优化、组合数学和控制领域）。

论文结论较为谦逊，承认目前约束的有效性依赖于人类对数学论证的审查，而非形式化证明辅助工具（如 Lean），尽管这暗示了未来与形式化验证工具集成后可以实现完全自主的循环。