I have following problem regarding Semi-Definite Programming (SDP):

Consider the pair of primal and dual SDPs:

primal $$\text{ minimize } c^Tx$$ subject to: $$F_{(x)} \leqslant 0$$ dual $$\text{ maximize } tr(F_0Z)$$ subject to: $$tr(F_iZ)+c_i = 0, i = 1,...,n$$ $$ Z \geqslant 0$$

where: $c,x \in \mathbb{R}^n$

and $F_{(x)}=F_0 + x_1F_1 + ...+ x_nF_n$

and $F_i \in \mathbb{S}^p$ for i=1,...,n

Let $Z^*$ be an optimal solution for dual. Show that every optimal solution $x^*$ of the following unconstrained problem $$\text{ minimize } c^Tx + Mmax(0, \lambda_{max}(F_{(x)}))$$, where constant $M>tr(Z^*)$ and $\lambda_{max}(F_{(x)})$ denotes the largest eigenvalue of $F_{(x)}$, is an optimal solution of the primal.

[Hint: reformulate the unconstrained problem into as SDP and then derive its dual form]

I find this difficult, because the objective function includes $max()$, which I dont know how to interpret in terms of condition. Otherwise I would start with:

$$\text{ minimize } t$$ subject to: $$ c^Tx + Mmax(0, \lambda_{max}(F_{(x)})) - t \leqslant 0$$

Which is kind of standard way of turning problems into SDPs.

I have also considered equality constraint, but I just dont know what to do with the $max()$. Also, I am not sure about SDP duals, since it seems the Lagrangian doesnt follow the scalar case. I have found only this Semi definite duals document, where they say I can get SDP dual if I have the primal in the correct/standard form.


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.