  The Standard Quadratic optimization Problem (StQP), arguably the simplest
among all classes of NP-hard optimization problems, consists of extremizing a
quadratic form (the simplest nonlinear polynomial) over the standard simplex
(the simplest polytope/compact feasible set). As a problem class, StQPs may be
nonconvex with an exponential number of inefficient local solutions. StQPs
arise in a multitude of applications, among them mathematical finance, machine
learning (clustering), and modeling in biosciences (e.g., selection and
ecology). This paper deals with such StQPs under an additional sparsity or
cardinality constraint, which, even for convex objectives, renders NP-hard
problems. One motivation to study StQPs under such sparsity restrictions is the
high-dimensional portfolio selection problem with too many assets to handle, in
particular, in the presence of transaction costs. Here, relying on modern conic
optimization techniques, we present tractable convex relaxations for this
relevant but difficult problem. We propose novel equivalent reformulations of
these relaxations with significant dimensional reduction, which is essential
for the tractability of these relaxations when the problem size grows.
Moreover, we propose an instance generation procedure which systematically
avoids too easy instances. Our extensive computational results illustrate the
high quality of the relaxation bounds in a significant number of instances.
Furthermore, in contrast with exact mixed-integer quadratic programming models,
the solution time of the relaxations is very robust to the choices of the
problem parameters. In particular, the reduced formulations achieve significant
improvements in terms of the solution time over their counterparts.
