Separation and Relaxation for cones of quadratic forms

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.


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



View Separation and Relaxation for cones of quadratic forms