Separating doubly nonnegative and completely positive matrices |
| |
Authors: | Hongbo Dong Kurt Anstreicher |
| |
Institution: | 1. Department of Applied Mathematics and Computational Sciences, University of Iowa, Iowa City, IA, 52242, USA 2. Department of Management Sciences, University of Iowa, Iowa City, IA, 52242, USA
|
| |
Abstract: | The cone of Completely Positive (CP) matrices can be used to exactly formulate a variety of NP-Hard optimization problems. A tractable relaxation for CP matrices is provided by the cone of Doubly Nonnegative (DNN) matrices; that is, matrices that are both positive semidefinite and componentwise nonnegative. A natural problem in the optimization setting is then to separate a given DNN but non-CP matrix from the cone of CP matrices. We describe two different constructions for such a separation that apply to 5 × 5 matrices that are DNN but non-CP. We also describe a generalization that applies to larger DNN but non-CP matrices having block structure. Computational results illustrate the applicability of these separation procedures to generate improved bounds on difficult problems. |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|