论文标题
在大规模多项式优化中利用恒定轨迹特性
Exploiting constant trace property in large-scale polynomial optimization
论文作者
论文摘要
我们证明，具有球限制的多项式优化问题（POP）的每个半限定力矩放松可以作为半限定程序重新构成，该程序涉及具有恒定痕量特性（CTP）的矩阵。结果，可以通过一阶方法来有效地求解这种瞬间放松，例如利用CTP，例如，基于条件梯度的增强拉格朗日方法。我们还将此CTP探索框架扩展到具有不同稀疏结构的大规模弹出式。我们的框架的效率和可扩展性在二阶时刻弛豫中说明了各种随机生成的四次二次二次程序。
We prove that every semidefinite moment relaxation of a polynomial optimization problem (POP) with a ball constraint can be reformulated as a semidefinite program involving a matrix with constant trace property (CTP). As a result such moment relaxations can be solved efficiently by first-order methods that exploit CTP, e.g., the conditional gradient-based augmented Lagrangian method. We also extend this CTP-exploiting framework to large-scale POPs with different sparsity structures. The efficiency and scalability of our framework are illustrated on second-order moment relaxations for various randomly generated quadratically constrained quadratic programs.
