About the use of Schur's complement. Why they are equivalent?

203 Views Asked by At

$$y^{\top}Qy+y^{\top}q+r\geq -ay^{\top}x-b, \qquad \forall y \in \mathbb R^{n}$$

where $Q \succeq 0$. One can use Schur's complement to replace it by an equivalent linear matrix inequality (LMI).

$$\pmatrix{Q&q/2+ax/2\\ q^{\top}/2+ax^{\top}/2& r+b\geq 0} \succeq 0$$

1

There are 1 best solutions below

3
On BEST ANSWER

There is no Schur complement involved. The idea is to use the vector $\pmatrix{y\\1}$ instead of $y$. Then it is easy to check that your first inequality is equivalent to $$ \pmatrix{y\\1}^T\pmatrix{Q & \frac12(q+ax)\\ \frac12(q+ax)& r+b} \pmatrix{y\\1}\ge0 \quad \forall y. $$ By scaling, we can replace the vector $\pmatrix{y\\1}$ by any vector $\pmatrix{y\\z}$ with $z\ne0$.

To prove semi-definiteness of the full matrix, we need to check this only for vectors of the form $\pmatrix{y\\0}$. By the considerations above, we have $$ \pmatrix{y\\\frac1k}^T\pmatrix{Q & \frac12(q+ax)\\ \frac12(q+ax)& r+b} \pmatrix{y\\ \frac1k}\ge0 \quad \forall y, k\in \mathbb N. $$ Letting $k\to\infty$, gives $$ \pmatrix{y\\0}^T\pmatrix{Q & \frac12(q+ax)\\ \frac12(q+ax)& r+b} \pmatrix{y\\ 0}\ge0 \quad \forall y, $$ and the matrix in question is positive semi-definite.