Dual Certificates and Efficient Rational Sum-of-Squares Decompositions for Polynomial Optimization over Compact Sets
Dual Certificates and Efficient Rational Sum-of-Squares Decompositions for Polynomial Optimization over Compact Sets
复制标题
DOI：
10.1137/21m1422574
复制
发表时间：
2021-05
期刊：
影响因子：
--
通讯作者：
Maria M. Davis;D. Papp
中科院分区：
文献类型：
--
作者：
Maria M. Davis;D. Papp
研究了紧半代数集上正多项式的加权平方和证书的计算问题。基于凸优化的边界点方法的理论，我们引入了对偶锥证书的概念，这使我们能够将来自平方和锥的对偶的向量解释为WSOS多项式的严格非负性证书。而传统的WSOS证书是他们认证的多项式的替代表示，双证书不同于认证的多项式;此外，每个双证书认证WSOS多项式的全维凸锥。因此，理性的WSOS证书可以构造从数字计算的双重证书在很少的额外成本，没有任何舍入或投影步骤应用到数字证书。作为一个额外的算法应用程序，我们提出了一个几乎完全数值混合算法计算的最佳WSOS下界的一个给定的多项式沿着一个合理的双重证书，与多项式时间的计算成本，每次迭代和线性收敛速度。
We study the problem of computing weighted sum-of-squares (WSOS) certificates for positive polynomials over a compact semialgebraic set. Building on the theory of interior-point methods for convex optimization, we introduce the concept of dual cone certificates, which allows us to interpret vectors from the dual of the sum-of-squares cone as rigorous nonnegativity certificates of a WSOS polynomial. Whereas conventional WSOS certificates are alternative representations of the polynomials they certify, dual certificates are distinct from the certified polynomials; moreover, each dual certificate certifies a full-dimensional convex cone of WSOS polynomials. As a result, rational WSOS certificates can be constructed from numerically computed dual certificates at little additional cost, without any rounding or projection steps applied to the numerical certificates. As an additional algorithmic application, we present an almost entirely numerical hybrid algorithm for computing the optimal WSOS lower bound of a given polynomial along with a rational dual certificate, with a polynomial-time computational cost per iteration and linear rate of convergence.