Optimization: Formulation of the dual of a semi-definite program (SDP)

[Master1022]

Homework Statement

Given the semidefinite primal program below, find its dual

Relevant Equations

Inner product

Hi,

I was working through the following optimization problem, and am getting stuck on how to get to the dual problem that is being presented.

Question:
Find the dual problem for the semidefinite primal problem below:
$$min_{X} tr(C^T X)$$
$$\text{subject to} AX = B$$
$$X \succeq 0$$

(the answer is given as:
$$max_{Z} -tr(B^T X)$$
$$\text{subject to} A^T Z + C \succeq 0$$

Attempt:
I need to start by re-writing the constraints in the required form:
$$AX = B \rightarrow AX - B = 0$$
$$X \succeq 0 \rightarrow - X \preceq 0$$

Now we can write the Lagrangian function with some parameters $Z$ and $Y$:
$$L = tr(C^T X) + \langle AX - B, Z \rangle + \langle -X, Y \rangle$$
where $\langle P, Q \rangle = tr(P^T Q)$ for matrix constraints
$$L = tr(C^T X) + \langle AX, Z \rangle - \langle B, Z \rangle - \langle X, Y \rangle$$
$$L = tr(C^T X) + tr((AX)^T Z) - tr(B^T Z ) - tr(X^T Y) \rightarrow tr \left( C^T X + X^T A^T Z - X^T Y \right) - tr(B^T Z)$$
Then I can use the fact that: $tr(A^T B) = tr(B^T A)$ and can write $tr(C^T X) = tr(X^T C)$
$$L = tr \left( X^T (C + A^T Z - Y) \right) - tr(B^T Z)$$

This is one point where I don't fully understand the logic. Now I want to 'remove' dependence on $X$ from the above expression by thinking about the value of $C + A^T Z - Y$. If $C + A^T Z - Y \neq 0$, then we could pick $X$ to be something to make the minimum $-\infty$ (although I don't fully understand why this isn't ideal). Otherwise, if $C + A^T Z - Y = 0$, then the minimum becomes: $- tr(B^T Z)$

This leads us to the dual problem:
$$max_{Z} -tr(B^T X)$$
$$\text{subject to} A^T Z + C - Y \succeq 0$$

I am left with a few questions:
1. I don't know why there is a $Y$ in my expression (from inequality parameter), which isn't present in the answer?
2. Do I need to include the constraints on the inequality parameters?
3. (from above) why do we want to remove $X$ dependence from the expression such that min doesn't go to $-\infty$?

Thanks in advance

 

[Nino MMP]

for any help! The dual problem should be:max_{Z} -tr(B^T Z) \text{subject to} A^T Z + C \succeq 0 When setting up the Lagrangian, you need to introduce a variable (in this case, Y) for each inequality constraint. The Y variable is used to represent the constraint that X is greater than or equal to 0. The reason why we want to remove dependence on X is because the primal problem is an optimization problem, and the goal is to find the optimal X. Since the dual problem does not depend on X, it is not an optimization problem, but rather, a feasibility problem. We want to find values for Z such that the constraint is satisfied, regardless of the value of X. Therefore, if the constraint cannot be satisfied, we want the objective function to become -∞ so that there is no optimal solution.