Separation and relaxation for cones of quadratic forms |
| |
Authors: | Samuel Burer Hongbo Dong |
| |
Institution: | 1. Department of Management Sciences, University of Iowa, Iowa City, IA, 52242-1994, USA 2. Wisconsin Institutes for Discovery, University of Wisconsin, Madison, WI, 53715-1003, USA
|
| |
Abstract: | Let ${P \subseteq \mathfrak{R}_{n}}$ be a pointed, polyhedral cone. In this paper, we study the cone ${\mathcal{C} = {\rm cone}\{xx^T : x \in P\}}$ of quadratic forms. Understanding the structure of ${\mathcal{C}}$ is important for globally solving NP-hard quadratic programs over P. We establish key characteristics of ${\mathcal{C}}$ and construct a separation algorithm for ${\mathcal{C}}$ provided one can optimize with respect to a related cone over the boundary of P. This algorithm leads to a nonlinear representation of ${\mathcal{C}}$ and a class of tractable relaxations for ${\mathcal{C}}$ , each of which improves a standard polyhedral-semidefinite relaxation of ${\mathcal{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 ${\mathcal{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 5 × 5 completely positive matrices. |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|