Abstract
We consider the quadratic optimization problem maxxELEMENT OFCxTQx+qTx, where CSUBSET OF OR EQUAL TO Rn is a box and r:=rank(Q) is assumed to be 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. (C) 2021, The Author(s), under exclusive licence to Springer-Verlag GmbH, DE part of Springer Nature.