Maximizing a Concave function over a Non convex constraint set 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 and I assume $K<<n$. 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? 
 A: I will give you an approximate solution for your problem. Notice that $\|\mathbf{x}\|_{2}^{2} \leq min (K,n)$. Hence, you can solve first the optimization problem
\begin{equation}
 \begin{array}{c}
 minimize \hspace{1cm} -\frac{1}{2}\mathbf{y}^{T}\mathbf{B}\mathbf{y} \\
s.t. \hspace{2cm} \|\mathbf{y}\|_{2}^{2} \leq min (K,n), \\
\end{array}
\end{equation} whose solution is $\mathbf{y}^{\star} = \sqrt{min (K,n)}\mathbf{v}_{max}$. The vector $\mathbf{v}_{max}$ is the unitary eigenvector of $\mathbf{B}$ associated to the maximum eigenvalue.
Now, you solve the problem
\begin{equation}
 \begin{array}{c}
 minimize \hspace{1cm} \sum_{i=1}^{n}(y^{\star}_i -x_i)^2 \\
s.t. \hspace{2cm} x_i(1-x_i)=0,  \\
\hspace{2cm} \|\mathbf{x}\|_{0} \leq K. \\
\end{array}
\end{equation} This problem is easy to solve. For a given $K$, at most $min(\lfloor K \rfloor, n)$ elements of $\mathbf{x}$ can be set to $1$. Firstly, set $\mathbf{x}=\mathbf{0}$. Then, you begin by setting  $x_i$ to $1$ in the term  $(y^{\star}_i -x_i)$ that reduces the cost function as much as possible. You continue the procedure until  $\|\mathbf{x}\|_{0} = min(\lfloor K \rfloor, n)$ or the cost function does not reduce anymore.
