Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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|cite|improve this question
Usually we relax the integer constraint to real number between 0 and 1 ? – Arthur Oct 16 '12 at 3:14

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|cite|improve this answer

Your Answer


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.