A new polynomially solvable class of quadratic optimization problems with box constraints
Milan Hladík, Michal Černý, Miroslav Rada · arXiv (Cornell University) · 2019
We consider the quadratic optimization problem $\\max_{x \\in C}\\ x^T Q x + q^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.