3
$\begingroup$

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.

| cite | improve this question | | | | |
$\endgroup$
1
$\begingroup$

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$.

| cite | improve this answer | | | | |
$\endgroup$
  • $\begingroup$ It is a good answer. Though I do not know either how to prove the other direction, I think the direction you proved is more informative practically. That is to say, if we want to confirm that Problem 1 is infeasible, we can instead try to solve Problem 2, because showing the feasibility of a problem may be much easier than showing its infeasibility (by simply finding a feasible point). As for the other direction, even if we could show that Problem 2 is infeasible, such that we know Problem 1 is feasible, we still do not have an answer to Problem 1 except knowing its feasibility. $\endgroup$ – George C Mar 13 at 16:03
  • $\begingroup$ @GeorgeC I think that the interpretation is given in 1st paragraph of section 2.2.1 and "Infeasibility criterion for LMIs" (page 29). I updated my answer. Please check it. $\endgroup$ – River Li Mar 14 at 15:11
  • $\begingroup$ The answer is now complete. Thanks. I was stuck with the matrix form and did not try to rewrite it into the standard LMI form. The geometric interpretation was indeed inspired by page 29 of the book, albeit unsuccessful in the matrix form. $\endgroup$ – George C Mar 14 at 18:41
2
$\begingroup$

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.

| cite | improve this answer | | | | |
$\endgroup$
  • $\begingroup$ The intuition behind your answer is correct, but the details of the answer are not. Note that problem 2 is feasible when $A=\pmatrix{1&0\\ 0&-1}$ and $Q=\pmatrix{1&0\\ 0&0}$. $\endgroup$ – user1551 Mar 14 at 11:05
  • $\begingroup$ @user1551 You are right, I didn't think it through. Anyway I've updated my answer with a proof. Thanks for the feedback. $\endgroup$ – obareey Mar 14 at 14:56
  • $\begingroup$ It is also a very good answer (though I already accepted the answer by River Li). In addition, I was not aware that problem 2 is associated with the non-Hurwitzness of the matrix A. It is a very instructive answer certainly. $\endgroup$ – George C Mar 14 at 18:44
  • $\begingroup$ (+1)nice solution. $\endgroup$ – River Li Mar 15 at 0:39
1
$\begingroup$

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$.

| cite | improve this answer | | | | |
$\endgroup$
  • $\begingroup$ Very good solution in terms of convex optimization theory. $\endgroup$ – George C Mar 14 at 18:53
  • $\begingroup$ (+1)nice solution. $\endgroup$ – River Li Mar 15 at 0:39

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.