# How to construct solutions for a set of polynomial matrix inequalities?

How can one find solutions to the set of (polynomial) matrix inequalities $$M \succ 0,\quad A_i^TMA_i \preceq c\cdot M,\quad\forall i=1,\dots,m$$ where $M=M^T\in\mathbb{R}^{n\times n}$ and $A_i \in\mathbb{R}^{n\times n}$ and $c\in(0,1)$ is a constant?

Remark: If the matrices $A_i$ are known and $c$ is fixed, the above conditions become LMIs and one can check if an appropriate $M$ can be found. The matrices $A_i$ do not have to be symmetric. As an example, given $$A_{1} = \begin{pmatrix} -0.2694 & 0.2820 \\ -0.3521 & -0.3555 \end{pmatrix},\quad A_{2} = \begin{pmatrix} -0.0853 & -0.2789\\ 0.1978 & -0.3814 \end{pmatrix}$$and $c=0.5$ one can find $$M = \begin{pmatrix} 2.9647 & -0.0338\\ -0.0338 & 3.0563 \end{pmatrix}$$ using YALMIP / SeDuMi.

However, I would actually like to optimize over parameters of the matrices $A_i$ according to a cost function, subject to the condition above (i.e. $M$ is not known and only any particular one needs to be found; $c=0.99$ can be taken initially). The number $m$ of matrices $A_i$ can be fixed a priori. I usually have $m\in\{3,4,5\}$ and $n=2$ or $n=6$. Currently, the optimization is done without the constraint above, which is checked afterwards.

Is there a way to optimize over $A_i$ and simultaneously make sure any $M$ exists such that the inequalities hold?

• It is not entirely clear what you want. Given $M$ and $c$, find $A_i$? – Johan Löfberg Mar 10 '15 at 16:04
• Dear Johan, thank you for the quick reply and for pointing this out. My bad! I reformulated and hope it became clearer. – orest Mar 10 '15 at 17:14
• So you essentially have a variant of a robust discrete-time control problem? – Johan Löfberg Mar 10 '15 at 21:21
• I guess you refer to the discrete-time Lyapunov equation $A^TPA-P+Q=0$ having a similar structure? In fact, according to Theorem 2 in a paper it is possible to reformulate the inequality to obtain $$\left( \begin{array}{cc} M_i & A_i^TG^T \\ GA_i & G+G^T-M_i\end{array} \right) \succeq 0$$ assuming $c=1$. This helps a bit, now it is a BMI. If the condition cannot be solved for some given $A_i$, how to get an idea how those $A_i$ need to be modified in order to fulfill the equations? Thank you sincerely for helping. – orest Mar 12 '15 at 15:47
• I refer to the case of finding K and $P$ such that $(E_i+B_iK)^TP(E_i+B_iK) \preceq cP$, which can be reformulated to a convex condition by congruence with $P^{-1}$, variable change $Q=P^{-1}$ and $Y = KP^{-1}$, and a Schur complement. Essentially everything else is intractable (although there are some solvable cases) – Johan Löfberg Mar 12 '15 at 16:03