⚡ electrical engineering

Disjunctive Sum of Squares

本文介绍了析取平方和的概念，这是一种通过多个并行代数恒等式来验证多项式非负性的方法，它使得能够构建具有固定规模半定约束且无需优化的替代方案的收敛优化层级，同时展示了其在多项式优化、余正优化和组合优化中的实际应用。

原作者： Amir Ali Ahmadi, Sanjeeb Dash, Yixuan Hua, Bartolomeo Stellato

发布于 2026-05-28

📖 1 分钟阅读☕ 轻松阅读

原作者： Amir Ali Ahmadi, Sanjeeb Dash, Yixuan Hua, Bartolomeo Stellato

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

想象你是一名侦探，试图证明一台神秘而复杂的机器（一个数学多项式）永远不会产生负数。在数学世界中，这被称为证明“非负性”。

几十年来，解决这一谜题的标准方法是找到一个单一、完美的代数方程，它就像一把万能钥匙。如果你能将机器的输出写为平方和（例如 $A^2 + B^2 + C^2$ ），你就确切地知道它绝不可能是负数，因为平方数总是非负的。

然而，这种“单把钥匙”的方法存在一个主要缺陷：有时，为了让那一个方程成立，你必须使用极其复杂的高次项。这就像试图用一把长达 50 英尺的巨型骨架钥匙去开一扇简单的门。它确实能打开，但它沉重、建造成本高昂，并且在许多现实场景中计算上根本无法使用。

新构想：一支小钥匙团队

本文介绍了一种名为析取平方和（Disjunctive Sum of Squares）的新策略。作者提出，与其寻找一把巨大而复杂的钥匙，不如使用一支更小、更简单的钥匙团队。

核心概念如下：

分割世界：想象所有可能的输入构成一个大房间。我们不再试图一次性证明整间房间内的机器都是安全的，而是将房间划分为更小、更易管理的区域（就像把披萨切成片）。
局部证明：在每个区域内，我们只需使用一个简单、低次的方程来证明机器是安全的。
“或”逻辑：我们不需要一个方程覆盖所有情况。我们只需证明：“如果你在区域 A，机器是安全的；或者如果你在区域 B，机器是安全的；或者如果你在区域 C……"只要房间中的每一个可能点都至少落入这些安全区域之一，整台机器就被证明是安全的。

为什么这是一个颠覆性的突破？

简洁性：每个区域内使用的“钥匙”（代数恒等式）比旧方法所需的那把巨型钥匙要简单和微小得多。
并行处理：由于每个区域是独立的，你可以同时检查所有区域。这就像拥有一支侦探团队同时检查不同的房间，而不是一名侦探独自检查整栋大楼。
效率：作者从数学上证明，无论机器多么复杂，你总能找到这些简单、低次的证明。你不需要让方程变得更复杂；你只需要增加更多的区域。

论文中提到的现实世界应用

作者将这种“钥匙团队”方法应用于几个难题：

“莫特金”谜题：他们利用这种方法证明了一个著名数学谜题（莫特金多项式）的安全性，而旧方法在处理该问题时曾陷入困境。他们找到了使用简单方程的证明，而旧方法若不变得极其复杂则无法找到这些证明。
矩阵余正定性：这是一种涉及数字网格（矩阵）的特定类型问题。作者展示了如何将问题分解为更小的几何形状（三角形和锥体），以证明这些矩阵是安全的，这在优化和经济学中非常有用。
寻找“团”：在图论（由点和线组成的网络）中，“团”是指一组点，其中每个点都与其他所有点相连。寻找最大团是一个众所周知的难题。作者利用他们的方法，通过将问题分解为更小的部分来解决它，成功地在几个随机网络中找到了最大组的精确大小。

核心结论

该论文主张，我们不需要强行使用单一、庞大且复杂的解决方案来证明数学真理。相反，通过将问题划分为更小、重叠的部分，并用简单的工具解决每一部分，我们可以更快、更高效地证明整体为真。这之间的区别在于：是试图用一根巨大的杠杆独自撬起一块巨石，还是由一群人使用小而简单的杠杆协同工作。

技术摘要：析取平方和

问题陈述

本文解决了多项式非负性认证这一基本问题。虽然多项式 $p$ 在 $p(x) \geq 0$ 对所有 $x \in \mathbb{R}^n$ 成立时是非负的，但判定该性质通常是 NP 难的。标准方法是平方和（SOS）方法，它通过将 $p$ 表示为单一代数恒等式 $p(x) = \sum q_i^2(x)$ 来认证非负性。然而，并非所有非负多项式都是 SOS（希尔伯特已证实这一点），且证明那些非 SOS 多项式的非负性通常需要将 $p$ 乘以一个高次 SOS 多项式（例如，通过希尔伯特第 17 问题的阿廷解法）。这会导致代数恒等式的次数显著高于原多项式，进而产生规模呈指数级增长的半定规划（SDP），使其在计算上变得不可行。

驱动本研究的核心问题是：能否通过构建多个代数恒等式而非单一恒等式，来降低基于 SOS 的多项式非负性证明的复杂度？

方法论

作者引入了析取平方和（Disjunctive SOS）的概念。非负性不再通过单一的全局恒等式认证，而是通过一组代数恒等式来认证，每个恒等式在定义域的具体子区域上有效。这些子区域由代数析取定义，形成空间的划分（或覆盖）。

