Relation between two linear matrix inequality (LMI) problems

Question

The following $>, \geq$ signs are referred to positive definiteness.

Given an arbitrary matrix $A\in \mathbb{R}^{n\times n} $.

Problem 1: Find a matrix $P=P^\text{T}\in\mathbb{R}^{n\times n}$, $P>0$, such that $A^\text{T}P+PA<0$.

Problem 2: Find a matrix $Q=Q^\text{T}\in\mathbb{R}^{n\times n}$, $Q\geq0$, $Q\neq0$, such that $QA^\text{T}+AQ\geq0$.

Claim: Problem 1 is infeasible (no solution exists) if and only if Problem 2 is feasible.

My question is how to prove the claim?

I try to think of the problem from geometric point of view. $A^\text{T}P+PA<0$ defines a "half space". Problem 1 is infeasible if such half space does not intersect the positive definite cone ($P>0$). Yet $QA^\text{T}+AQ\geq0$ defines another half space whose relation to the previous one is something I cannot figure out. If somehow the second half space will intersect the positive definite cone, then the second problem is feasible.

This question is simplified from a statement without proof in the book LMI for System and Control Theory by Boyd et al, section 2.2. Thanks for any comment.

Answer 1

Update

Actually, the interpretation is given in 1st paragraph of section 2.2.1 and "Infeasibility criterion for LMIs" (page 29).

First, write out the LMI $$P > 0, \quad A^T P + PA < 0$$ in the form $F_0 + \sum_{i=1}^m x_iF_i > 0$. Let $P_1, P_2, \cdots, P_m$ be a basis for symmetric $n\times n$ matrices ($m = n(n+1)/2$). Let $F_0 = 0$. Let $$F_i = \left( \begin{array}{cc} P_i & 0 \\ 0 & -A^TP_i - P_iA \\ \end{array} \right), \quad i = 1, 2, \cdots, m. $$ See here for an example (1st page): http://users.isy.liu.se/rt/andersh/teaching/lmi.pdf

Second, from 1st paragraph of section 2.2.1 and "Infeasibility criterion for LMIs" (page 29), Problem 1 is infeasible if and only if there exists $0 \ne G \ge 0$ such that $\mathrm{Tr}(GF_i) = 0$ for $i = 1, 2, \cdots, m$ and $\mathrm{Tr}(GF_0)\le 0$. Let $$G = \left( \begin{array}{cc} G_{11} & G_{12} \\ G_{12}^T & G_{22}\\ \end{array} \right). $$ Note that $\mathrm{Tr}(GF_i) = \mathrm{Tr}(G_{11}P_i) + \mathrm{Tr}(G_{22}(-A^TP_i - P_iA)) = -\mathrm{Tr}((G_{22}A^T + AG_{22} - G_{11})P_i)$.
Thus, Problem 1 is infeasible if and only if there exists $0 \ne G \ge 0$ such that $\mathrm{Tr}((G_{22}A^T + AG_{22} - G_{11})P_i) = 0$, $\forall i$ or equivalently $G_{22}A^T + AG_{22} - G_{11} = 0$. Here we have used the fact that if $C$ is a symmetric matrix and $\mathrm{Tr}(CP_i) = 0, \forall i$, then $C = 0$ (the proof is easy). Also, $G_{22} = 0$ implies $G_{11} = 0$ and hence $G = 0$ (Contradiction). As a result, Problem 1 is infeasible if and only if Problem 2 is feasible.

Partial answer

Remark: For another part, I do not have a complete solution currently.

If Problem 2 is feasible, let us prove that Problem 1 is infeasible. Suppose that Problem 1 is feasible. Since $-A^TP - PA \succ 0$, we have $\mathrm{Tr}(Q(A^TP + PA)) = - \mathrm{Tr}(Q( - A^TP - PA )) < 0$. On the other hand, we have $\mathrm{Tr}(Q(A^TP + PA)) = \mathrm{Tr}((QA^T + AQ)P) \ge 0$. Contradiction.

