常见的凸集

我们在 Affine set 和 convex set 的定义 一文中讲解了凸集（convex set）的概念。我们先来回顾一下凸集的定义：

如果连接集合 $C$ 当中的任何两点构成的线段也在集合 $C$ 之中，那么我们就说集合 $C$ 是一个 convex set。

或者我们用数学的语言来描述：

对于集合 $C$ 中的任何 $x_1,x_2$，对任意 $0\le \theta \le 1$，如果我们有 $\theta x_1+(1-\theta )x_2\in C$。我们就说这个集合是一个凸集合 （convex set）。

一些常见的是凸集的集合可以总结如下：

1. 空集 $\varnothing$。
2. 只有一个元素的集合 { x 0 } \{x_0\} {x0​}。
3. 整个 ${\mathbb{R}}^n$ 空间。
4. 任意直线。
5. 任意线段。
6. ${\mathbb{R}}^n$ 中的任意线性空间。

上述的6个例子都是较为明显的凸集合的例子。在本文中我们将要重点看另外一个常见的例子，椭圆（ellipsoid）。

我们容易想象到，如果连接椭圆中的任意两点，那么得到的线段也将在椭圆中，所以椭圆自然是一个凸集合。

但是我们怎么从数学上严格得证明椭圆是一个凸集合呢？这就是本文将要讨论的问题。

椭圆是凸集的证明

从定义上证明椭圆是一个凸集合

我们先来看椭圆集合的数学定义。我们用集合

E = { x ∣ ( x − x c ) T P − 1 ( x − x c ) ≤ 1 } \mathscr{E} =\{x \vert (x - x_c)^T P^{-1} (x - x_c) \leq 1 \} E={x∣(x−xc​)TP−1(x−xc​)≤1}

表示椭圆。其中 $P$ 是一个对称正定的矩阵。通常我们用 $P\succ 0$ 表示矩阵 $P$ 是正定的。 $x_c\in {\mathbb{R}}^n$ 称为椭圆的中心。

下面我们从定义上去证明 $\mathcal{E}$ 这个集合是凸集合。

对于 $\forall x,y\in \mathcal{E}$，以及任意 $0\le \theta \le 1$，我们想要证明 $\theta x+(1-\theta )y$ 也属于集合 $\mathcal{E}$。

因为 $x,y\in \mathcal{E}$，所以我们有
$$\begin{gathered} (x-x_c{)}^T{P}^{-1}(x-x_c)\le 1, \\ (y-x_c{)}^T{P}^{-1}(y-x_c)\le 1 \end{gathered}$$.

我们希望证明
$(\theta x+(1-\theta )y-x_c{)}^T{P}^{-1}(\theta x+(1-\theta )y-x_c)\le 1(\ast )$

我们把 $(\ast )$ 式的左边展开，我们可以得到
$$\begin{array}{rl}\text{LHS}=& {\theta }^2(x-x_c{)}^T{P}^{-1}(x-x_c)+\\ & (1-\theta {)}^2(y-x_c{)}^T{P}^{-1}(y-x_c)+\\ & (1-\theta )\theta (y-x_c{)}^T{P}^{-1}(x-x_c)+\\ & \theta (1-\theta )(x-x_c{)}^T{P}^{-1}(y-x_c)\\ \le & {\theta }^2+(1-\theta {)}^2+2\theta (1-\theta )(x-x_c{)}^T{P}^{-1}(y-x_c)\end{array}$$.

这里我们应用了 $P^{-1}={\left(P^{-1}\right)}^T$，并且 $(y-x_c{)}^T{P}^{-1}(x-x_c)=(x-x_c{)}^T{P}^{-1}(y-x_c)$。

所以为了证明 $\text{LHS}\le 1$，我们只须要证明 $(y-x_c{)}^T{P}^{-1}(x-x_c)\le 1$ 即可。

因为 $P\succ 0$ 并且 $P$ 是对称的，我们有 $P^{-1}$ 也是正定对称的。

那么，怎么证明 $P^{-1}$ 也是正定对称的呢？

