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.

Citation

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

Article

Download

View Separation and Relaxation for cones of quadratic forms