2
$\begingroup$

I am confused regarding the Schur complement. From Boyd and Vandenberghe's Convex Optimization,

Suppose $X \in S^n_{++}$ partitioned as $$X = \begin{bmatrix} A & B\\ B^T & C\\ \end{bmatrix}$$ where $A \in S^k$. The Schur complement of $X$ (with respect to $A$) is $S=C-B^TA^{-1}B$. Show that the Schur complement, viewed as function from $S^n$ into $S^{n-k}$, is matrix concave on $S^n_{++}$.


I believe the goal is to show that $y^TSy\leq0$, where $y\in\mathbb{R}^{n-k}$. So, I follow a similar argument as given in the book (i.e., Example 3.4). I define $h(y,S)=y^TSy$. Then, I think we should consider the hypograph? That is, if the hypograph of $h$ is convex set, then $h$ is concave. Following this idea, I have the following:

$$\begin{align} \mathbf{hypo}\, h &= \left\{ (y,S,t) \mid y^TSy\geq t \right\} \\ &= \left\{ (y,S,t) \mid \begin{bmatrix} S & y \\ y^T & t \end{bmatrix} \leq 0 \right\} \end{align}$$

Since the last line can be expressed as a linear matrix inequality (LMI) of $(y,S,t)$, the hypo of $h$ is a convex set. This implies that $S$ is matrix concave? But I can also consider the epigraph isn't it? Then, I'll get a similar LMI with a different inequality. So, does that means it is both convex and concave? Moreover, if $X \in S^n_{++}$, it also implies that $A$ and $S$ is positive definite? Do they play role here? I'm very confused.

$\endgroup$
1
  • $\begingroup$ Which question is that? Which number? $\endgroup$ Commented May 21, 2023 at 9:13

1 Answer 1

5
$\begingroup$

You want to show matrix concavity: $$ S(\theta X_1 + (1-\theta) X_2) \succeq \theta S(X_1) + (1-\theta) S(X_2), \ \ \forall \theta \in [0,1], X_1, X_2 \in S^n_{++} $$ This is equivalent to showing that the matrix hypograph is a convex set: $$ \mathbf{hypo}\ S: =\{ (X,T) \ | \ S(X) \succeq T, \ X \in S^n_{++}, \ T \in S^{n-k} \} $$ But then we can use properties of the Schur Complement to show for positive definite $X$ we have: $$ \ S(X) = C - B^T A^{-1} B \succeq T \Leftrightarrow \begin{bmatrix} A & B\\ B^T & C- T \end{bmatrix} \succeq 0\Leftrightarrow \ X - \begin{bmatrix} 0 & 0\\ 0 & T \end{bmatrix} \succeq 0 $$ So let $L$ be the linear map $S^n \times S^{n-k} \rightarrow S^n$: $$ L(X,T) := X - \begin{bmatrix} 0 & 0\\ 0 & T \end{bmatrix} $$ We conclude: $$ \mathbf{hypo}\ S =\{ (X,T) \ | \ L(X,T) \in S^n_{+}, \ X \in S^n_{++}, \ T \in S^{n-k} \} $$ So then we can conclude the hypograph is a convex set because the semidefinite cone is.

$\endgroup$
3
  • $\begingroup$ I wish to verify something. So, in the last line, we have $$X\geq\Bigg[\begin{matrix} 0 & 0\\ 0 & T\\ \end{matrix}\Bigg]$$ I suppose the value of T is not important right? Because X is positive definite, so that is suffice to show it is a convex set. $\endgroup$
    – M.A.N
    Commented Dec 15, 2020 at 14:53
  • $\begingroup$ Sorry, a bit blur. I don't understand why that inequality is satisfied. $\endgroup$
    – M.A.N
    Commented Dec 15, 2020 at 15:01
  • $\begingroup$ I didn't go into details, but if you look up Schur complement, it's a standard result: en.wikipedia.org/wiki/Schur_complement $\endgroup$
    – p.s.
    Commented Dec 15, 2020 at 15:10

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .