Can this problem be reduced to solving an LMI?

Question

Let $A \in \mathbb{R}^{n\times n}$ and $B \in \mathbb{R}^{n\times m}$. We want to choose an $X \in \mathbb{R}^{m\times n}$ such that the following matrix

$$ M(X) := \begin{bmatrix} A & - B X A\\ I_n & 0_{n\times n} \end{bmatrix} $$

is Schur stable (i.e., all eigenvalues of $M(X)$ have magnitudes less than $1$). Can it be solved by using linear matrix inequalities (LMIs)?

Answer 1

The matrix $M(X)$ is Schur stable if and only if there exists a symmetric positive definite matrix $P$ such that $M(X)^TPM(X)-P\prec0$ for some choice for $X$; i.e. it is negative definite for some choice for $X$. This is clearly a nonlinear inequality in the variables $P$ and $X$.

In fact, this is an instance of the static-output feedback problem, many instances of which are known to be NP-Hard. In this regard, unless is some very specific scenarios in which the structure of the problem can be exploited, this problem cannot be equivalent reformulated an LMI problem. However, this problem can be solved by solving a sequence of LMI problems iteratively. This problem has been very well studied due to its importance.

If we rewrite $M(X)=\bar A+\bar BX\bar C$, then the inequality $M(X)^TPM(X)-P\prec0$ can equivalently reformulated as

$$N_C^TA^TPAN_C-P\prec0,\ N_B^TAQA^TN_B-Q\prec0,\ PQ=I$$

where $N_B$ is a basis of the null-space of $\bar B^T$ and $N_C$ is a basis of the null-space of $\bar C$. Due to the constraint $PQ=I$, this problem is not convex.

One way to solve that is through the use of the Cone Complementary Algorithm introduced by Laurent El Ghaoui, Francois Oustry, and Mustapha AitRami in the paper "A Cone Complementarity Linearization Algorithm for Static Output-Feedback and Related Problems".

Algorithm:

1. Find a feasible point $(P_0,Q_0$. If there are none, exit. Set $k = 0$.
2. Set $V_k = S_k$, $W_k = Q_k$; and find $X_{k+1}$, $Q_{k+1}$ that solve the LMI problem

$$\mathrm{minimize\ Trace}(V_kP + W_kQ)\ \mathrm{subject\ to}\\ N_C^TA^TPAN_C-P\prec0,\\ N_B^TAQA^TN_B-Q\prec0,\\ \begin{bmatrix}P & I\\I & Q\end{bmatrix}\succeq0,\ P,Q\succ0$$

3. If a stopping criterion is satisfied, exit. Otherwise, set $k = k+1$ and go to Step 2.

It has been proven that the sequence of optimums converge to some values. Optimality holds whenever the minimum is equal to $2n$.

Once the algorithm has converged to a solution for $P$ and $Q$ that satisfies the initial nonlinear program, one can just simply substitute for $P$ in it and solve the LMI problem $$ \begin{bmatrix} -P & M(X)^TP\\ PM(X) & -P \end{bmatrix}\prec0 $$

in the variable $X$.