用AI自动发现凸松弛，提升优化问题下界
AI-Assisted Discovery of Convex Relaxations via Dual Agents
- 双代理协同搜索有效松弛约束
- 在两个常数上分别将下界提升至1.2937和0.37912
- 通过区间算术严格验证，适合形式化推理研究者
近期工作表明，大语言模型代理可通过搜索极值构造来改进紧致常数不等式，得到上界。本文聚焦互补方向：对任意可行函数，非凸问题的凸松弛可导出下界，更紧的松弛带来更强下界。我们实例化自研研究范式：编码代理提出有效收紧约束，理论代理验证并寻找反例，每个报告的边界均由显式对偶可行点通过严格区间算术验证。针对Tao等人研究的两个优化常数——首阶自相关不等式（C_{6.2}）与Erdős最小重叠常数（C_{6.5}），我们分别将认证下界从1.28提升至1.2937，从0.379005提升至0.37912。
原文摘要 · Abstract (English)
Recent work shows that LLM agents can improve sharp-constant inequalities by searching for extremal constructions, which yield upper bounds. We address the complementary side: a lower bound holds for every admissible function and follows from a convex relaxation of the nonconvex problem, with tighter relaxations giving stronger bounds. We instantiate the autoresearch paradigm to discover such relaxations: a coding agent proposes valid tightening constraints, a theory agent verifies each one and searches for counterexamples, and every reported bound is certified by an explicit dual-feasible point checked in rigorous interval arithmetic. On two optimization constants studied by \citet{tao2025alphaevolve} - the first autocorrelation inequality ($C_{6.2}$) and the Erdős minimum-overlap constant ($C_{6.5}$) - we improve the certified lower bounds from $1.28$ to $1.2937$ and from $0.379005$ to $0.37912$, respectively.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。