Approximating large quadratic optimization problems

Question

For some positive-definite matrix $A \in \mathbb{R}^{K \times K}$ I want to solve the quadratic optimization problem $$\max_{x\in [0,1]^K} x^T A x \\ \text{s.t.} \\ \sum_{i=1}^{K}x_{i}=1$$ The problem is that $K$ is very large. Are there useful approximations to the quadratic form $x^TAx$ that would allow an approximate solution? Is dimensionality reduction of $A$ a useful idea?

Answer 1

If you are taking $\max$ then your problem is not convex, and you are having serious issues. If you wanted $\min$ and did not insist on the positivity, then the solution is just $A^{-1} \mathbb{1}/\mathbb{1}^T A^{-1} \mathbb{1},$ where $\mathbb{1}$ is the vector of all ones. If you did not have the sum constraint either, then you are in luck with $\max$ - it is just the eigenvector of the largest eigenvalue, which is easy to find by iterative methods.