I want to know if the following problem has been solved
max_w w'Rw
where the entries of the vector w are binary (w_i= {0,1} )
3
-
$\begingroup$ where the matrix is positive semidefinite. Obviously, this problem is a NP-Hard combinatorial problem. My question is if this problem can be relaxed and somehow rewritten as a convex problem. Thanks $\endgroup$– CruiselanCommented Feb 15, 2013 at 17:37
-
$\begingroup$ The statement of the question should be edited into the body of the question, not left in a comment. $\endgroup$– Gerry MyersonCommented Feb 15, 2013 at 22:06
-
$\begingroup$ search for "binary QP" or "boolean QP" and you'll find tons of info. $\endgroup$– SuvritCommented Feb 15, 2013 at 23:54
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
- After a Cholesky factorization $R=T'T$, your problem becomes the maximization of the Euclidean norm over the parallelotope formed by the points $Tw$. This problem is discussed in H. L. Bodlaender, P. Gritzmann, V. Klee, J. van Leeuwen: Computational complexity of norm-maximization, Combinatorica 10 (1990), 203-225.
- If your matrix is just symmetric, not necessarily p.s.d., then it is essentially the maximum cut problem. For this problem, there are (famous) convex relaxations, using for example semidefinite programming.
