# Maximizing positive definite quadratic using the eigendecompoisition

Consider the problem:

$\textrm{max}\;\; x^T Q x$

subject to $||x||_\infty \leq 1$, where $Q$ is a positive definite matrix.

I believe this problem is NP-hard (although I have only found hardness results for positive semi-definite matrices).

Consider now the following algorithm. Let $q_1$ be the largest eigenvector of $Q$. Let the solution $x$ be defined by $x_i = \textrm{sign}(q_{1i})$.

When does this algorithm fail? So far, I have looked for examples in 2d or 3d, and have not found any.

Note that the intuition here is that $x$ should be as close as possible to $q_1$.

-
What is $q_i??$ –  Igor Rivin Apr 4 '12 at 6:08
Sorry, I meant $q_{1i}$, the $i$-th entry of the largest eigenvector $q_1$. The question is now edited. –  Woland Apr 4 '12 at 19:09

The reference where all is revealed is Bodlaender, Gritzman, Klee, Van Leeuwen

-