Help with SDP and Schur's Complement

Question

I'm trying so hard to understand SDP and how Schur's complement is used and what does it even mean? Is there a good and simple reference with some numerical examples that can answer my question especially that I'm not that great in linear algebra. I mean, what does Schur's complement even mean in words? I don't understand what does it do? Please help

Answer 1

The Schur complement, in a nutshell, is about breaking down the condition that a big matrix is positive into the "simpler" condition that two smaller matrices are positive.

Here's an examination of the Schur complement in the context of quadric surfaces. Suppose we are given an equation of the form $$ \sum_{i,j=1}^3 a_{ij} x_i x_j = 1. $$ Without loss of generality, we suppose that $a_{ij} = a_{ji}$. We want to determine whether the surface described by this equation is an ellipsoid. As it turns out, this happens exactly when the matrix $A$ (with entries $a_{ij}$) is positive definite. Note that our equation can also be written in the form $x^TAx = 1$.

---

As a warm-up, let's consider the $2$-dimensional version of the problem. When does the equation $$ a_{11}x_1^2 + 2a_{12} x_1x_2 + a_{22}x_2^2 = 1 $$ describe an ellipse? As before, this occurs when the matrix $A$ is positive definite, but let's try to see why this is the case. By Sylvester's criterion, $A$ will be positive definite if and only if $a_{11} > 0$ and $a_{11}a_{12} - a_{12}^2 > 0$. With this in mind, consider the quadratic function $$ f(t) = a_{11} t^2 + 2a_{12}t + a_{22}. $$ The fact that $a_{11} > 0$ tells us that the graph of this function is an upward-opening parabola. The fact that $a_{11}a_{12} - a_{12}^2 > 0$ tells us that this quadratic function does not have a real root, since its discriminant is given by $$ b^2 - 4ac = 4(a_{12}^2 - a_{11}a_{22}) < 0. $$ So, if we complete the square to rewrite $f(t)$ in "vertex form", then we should find that $$ f(t) = a_{11}(t - h)^2 + k $$ for some $k > 0$. Now, note that our original equation can be written in the form $$ x_{2}^2 \cdot f(x_1/x_2) = 1. $$ With our rewritten quadratic, this is now the equation $$ a_{11}(x_1 - hx_2)^2 + k x_2^2 = 1. $$ In other words, the positive definiteness of $A$ is important because it ensures that $x^TAx$ is a sum of squares.

Another way to think about the new equation is as follows. We made a substitution $$ \pmatrix{y_1\\y_2} = \pmatrix{1 & -h\\0 & 1} \pmatrix{x_1 \\ x_2} $$ such that the new equation was of the form $$ b_{11} y_1^2 + b_{22}y_2^2 $$ for some positive $b_{11},b_{22}$. To put this another way, we found that $$ P = \pmatrix{1 & -h\\0 & 1} \implies P^TAP = \pmatrix{b_{11} & 0\\0 & b_{22}}. $$

---

Now, is there some way that we can use our result for $2$-D space for $3$-D space? One idea is to make a substitution that gets us "halfway there". That is, perhaps we can find a $3 \times 3$ invertible matrix $P$ such that the substitution $$ \pmatrix{y_1\\y_2\\y_3} = P \pmatrix{x_1\\x_2\\x_3} $$ yields an equation of the form $$ b_{11}y_1^2 + (b_{22}y_2^2 + 2b_{23}y_2y_3 + b_{33}y_3^2) = 1. $$ From there, all we'd need to do is apply our approach from last time on the expression $b_{22}y_2^2 + 2b_{23}y_2y_3 + b_{33}y_3^2$. This is exactly what the Schur complement does for us! Partition $A$ into the matrices $$ A = \pmatrix{a_{11} & v\\ v^T & M}. $$

We know that there exists an invertible matrix $P$ such that $$ PAP^T = \pmatrix{a_{11} & 0\\0 & M - a_{11}^{-1} vv^T} = \pmatrix{b_{11} & 0 & 0\\0 & b_{22} & b_{23}\\0 & b_{23} & b_{33}}. $$ Correspondingly, making the substitution $y = Px$ leads to an equation in the form that we wanted, and now all that's left to do is check if $a_{11}$ is positive and the $2 \times 2$ matrix $\pmatrix{b_{22} & b_{23}\\ b_{23} & b_{33}}$ is positive definite.