2
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ One reason strategy 1) can fail is that there's no reason rounding will move you in the gradient direction. You could try rounding according to the gradient direction, but it's possible you could be moving very far, and the gradient might change drastically throughout that step. Strategy 2 could just find local minimum, of which there could be tons. $\endgroup$ – spitespike Jul 10 '17 at 21:45
2
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Thanks very much @Brian Borchers. Following your suggestion and looking around the literature, I see that MAX-CUT is polynomial for planar graphs. ( web.eecs.umich.edu/~pettie/matching/… ) As it happens, my quadratic form is sparse and similar, possibly equivalent, to a planar graph's Laplacian. $\endgroup$ – spitespike Jul 10 '17 at 20:39
  • $\begingroup$ That might be a good way to approach your problem. Good luck. $\endgroup$ – Brian Borchers Jul 12 '17 at 15:09
0
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ I'm afraid I don't follow your point. Could you explain the impetus for estimating the maximum this way? An easy upper bound for $f$ is $n\lambda$ where $\lambda$ is the spectral radius of $A$, computable by power iteration or similar. The problem is to compute the integral state; how would you extract it from $X$ if not computing the dominant eigenvector as the best rank 1 approximation, then doing some kind of rounding? $\endgroup$ – spitespike Jul 25 '17 at 22:08
  • $\begingroup$ @spitespike Have you performed any numerical experiments and compared the upper bound provided by the SDP relaxation with the one given by the spectral radius? I have not and I am curious. Forming a rank-1 matrix from the dominant eigenvector does not guarantee that the resulting matrix is a correlation matrix, as the main diagonal may not have only 1's. $\endgroup$ – Rodrigo de Azevedo Jul 25 '17 at 22:28
  • $\begingroup$ That would be interesting, but I haven't compared. (It turns out my problem can be reduced to planar MAXCUT.) I am more interested in the state achieving the maximum rather than the value of the maximum. Does computing X suggest a state? $\endgroup$ – spitespike Jul 25 '17 at 22:51

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.