技术摘要：球面多项式优化中的特征值计算层级结构

问题陈述

本文研究了在实数单位球面 $\mathbb{R}^n$ 上最小化实齐次多项式（型）$p(x)$ 的基本问题：
$$p_{\min} = \min_{x \in \mathbb{R}^n, \|x\|=1} p(x).$$
对于次数 $D \geq 3$ 的情况，该问题是 NP-难的，并涵盖了广泛的应用领域（如图论中的最大稳定集、计算复杂度以及量子信息理论中的 $2 \to 4$ 范数计算）。

解决该问题的标准方法是实平方和（RSOS）层级结构，它提供了一系列收敛于 $p_{\min}$ 的下界。然而，随着问题规模（变量数 $n$ 和次数 $D$）的增加，每个 RSOS 层级都需要求解一个完整的半正定规划（SDP）。随着规模增大，SDP 的规模会迅速增长，使得该方法在处理大规模实例时在计算上变得不可行。

方法论

作者提出了一种名为 HRSOS（Hermitian Real Sum-of-Squares，埃尔米特实平方和）的新型层级结构，通过一系列最小特征值计算而非完整的 SDP 来逼近 $p_{\min}$。该方法依赖于三个核心组件：

1. 归约为埃尔米特优化： 作者建立了从球面上的实优化到复球面上的埃尔米特优化的归约关系。对于实型 $p$，他们定义了一个极大对称的 Gram 算子 $P = M(p)$。他们证明了实型的最小值 $p_{\min}$ 与相关的埃尔米特型 $P_{\min}$ 的最小值之间存在一个已知常数因子 $\delta(d)$ 的界限：
   $$P_{\min} \leq p_{\min} \leq \frac{P_{\min}}{\delta(d)}.$$
   至关重要的是，这种归约保留了 $p_{\min} > 0$ 当且仅当 $P_{\min} > 0$ 的性质。

2. 利用 HSOS 层级结构： 埃尔米特优化问题通过埃尔米特平方和（HSOS）层级结构来求解。与 RSOS 层级不同，HSOS 层级是一个“谱”层级，其在第 $k$ 层的界限仅仅是根据输入型构造的特定埃尔米特算子的最小特征值。已知 HSOS 层级的收敛速度为 $O(1/k)$。

3. 构建 HRSOS 层级结构： 通过结合上述归约与 HSOS 层级，作者构建了一系列广义特征值问题。在第 $k$ 层，界限 $\eta_k$ 计算为：
   $$\eta_k = \lambda_{\min}\left( (N^{(d)}_k)^{-1/2} P_k (N^{(d)}_k)^{-1/2} \right),$$
   其中 $P_k$ 和 $N^{(d)}_k$ 是由 $p$ 和范数型 $\|x\|^{2d}$ 导出的算子。在实践中，这通过求解广义特征值问题 $P_k \psi = \lambda N^{(d)}_k \psi$ 来完成，从而避免了显式求逆大型矩阵。

作者将该框架扩展到了多项式齐次型（针对乘积球面的优化）和张量谱范数，从而构建了 m-HRSOS 层级结构。

核心贡献

• 实优化的谱层级结构： 本文引入了第一个仅依赖于特征值计算而非完整 SDP 的实球面多项式优化收敛层级结构。
• 收敛保证： 作者证明了 HRSOS 层级以 $O(1/k)$ 的速率加性收敛于 $p_{\min}$。虽然当 $D \leq 2n$ 时，该速率慢于已知最优的 $O(1/k^2)$ RSOS 速率，但在 $D > 2n$ 时，它与 RSOS 的已知 $O(1/k)$ 速率一致。
• 张量谱范数计算： 该方法被推广用于计算张量的实谱范数和双二次型最小化，为现有的张量分解和优化技术提供了谱替代方案。
• 规范构造： 与其他“更廉价”的替代方案（如调和层级结构）不同，所提出的方法是完全规范的，不需要任意选择求积规则或核函数。

结果与数值性能

作者在 MATLAB 中实现了 HRSOS 层级结构，并将其与 RSOS、DSOS（对角占优 SOS）和调和层级结构进行了对比。

• 可扩展性： 主要优势在于可扩展性。由于 SDP 求解器的内存限制，RSOS 仅限于小规模问题（例如次数为 4 且变量数 $\approx 25$ 的多项式），而 HRSOS 可以处理显著更大的实例（例如次数为 4 且变量数 $>90$ 的多项式），因为它利用了稀疏广义特征值求解器。
• 效率对比 RSOS： 对于 RSOS 可行的较小问题，RSOS 通常在单位计算时间内提供更紧的界限。然而，对于 RSOS 失效的大规模问题，HRSOS 是唯一的可行谱替代方案。
• 效率对比其他方案： 与无需优化的调和层级结构相比，HRSOS 在单位时间内提供了更好的界限。调和层级结构需要在规模随 $n$ 指数增长的求积规则上最小化多项式，这在 $n \geq 10$ 时会变得极其昂贵。HRSOS 避免了这种离散优化瓶颈。
• 收敛性： 在数值实验（包括 Motzkin 多项式和随机四次型）中，HRSOS 在固定时间预算内，在界限质量方面始终优于 DSOS 和调和层级结构。

意义与主张

本文声称，HRSOS 层级结构通过利用来自埃尔米特优化和量子 de Finetti 定理的技术，为解决大规模约束实优化问题开辟了一条新路径。

• 实际影响： 该方法使得计算目前对于标准基于 SDP 的方法而言难以处理的多项式优化问题成为可能。
• 理论桥梁： 它建立了实优化与埃尔米特优化之间的严谨联系，表明其他的埃尔米特谱技术也可以被改编用于实问题。
• 谦逊态度： 作者承认，虽然其收敛速率（$O(1/k)$）在低次数下不如最优 RSOS 速率快，但其在高维问题中的计算可行性使其成为一个更优的实用工具。他们还指出，对于约束优化，实最小值与埃尔米特最小值之间的直接等价性并不总是成立，这表明在不诉诸二分法或完整 SDP 的情况下，如何适配该层级结构以处理一般约束仍需进一步研究。

文章总结道，对于球面上的大规模多项式优化和张量谱范数计算，所提出的特征值计算层级结构在计算可行性与界限质量之间提供了极具吸引力的平衡，并优于现有的非 SDP 替代方案。