Maximizing a certain concave function over a non-convex set

Question

I have been working on a problem which involves maximizing a concave function over a non convex constraint set. The problem is the following $$max. \frac{1}{2}x^TBx\\ s.t.\ x_i(1-x_i)=0,\ \ i=1,\cdots,\ n\\ ||x||_0\le K$$ where I know that $B$ is a positive definite matrix. It can be easily seen that the solution to this problem would be to find a subset $S\subset [n]:=\{1,2,\cdots,\ n\}$ such that $$||(e_{1})_S||_1\ge||(e_{2})_S||_1\ge \cdots\ge ||(e_{n})_S||_1 $$ where $e_i$ is an eigenvector corresponding to the $i$ th largest eigenvalue of the matrix $B$. But solving this problem seems to be hard (It seems to me it is NP-hard though I am not sure about it). So, I was thinking can we solve this problem by relaxing the equality constraints? I noted that if the matrix $B$ is diagonal with positive elements then the problem has a unique solution. So I am also curious whether there is some general theory about these kind of non convex problems.

EDIT There is a further piece of information. I know that the matrix $B$ is tri-diagonal and diagonally dominant. Does that help anyway?

Answer 1

Your first set of constraints enforce that $x_i \in \{0,1\}$, and given this your second constraint is equivalent to $\sum_i x_i \leq K$. In the case where $B$ is diagonal with positive entries your problem is thus equivalent to a 0/1 knapsack problem, which is an NP-hard problem. However a pseudo-polynomial dynamic programming algorithm exists, and it should be fairly straight-forward to modify that algorithm to a pseudo-polynomial algorithm for your problem in the case where $B$ is tri-diagonal (i.e., it should run in ${\cal O}(nK)$ time).