In example 3.4 of Boyd & Vandenberghe's Convex Optimization, function $f : \mathbb{R}^n \times \mathbb{S}^n \to \mathbb{R}$, defined as $$f(x, Y) := x^T Y^{-1}x$$ is convex on $\mathrm{dom} f = \mathbb{R}^n \times \mathbb{S}_{++}^n$, where $\mathbb{S}$ denotes the space of symmetric matrices and $\mathbb{S_{++}}$ denotes the space of positive definite matrices. It then shows $f$'s convexity via epigraph.
$$\text{epi} f = \left\{(x, Y, t) \mid Y \succ 0 , x^T Y^{-1} x \leq t \right\} = \left\{(x, Y, t) \mid \begin{pmatrix} Y & x \\
x^T & t \end{pmatrix} \succeq 0, Y \succ 0 \right\}$$
and says "the last condition is a linear matrix inequality in $(x, Y, t)$, and therefore $\text{epi} f$ is convex".
I'm confused about the quoted line.
-
Why is it an LMI? I would think $x^T a + b^T Y b + c \cdot d < e$ is a LMI, but here there are multiplications between $x$ and $Y$, why it's still a LMI in $(x, Y, t)$?
-
Why does being an LMI leads to convexity? In example 2.10 of Boyd & Vandenberghe's book, it's the solution set of a linear matrix inequality is convex, but here it's not the solution set.
Best Answer
We can think of the condition $$\begin{bmatrix}Y & x \\ x^{\mathsf T} & t\end{bmatrix} \succeq 0$$ as the intersection of infinitely many inequalities in $Y, x, t$: the inequalities $$u^{\mathsf T}\begin{bmatrix}Y & x \\ x^{\mathsf T} & t\end{bmatrix} u \ge 0$$ for all $u \in \mathbb R^{n+1}$.
These are, individually, linear inequalities in $Y,x,t$, and therefore each one defines a closed half-space; the intersection of arbitrarily many half-spaces is convex.
It is for the same reason that the condition $Y \succ 0$ defines a convex set $\mathbb{S}^n_{++}$.