摘要：加州大学伯克利分校研究者Phillip Kerger公布了一项无导数凸优化研究，将确定性精确函数值模型的查询复杂度下界从Ω(d)提高到Ω(d²/log d)，与1996年提出的近二次上界只差对数因子。
7月14日，加州大学伯克利分校工业工程与运筹学研究者 Phillip Kerger 在 arXiv 提交论文《Closing the Oracle-Complexity Gap in Derivative-Free Convex Optimization》。
论文研究一个延续了 30 年的理论问题：当优化算法只能查询函数值、无法获得梯度时，最坏情况下需要查询多少次，才能找到足够接近最优解的点？
论文给出的答案接近维度的平方。此前已知下界只有线性规模，已知上界则接近二次规模，两者之间存在一个多项式缺口。
这次证明将下界提高到：
Ω(d² / log(d+1))
结合已有上界，可以把该问题的维度依赖确定为：
Õ(d²)
其中波浪号表示忽略若干对数因子。
论文作者在正文中明确说明，GPT-5.6 Sol Pro 承担了主要数学推导工作。作者将模型生成的结果整理为论文，检查每个论证，并对文稿中的全部陈述负责。
30年的缺口是什么
凸优化研究如何在一个凸区域内找到凸函数的最小值。许多工程设计、参数优化、资源调度和机器学习问题都可以写成这种形式。
如果算法能够获得梯度，它可以知道函数在当前位置下降最快的方向。但在物理实验、复杂仿真、黑箱设备和部分工业优化中，一次计算只能返回一个结果值。
例如，给出一组设计参数，仿真软件返回能耗；调整一组工艺参数，生产试验返回质量指标；修改一个控制方案，系统返回运行成本。算法看到了结果，却没有获得各个参数对应的梯度。
这类方法称为无导数优化或零阶优化。
论文考虑的是一个较为纯粹的理论模型：
- 优化对象是定义在
d维单位球上的凸函数； - 函数满足 1-Lipschitz 条件，数值变化不会无限剧烈；
- 算法每次可以选择一个点，并获得该点的精确函数值；
- 算法没有梯度、次梯度和分离超平面；
- 算法可以使用无限计算时间和内存；
- 算法采用确定性策略，不使用随机采样。
在这个模型中，查询次数代表函数评估次数。一次物理实验、一次复杂仿真或一次黑箱计算都可以理解为一次查询。
1996年，俄罗斯数学家 Vladimir Protasov 给出了一种算法，其查询次数上界约为：
O(d² log² d)
但此前能够证明的通用下界只有：
Ω(d)
假设问题有 1000 个维度，线性下界与二次上界之间可以相差几个数量级。理论上一直无法判断二次规模的函数评估是否必要。
新证明说明了什么
Kerger 的论文构造了一组特殊的凸函数，并设计了一个“抵抗性预言机”。
预言机可以理解为回答算法查询的黑箱。算法每选择一个点，黑箱返回该点的函数值。抵抗性预言机在回答的同时，保留尽可能多的候选函数。
证明过程利用了一个关键结构：即使算法已经查询了很多点，仍然可能存在两个不同的凸函数，它们对此前所有查询给出完全相同的答案，但两者的最优点相距较远。
确定性算法看到相同的查询记录，只能采取相同的后续步骤，并输出相同结果。这个结果无法同时接近两个函数的最优点，因此至少会在其中一个函数上失败。
论文通过凸几何、体积估计、平均宽度和 Urysohn 不等式等工具证明，在查询次数少于约 d²/log(d+1) 时，预言机仍然能够保留这样的两个函数。
由此得到近二次下界。
这个结论表明，在论文规定的最坏情况模型中，即使每次查询都返回精确实数，算法拥有无限计算能力和无限内存，缺少梯度信息仍然会产生接近二次规模的查询成本。
论文还把结果推广到混合整数凸优化。对于包含 d 个连续变量和 n 个离散变量的问题，函数值查询下界达到：
Ω~(d² 2^n)
这项扩展与组合优化、工业排产和混合决策问题存在一定联系。
GPT-5.6如何完成证明
论文附录公开了研究过程、提示词和两次完整对话。
第一次任务交给 GPT-5.6 Sol Pro 后，模型连续处理了 148 分钟，给出一个近二次查询下界证明。这个版本适用于精度约为 d^-3 的条件。
作者随后要求模型提高精度，使结果能够与 1996 年的上界在相同条件下比较。第二次推导耗时 230 分钟，将精度提高到论文采用的 d^-1/2 量级。
因此，“一个提示解决30年难题”的说法容易造成误解。
从模型接口看，初始证明来自一次长时间运行；从研究方法看，作者提交的是一份详细的数学研究任务书。提示中包含：
- 完整的问题定义和查询模型；
- 已知上界、下界和文献检查点；
- 可以接受的结论形式；
- 明确排除的错误路线；
- 对精度、维度和查询次数的审计要求；
- 多种建议探索的数学方法；
- 对最多 64 个并行代理的调度要求；
- 独立验证、反例搜索和失败记录机制。
提示还要求各个代理提交具体引理、证明、算法、反例或参数计算，不接受泛泛的研究建议。
模型需要维持多条相互独立的证明路线，记录每条路线缺少的关键引理。当候选证明出现后，再安排代理分别检查精度、量词顺序、查询模型、隐含假设和指数计算。
这套方法更接近一个由模型调度的数学研究组。
承担任务的是 GPT-5.6 Sol Pro。提示使用了多代理研究工作流，但没有采用 Sol Ultra 产品模式。论文公开了原始提示和对话，其他研究者可以检查模型提出了哪些思路，以及作者对哪些部分进行了修改。
Lean验证覆盖了哪些内容
仅靠语言模型生成数学文本，很难排除遗漏条件、错误引用和看似合理的推导跳步。
作者使用 Lean 4 和 mathlib 对主要下界进行了形式化验证。Lean 要求把定义、定理和推理步骤转换为机器能够检查的形式，每一步都必须满足类型系统和逻辑内核的要求。
配套 GitHub 仓库目前包含两个验证版本：
- 初始的
d^-3精度下界； - 论文使用的
d^-1/2精度下界。
仓库说明显示，后一个版本已经形式化覆盖论文中的球面平均、Brunn-Minkowski 不等式、内在 Urysohn 不等式以及抵抗性预言机构造。代码没有使用项目自定义公理，也没有在生产证明中保留 sorry 或 admit 形式的证明占位。
形式化范围存在明确边界。Lean 仓库验证了论文的确定性近二次下界，没有验证 Protasov 的既有上界、由上下界合并得到的双侧复杂度结论，也没有覆盖混合整数推广。
Lean 能够检查“形式化后的定理是否由给定公理和定义推出”，无法判断问题选择是否重要、相关文献是否遗漏，也不能替代数学界的同行评审。
目前论文仍是 arXiv 预印本。
这项成果与一般数学问答有什么区别
大模型过去已经能够解答竞赛题、补全证明和调用计算工具。这类任务通常具备已知答案，模型需要恢复一条已有解法。
Kerger 研究的问题没有现成标准答案。模型需要提出新的困难实例、设计抵抗性预言机、组合凸几何工具，并把线性下界提高到近二次下界。
论文作者也没有把 GPT-5.6 描述为写作助手或证明润色工具。他认为主要数学解法由模型给出，自己的工作集中在任务设计、结果检查、精度改进、文稿整理和责任承担。
公开对话、论文原文和 Lean 代码形成了三层记录：
- 对话记录展示模型如何找到证明；
- 论文将证明整理成人类数学语言；
- Lean 检查形式化后的推理链条。
这种发布方式为 AI 参与数学研究提供了较完整的核验材料。
结论仍然有严格边界
论文处理的是确定性、精确函数值、非光滑凸优化的最坏情况查询复杂度。结果不能直接推广到所有优化任务。
它没有证明以下结论：
- 所有实际凸优化问题都需要
d²次计算； - 随机算法也具有相同下界；
- 平滑或强凸函数具有相同复杂度；
- 含噪声的实际实验可以直接套用该结论；
- GPT-5.6 已经能够独立完成任意数学研究。
论文仍留下若干问题。上下界之间还存在对数因子；随机查询模型尚未解决；加入平滑性或强凸性后的复杂度也需要继续研究。
这项工作的价值集中在两个方面。
其一，一个延续自 1996 年的复杂度缺口获得了近乎完整的答案。其二，模型参与过程、原始对话和形式化证明同时公开，使研究者能够逐层检查 AI 在成果中承担的具体工作。
AI 参与数学研究已经具备一条可复查的工作链：研究者定义问题和验收标准，模型进行长时间并行探索，人类承担审查与署名责任，证明助手完成形式化核验。