On Standard Quadratic Programs with Exact and Inexact Doubly Nonnegative Relaxations
Emre Alper Yıldırım, University of Edinburgh
December 11, Friday
13:40 via Zoom
The problem of minimizing a (nonconvex) quadratic form over the unit simplex, referred to as a standard quadratic program, admits an exact convex conic formulation over the computationally intractable cone of completely positive matrices. Replacing the intractable cone in this formulation by the larger but tractable cone of doubly nonnegative matrices, i.e., the cone of positive semidefinite and componentwise nonnegative matrices, one obtains the so-called doubly nonnegative relaxation, whose optimal value yields a lower bound on that of the original problem. We present a full algebraic characterization of the set of instances of standard quadratic programs that admit an exact doubly nonnegative relaxation. This characterization yields an algorithmic recipe for constructing such an instance. In addition, we explicitly identify three families of instances for which the doubly nonnegative relaxation is exact. We also provide an algebraic characterization of the set of instances for which the doubly nonnegative relaxation has a positive gap and show how to construct such an instance using this characterization.
(Joint work with Yakup Görkem Gökmen)
Emre Alper Yildirim is a Lecturer at the School of Mathematics at the University of Edinburgh. He graduated from Bilkent University with a B.S. degree in Industrial Engineering in 1997. He earned his M.S. and Ph.D. degrees in Operations Research at Cornell University in 2000 and 2001, respectively. Prior to joining the University of Edinburgh, he held faculty positions at Stony Brook University, Bilkent University, and Koc University. His research interests are in mathematical optimization and applications. He is particularly interested in convex conic optimization and various convex relaxations of nonconvex optimization problems.
