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?


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).

  • $\begingroup$ Can you give me a reference to the algorithm you are referring to. It will be really helpful. $\endgroup$ Dec 27 '14 at 16:13
  • $\begingroup$ Also, can it be solved approximately by convex relaxation of the constraint that the $x_i$ are in $\{0,1\}$? $\endgroup$ Dec 27 '14 at 16:14
  • $\begingroup$ @kaptenkas, in the case where $B$ is diagonal with positive entries I already know that the solution is to assign $x_i=1$ for all the indices that correspond to the $K$ largest diagonal entries of $B$, then how come is it NP-hard? $\endgroup$ Jan 4 '15 at 17:35

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.