首先，因为 $P$ 是对称的，所以 $P^{-1}$ 也是对称的。下面我们去证明 $P^{-1}$ 是正定的，即对于 $\forall x\in {\mathbb{R}}^n$ 且 $x\ne 0$，我们须要证明 $x^T{P}^{-1}x>0$。因为 $P$ 是可逆的，所以对于 $x$，我们能找到一个向量 $y\in {\mathbb{R}}^n$，使得 $x=Py$。因为 $x\ne 0$，所以 $y\ne 0$。 于是，$x^T{P}^{-1}x=y^T{P}^T{P}^{-1}Py=y^{T}Py>0$。从而 $P^{-1}$ 也是正定的。

证明了 $P^{-1}$ 是正定的，我们可以把 $P^{-1}$ 写成 $P^{-1}=U\Lambda U^T$，其中 $U$ 是正交化（orthogonal）矩阵，即 $U^{T}U=I$。$\Lambda$ 是一个对角矩阵，且对角线的元素均大于 0。 从而我们可以定义 $(P^{-1}{)}^{1/2}=U{\Lambda }^{1/2}{U}^T$。

现在我们来看 $(y-x_c{)}^T{P}^{-1}(x-x_c)$，
$(y-x_c{)}^T{P}^{-1}(x-x_c)=(y-x_c{)}^T(P^{-1}{)}^{1/2}(P^{-1}{)}^{1/2}(x-x_c)$。

根据 Cauch-Schwartz 不等式，$$||xy|{|}^2\le ||x|{|}^2||y|{|}^2$$

我们有，$$\begin{gathered} \left|\right|\left[(y-x_c{)}^T(P^{-1}{)}^{1/2}\right]\left[(P^{-1}{)}^{1/2}(x-x_c)\right]|{|}^2 \\ \le ||(P^{-1}{)}^{1/2}(y-x_c)|{|}^2\cdot ||(P^{-1}{)}^{1/2}(x-x_c)|{|}^2 \\ \le 1\cdot 1=1 \end{gathered}$$

其中最后一个不等式来自于 $x,y\in \mathcal{E}$，即
$$\begin{gathered} (x-x_c{)}^T{P}^{-1}(x-x_c)\le 1, \\ (y-x_c{)}^T{P}^{-1}(y-x_c)\le 1 \end{gathered}$$.

这样我们就证明了对任意 $0\le \theta \le 1$，$\theta x+(1-\theta )y$ 也属于集合 $\mathcal{E}$。

于是，我们就从数学上证明了椭圆集合是一个凸集合。

从 norm 的角度去看 ellipsoid

下面，我们来看如何从 norm 的角度去看椭圆。

如果 || $\cdot$ || 是 ${\mathbb{R}}^n$ 上的一个 norm，那么对应于 || $\cdot$ || 的 norm ball 定义为集合 { x ∣ ∣ ∣ x − x c ∣ ∣ < = r } \{x \vert \hspace{2mm} ||x - x_c|| <= r \} {x∣∣∣x−xc​∣∣<=r}。其中 $x_c$ 称为 norm ball 的中心，$r$ 称为 norm ball 的半径。

我们可以证明 norm ball 是一个凸集合。

对于不熟悉 norm 定义的读者，我们先来快速回顾一下 norm 的定义。
如果 $||\cdot ||$ 满足下面三个性质，那么 $||\cdot ||$ 就称为 norm。

1. 对于任意的 $x\in {\mathbb{R}}^n$，$||x||\ge 0$, $||x||=0$ 当且仅当 $x=0$.
2. $||cx||=c\cdot ||x||$，对于任意 $c\in R,c>0$.
3. 三角不等式，即 $||x+y||\le ||x||+||y||$.

