$\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:
- 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.
- 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}
$$
- 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)$.
