An accelerated first-order method for solving SOS relaxations of unconstrained polynomial optimization problems

作者：Bertsimas Dimitris; Freund Robert M; Sun Xu Andy^*

来源：Optimization Methods and Software, 2013, 28(3): 424-441.

DOI：10.1080/10556788.2012.656114

• polynomial optimization
• semidefinite programming relaxation
• accelerated first order methods
• global optimization

Our interest lies in solving sum of squares (SOS) relaxations of large-scale unconstrained polynomial optimization problems. Because interior-point methods for solving these problems are severely limited by the large-scale, we are motivated to explore efficient implementations of an accelerated first-order method to solve this class of problems. By exploiting special structural properties of this problem class, we greatly reduce the computational cost of the first-order method at each iteration. We report promising computational results as well as a curious observation about the behaviour of the first-order method for the SOS relaxations of the unconstrained polynomial optimization problem.

• 出版日期2013-6-1
• 单位IBM