Optimization Online


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

Masakazu Kojima (kojima***at***is.titech.ac.jp)
Sunyoung Kim (skim***at***math.ewha.ac.kr)
Hayato Waki (waki9***at***is.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).


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

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Programming Society