Maximizing a quadratic form on unit cube lattice points $\{ -1 , 1 \}^n$

Question

Consider the problem: given a symmetric, positive-definite, quadractic form with matrix $A = A^T \in \mathbb R^{n \times n}$ compute the vector $y \in \{-1,1\}^n$ achieving the maximum

$$\max_{x \in \{-1,1\}^n } x^TAx$$

Is there an efficient algorithm?

Two possibilities I was considering. Do they work for almost every example? If both work, which is more computationally efficient?

1. The function $f(x)=x^TAx$ achieves its maximum (the spectral radius of $A$) on the unit sphere $\{\|x\|_2=1\}$ exactly when $x$ is a eigenvector for the the dominant eigenvalue. So you could get a decent estimate to the problem by computing the dominant eigenvector $u$ with $\|u\|_\infty =1$ and then rounding every component of $u$ to $\pm 1$. Is there a reason this could fail generically? Computing eigenvectors is hard, but here don't need to be very concerned with precision, as you're rounding anyway.

2. The gradient of $f$ is $\nabla f(x) = 2Ax$. You could perform a gradient flow in the unit sphere $[-1,1]^n$ to find a point $p$ achieving at least a local maximum on $[-1,1]^n$. Would $p$ be a lattice point for a generic $A$? If not, what could prevent the nearest lattice point from being the desired maximum?

Answer 1

Unfortunately, your problem is NP-Hard, so you can't expect to find an efficient algorithm. In practice, these problems are often approached using heuristic algorithms. If you really want a provably optimal solution, branch and bound methods are appropriate.

To see that this problem is NP-Hard, start with the MAX-CUT problem on a graph. This problem is well known as an NP-Hard problem. Let $L$ be the graph Laplacian. A property of the graph Laplacian is that $L$ is positive semidefinite. The MAX-CUT problem can be formulated as

$\max_{x_{i}=\pm 1} \frac{1}{4} x^{T}Lx$

Thus an efficient (polynomial time) algorithm for your problem could be used to solve MAX-CUT in polynomial time.

Answer 2

We have the following Boolean optimization problem in $\mathrm x \in \{\pm 1\}^n$

$$\max_{\mathrm x \in \{\pm 1\}^n} \mathrm x^\top \mathrm A \,\mathrm x$$

Since $\{\pm 1\}$ is the solution set of the quadratic equation $x_i^2 = 1$, we have the following (non-convex) quadratically constrained quadratic program (QCQP) in $\mathrm x \in \mathbb R^n$

$$\begin{array}{ll} \text{maximize} & \mathrm x^\top \mathrm A \,\mathrm x\\ \text{subject to} & x_i^2 = 1, \quad \forall i \in \{1,2,\dots,n\}\end{array}$$

Exhaustive evaluation of the objective function at all $2^n$ points is only feasible for small $n$. Though this problem is hard, finding an upper bound on the maximum is easy.

---

SDP relaxation

Note that

$$\mathrm x^\top \mathrm A \,\mathrm x = \mbox{tr} \left( \mathrm x^\top \mathrm A \,\mathrm x \right) = \mbox{tr} \left( \mathrm A \mathrm x \mathrm x^\top \right) = \langle \mathrm A , \mathrm x \mathrm x^\top \rangle$$

Since $\mathrm x \in \{\pm 1\}^n$, all $n$ entries on the main diagonal of $\mathrm x \mathrm x^{\top}$ are equal to $1$. Thus, $\mathrm x \mathrm x^{\top}$ is symmetric, positive semidefinite and has only ones on its main diagonal, i.e., it is a correlation matrix. Also, its rank is $1$. Hence, the original Boolean optimization problem can be written as the following rank-constrained optimization problem in $n \times n$ symmetric matrix $\rm X$

$$\begin{array}{ll} \text{maximize} & \langle \mathrm A , \mathrm X \rangle\\ \text{subject to} & x_{ii} = 1, \quad \forall i \in \{1,2,\dots,n\}\\ & \mathrm X \succeq \mathrm O_n\\ & \mbox{rank} (\mathrm X) = 1\end{array}$$

which is a hard problem due to the rank constraint. Relaxing the optimization problem above by discarding the rank constraint, we then obtain the following semidefinite program (SDP) in $\rm X$

$$\boxed{\begin{array}{ll} \text{maximize} & \langle \mathrm A , \mathrm X \rangle\\ \text{subject to} & x_{ii} = 1, \quad \forall i \in \{1,2,\dots,n\}\\ & \mathrm X \succeq \mathrm O_n\end{array}}$$

which is convex and computationally tractable. This SDP relaxation provides an upper bound on the maximum of the original Boolean optimization problem. In the very, very fortunate case where the optimal solution of the SDP happens to be rank-$1$, we have also solved the original problem.