Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

share|improve this question
    
Usually we relax the integer constraint to real number between 0 and 1 ? –  Arthur Oct 16 '12 at 3:14
add comment

1 Answer

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.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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