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

Masakazu Kojima (kojimais.titech.ac.jp)
Sunyoung Kim (skimmath.ewha.ac.kr)
Hayato Waki (waki9is.titech.ac.jp)

Abstract: 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.

Keywords: Global optimization, Convex relaxation, Nonconvex program, Quadratic program, Semidefinite program, Second-order cone program, Lift-and-project linear programming procedure, Polynomial optimization problem

Category 1: Linear, Cone and Semidefinite Programming

Category 2: Global Optimization

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

Download:

Entry Submitted: 06/09/2002
Entry Accepted: 06/09/2002
Entry Last Modified: 04/29/2004

Modify/Update this entry