Schur Complement Lemma

Proof: Recall that the matrix \(S\) is positive semi-definite if and only if \(x^TSx \ge0\) for any vector \(x\). Partitioning the vector \(x\) similarly to \(S\), as \(x=(y,z)\), we obtain that \(S\) is positive semi-definite if and only if

\[ \forall \: (z,y)  :  g(y,z) := \left( \begin{array}{c} y \\ z \end{array} \right)^T \left( \begin{array}{cc} A & B \\ B^T & C \end{array} \right) \left( \begin{array}{c} y \\ z \end{array} \right) \ge 0. \]

This is equivalent to: for every \(y\),

\[ 0 \ge f(y) := \min_{z} \: g(y,z) . \]

Since \(S\) is positive semi-definite, the corresponding quadratic function \(g\) is convex, jointly in its two arguments. Due to the partial minimization result, we obtain that the partial minimum \(f(y)\) is convex as well.

It is easy to obtain a closed-form expression for \(f\). We simply have to minimize the convex quadratic function \(g\) with respect to its second argument. Since the problem of minimizing \(g\) is not constrained, we just set the gradient of \(g\) with respect to \(z\) to zero (see here):

\[ \nabla_z g (y,z) = 2(Cz+B^Ty) = 0, \]

which leads to the (unique) optimizer \(z^\ast(y) := -C^{-1}B^Ty\). Plugging this value we obtain:

\[ f(y) = g(y,z^\ast(y)) = y^T(A-BC^{-1}B^T)y. \]

Since \(f\) is convex, its Hessian must be positive semi-definite. Hence \(A-BC^{-1}B^T \succeq 0\), as claimed.