  


Separation and Relaxation for cones of quadratic forms
Samuel Burer (samuelbureruiowa.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 NPhard 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 polyhedralsemidefinite 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 Modify/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  