Relation between two linear matrix inequality (LMI) problems 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.
 A: 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.
A: 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$.
A: 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$.
