精读笔记
Problem Setting
这篇论文处理的是多项式非负性证明与多项式优化下界构造中的一个老问题：SOS 证书可计算但不完备，Positivstellensatz 路线完备但通常通过提高次数获得完备性，导致 SDP 规模爆炸。
真正困难点在于，非负性是全局性质，而 SOS 证书要求用一个代数恒等式同时解释所有方向/区域上的非负性。许多经典非 SOS 例子不是“处处难”，而是无法被一个低次数全局 Gram 表示捕捉。以前方法卡在这里：要么接受保守性，要么提高次数；提高次数直接扩大 monomial basis，SDP 矩阵大小组合爆炸。
本文抓住的关键矛盾是：完备性需要表达能力，但表达能力未必只能通过提高单个证书次数获得，也可以通过增加证书数量、让每个证书只负责局部区域来获得。论文实际是在探索这种复杂度交换是否有理论完备性和计算价值。
Motivation
已有路线不够的根源不是 SOS 太弱，而是“单个全局代数身份”这个建模选择太刚性。Artin/Reznick 等结果告诉我们可以通过乘子或幂次把非负性变成 SOS，但次数上界极差；Lasserre/Putinar 在约束优化中也把层级推进体现为更高阶 moment/SOS 矩阵。对工程计算而言，这类完备性经常停留在理论层面。
作者的核心观察是：如果允许证明有 case distinction，很多低次数证书立刻出现。Motzkin 的例子很说明问题：全局不是 SOS，但按 x1x2 的符号分成两块后，每块都有同次数证书。这个观察本质上是把代数几何里的全局证书改造成“局部证明 + 覆盖”。
关键缺口是：这种 case-based SOS 是否只是若干巧合例子，还是能形成一个完整 Positivstellensatz？本文的主要理论目标就是填这个缺口：证明在标准正定假设下，可以固定一族显式划分，并保持每个局部 SOS 证书次数不超过原多项式次数。
Core Idea
核心思想可以概括为：不要让一个 SOS 证书承担整个空间的非负性证明，而是先把空间切成若干代数区域，在每个区域上用一个低次数 Putinar-like 证书证明非负。若区域由 q_{k,j}(x) >= 0 定义，则在第 k 个区域上寻找 p = s_{k,0} + Σ_j s_{k,j} q_{k,j}，其中 s 是 SOS。只要这些区域覆盖全空间，所有局部身份合起来就是全局非负性证书。
这改变了建模方式：传统 SOS 的表达能力来自更大的 monomial basis；本文的表达能力来自更细的空间划分。新的 inductive bias 是“非负性通常具有局部简单性”：在足够小的区域内，一个正定多项式看起来像在某个正值点附近的稳定扰动，可以被低阶 SOS 余项吸收。理论上，这通过局部 Positivstellensatz 实现；几何上，是用球面 cap 覆盖单位球。
和 prior 的本质区别在于，本文不试图构造一个越来越高阶的全局证书，而是构造越来越多的低阶局部证书。scalability 的希望来自固定 SDP block size 和天然并行性；代价是区域数量可能指数增长。
Method
1. 相对于代数析取的 SOS cone：它解决的是“多个局部证书如何形式化为一个全局 cone”的问题。给定覆盖 R^n 的区域 Ω_k，每个区域要求 p = s_{k,0} + Σ s_{k,j} q_{k,j}。核心变化是非负 cone 的内近似不再由一个 SOS cone 给出，而由一组共享 p、彼此独立的局部 SOS 约束给出。
2. 局部 Positivstellensatz：它解决的是“为什么低次数局部证书一定存在”。若 p(x*) > 0，则在 x* 附近可以写成 p = local-barrier + SOS，其中 local-barrier 是形如 A(x^T x*)^d - t h_d(x;x*) 的多项式。该多项式定义一个球面 cap；在 cap 内它非负，因此局部证书成立。关键是 SOS 部分仍保持 degree d。
3. 从局部到全局：用球面 net 覆盖 S^{n-1}，每个 net point 对应一个 cap 和一个局部代数不等式。随着 net 变细，cap 变小，局部证书条件更容易满足。于是层级推进的是 net resolution / region count，而不是 SOS degree。
4. 固定 SDP 尺寸的优化层级：最小化 form over sphere 可写为最大 γ 使 p - γ||x||^d 非负。用 disjunctive SOS cone 替代非负 cone 得到下界层级。每层最大 SDP block 的大小固定，但 block 数增加且可并行。
5. optimization-free 版本：用 simplicial cones 划分空间，若 p(V_k x) 的所有系数非负，则 p 在 cone(V_k) 上非负。它解决的是“能否不解 SDP”的问题，核心变化是把 SOS 证书降为系数正性证书，但表达能力更弱，通常需要更多区域。
6. copositive 特化：对非负正交锥/单纯形的几何定制划分，得到 disjunctive P+N 条件。这里的机制是对每个 simplicial cone 检查 V_k^T Q V_k 是否有 P+N 分解，从而局部证明二次型在该 cone 上非负。
Key Insight / Why It Works
这篇论文真正有效的原因是把“高阶全局代数复杂性”转化为“低阶局部几何复杂性”。正定多项式在单位球上有正 margin；只要区域足够小，p 在该区域内不会剧烈变化。局部 Positivstellensatz 利用这一点，把 p 分解成一个定义 cap 的显式低阶项加 SOS 余项。也就是说，完备性来自 compactness + positive margin，而不是来自高阶乘子。
最核心贡献是 Theorem 1 类型的 disjunctive Positivstellensatz：它证明固定次数也能完备，只要允许区域数量增加。这是概念上比较干净的复杂度 trade-off。固定 SDP block size 不是单纯 engineering，而是这个理论转移的直接结果。
但实际性能很可能主要来自 adaptive partition / branch-and-bound，而不是通用 Positivstellensatz 构造。理论 net 是保守且指数级的；实验中少量区域成功，说明许多测试多项式有很强的可分区域结构。换言之，经验增益来自 instance geometry 被划分捕捉，而不是一个普遍低复杂度定理。
optimization-free 部分本质上是系数非负/Pólya 型思想的局部化。它的 insight 很清楚：在足够小的 cone 上，正定 form 经线性变换后主导项压过其余项，系数变正。但这更像极端保守的局部证书，理论漂亮，实际可能区域爆炸。
branch-and-bound 框架是 test-time compute：不断细化最可疑区域，用局部 SOS/P+N bound 缩小 gap。它没有改变 NP-hard 本质，也没有给出多项式复杂度；它把难度交给自适应搜索。这里的“推理”不是隐藏的全局理解，而是空间划分下的局部证书复用。
Relation To Prior Work
最接近的谱系有三条：SOS/Positivstellensatz 层级、Pólya/系数正性证书、copositive cone 内近似与 simplicial partition。
相对 Artin/Reznick/Stengle/Putinar/Lasserre，本文的实质差异是复杂度增长轴不同。传统方法通过提高次数扩大单个证书的表达能力；本文通过增加 disjuncts 保持每个证书低阶。这个差异不是表面形式，而是直接改变 SDP 规模结构：block size 固定、block 数增长、天然并行。
相对 DSOS/SDSOS，本文不是简单换 cone。局部 Positivstellensatz 的证明中确实出现 diagonal dominance / sdsos 结构，但核心不是用更便宜 cone 替代 SOS，而是用析取划分让低阶甚至结构化证书成为可能。
相对 branch-and-bound/global optimization，本文的新信息是每个 node 的 lower bound 来自代数证书，而不是普通 convex relaxation/interval bound。反过来说，实用算法部分也很像传统 SBB，只是 bounding oracle 换成 disjunctive SOS/P+N。
相对 copositive approximation，disjunctive P+N 与已有 simplicial subdivision 方法关系很近。实质创新是把它纳入同一个 disjunctive certificate 框架，并强调 SDP block 固定；但对 copositive 特例而言，部分思想可视为已有 P+N/partition 方法的系统化重组。
Dataset / Evaluation
实验覆盖了三类任务：经典非 SOS 多项式非负性、copositive/QP、最大 clique 的 copositive formulation。覆盖面足以说明框架不是只为 Motzkin 定制，尤其 Delzell 例子有说服力，因为它对某些 Reznick-type 证书不友好，却有两区域低阶 disjunctive 证书。
不过 evaluation 主要是小到中等规模的 proof-of-concept。多项式实验集中在经典手工构造的困难例子，这些例子往往具有高度代数结构；它们能验证“存在可利用的局部结构”，但不能证明一般 POP 上会优于成熟 sparse-SOS 或专用全局优化器。
copositive/QP/clique 实验更接近应用，但仍是有限实例。clique 上 n=75 random graph 的结果有趣，不过算法利用整数终止和 Motzkin-Straus/copositive 结构，不能直接外推到大规模组合优化。
实验确实支持核心 claim 中最弱但重要的一点：固定低阶 SDP + 自适应区域划分可以在一些传统 SOS 失败的实例上工作。它没有充分验证的是：区域数在真实高维问题中是否可控，或者相比已有 branch-and-bound/SDP bounds 是否系统占优。文中未充分说明不同 bound oracle、划分策略、初始化对性能的敏感性。
Limitation
第一，理论完备性主要针对 positive definite forms。正定 margin 是局部证书拼接的关键；一旦存在零点，尤其是 bad point，局部正 margin 消失，理论不再直接覆盖。论文最后也明确提出是否存在无法被任意有限 disjunctive SOS 证明的非负 form，这是根本性问题。
第二，复杂度只是转移。固定 SDP block size 的代价是区域数量增长，通用构造指数级，且常数依赖 p_min、系数范数、旋转后系数范数等量。这些量在病态实例中会非常差。所谓 scalability 不是全局复杂度降低，而是把大 SDP 变成大量小 SDP，并依赖并行和自适应搜索。
第三，实际算法的成功高度依赖 partition geometry。若低值区域细长、零集复杂、或者局部非负性无法被简单 cone/cap 捕捉，branch-and-bound 可能退化。文中实验没有系统 stress test 这种情况。
第四，optimization-free 证书虽然不需要 SDP，但可能是最保守的版本。系数非负在变换后成立需要区域很小，本质是用细分换掉优化；在高维中区域数可能更快爆炸。
第五，与已有 sparse/symmetric SOS 技术尚未结合。当前方法若直接用于高变量多项式，monomial basis 即使次数固定也可能很大；固定 degree 不等于绝对可扩展。
第六，增益归因不完全清晰。实验中的少区域成功可能来自经典测试实例具有明显符号/对称/分块结构，而不是 disjunctive SOS 在一般实例上天然高效。
Takeaway
- 1. 最值得记住的是复杂度轴的转换：从提高 SOS degree 到增加 algebraic disjunction。
- 这个视角可以迁移到其他证书系统：当单个全局证书太贵时，考虑局部低阶证书 + 覆盖。
- 2. 理论上最干净的贡献是 disjunctive Positivstellensatz：在正定假设下，低次数局部证书具有完备性。
- 这给“case-based algebraic proof”一个正式基础。
一句话总结
这篇论文把 SOS 非负性证明从“单个高次数全局证书”推进到“多个低次数局部证书覆盖空间”的复杂度重分配框架，是 Positivstellensatz/SOS 层级的一种几何化、可并行化演化。