Journal article
Separation and relaxation for cones of quadratic forms
Mathematical programming, Vol.137(1-2), pp.343-370
02/01/2013
DOI: 10.1007/s10107-011-0495-6
Abstract
Let be a pointed, polyhedral cone. In this paper, we study the cone of quadratic forms. Understanding the structure of is important for globally solving NP-hard quadratic programs over P. We establish key characteristics of and construct a separation algorithm for provided one can optimize with respect to a related cone over the boundary of P. This algorithm leads to a nonlinear representation of and a class of tractable relaxations for , each of which improves a standard polyhedral-semidefinite relaxation of . 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 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 5 x 5 completely positive matrices.
Details
- Title: Subtitle
- Separation and relaxation for cones of quadratic forms
- Creators
- Samuel Burer - University of IowaHongbo Dong - University of Wisconsin
- Resource Type
- Journal article
- Publication Details
- Mathematical programming, Vol.137(1-2), pp.343-370
- Publisher
- Springer Nature
- DOI
- 10.1007/s10107-011-0495-6
- ISSN
- 0025-5610
- eISSN
- 1436-4646
- Number of pages
- 28
- Grant note
- CCF-0545514 / NSF; National Science Foundation (NSF)
- Language
- English
- Date published
- 02/01/2013
- Academic Unit
- Business Analytics
- Record Identifier
- 9984380548202771
Metrics
1 Record Views