Some facts are used:

Fact 1: If $B, C$ are both $n\times n$ matrices, then $\mathrm{Tr}(BC) = \mathrm{Tr}(CB)$.

Fact 2: If $X\succeq 0$ and $Y \succ 0$, then $\mathrm{Tr}(XY) \ge 0$.

Fact 3: If $0 \ne X \succeq 0$ and $Y \succ 0$, then $\mathrm{Tr}(XY) > 0$.

Answer 2

I guess this problem can be considered by duality.

First, let us consider the following optimization problem: \begin{equation} \tag{P} \begin{array}{cl} {\min_{t,P}} & {t,} \\ {\text{s.t.}} & {A^TP + PA - t I \preceq 0,} \\ {} & {P \succ 0.} \end{array} \end{equation} We denote the optima of (P) by $p^*$. And its corresponding Lagrangian function is \begin{equation} L(P,t;Q,Z)=t + \langle Q, A^TP + PA - t I \rangle - \langle Z, P \rangle. \end{equation} Now, the dual problem can be formulated \begin{equation} \tag{D} \begin{array}{cl} {\max_{Q,Z}} & {0} \\ {\text{s.t.}} & {QA^T+ AQ = Z} \\ {} & {Q \succeq 0} \\ {} & {Z \succeq 0} \end{array} \end{equation} Again, we denote the optima of (D) by $d^*$. Obviously, if (D) is feasible $d^*=0$, otherwise $d^* = -\infty$.

In addition, the slater condition shows that the strong duality can be held here, and thus $d^*=p^*$.

Next, let us try to prove the statement.

Forward direction.

If we can find $P \succ 0$ such that $A^T P + PA \prec 0$. Obviously the optima of (P) is negative, i.e., $p^* < 0$. Thus \begin{equation} d^* = p^* < 0. \end{equation} So the dual problem must be infeasible. In other words, we cannot find a positive semi-definite $Q$ such that $QA^T+AQ \succeq 0$.

Backward Direction If we cannot find $P \succ 0$ such that $A^T P + PA \prec 0$. Similarly we have $p^* \ge 0$. Thus \begin{equation} d^* = p^* \ge 0. \end{equation} So the optima of dual problem must be $0$. In other words, the dual problem is feasible and we must be able to find a positive semi-definite $Q$ such that $QA^T+AQ \succeq 0$.

Answer 3

It is well-known that problem 1 is feasible if and only if $A$ is Hurwitz, i.e. all eigenvalues of $A$ are in the left half plane. Similarly, one can show that problem 2 is feasible if and only if $A$ is not Hurwitz. $A$ cannot be Hurwitz and not Hurwitz at the same time, hence the result follows.

Proof of Second Claim. Assume that $A$ is not Hurwitz. Then there exist an eigenvalue of $A$ such that $\operatorname{Re}{\lambda} \geq 0$. Then $Q=Q^T=xx^T + yy^T\geq0$ is a solution where $A(x+iy)=\lambda (x+iy)$ since $QA^T+AQ=2(\operatorname{Re}{\lambda})Q\geq0$.

Now assume there exists a real nonzero $Q=Q^T\geq0$ such that $QA^T+AQ \geq 0$. For the sake of contradiction assume that $A$ is Hurwitz. Let $A^Tx=A^H x=\lambda x$ where $\operatorname{Re}{\lambda}<0$. So, $$x^H QA^H x+x^H AQ x = 2(\operatorname{Re}{\lambda}) x^H Q x \geq 0$$ which implies $Qx=0$ for any eigenvector of $A^T$ since $Q=Q^H$. Similarly, for any generalized eigenvector of $A^T$ such that $A^Ty=\lambda y+x$ it is easy to show that $Qy=0$. Since generalized eigenvectors of any matrix spans the whole space, $Q$ must be the trivial solution. Hence, $A$ is not Hurwitz.