1
$\begingroup$

This question is part of my continuing efforts to answer my original question in A puzzling KKT for LMI vs. scalar constraint.

Consider an SDP \begin{align} &\min - \text{Tr}(P)\\ &\ \ \text{s.t.} \begin{pmatrix} A^TP + PA +C^TPC + Q & PB + C^TPD \\ B^T P + D^TPC& R+D^TPD \end{pmatrix}\succeq0, P\succeq0 \end{align}

In a paper, they define a dual variable as \begin{align} Z= \begin{pmatrix} S&U^T&0\\ U&T&0\\ 0&0&W \end{pmatrix}, \end{align} and claim that \begin{align} AS+SA^T + CSC^T + BU + DUC^T + U^TB^T + CU^TD^T + D^TTD + W + I=0. \end{align} By computing the KKT stationarity condition, we get that the Trace of this equation is zero rather than its argument. What am I missing?

I will be happy for help about this step and two more related questions:

  1. How will the equation change if we change to objective to $-\text{Tr}(R+D^TPD)$.
  2. Is it a standard SDP? I learned that the objective should be expressed as $c^Tx$.
$\endgroup$
0
3
$\begingroup$

You can write the primal as: \begin{align} &\min - \text{Tr}(P)\\ &\ \ \text{s.t.} \begin{pmatrix} A^TP + PA +C^TPC + Q & PB + C^TPD & 0 \\ B^T P + D^TPC& R+D^TPD & 0 \\ 0 & 0 & P \end{pmatrix}\succeq0 \end{align} The Lagrangian is: \begin{align} L(P,Z) = - \text{Tr}(P) - \langle \begin{pmatrix} A^TP + PA +C^TPC + Q & PB + C^TPD & 0 \\ B^T P + D^TPC& R+D^TPD & 0 \\ 0 & 0 & P \end{pmatrix} , Z \rangle \end{align} If you take the derivative with respect to $P$ you obtain the stationarity condition: \begin{align} 0&=\frac{\partial L(P,Z)}{\partial P}\\ &= - \frac{\partial}{\partial P} \left\{\text{Tr}(P) + \text{Tr} \left(S^T(A^TP+PA + C^TPC+Q) + U(PB+C^TPD))\right)\right\}\\ &\ \ \ \ \ - \frac{\partial}{\partial P} \left\{ \text{Tr}\left(U^T(B^TP+D^TPC) + T^T(R+D^TPD) + P^TW)\right)\right\}. \end{align} By using the general relation $\frac{\partial}{\partial P} \text{Tr}(\Gamma P \Lambda) = \frac{\partial}{\partial P} \text{Tr}(\Lambda\Gamma P ) = \Lambda^T\Gamma^T$ for any $\Lambda,\Gamma$ and the cyclic trace property, we get: \begin{align} 0&= I + AS + SA^T + CSC^T + U^TB^T + CU^TD^T + BU + DUC^T + DTD^T+ W. \end{align}

As for your other questions:

  1. the $I$ at the end will become $DD^T$
  2. there is no 'standard' SDP, but an SDP in standard form is: $$\min_{X \succeq O} \{ \text{Tr}(CX) : \text{Tr}(A_iX)=b_i, \; i=1,\ldots,m\}$$ so clearly the given SDP is not in standard form. You can always reformulate it into standard form though (using a different choice for $X$).
$\endgroup$
7
  • 1
    $\begingroup$ @Morad $\langle A,B \rangle = \text{Tr}(A^TB)$, not $\text{Tr}(AB)$ $\endgroup$ – LinAlg Feb 24 at 22:45
  • 1
    $\begingroup$ @Morad I have updated the derivation and found discrepancies in the terms $CSC^T$ and in $DTD^T$ $\endgroup$ – LinAlg Feb 24 at 22:57
  • $\begingroup$ Correct, there was a typo in the first entry and I corrected it to $C^TPC$. The $DTD^T$ term does not have a typo however. I noticed the inner product typo, but some reviewers did not approve my second edit. $\endgroup$ – Morad Feb 24 at 23:20
  • $\begingroup$ For the inner product, $A$ is symmetric, no? $\endgroup$ – Morad Feb 25 at 4:56
  • 1
    $\begingroup$ @Morad not necessarily, it is a valid inner product on the set of all (including asymmetric) matrices $\endgroup$ – LinAlg Feb 25 at 14:14

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.