Graph-theoretic algorithms for polynomial optimization problems

The objective of this tutorial paper is to study a general polynomial optimization problem using a semidefinite programming (SDP) relaxation. The first goal is to show how the underlying structure and sparsity of an optimization problem affect its computational complexity. Graph-theoretic algorithms are presented to address this problem based on the notions of low-rank optimization and matrix completion. By building on this result, it is then shown that every polynomial optimization problem admits a sparse representation whose SDP relaxation has a rank 1 or 2 solution. The implications of these results are discussed in details and their applications in decentralized control and power systems are also studied.