Non-negative quadratic maximization

2010-12-09T22:22:54Z

For a given symmetric, positive semidefinite, $n \times n$ matrix $A$, we want to solve the problem $$\max_{||x|| = 1, \;\;x >= 0} x^T A x.$$ Here, $x >= 0$ indicates that $x$ must be component-wise non-negative. Without the $x >= 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 >= 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 by Noah Stein for Non-negative quadratic maximization

2010-12-09T23:08:16Z

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 SDP 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.

Non-negative quadratic maximization - MathOverflow

Non-negative quadratic maximization

Answer by Noah Stein for Non-negative quadratic maximization