Optimization Online


Separation and Relaxation for cones of quadratic forms

Samuel Burer (samuel-burer***at***uiowa.edu)
Hongbo Dong (hongbo-dong***at***uiowa.edu)

Abstract: Let P be a pointed, polyhedral cone in R_n. In this paper, we study the cone C = cone{xx^T: x \in P} of quadratic forms. Understanding the structure of C is important for globally solving NP-hard quadratic programs over P. We establish key characteristics of C and construct a separation algorithm for C provided one can optimize with respect to a related cone over the boundary of P. This algorithm leads to a nonlinear representation of C and a class of tractable relaxations for C, each of which improves a standard polyhedral-semidefinite relaxation of C. The relaxation technique can further be applied recursively to obtain a hierarchy of relaxations, and for constant recursive depth, the hierarchy is tractable. We apply this theory to two important cases: P is the nonnegative orthant, in which case C is the cone of completely positive matrices; and P is the homogenized cone of the ``box" [0,1]^n. Through various results and examples, we demonstrate the strength of the theory for these cases. For example, we achieve for the first time a separation algorithm for 5X5 completely positive matrices.

Keywords: Quadratic form, Convex hull, Separation, Relaxation, Global optimization, Semidefinite programming

Category 1: Global Optimization (Theory )

Category 2: Linear, Cone and Semidefinite Programming

Category 3: Nonlinear Optimization (Quadratic Programming )

Citation: Working paper, Dept. of Management Sciences, University of Iowa, Iowa City IA, May 2010.

Download: [PDF]

Entry Submitted: 05/18/2010
Entry Accepted: 05/18/2010
Entry Last Modified: 06/21/2011

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 Optimization Society