于是，对于 norm ball， 即集合 C = { x ∣ ∣ ∣ x − x c ∣ ∣ < = r } C = \{x \vert \hspace{2mm} ||x - x_c|| <= r \} C={x∣∣∣x−xc​∣∣<=r}，如果有 $x,y\in C$，以及 $0\le \theta \le 1$，那么
$$\begin{array}{rl}||\theta x+(1-\theta )y-x_c||& =||\theta (x-x_c)+\\ & (1-\theta )(y-x_c)||\\ & \le ||\theta (x-x_c)||+||(1-\theta )(y-x_c)||\\ & \le \theta r+(1-\theta )r=r\end{array}$$

从而 $\theta x+(1-\theta )y$ 也属于集合 $C$。即 $C$ 是一个 convex set。

为了从 norm 的角度去看椭圆这个集合，我们先来看 Mahalanobis norm。

Mahalanobis norm

我们定义 Mahalanobis norm 为 $||x|{|}_p=\sqrt{x^{T}Px}$。其中 $x\in {\mathbb{R}}^n$，$P$ 是对称的，且$P\succ 0$，即 $P$ 是对称正定的。

我们先证明 Mahalanobis norm 是一个 norm。

1. 如果 $||x|{|}_p=0$，那么 $x^{T}Px=0$。而根据 $P\succ 0$，当 $x^{T}Px=0$ 时，我们有 $x=0$.
2. 对于任意 $c\in R,c>0$，$||cx|{|}_p=c\sqrt{x^{T}Px}=c||x|{|}_p$。
3. 三角不等式。根据 Mahalanobis norm 的定义，我们有 $||x+y|{|}_p^2=(x+y{)}^{T}P(x+y)=x^{T}Px+y^{T}Py+x^{T}Py+y^{T}Px=x^{T}Px+y^{T}Py+2x^{T}Py$. 因为 $P$ 是对称且正定的，所以我们可以将 $P$ 写成 $P=U\Lambda U^T$. 其中 $U$ 是正交化矩阵，即 $U^{T}U=I$，$\Lambda$ 是对角矩阵，对角线上的元素都是正的。类似于之前的讨论，我们可以定义 $P^{1/2}=U{\Lambda }^{1/2}{U}^T$. 从而，
   $$\begin{array}{rl}||x+y|{|}_p^2& =||x|{|}_p^2+||y|{|}_p^2+2x^T{P}^{1/2}{P}^{1/2}y\\ & \le ||x|{|}_p^2+||y|{|}_p^2+2|x^T{P}^{1/2}{P}^{1/2}y|\\ & \le ||x|{|}_p^2+||y|{|}_p^2+2||P^{1/2}x|{|}_2\cdot ||P^{1/2}y|{|}_2\\ & =||x|{|}_p^2+||y|{|}_p^2+2||x|{|}_p\cdot ||y|{|}_p\end{array}$$
   所以三角不等式成立。
   这里倒数第二步的不等式用到了 Cauch-Schwartz 定理。

我们证明了 Mahalanobis norm 确实是一个 norm。那么它与椭圆有什么关系呢？

椭圆是一个 norm ball

实际上，椭圆就是在 Mahalanobis norm 下的一个 norm ball。因为在 Mahalanobis norm 下，一个 norm ball 就定义为：

C = { x ∣ ∣ ∣ x − x c ∣ ∣ p ≤ r } C = \{x \vert \hspace{2mm} ||x - x_c||_p \leq r \} C={x∣∣∣x−xc​∣∣p​≤r} ，

即 C = { x ∣ ( x − x c ) T P ( x − x c ) ≤ r } C = \{x \vert \hspace{2mm} \sqrt{(x - x_c)^T P (x - x_c) } \leq r \} C={x∣(x−xc​)TP(x−xc​) ​≤r}。

取 $r=1$，我们就得到了椭圆的定义。所以，椭圆就是在 Mahalanobis norm 下的一个 norm ball。而我们之前证明了 Mahalanobis norm 是一个 norm，并且任意 norm 上的 norm ball 都是一个凸集合。自然得，椭圆也是凸集合。

从仿射的角度看椭圆

参考文献

Convex optimization, Chapter 1, Stephen Boyd, Lieven Vandenberghe, Cambridge University Press, (2004)