Details

Autor(en) / Beteiligte

• Burer, Samuel
• Dong, Hongbo

Titel

Separation and relaxation for cones of quadratic forms

Ist Teil von

• Mathematical programming, 2013-02, Vol.137 (1-2), p.343-370

Ort / Verlag

Berlin/Heidelberg: Springer-Verlag

Erscheinungsjahr

2013

Link zum Volltext

Quelle

EBSCOhost Business Source Ultimate

Beschreibungen/Notizen

• 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 × 5 completely positive matrices.