Improving efficiency and scalability of sum of squares optimization: Recent advances and limitations
Improving efficiency and scalability of sum of squares optimization: Recent advances and limitations
复制标题
DOI：
10.1109/cdc.2017.8263706
复制
发表时间：
2017-10
期刊：
影响因子：
--
通讯作者：
Amir Ali Ahmadi;G. Hall;A. Papachristodoulou;J. Saunderson;Yang Zheng
中科院分区：
文献类型：
--
作者：
Amir Ali Ahmadi;G. Hall;A. Papachristodoulou;J. Saunderson;Yang Zheng
众所周知，任何平方和（SOS）程序都可以转换为特定结构的半定程序（SDP），这就是SOS程序的计算瓶颈，因为当SOS程序中涉及的多项式具有大量变量和次数时，该过程生成的SDP很大并且求解成本很高。在本文中，我们回顾了 SOS 优化技术，并提出了两种提高其计算效率的新方法。第一种方法利用底层 SDP 的稀疏性来获得计算加速。如果描述问题的多项式的系数具有特定的稀疏模式（称为弦稀疏），则可以获得进一步的改进。第二种方法完全绕过半定规划，而是依赖于求解一系列更容易处理的凸规划，即线性和二阶锥规划。这就提出了一个问题，即如何通过二阶可表示锥来逼近 SOS 多项式的锥。在本文的最后一部分，我们提出了与这个问题相关的一些最近的负面结果。
It is well-known that any sum of squares (SOS) program can be cast as a semidefinite program (SDP) of a particular structure and that therein lies the computational bottleneck for SOS programs, as the SDPs generated by this procedure are large and costly to solve when the polynomials involved in the SOS programs have a large number of variables and degree. In this paper, we review SOS optimization techniques and present two new methods for improving their computational efficiency. The first method leverages the sparsity of the underlying SDP to obtain computational speed-ups. Further improvements can be obtained if the coefficients of the polynomials that describe the problem have a particular sparsity pattern, called chordal sparsity. The second method bypasses semidefinite programming altogether and relies instead on solving a sequence of more tractable convex programs, namely linear and second order cone programs. This opens up the question as to how well one can approximate the cone of SOS polynomials by second order representable cones. In the last part of the paper, we present some recent negative results related to this question.