Sums of squares and semidefinite program relaxations for polynomial optimization problems with structured sparsity

Unconstrained and inequality constrained sparse polynomial optimization problems (POPs) are considered. A correlative sparsity pattern graph is defined to find a certain sparse structure in the objective and constraint polynomials of a POP. Based on this graph, sets of the supports for sums of squares ( SOS) polynomials that lead to efficient SOS and semidefinite program ( SDP) relaxations are obtained. Numerical results from various test problems are included to show the improved performance of the SOS and SDP relaxations.