A hierarchy of spectral relaxations for polynomial optimization
A hierarchy of spectral relaxations for polynomial optimization
复制标题
用于多项式优化的谱松弛层次
DOI：
--
复制
发表时间：
2020
影响因子：
6.3
通讯作者：
Victor Magron
中科院分区：
文献类型：
--
作者：
N. Mai;Jean B. Lasserre;Victor Magron
我们证明了（1）任何约束多项式优化问题（POP）在欧氏球面中的一个簇上都有一个等价的公式;（2）所得到的矩SOS族中的半定松弛对所涉及的矩阵具有常迹性质（CTP）.然后，我们利用CTP，以避免解决半定松弛通过邻点方法，而是使用特设谱方法最大限度地减少矩阵束的最大特征值。收敛到半定松弛的最佳值是有保证的。因此，我们得到了一个层次的非光滑的“光谱松弛”的初始POP。效率和鲁棒性的光谱层次进行测试，对几个平等约束的POP球以及随机生成的二次约束二次问题的样本。
We show that (1) any constrained polynomial optimization problem (POP) has an equivalent formulation on a variety contained in an Euclidean sphere and (2) the resulting semidefinite relaxations in the moment-SOS hierarchy have the constant trace property (CTP) for the involved matrices. We then exploit the CTP to avoid solving the semidefinite relaxations via interior-point methods and rather use ad-hoc spectral methods for minimizing the largest eigenvalue of a matrix pencil. Convergence to the optimal value of the semidefinite relaxation is guaranteed. As a result we obtain a hierarchy of nonsmooth “spectral relaxations” of the initial POP. Efficiency and robustness of this spectral hierarchy is tested against several equality constrained POPs on a sphere as well as on a sample of randomly generated quadratically constrained quadratic problems.