Non-negative quadratic maximization

Question

For a given symmetric and positive semidefinite $n \times n$ matrix $A$, we want to solve the problem $$\max_{||x|| = 1, \ x\geq 0} x^T A x.$$ Here, $x\geq 0$ indicates that $x$ must be component-wise non-negative. Without the $x\geq 0$ constraint, the solution $x$ must be the eigenvector corresponding to the largest eigenvalue (from Ky Fan). Is there a well-known solution for the case when $x\geq 0$?

If not, are there any good relaxations (or randomized algorithms) to find $x$? For instance, are there any approximation bounds on how far from the optimum is the "largest eigenvector" of $A$?

Answer 1

First, note that the condition that $A$ be positive semidefinite (PSD) doesn't buy you anything. Replacing $A$ by $A+kI$ changes the objective value of any feasible solution by $k$, so if we could solve the given problem when the matrix in the objective is PSD, we could just choose some $k$ large enough to make $A+kI$ PSD, solve the resulting problem with $A+kI$, and subtract $k$ to get the answer to the problem with $A$ instead.

A matrix is called copositive if $x^T A x\geq 0$ for all $x\geq 0$. Checking copositivity of $A$ is the same as checking whether the optimal value of your problem on $-A$ is nonpositive. As shown by Murty and Kabadi ("Some NP-Complete Problems in Quadratic and Nonlinear Programming"), this problem is co-NP-complete. Thus your given problem is NP-hard.

That said, it is a quadratically constrained quadratic program ("QCQP"), which is a well-studied kind of problem, so I would suggest looking into these. For certain classes of them there are well-performing approximation algorithms. In general there are SDP relaxations, although proving performance guarantees is often difficult.

One last thing to note: at least when $A$ is PSD, your formulation is equivalent to one in which the equality constraint is replaced by $\leq$, and then the feasible set will be convex. So you may see the problem in this form.

EDIT: I'm not sure if this is the kind of thing you are looking for, but there is a sequence of SDP relaxations which will give you upper bounds on the objective function. To construct these, we will need the completely positive matrices, which form a convex cone dual to the copositive matrices above. The completely positive matrices are convex combinations of outer products $xx^T$ where $x\geq 0$.

Your problem can be rewritten as maximizing $Tr(AX)$ subject to the conditions that $Tr(X) = 1$ and $X = xx^T$ for $x\geq 0$. Since the objective is now linear, we can go ahead and convexify the feasible set to get the equivalent problem of maximizing $Tr(AX)$ subject to $Tr(X)=1$ and $X$ is completely positive.

Now, being dual to copositivity, complete positivity is also hard to test. But there are a nice sequence of SDP relaxations which give tighter and tighter outer approximations to the completely positive cone; these are just dual to the inner approximations of the copositive cone given by Parrilo ("Semidefinite Programming Based Tests for Matrix Copositivity"). For example, the first relaxation is that $X$ be elementwise nonnegative and PSD, two obvious necessary conditions for complete positivity (in fact these are sufficient for $4\times 4$ and smaller matrices, in which case the relaxation is exact).

Substituting in any such relaxation will give you an SDP which upper bounds the value of your problem of interest.