【硬核书】稀疏多项式优化:理论与实践，220页pdf

2022 年 9 月 30 日 专知

许多应用，包括计算机视觉，计算机算法，深度学习，量子信息的纠缠，图论和能源网络，都可以在多项式优化的框架内成功解决，多项式优化是一个新兴领域，在过去20年的研究越来越多。这些技术的一个关键优势是它们能够使用优化公式对广泛的问题进行建模。多项式优化在很大程度上依赖于Lasserre提出的矩-平方和(矩-SOS)方法，该方法为正多项式提供了证明。然而，在实践方面，天下没有免费的午餐，这种优化方法通常包含严重的可扩展性问题。幸运的是，对于许多应用程序(包括前面提到的那些应用程序)，我们可以正视问题，并利用描述问题的成本和约束所产生的固有数据结构。

https://www.worldscientific.com/worldscibooks/10.1142/q0382#t=aboutBook

这本书提出了几个研究努力，以解决这一科学挑战与重要的计算含义。它提供了可选优化方案的开发，至少在某些已确定的问题类别中，这些方案在计算复杂度方面具有很好的扩展性。它还具有一个统一的建模框架，以处理涉及交换变量和非交换变量的广泛应用，并解决具体的大规模实例。读者可以找到一个实用的部分，专门介绍可用的开源软件库的使用。

这本跨学科专著是学生，研究人员和专业人士的必要阅读解决优化问题与多项式输入数据感兴趣。

背景知识 Preliminary Background:

Semidefinite Programming and Sparse Matrices
Polynomial Optimization and the Moment-SOS Hierarchy

相关稀疏 Correlative Sparsity:

The Moment-SOS Hierarchy Based on Correlative Sparsity
Application in Computer Arithmetic
Application in Deep Networks
Application in Noncommutative Optimization and Quantum Information

Term Sparsity:

The Moment-SOS Hierarchy Based on Term Sparsity
Combining with Correlative Sparsity
Application in Optimal Power-Flow
Application in Dynamical Systems
Alternatives to Sums of Squares

Appendix: Software Libraries:

Gloptipoly, Yalmip in MATLAB
TSSOS in Julia

本书提出了一些研究工作，以解决这一具有重要计算意义的科学挑战，并提供了替代优化方案的发展，这些方案在计算复杂性方面可以很好地扩展，至少在一些确定的问题类中。

本书提出的算法框架主要利用输入数据的稀疏性结构来解决大规模多项式优化问题。对于涉及较少项的无约束问题，第一种补救方法是通过丢弃从未出现在平方和分解(SOS)中的项来减小松弛项的大小。该技术基于Reznick [Rez78]的一个结果，包括计算输入多项式的牛顿多边形(该多项式支撑的凸包)，并只选择支撑位于该多边形一半的多项式。

对于无约束或有约束多项式优化问题，我们提出松弛的稀疏利用层次结构。与密集的层次结构相比，它们在实践中提供了更快的近似解，但也有相同的理论收敛保证。我们的框架不局限于静态多项式优化，我们揭示了从动力系统分析中产生的感兴趣值的近似层次。我们还提出了涉及非交换变量的各种扩展问题，例如任意大小的矩阵或量子物理算符。

在这一点上，我们想强调基于稀疏SOS分解的正性证书的替代方案的存在性。代替用SDP计算SOS分解，我们可以基于线性规划(LP)计算Bernstein分解或Krivin - Stengle证书的其他正性证书，非负电路的几何/二阶锥规划和扩展对角优势SOS，算术几何指数的相对熵规划。本书还概述了这些不同的可选分解方法。第二点要强调的是，稀疏性的概念是许多科学领域固有的，我们概述了与本书中提出的算法框架的一些相似和不同之处。在机器学习、统计或信号处理的背景下，利用稀疏性归结为选择变量或特征，通常使用“1范数正则化”[BT09]。它通常用于使模型或预测更容易解释或使用成本更低。换句话说，即使潜在的问题不允许稀疏解，人们仍然希望能够找到最佳的稀疏近似。类似的情况发生在具有稀疏状态约束和动力学的动力系统中，其中轨迹集不一定是稀疏的。在代数几何的背景下，人们考虑了多项式方程的稀疏系统，其中稀疏意味着出现在每个方程中的项集合是固定的。Bernshtein定理[Ber75]是一个关键成分，因为它基于描述系统的多项式的牛顿多边形的混合体积，为期望的复根数提供了精确的界限。我们同样利用牛顿多面体提供的支持信息来构建基于术语稀疏性的层次结构(在第二部分中介绍)。

本书的组织结构如下:第一章回顾了半定规划、稀疏矩阵理论的一些初步背景。第二章概述了多项式优化中矩- SOS层次的基本概念。本书的第一部分集中在“相关稀疏性”的概念上，当输入问题的变量之间的相关性很少时，就会出现相关稀疏性。第三章基于相关稀疏性，讨论了矩- SOS层次结构的第一个稀疏变体。第四章解释了如何应用稀疏矩- SOS层次结构为浮点非线性程序提供有效的舍入误差上界。第五章重点讨论深度神经网络的鲁棒性验证，特别是通过Lipschitz常数估计。第6章描述了非交换变量多项式优化的一个非常独特的应用。我们概述了量子信息论的研究前景。

本书的第二部分提出了一个补充框架，在那里我们展示了如何利用一个独特的稀疏性概念，称为“术语稀疏性”，当输入问题中涉及的术语数量很少时，通过与完全密集的情况进行比较，就会出现这种情况。第七章关注矩- SOS层次结构的第二个稀疏变体，基于术语稀疏性。第八章阐述了相关稀疏和术语稀疏的结合。第9章将术语稀疏框架扩展到复杂多项式优化，并展示了结果方案如何处理具有成千上万个变量和约束的最优问题。第10章将利用项稀疏性的框架扩展到非交换多项式优化(即特征值优化)。第11章是关于这个术语稀疏框架的应用，以分析各种控制系统的稳定性，无论是来自网络系统文献或在截止日期约束下的系统。第12章介绍了改进多项式优化方法可扩展性的备选算法。首先，我们提出了基于非负电路多项式和的算法，最近介绍了稀疏多项式的非负证书类，它们独立于已知的基于平方和的方法。然后，我们概述了现有的加快半定弛豫计算的方法。