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

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 unified treatment of many existing convex relaxation methods based on the lift-and-project linear programming procedure, the reformulation-linearization technique and the semidefinite programming relaxation for a variety of problems. It also extends the theory of convex relaxation methods, and thereby brings flexibility and richness in practical use of the theory.


Journal of Operations Research Society of Japan Vol.46 (2) 125-144 (2003).