convex optimization of an inequality

66 Views Asked by At

The motivation for this question is a relaxation of the well-known Riccati equation that will be introduced as a constraint in a convex optimization.

The variable is $P\succeq0$, and the constraint is \begin{align} P \succeq APA^T + Q - FPH^T(HPH^T+R)^{-1}HPF^T \end{align} where $R,Q\succ0$ and $A,F,H$ are arbitrary matrices.

We can organize the inequality as follows: \begin{align} P -APA^T - Q + FPH^T(HPH^T+R)^{-1}HPF^T\succeq 0 \end{align} However, it is not possible to "linearize" it using the Schur complement since $HPH^T+R\succ0$.

Any ideas are welcomed.

The standard approach fails: In order to represent the non-linear inequality, we can note that its LHS corresponds to the Schur complement of the matrix \begin{align} \begin{pmatrix} P -APA^T - Q & FPH^T\\ HPF^T& - (HPH^T+R) \end{pmatrix} \end{align} This matrix is neither positive or negative definite since $- (HPH^T+R)$ is negative definite while the Schur complement is positive.

1

There are 1 best solutions below

5
On

Let us start with the Riccati equation

$$\begin{align} APA^T-P + Q - FPH^T(HPH^T+R)^{-1}HPF^T=0. \end{align}$$

We can now relax this expression as

$$\begin{align} APA^T-P + Q - FPH^T(HPH^T+R)^{-1}HPF^T\succeq0. \end{align}$$

which is clearly equivalent to the LMI

$$\begin{align} \begin{bmatrix} APA^T-P + Q & FPH^T\\HPF^T & HPH^T+R \end{bmatrix} \succeq0 \end{align}$$ by virtue of the Schur complement.

Now consider the optimization problem

$$\begin{align} \max_{P\succeq0}\mathrm{trace}(P)\ \mathrm{such\ that} \begin{bmatrix} APA^T-P + Q & FPH^T\\HPF^T & HPH^T+R \end{bmatrix} \succeq0. \end{align}$$

It can be shown that the optimal solution $P^*$ satisfies $$\begin{align} AP^*A^T-P^* + Q - FP^*H^T(HP^*H^T+R)^{-1}HP^*F^T=0. \end{align}$$

I am looking for a suitable reference. In the meantime, you can numerically verify that this is indeed the case.