Exploiting Sparsity in SDP relaxation of Polynomial Optimization Problems

We present a survey on the sparse SDP relaxation proposed as a sparse variant of Lasserre’s SDP relaxation of polynomial optimization problems. We discuss the primal and dual approaches to derive the sparse SDP and SOS relaxations, and their relationship. In particular, exploiting structured sparsity in the both approaches is described in view of the quality and the size of the SDP relaxations. In addition, numerical techniques used in the Matlab package SparsePOP for solving POPs are included. We report numerical results on SparsePOP and the application of the sparse SDP relaxation to sensor network localization problems