论文标题
多项式优化的光谱松弛层次结构
A hierarchy of spectral relaxations for polynomial optimization
论文作者
论文摘要
我们表明（i）任何受约束的多项式优化问题（POP）在欧几里得球中包含的变体上具有等效的公式，并且（ii）矩层的层次层次结构中所得的半芬特弛豫具有恒定的跟踪特性（CTP）。然后，我们利用CTP来避免通过内点方法求解半决赛松弛，而宁愿使用临时光谱方法，以最大程度地减少基质铅笔的最大特征值。可以保证融合到半决赛松弛的最佳值。结果，我们获得了初始POP的非平滑“光谱弛豫”层次结构。该频谱层次结构的效率和鲁棒性针对球体上的几个相等性的POP以及随机产生的四次约束二次问题（QCQPS）的样本进行了测试。
We show that (i) any constrained polynomial optimization problem (POP) has an equivalent formulation on a variety contained in an Euclidean sphere and (ii) 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 that minimize 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 (QCQPs).
