Semi-definite programming, and bound on the trace distance

convex optimizationmatricesnuclear normpositive-semidefinitesemidefinite-programming

I'm quite new to semi-definite programming (SDP), and I'd like to compute a program that has some conditions on the distance between two vectors.

More precisely I have some fixed positive real $\delta > 0$ and complex semi-definite matrices $\rho \succcurlyeq 0$ and $\sigma \succcurlyeq 0$, and I want to:

  1. Minimize $t$
  2. Subject to:
    1. $\rho' \succcurlyeq 0$
    2. $t > 0$
    3. $t \sigma \succcurlyeq \rho$
    4. $\|\rho'-\rho\|_* = Tr(|\rho'-\rho|) \leq \delta$ (this is the trace distance, i.e. the sum of the module of the eigen values of $\rho'-\rho$)

I can easily turn the first 3 conditions into an SDP by assuming that a matrix $X$ is positive, and enforcing the diagonal blocks of $X$ to be equal to $\rho'$, $t$ and $t\sigma – \rho'$ with linear conditions. However, I can't find how to treat the last condition $Tr(|\rho'-\rho|) \leq \delta$ as it's not linear.

Can I somehow give more conditions on $X$ to force also the last condition, or is it just that this problem can't be solved with a SDP ?

Thanks!

— EDIT —

Thanks a lot Brian Borchers for the reference! So I tried to look at the proof (page 19 for people interested), the first part goes well (the matrix it defines + computing the trace of this things just looks just a bit magic, but it works™), but for the other direction I'm not sure to see how to proceed: indeed, we suppose $\|X\|_* \leq \delta$ and we need to prove that if we define
$$\gamma = \frac{2\delta – 2 \|X\|_*}{p+q}$$
$$X = U \Sigma U^\dagger + \gamma I$$
$$Z = V \Sigma V^\dagger + \gamma I$$
then we need to prove that $Tr(Y)+Tr(Z) \leq 2\delta$ (this is easy) and
$$\begin{pmatrix}Y & X \\ X^\dagger & Z\end{pmatrix} \geq 0$$
However this last equality is not clear to me. I was thinking to use Schur complement that seems to be quite common in SDP, which is equivalent to something like:

  1. $V \Sigma V^\dagger + \gamma I \geq 0$ (easy as well)
  2. $U \Sigma U^\dagger + \gamma I – X^\dagger(V \Sigma V^\dagger + \gamma I)^{-1} X \geq 0$

(remark: Schur complement seems to be true for definite matrices and not for semi definite matrices (D^{-1} does not even makes sense when $D \geq 0$), i.e. it should be $>$ instead of $\geq$… what's the equivalent for semi definite matrices?)

However, I don't see how to derive equation 2… Any suggestion?

Best Answer

The OP has now clarified that the 4th constraint is that the nuclear norm (trace-norm, etc.) of the difference between $\rho$ and $\rho^{\prime}$ is less than $\delta$.

$\| \rho - \rho^{\prime} \|_{*} \leq \delta$.

There's a standard reformulation for this, which can be found in the SIAM Review survey paper on SDP by Vandenberghe and Boyd.

$X=\rho - \rho^{\prime}$

$ \left[ \begin{array}{cc} Y & X \\ X^{H} & Z \end{array} \right] \succeq 0$

$ \mbox{tr}(Y)+\mbox{tr}(Z) \leq 2 \delta$

Related Question