Abstract
We consider the problem of maximization of a convex quadratic form on a convex polyhedral set, which is known to be NP-hard. In particular, we focus on upper bounds on the maximum value.
We investigate utilization of different vector norms (estimating the Euclidean one) and different objective matrix factorizations. We arrive at some kind of duality with positive duality gap in general, but with possibly tight bounds.
We discuss theoretical properties of these bounds and also extensions to generally preconditioned factors. We employ mainly the maximum vector norm since it yields efficiently computable bounds, however, we study other norms, too.
Eventually, we leave many challenging open problems that arose during the research. © 2020, Springer-Verlag GmbH Germany, part of Springer Nature.