# Does strong duality hold for this semidefinite program?

$$\DeclareMathOperator{\Tr}{Tr}\DeclareMathOperator*{\argmax}{\arg\!\max}$$Consider the following semidefinite program (SDP) \begin{aligned} \max_V \quad & \Tr(V) \\ \textrm{s.t.} \quad & \begin{bmatrix} AVA^T + Q - V & \sqrt{\lambda}AVC^T \\ \sqrt{\lambda}CVA^T & CVC^T + R \end{bmatrix} \succeq 0 \\ \quad & V \succeq 0 \end{aligned} \tag{1} where $$V \in \mathbb R^{n \times n}, A \in \mathbb R^{n \times n}, C \in \mathbb R^{n \times m}, Q \in \mathbb R^{n \times n} \succeq 0, R \in \mathbb R^{m \times m} \succ 0,$$ and $$\lambda \in [0,1]$$. This SDP shows up in Theorem 6 in the paper

B. Sinopoli, L. Schenato, M. Franceschetti, K. Poolla, M. I. Jordan, and S. S. Sastry, “Kalman filtering with intermittent observations,” IEEE Transactions on Automatic Control, vol. 49, no. 9, pp. 1453–1464, Sep. 2004, doi: 10.1109/TAC.2004.834121.

Suppose that the input parameters $$A,C,Q,R,$$ and $$\lambda$$ are always chosen such that a solution for $$(1)$$ exists. Does strong duality hold for $$(1)$$?

$$\DeclareMathOperator{\Tr}{Tr}\DeclareMathOperator*{\argmax}{\arg\!\max}$$It turns out that strong duality holds for a slightly different but equivalent SDP. We prove this using the following three steps:

1. We show that a matrix $$V$$ solves $$(1)$$ if and only if $$V \succeq 0$$ and it solves the following "modified" algebraic Riccati equation \begin{align} V &= AVA^T + Q - \lambda AVC^T (CVC^T + R)^{-1}CVA^T \\ &= g_\lambda(V) \tag{2} \end{align} where we have defined the function $$g_\lambda(V) = AVA^T + Q - \lambda AVC^T (CVC^T + R)^{-1}CVA^T$$ as given in equation (16) in the paper.
2. We show that a matrix $$V \succeq 0$$ solves $$(2)$$ if and only if the same matrix $$V$$ solves the problem \begin{aligned} \min_V \quad & \Tr(V) \\ \textrm{s.t.} \quad & \begin{bmatrix} AVA^T + Q - V & \sqrt{\lambda}AVC^T \\ \sqrt{\lambda}CVA^T & CVC^T + R \end{bmatrix} \preceq 0 \\ \quad & V \succeq 0 \end{aligned} \tag{3}
3. We invoke Slater's condition to show that that there exists a $$V$$ that is strictly feasible for the problem in $$(3)$$, which implies that strong duality holds for $$(3)$$.

Note that there is a typo in Theorem 6 in the paper, where the condition $$\begin{bmatrix} AVA^T - V & \sqrt{\lambda}AVC^T \\ \sqrt{\lambda}CVA^T & CVC^T + R \end{bmatrix} \succeq 0$$ should instead be $$\begin{bmatrix} AVA^T + Q - V & \sqrt{\lambda}AVC^T \\ \sqrt{\lambda}CVA^T & CVC^T + R \end{bmatrix} \succeq 0$$

## Step 1

Although a proof of the statement given in step 1 is given in part (b) of Theorem 6 in the paper, we repeat it here with some additional commentary for convenience (and to avoid repetition in step 2).

First, we show that if $$V$$ solves $$(1)$$, then $$V$$ solves $$(2)$$. Suppose that $$V$$ solves $$(1)$$ and suppose that, for the sake of contradiction, $$V$$ does not solve $$(2)$$.

Because $$V$$ is feasible in $$(1)$$, then $$\begin{bmatrix} AVA^T + Q - V & \sqrt{\lambda}AVC^T \\ \sqrt{\lambda}CVA^T & CVC^T + R \end{bmatrix} \succeq 0$$ Then, using the Schur complement lemma, $$V \preceq g_\lambda(V)$$. Next, because $$V$$ does not solve $$(2)$$, then $$V \neq g_\lambda(V)$$.

Because $$V \preceq g_\lambda(V)$$ and $$V \neq g_\lambda(V)$$, then $$V \prec g_\lambda(V)$$. This implies that $$\Tr(V) \prec \Tr(g_\lambda(V))$$. However, because $$V$$ solves $$(1)$$, such that for every $$\tilde V$$ in the feasible set of $$(1)$$, we have that $$\Tr(V) \succeq \Tr(\tilde V)$$, then there is a contradiction. Therefore, $$V$$ solves $$(2)$$.

Next, we show that if $$V$$ solves $$(2)$$, then $$V$$ solves $$(1)$$. Suppose that $$V$$ solves $$(2)$$, such that $$V = g_\lambda(V)$$. This implies that $$V \preceq g_\lambda(V)$$. By the Schur complement lemma, this implies that $$\begin{bmatrix} AVA^T + Q - V & \sqrt{\lambda}AVC^T \\ \sqrt{\lambda}CVA^T & CVC^T + R \end{bmatrix} \succeq 0$$ Hence, $$V$$ is feasible in $$(1)$$. It remains to show that $$V$$ is also maximal, in the sense that $$\forall \tilde V \succeq 0, V \succeq \tilde V$$. In corollary 13.1.2 in the book

P. Lancaster and L. Rodman, Algebraic Riccati equations. in Oxford science publications. Oxford : New York: Clarendon Press ; Oxford University Press, 1995.

it was shown that, if the pair $$(C,A)$$ is detectable, then there exists a unique maximal solution to $$(2)$$. We will make this assumption to conclude that $$V$$ is maximal, and hence solves $$(1)$$.

## Step 2

We can employ a proof similar to the one given in step 1 to complete step 2. We omit this proof for brevity.

## Step 3

We now invoke Slater's condition to conclude that strong duality holds for $$(3)$$. First, suppose that $$(A,Q)$$ is controllable and $$(C,A)$$ is detectable, and let $$\lambda > \overline{\lambda}$$ as given in Theorem 6 in the paper by Sinopoli et al. given in the question.

Then, from theorem 5 (corollary 1) in the paper, there exists a $$Z$$ and $$0 \prec Y \preceq I$$ such that $$\Psi_\lambda(Y,Z) \succ 0$$. Next, from theorem 5 in the paper, because there exists a $$Z$$ and $$0 \prec Y \preceq I$$ such that $$\Psi_\lambda(Y,Z) \succ 0$$, then there exists an $$X$$ such that $$X \succ g_\lambda(X)$$.

Finally, from lemma 1(g) in Appendix A in the paper, because $$X \succ g_\lambda(X)$$, then $$X \succ 0$$. Note that the condition $$X \succ 0$$ is the strict version of the second constraint in $$(3)$$, and the condition $$X \succ g_\lambda(X)$$ is the strict version of the first constraint in $$(3)$$. Therefore, by Slater's condition, strong duality holds for $$(3)$$.