The usual way to define a semi-definite program (SDP), e.g., as given in Boyd and Vandenberghe's convex optimization book, is: $$ \begin{array}{cl} \min & c^\top x \\ \mathrm{s.t.} & 0 \succeq x_1 F_1+ \ldots+x_nF_n + G \\ & Ax = b \end{array} $$ where $ 0 \succeq M$ denotes $0 - M$ is a p.s.d. matrix. In the above problem $x \in \mathbb{R}^{n}$ is an optimization variable, while $F_1,\ldots,F_n, G$ are symmetric (known) matrices. Similarly $A \in \mathbb{R}^{m \times n},b \in \mathbb{R}^n$ are (known) linear equality system's matrices.

My question is, without being bothered by the standard notation as above, can we say any problem which has all linear constraints and an additional p.s.d.-ness constraint is SDP? For example, $$ \begin{array}{cl} \min & c^\top x \\ \mathrm{s.t.} & \sum_{(j,k) \in S_i} Y_{j,k} = x_i, \quad i=1,\ldots,n\\ & Y \succeq 0 \end{array} $$ Here, $S_i$ is a set of indexes, and for each $i$ we are summing the elements $(j,k) \in S_i$ of matrix $Y$ and equate it to $x_i$.

The reason I am confused is that writing $Y$ in the latter problem in form $x_1 F_1+ \ldots+x_nF_n + G$ seems not straightforward, i.e., another linear system on $Y$ matrix has to be solved, etc..

  • 2
    $\begingroup$ The first problem is what I consider dual form. The second problem is what I normally consider primal form. You can input the primal form directly to say Mosek. No need to convert it dual form. I would read about SDP in the Mosek modelling cookbook. $\endgroup$ – ErlingMOSEK Feb 4 '20 at 6:11

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.