3. Duality

The dual problem associated with the SDP is :

\[\begin{split}\begin{align*} maximize\quad &-Tr(F_{0}Z) \\ subject\ to \quad &Tr(F_{i}Z) = c_{i}, i=1,...m, \\ & Z \ge 0, \ Z^{T} = Z \in \mathbb{R}^{n\times n} \end{align*}\end{split}\]

The lagrangian of the original problem is :

\[\begin{split}\begin{align*} \mathcal{L}(x,z) &= c^{T}x - z^{T}F(x)z \\ & = c^{T}x - Tr( z^{T}F(x)z) \\ & = c^{T}x - Tr( F(x)z^{T}z) \\ & = c^{T}x - Tr( F(x)Z) , \quad where Z = z^{T}z\\ & = c^{T}x - Tr( (F_{0} + \sum_{i=1}^{m}x_{i}F_{i})Z) \\ \end{align*}\end{split}\]
\[\frac{\partial \mathcal{L}(x,Z)}{\partial x_{i}} = c_{i} - Tr(F_{i}Z) = 0, i = 1,...,m\]
\[\mathcal{L}(x,z)^{*} = -Tr(F_{0}Z)\]

This dual problem is also a SDP. i.e. it can be put into the same formulation as the primal problem.

Proof:

Firstly, we note that the feasible set \(\{ Z\mid Z= Z^{T}\in R^{n\times n}, Tr(F_{i}Z)=c_{i}, i=1,..,m \}\) is actually an affine set. As any linear combination of the elements in the set is also in the set, as we have :

\[\alpha_{1}Z_{1} + \alpha_{2}Z_{2} = (\alpha_{1}Z_{1} + \alpha_{2}Z_{2})^{T} ,\ \alpha_{1} + \alpha_{2} = 1\]
\[Tr(F_{i}(\alpha_{1}Z_{1} + \alpha_{2}Z_{2})) = \alpha_{1}Tr(F_{i}Z_{1}) + \alpha_{2}Tr(F_{i}Z_{2}) = c_{i}\]

So we can express the feasible set in the form:

\[\{G(y)=G_{0} + y_{1}G_{1} + \cdot \cdot\cdot + y_{p}G_{p}\mid y\in \mathcal{R}^{p} \}\]

3.1 Strong Duality

Duality Gap is (using the upper constrains and the definition of F(x)):

\[\eta = c^{T}x + Tr(F_{0}Z) = \sum_{i=1}^{m}Tr(ZF_{i}x_{i}) + Tr(ZF_{0}) = Tr(ZF(x)) \ge 0\]

in which we use \(Tr(AB)\ge 0\) when \(A = A^{T}\ge 0\) and \(B=B^{T}\ge 0\), Thus we have :

\[c^{T}x \ge -Tr(F_{0}Z)\]

i.e. the dual objective value is lower bounds of the primal optimal value.

Theorem Strong Duality. we have p* = d* if either of the following conditions holds:

  • The primal problem is strictly feasible. i.e. exist an x with F(x) > 0.
  • The dual problem is strictly feasible. i.e. exist a Z with \(Z=Z^{T}>0\).

(\(F(x) \ge 0\) is the feasible condition, while F(x) > 0 is the strictly feasible condtion). If both conditions hold, the optimal set X and Z are nonempty.

In this case,

\[c^{T}x = -Tr(F_{0}Z) = p* = d*\]

Thus \(Tr(F(x)Z) = 0\), Since \(F(x)\ge 0\) and \(Z\ge 0\), we have F(x)Z=0, the complementary slackness condition.

Example : consider an example to further show the strong duality:

\[\begin{split}\begin{align*} & minimize \quad x_{1} \\ & subject\ to \quad \begin{bmatrix} 0 & x_{1} & 0 \\ x_{1} &x_{2}&0 \\ 0&0&x_{1}+1 \end{bmatrix} \ge 0 \end{align*}\end{split}\]

The feasible set of the upper problem is \(\{[x_{1}, x_{2}]^{T} \mid x_{1}=0, x_{2}\ge 0 \}\) And in this feasible set, the optimal is \(p^{*} = 0\). Its dual problem is :

\[\begin{split}\begin{align*} & maximize\quad -z_{2} \\ & subject\ to \quad \begin{bmatrix} z_{1} &(1-z_{2})/2 & 0 \\ (1-z_{1})/2 & 0 & 0 \\ 0 & 0 & z_{2} \end{bmatrix} \ge 0 \end{align*}\end{split}\]

The dual feasible set is \(\{[z_{1}, z_{2}]^{T} \mid z_{1}\ge 0, z_{2}=1 \}\), the optimal is \(d^{*} = -1\). In the primal problem we have \(F(x) = F([0, x_{2}])\) which then have :math:`F(x) ge 0 `, thus the primal problem is feasible but not strictly feasible. Same, the dual problem is feasible but not strictly feasible. It violates the following optimal conditions. As a result, it has non-zero duality gap.

3.2 Optimal Condition

Thus we have the optimal conditions for SDP:

\[\begin{split}\begin{align*} &F(x)\ge 0\\ &Z\ge 0, \ Tr(F_{i}Z) = c_{i}, i=1,...,m, \\ &ZF(x) = 0 \end{align*}\end{split}\]

Which are primal feasible, dual feasible, and zero duality-gap. Which is equvialent to the stictly feasible conditions of primal problem and dual problem.

3.3 Primal-Dual

The primal dual methods for SDP is :

  • Generate a sequence of primal and dual feasible points \(x^{(k)}\) and \(z^{(k)}\), where k donates the iteration numbers.
  • \(x^{(k)}\) is suboptimal, which gives an upper bound. And \(z^{(k)}\) as a certificate, which gives an lower bound.
  • We have the duality gap from the upper derivatives \(c^{T}x - p^{*} \le \eta^{k} = c^{T}x^{(k)} + Tr(F_{0}Z^{(k)})\) , we could use this as the stopping certierion \(c^{T}x^{(k)} + Tr(F_{0}Z^{(k)}) \le \epsilon\) .

Which could be formed as Primal-Dual Optimization Problem :

\[\begin{split}\begin{align*} & minimize \quad c^{T}x + Tr(F_{0}Z) \\ & subject\ to \quad F(x) \ge 0,\ Z\ge 0,\ Tr(F_{i}Z) = c_{i}, i=1,...,m \end{align*}\end{split}\]

Which is also an SDP.