  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.
