4
$\begingroup$

Let $X=\{x_{ij}\} \in R^{n \times n}$ denote a variable matrix, and $C_k,k=1,\ldots,m$ denote subsets of $\{(i,j):i=1,\ldots,n, \quad j=1,\ldots,n\}$, while $w_{ij}$ and $w_k$ are constants. The following optimization problem seems not a standard semi-definite programming since it is maximizing a convex function rather than minimizing it. So how to solve it ?

$$max \quad \sum_{i,j, i<j} w_{ij}x_{ij} + \sum_k w_k(\sum_{(u,v)\in C_k} x_{uv})^2 $$ $$ s.t. \quad x_{ij}=\{0,1\} , \; X=\{ x_{ij}\} \; \text{positive semi-definite} $$

$\endgroup$
  • $\begingroup$ Usually we relax the integer constraint to real number between 0 and 1 ? $\endgroup$ – Arthur Oct 16 '12 at 3:14
1
$\begingroup$

Seems to me the author is asking for a semidefinite programing solution. The first term of his objective function is like those in standard SDP problems, but he has a second term.

$\endgroup$

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.