polynomial optimization problem – Page 2

Generalized Lagrangian Duals and Sums of Squares Relaxations of Sparse Polynomial Optimization Problems

Published: 2003/09/29

Global Optimization Theory, Semi-definite Programming global optimization, lagrangian dual, lagrangian relaxation, polynomial optimization problem, semidefinite programming, semidefinite relaxation, sparsity, sums of squares optimization

Sequences of generalized Lagrangian duals and their SOS (sums of squares of polynomials) relaxations for a POP (polynomial optimization problem) are introduced. Sparsity of polynomials in the POP is used to reduce the sizes of the Lagrangian duals and their SOS relaxations. It is proved that the optimal values of the Lagrangian duals in the … Read more

A General Framework for Convex Relaxation of Polynomial Optimization Problems over Cones

Published: 2002/06/09, Updated: 2004/04/29

Sunyoung Kim

Masakazu Kojima

Hayato Waki

Global Optimization, Linear, Cone and Semidefinite Programming convex relaxation, global optimization, lift-and-project linear programming procedure, nonconvex optimization, polynomial optimization problem, quadratic programming, second-order cone program, semidefinite programming

The class of POPs (Polynomial Optimization Problems) over cones covers a wide range of optimization problems such as $0$-$1$ integer linear and quadratic programs, nonconvex quadratic programs and bilinear matrix inequalities. This paper presents a new framework for convex relaxation of POPs over cones in terms of linear optimization problems over cones. It provides a … Read more