核心定义

代数析取：一组多项式 $\mathcal{D} = \{\{q_{k,j}\}\}$ ，使得区域 $\Omega_k = \{x \mid q_{k,j}(x) \geq 0, \forall j\}$ 的并集覆盖 $\mathbb{R}^n$ 。
析取 SOS 证明：若对于每个区域 $\Omega_k$ ，存在 SOS 多项式 $s_{k,j}$ 使得：
$p(x) = s_{k,0}(x) + \sum_{j=1}^{n_k} s_{k,j}(x)q_{k,j}(x) \quad \text{对所有 } x \in \Omega_k \text{ 成立}$
则称多项式 $p$ 是关于 $\mathcal{D}$ 的析取 SOS。关键在于，SOS 多项式 $s_{k,j}$ 的次数可以保持较低（具体而言，受限于 $p$ 的次数），而在全局 SOS 证明中，次数通常必须增加。

理论框架

本文确立了两个主要的理论结果，称为析取正定理（Disjunctive Positivstellensätze）：

基于 SDP 的析取正定理（定理 1）：
对于任意 $d$ 次正定形式 $p$ ，存在一个显式的代数析取族（通过球冠构造），使得 $p$ admits 一个析取 SOS 证明，其中 SOS 乘子的次数至多为 $d$ 。这使得利用固定规模（独立于层级水平）的 SDP 构建单位球上多项式最小化的收敛下界层级成为可能。
无优化析取正定理（定理 8）：
一个更强的结果表明，对于任意正定形式，存在一个单纯形析取族（多面体锥），使得 $p$ 的非负性可以通过检查其在每个锥内进行线性坐标变换后的系数是否非负来直接认证。这种方法不需要优化求解器（仅需线性规划或直接系数检查），但相比 SDP 方法可能需要更多的区域。

算法框架

作者提出了一个**空间分支定界（SBB）**框架，用于自适应地搜索这些析取证明。与理论证明中的均匀划分空间不同，该算法：

维护一个子区域（单纯形锥）的树结构。
在每个子区域上通过 SDP（或线性检查）计算下界。
通过投影梯度下降计算上界。
通过平分具有最小下界的子区域的最长边来进行分支。
这种自适应方法旨在用比均匀构造更少的子区域找到证书。

主要贡献与结果

1. 理论保证

固定次数：本文证明了低次析取 SOS 证明始终存在。证明中 SOS 多项式的次数无需随层级水平增长；它可以固定在原多项式的次数上。
收敛性：作者构建了一个具有固定规模约束的 SDP 层级，该层级收敛于单位球上齐次多项式的全局最小值。他们确立了 $O(1/m)$ 的收敛速率，其中 $m$ 与空间划分的分辨率相关。
无优化证书：第二个正定理提供了一种无需解 SDP 即可认证非负性的方法，转而依赖线性变换和系数非负性检查。

2. 在约束优化中的应用

多项式优化：通过将析取方法与 [2] 中的归约技术相结合，作者为紧基本半代数集上的一般多项式优化问题（POPs）构建了一个收敛的下界层级。
余正规划：该方法被专门用于认证矩阵的余正性（检查 $x^T Q x \geq 0$ 对于 $x \geq 0$ ）。作者定义了一种“析取 P+N"条件，即如果矩阵在非负象限的每个单纯形子区域上都能分解为一个半正定矩阵和一个非负矩阵，则该矩阵被认证为余正的。这产生了一个完整的层级，其中 SDP 约束的规模保持固定（ $n \times n$ ），这与现有层级中约束规模随层级呈多项式增长的情况形成对比。

3. 数值实验

作者展示了以下方面的数值实验：

非 SOS 多项式：算法通过 SBB 框架，使用少量子区域（通常少于 20 个）成功认证了经典非 SOS 多项式（如 Motzkin、Robinson、Choi-Lam、Delzell 多项式）的非负性。
余正规划：该算法解决了非凸二次规划问题，并在随机实例上计算了图的团数（通过 Motzkin-Straus 定理）。
性能：结果表明，与均匀划分相比，析取方法可以用显著更少的子区域认证非负性并求解优化问题，且 SDP 约束的规模保持可控。

意义与主张

本文主张，析取平方和方法通过将证明的复杂度（SOS 多项式的次数）与所用代数恒等式的数量解耦，为传统 SOS 层级提供了一种可行的替代方案。

计算效率：通过保持 SOS 多项式的次数低且固定，底层 SDP 的规模在整个层级中保持恒定，避免了标准 SOS 方法中因多项式次数增加而导致的“维数灾难”。
灵活性：该框架支持基于 SDP 的搜索（以较少的区域获得更紧的界）和无优化的搜索（以获得更快但可能较粗糙的证书）。
完备性：作者证明了该方法是完备的；对于任何严格正的多项式（或严格余正的矩阵），其框架内都存在证书。

本文最后指出，虽然理论构造使用了均匀划分，但实际的 SBB 算法会自适应地细化空间，这表明特定实例的析取可以进一步减少所需区域的数量。这项工作为将析取 SOS 与稀疏性和对称性利用相结合，以及探索该框架的对偶矩侧开辟了途径。