- Separation and Relaxation for cones of quadratic forms Samuel Burer (samuel-bureruiowa.edu) Hongbo Dong (hongbo-donguiowa.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/2010Entry Accepted: 05/18/2010Entry Last Modified: 06/21/2011Modify/Update this entry Visitors Authors More about us Links Subscribe, Unsubscribe Digest Archive Search, Browse the Repository Submit Update Policies Coordinator's Board Classification Scheme Credits Give us feedback Optimization Journals, Sites, Societies Optimization Online is supported by the Mathematical Optmization Society.