optimization related to sdp

Question

I have the dual solution of an sdp problem and strong duality hold in this case, I have the dual feasible solutions . From the Dual feasible solutions can i get the primal feasible solution?

Answer 1

I'll assume in my answer that you're using the convention that the primal problem is:

$\max tr(CX) $

subject to

$tr(A_{i}X)=b_{i}\;\; i=1, 2, ..., m$

$X \succeq 0$

where $X$ is an $n$ by $n$ symmetric and PD matrix. The dual is

$\min b^{T}y$

subject to

$A^{T}(y)-C=Z$

$Z \succeq 0$

The same basic approach carries over to other primal-dual formulations of the SDP.

The KKT conditions for the primal dual pair are that

$A(X)=b$

$A^{T}(y)-C=Z$

$XZ=0$

$X \succeq 0$

$Z \succeq 0$

The complementary condition $XZ=0$, together with the requirement that $X$ and $Z$ must be PSD lead to:

1. $Z$ can be written as $Z=Q \Lambda Q^{T}$ where $Q$ is an orthogonal matrix and $\Lambda$ is a diagonal matrix with $\Lambda_{1,1} \geq \Lambda_{2,2} \geq ... \geq \Lambda_{k,k} \geq \Lambda_{k+1,k+1}=...=\Lambda_{n,n}=0$.

2. $X$ can be written as $X=QWQ^{T}$ where $W$ is also diagonal with $W_{1,1}=W_{2,2}=...=W_{k,k}=0$, and $W_{j,j} \geq 0$ for $j=k+1, k+2, ..., n$.

So, you can (in theory) find an optimal $X$ from an optimal $y$ and $Z$ by solving the equations

$tr(A_{i}X)=b_{i}\;\; i=1, 2, ..., m$

$X=QWQ^{T}$

where $W$ is a diagonal matrix matrix satisfying the requirements above.

This is typically severely over determined. In practice, you'll need to find a solution that satisfies the $tr(A_{i}X)=b_{i}$ constraints well enough in the least squares sense. This simplifies down to a nonnegative linear least squares problem in the vector of variables $W_{k+1,k+1}$, $W_{k+2,k+2}$, $...$, $W_{n,n}$.

In practice, unless you have an extremely good dual solution, it's unlikely that this approach will yield a very good primal solution- this has been a persistent problem with various dual methods for semidefinite programming such as the spectral bundle method or the dual interior point method implemented in DSDP. Primal-dual interior point methods don't have this problem, but of course these methods don't scale well to larger problem instances.