Sum of Squares Basis Pursuit with Linear and Second Order Cone Programming
Sum of Squares Basis Pursuit with Linear and Second Order Cone Programming
复制标题
使用线性和二阶锥规划求平方和基
DOI：
10.1090/conm/685/13712
复制
发表时间：
2015
期刊：
影响因子：
--
通讯作者：
G. Hall
中科院分区：
文献类型：
--
作者：
Amir Ali Ahmadi;G. Hall
我们设计了一个求解线性规划(LP)或二阶锥规划(SOCP)的迭代序列的方案，以逼近任何半定规划(SDP)或平方和(SOS)规划的最优值。序列中的第一个基于LP和SOCP的界来自Ahmadi和Majudar最近关于对角占优平方和(DSO)和比例对角占优平方和(SDSOS)多项式的工作。然后，我们通过寻找更好的基来迭代地改进这些界，在这些基中，更相关的SOS多项式允许DSO或SDSOS表示。从原始和对偶的角度对这一过程给出了不同的解释。虽然该方法适用于一般多项式规划的SDP松弛，但我们将其应用于离散优化的两个问题：最大独立集问题和划分问题。进一步证明了划分问题的一些完全平凡的情况会导致在平方和锥的边界上出现严格的正多项式，从而导致SOS松弛失效。
We devise a scheme for solving an iterative sequence of linear programs (LPs) or second order cone programs (SOCPs) to approximate the optimal value of any semidefinite program (SDP) or sum of squares (SOS) program. The first LP and SOCP-based bounds in the sequence come from the recent work of Ahmadi and Majumdar on diagonally dominant sum of squares (DSOS) and scaled diagonally dominant sum of squares (SDSOS) polynomials. We then iteratively improve on these bounds by pursuing better bases in which more relevant SOS polynomials admit a DSOS or SDSOS representation. Different interpretations of the procedure from primal and dual perspectives are given. While the approach is applicable to SDP relaxations of general polynomial programs, we apply it to two problems of discrete optimization: the maximum independent set problem and the partition problem. We further show that some completely trivial instances of the partition problem lead to strictly positive polynomials on the boundary of the sum of squares cone and hence make the SOS relaxation fail.