A Correlatively Sparse Lagrange Multiplier Expression Relaxation for Polynomial Optimization

Understand

In this paper, we consider polynomial optimization with correlative sparsity.

• We construct correlatively sparse Lagrange multiplier expressions (CS-LMEs) and propose CS-LME reformulations for polynomial optimization problems using the Karush-Kuhn-Tucker optimality conditions.
• Correlatively sparse sum-of-squares (CS-SOS) relaxations are applied to solve the CS-LME reformulation.
• We show that the CS-LME reformulation inherits the original correlative sparsity pattern, and the CS-SOS relaxation provides sharper lower bounds when applied to the CS-LME reformulation, compared with when it is applied to the original problem.