Non-negative quadratic maximization - MathOverflow most recent 30 from http://mathoverflow.net 2013-06-19T09:34:06Z http://mathoverflow.net/feeds/question/48843 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/48843/non-negative-quadratic-maximization Non-negative quadratic maximization unknown (yahoo) 2010-12-09T22:22:54Z 2010-12-13T19:16:50Z <p>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$? </p> <p>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$?</p> http://mathoverflow.net/questions/48843/non-negative-quadratic-maximization/48847#48847 Answer by Noah Stein for Non-negative quadratic maximization Noah Stein 2010-12-09T23:08:16Z 2010-12-10T17:17:03Z <p>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.</p> <p>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.</p> <p>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.</p> <p>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.</p> <p>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$.</p> <p>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.</p> <p>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).</p> <p>Substituting in any such relaxation will give you an SDP which upper bounds the value of your problem of interest.</p>