TY - JOUR

T1 - On Standard Quadratic Programs with Exact and Inexact Doubly Nonnegative Relaxations

AU - Gokmen, Y. Gorkem

AU - Yildirim, E Alper

N1 - Funding Information:
The work of the first author was supported, in part, by TÜBİTAK (Turkish Scientific and Technological Research Council) PhD Scholarship Program BİDEB 2211-A, which is gratefully acknowledged. We are grateful to two anonymous reviewers for their insightful and perceptive comments and suggestions, which considerably improved the exposition.
Publisher Copyright:
© 2021, The Author(s).

PY - 2022/5/31

Y1 - 2022/5/31

N2 - 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 establish several relations between the so-called convexity graph of an instance and the tightness of the doubly nonnegative relaxation. 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.

AB - 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 establish several relations between the so-called convexity graph of an instance and the tightness of the doubly nonnegative relaxation. 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.

U2 - 10.1007/s10107-020-01611-0

DO - 10.1007/s10107-020-01611-0

M3 - Article

SN - 0025-5610

VL - 193

SP - 365

EP - 403

JO - Mathematical programming

JF - Mathematical programming

ER -