Relations between the optimal solutions of two related Semi-Definite Programs

1

In system theory, we often encounter Semi-Definite Programs (SDPs) with Linear Matrix Inequality (LMI) constraints, such as those presented in this paper. I have introduced new variables based on the original decision variables and reformulated the LMIs using these new variables. Additionally, I have defined a similar SDP and, through simulation, identified relationships between their optimal solutions. I am now seeking mathematical proofs to substantiate these relationships. Further details will be provided below, and I would greatly appreciate any assistance in addressing my inquiry.

Consider following LMIs, where H \in \mathbb{R}^{(n+m) \times (n+m)} and W \in \mathbb{R}^{n \times n} are decision variables (0 <m \leq n) and we have:

H = \begin{bmatrix} H_{11} & H_{12} \\ H_{12}^T & H_{22} \end{bmatrix}, H_{11} \in \mathbb{R}^{n \times n}, H_{22} \succ 0 \in \mathbb{R}^{m \times m}

Also, D \in \mathbb{R}^{n \times (n+m)} and C \succeq 0 are constant matrices. Additionally, in all equations, 0 represents zero matrices of appropriate dimensions.

\begin{aligned} & \quad H - \begin{bmatrix} W & 0 \\ 0 & 0 \end{bmatrix} \succeq 0, \\ & \quad D^T \left(H_{11} - H_{12} H_{22}^{-1} H_{12}^T \right) D - H + C \succeq 0. \end{aligned}

Suppose K \in \mathbb{R}^{n \times j} is a constant matrix with rank n and j = n + n \cdot m . The matrix T \in \mathbb{R}^{(n+m) \times (j+m)} is constructed as:

T = \begin{bmatrix} K & 0 \\ 0 & I_m \end{bmatrix}

Suppose there exists a matrix S \in \mathbb{R}^{j \times (j+m)} such that D \cdot T = K \cdot S .

The new variable X \in \mathbb{R}^{(j+m) \times (j+m)} is defined as:

X = T^{T} H T = \begin{bmatrix} X_{11} & X_{12} \\ X_{12}^T & X_{22} \end{bmatrix}

Thus, the following relationships are established between the submatrices of H and X :

\begin{aligned} & X_{11} = K^T H_{11} K, \\ & X_{12} = K^T H_{12}, \\ & X_{22} = H_{22}. \end{aligned}

If we multiply the above LMIs from the left and right by T^T and T , respectively, we obtain:

X - \begin{bmatrix} K^T W K & 0 \\ 0 & 0 \end{bmatrix} \succeq 0
S^T K^T \left(H_{11} - H_{12} H_{22}^{-1} H_{12}^T \right) K S - T^T H T + T^T C T \succeq 0 \Rightarrow \\ S^T \left(X_{11} - X_{12} X_{22}^{-1} X_{12}^T \right) S - X + T^T C T \succeq 0

Selecting the new variable V as V = K^T W K , we construct two SDPs as follows.

First SDP:

\begin{aligned} & \max_{H, W} \operatorname{trace}(W) \\ & \quad \text{subject to:} \\ & \quad H - \begin{bmatrix} W & 0 \\ 0 & 0 \end{bmatrix} \succeq 0, \\ & \quad \begin{bmatrix} D^T H_{11} D - H + C & D^T H_{12}\\ H_{12}^T D & H_{22} \end{bmatrix} \succeq 0. \end{aligned}

Second SDP:

\begin{aligned} & \max_{X, V} \operatorname{trace}(V) \\ & \quad \text{subject to:} \\ & \quad X - \begin{bmatrix} V & 0 \\ 0 & 0 \end{bmatrix} \succeq 0, \\ & \quad \begin{bmatrix} S^T X_{11} S - X + T^T C T & S^T X_{12}\\ X_{12}^T S & X_{22} \end{bmatrix} \succeq 0. \end{aligned}

My Question:

Let H^* and W^* be the optimal solutions of the first SDP, and X^* and V^* the optimal solution of the second SDP.
We define Z^* as follows:

{Z^*} = T^{T} H^* T = \begin{bmatrix} {Z}_{11}^* & {Z}_{12}^* \\ ({Z}_{12}^*)^T & {Z}_{22}^* \end{bmatrix}

I seek to prove the following equalities:

  1. V^*= K^T W^* K
  2. ({X}_{22}^*)^{-1} \cdot ({X}_{12}^*)^T = ({Z}_{22}^*)^{-1} \cdot ({Z}_{12}^*)^T

note: Using Schur complement property, the equivalent of second LMIs substituted

My Attempt:

I have tested numerous examples with n \leq 6 and m \leq n using randomly generated K and D matrices, and in all cases, the equalities hold. However, I am uncertain how to establish a mathematical proof for these results.

2

This seems to be more of a math question than a CVX question. So this might not be the most appropriate venue for it.

3

You are right but because here are many experts I hope maybe someone can help me.

Do you have any suggestion where is it the best venue to ask this question?

4

Perhaps https://math.stackexchange.com , tagged with semidefinite-programming and optimization among others. if it doesn’t get an answer there after a few days, you could try https://mathoverflow.net/ , appropriately referencing your https://math.stackexchange.com post, although there is always a risk it can be downvoted and closed there if deemed too trivial as not being research-level…

You could instead try https://or.stackexchange.com/ . I don’t know which is best.

5

Thank you very much.

I have tried it before at:

I would also try https://or.stackexchange.com.

But I also hope to get help from experts here.