Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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$?

share|improve this question
1  
The unconstrained case goes back much earlier than Ky Fan. It is anterior to Weyl (1912). The ratio $\frac{x^TAx}{x^Tx}$ is named after Rayleigh. –  Denis Serre Dec 10 '10 at 7:20
add comment

1 Answer 1

up vote 9 down vote accepted

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.

share|improve this answer
    
Thanks, Noah. This is indeed a QCQP, with one quadratic constraint. If we just had one (non-convex) quadratic objective, with a (non-convex) quadratic constraint, it is a special QCQP with nice duality properties (for example, S-procedure in control theory, or Appendix B of Boyd and Vandenberghe book). So, I wonder if there are any such special properties when we have a concave objective, with more than one (but quite simple) convex constraints (that is, $||x|| \leq 1$ and $x \geq 0$. –  user11443 Dec 10 '10 at 4:13
    
I added a little more about that kind of thing, but as per my original remark, I don't see how information about the signature of $A$ should help. –  Noah Stein Dec 10 '10 at 17:19
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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