AI-Assisted Discovery of Convex Relaxations via Dual Agents
AI 深度解读
背景
在数学与优化领域，确定一个常数的精确值通常需要从两个方向夹逼：上界（Upper Bound）与下界（Lower Bound）。上界往往通过寻找极值构造（Extremal Constructions）来证明，即找到一个具体的例子使得常数不可能更大；而下界则要求证明对于所有符合条件的对象，常数都不可能更小。近期，随着 LLM 智能体（LLM agents）的发展，AI 辅助寻找极值构造以改进上界取得了显著进展。然而，如何通过 AI 自动发现凸松弛（Convex Relaxations）来证明并改进下界，仍是该领域亟待攻克的互补性难题。
核心内容
本文针对非凸问题的下界证明，提出了一种基于双智能体（Dual Agents）的 AI 辅助发现框架，旨在自动寻找更紧的凸松弛以推导出更强的下界。
核心逻辑在于：一个下界如果成立，必须适用于所有容许函数，而这通常可以通过对非凸问题进行凸松弛来实现——松弛越紧，得到的下界就越强。为了自动化这一发现过程，作者实例化了“Autoresearch”（自动研究）范式，构建了两个分工明确的智能体：
- 编码智能体（Coding Agent）：负责提出有效的收紧约束（Tightening Constraints），试图让凸松弛更逼近原非凸问题。
- 理论智能体（Theory Agent）：负责验证编码智能体提出的每一个约束。它不仅验证约束的正确性，还主动搜索反例（Counterexamples），以确保证明的严密性。
为了保证下界的绝对严谨性，该系统还引入了严格的数学验证机制：每一个报告的下界都附有一个显式的对偶可行点（Dual-feasible Point），并且该点会在**严格的区间算术（Rigorous Interval Arithmetic）**中进行双重检查，彻底排除了浮点误差与逻辑漏洞。
查看原文 →arxiv.org