SDP RELAXATIONS FOR QUADRATIC OPTIMIZATION PROBLEMS DERIVED FROM POLYNOMIAL OPTIMIZATION PROBLEMS

摘要

Based on the convergent sequence of SDP relaxations for a multivariate polynomial optimization problem (POP) by Lasserre (2006), Waki et al. (2006) constructed a sequence of sparse SDP relaxations to solve sparse POPs efficiently. Nevertheless, the size of the sparse SDP relaxation is the major obstacle in order to solve POPs of higher degree. This paper proposes an approach to transform general POPs to quadratic optimization problems (QOPs), which allows to reduce the size of the SDP relaxation substantially. We introduce different heuristics resulting in equivalent QOPs and show how sparsity of a POP is maintained under the transformation procedure. As the most important issue, we discuss how to increase the quality of the SDP relaxation for a QOP. Moreover, we increase the accuracy of the solution of the SDP relaxation by applying additional local optimization techniques. Finally, we demonstrate the high potential of this approach through numerical results for large scale POPs of higher degree.