We consider the maximization γ = max{xTAx, x ∈ {−1,1}n} for a given symmetric A∈ℛn×n. It was shown recently, using properties of zonotopes and hyperplane arrangements, that in the special case that A has a small rank, so that A = VV where V ∈ ℛn×m with m < n, then there exists a polynomial time algorithm (polynomial in n for a given m) to solve the problem max{xTVVTx, x ∈ {−1,1}n}. In this paper, we use this result, as well as a spectral decomposition of A to obtain a sequence of non-increasing upper bounds on γ with no constraints on the rank of A. We also give easily computable necessary and sufficient conditions for the absence of a gap between the solution and its upper bound. Finally, we incorporate the semidefinite relaxation upper bound into our scheme and give an illustrative example.
