Univariate Polynomial Optimization with Sum-of-Squares Interpolants
Univariate Polynomial Optimization with Sum-of-Squares Interpolants
复制标题
使用平方和插值法的单变量多项式优化
DOI：
--
复制
发表时间：
2016
期刊：
影响因子：
--
通讯作者：
D. Papp
中科院分区：
文献类型：
--
作者：
D. Papp
多项式优化中最常用的工具之一是用平方和多项式锥逼近非负多项式锥。这导致多项式时间可解的近似许多NP-难优化问题使用半定规划（SDP）。虽然理论上令人满意，但将涉及平方和多项式的优化问题转化为SDP并不总是实用的。首先，在常见的SDP公式中，对偶变量是半定矩阵，其条件数随着所涉及的多项式的次数呈指数增长，这对于浮点实现是不利的。其次，平方和多项式的SDP表示粗略地平方了优化变量的数量，将求解算法的时间和内存复杂度增加了几个数量级。在本文中，我们专注于第一，数值，问题。我们表明，使用多项式插值的平方和SDP的重新制定产生了显着的改善，在标准的制定，和问题涉及的平方和插值的数百度可以处理没有困难的常用的半定规划求解器。使用半无限优化问题的初步数值结果与理论预测一致。在所有考虑的问题中，可用内存是唯一限制多项式次数的因素。
One of the most common tools in polynomial optimization is the approximation of the cone of nonnegative polynomials with the cone of sum-of-squares polynomials. This leads to polynomial-time solvable approximations for many NP-hard optimization problems using semidefinite programming (SDP). While theoretically satisfactory, the translation of optimization problems involving sum-of-squares polynomials to SDPs is not always practical. First, in the common SDP formulation, the dual variables are semidefinite matrices whose condition numbers grow exponentially with the degree of the polynomials involved, which is detrimental for a floating-point implementation. Second, the SDP representation of sum-of-squares polynomials roughly squares the number of optimization variables, increasing the time and memory complexity of the solution algorithms by several orders of magnitude. In this paper we focus on the first, numerical, issue. We show that a reformulation of the sum-of-squares SDP using polynomial interpolants yields a substantial improvement over the standard formulation, and problems involving sum-of-squares interpolants of hundreds of degrees can be handled without difficulty by commonly used semidefinite programming solvers. Preliminary numerical results using semi-infinite optimization problems align with the theoretical predictions. In all problems considered, available memory is the only factor limiting the degrees of polynomials.