A new polynomially solvable class of quadratic optimization problems with box constraints

Abstract

We consider the quadratic optimization problem $\max _{x \in C}\ x^{\mathrm {T}}Q x + q^{\mathrm {T}}x$, where $C\subseteq {\mathbb {R}}^n$ is a box and $r:= {{\,\mathrm{rank}\,}}(Q)$ is assumed to be ${\mathcal {O}}(1)$ (i.e., fixed). We show that this case can be solved in polynomial time for an arbitrary Q and $q$. The idea is based on a reduction of the problem to enumeration of faces of a certain zonotope in dimension $O(r)$. This paper generalizes previous results where Q had been assumed to be positive semidefinite and no linear term was allowed in the objective function. Positive definiteness was a strong restriction and it is now relaxed. Generally, the problem is NP-hard; this paper describes a new polynomially solvable class of instances, larger than those known previously.