Skip to main content

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

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

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

Source Link

Non-negative quadratic maximization

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