# Maximizing a convex function with positive semidefinite constraint

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}$$

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