跳转至

球与锥

在本节中,我们介绍欧几里得球(Euclidean Ball)、椭球(Ellipsoid)与锥(cone)。

在上一节,我们首先复习了直线和线段的定义。本节,让我们从锥开始。

欧几里得球与椭球#

欧几里得球

一个\mathbb{R}^n上的欧几里得球满足如下形式:B(x_c, r) = \{x \mid \Vert x - x_c \Vert_2 \leq r\} = \{x \mid (x - x_c)^T(x - x_c) \leq r^2\} \ s.t. \ r \in \mathbb{R}_+

在上式中,x_c圆心r半径B(x_c, r)包括以x_c为中心,距离为r内的所有点。欧几里得球还常被表示为B(x_c, r) = \{x_c + ru \mid \Vert u \Vert_2 \leq 1\}

试证明欧几里得球是一个凸集

对于欧几里得球B(x_c, r)及其中两点x_1, x_2 \in B,我们有\Vert x_1 - x_c \Vert_2 \leq r\Vert x_2 - x_c \Vert_2 \leq r0 \leq \ \leq 1,那么

\begin{align} \Vert \theta x_1 + (1 - \theta) x_2 - x_c \Vert_2 &= \Vert \theta (x_1 - x_c) + (1 - \theta) (x_2 - x_c) \Vert_2 \\ &= \theta \Vert x_1 - x_c \Vert_2 + (1 - \theta) \Vert x_2 - x_c \Vert_2 \\ &= r \end{align}

一个更一般的球被称为椭球(ellipsoid)。

椭球

\epsilon = \{x \mid (x - x_c)^TP^{-1}(x - x_c) \leq 1\}

x_c \in \mathbb{R}^n是椭球\epsilon球心P \in \mathbb{S}^n_{++}是一个对称的正定矩阵,它决定了椭球在每个方向从球心x_c伸张的长度。椭球\epsilon的半轴的长度由\sqrt{\lambda_i}给出,其中\lambda_iP的特征值。我们很容易发现欧几里得球是椭球的一个特殊情况–当P为一个单位矩阵时。

(x - x_c)^TP^{-1}(x - x_c)实际上是x - x_c的p-范数,因此上式有时也写作\epsilon = \{x \mid \Vert x - x_c \Vert_p \leq 1\}

椭球还常被表达为\epsilon = \{x_c + Au \mid \Vert u \Vert_2 \leq 1\},其中A是一个非奇异方阵,u是一个单位球。也就是说我们通过方阵A旋转、拉伸这个单位球,最后再加上偏移量x_c得到椭球。在这个表达中我们可以假设A是对称、正定的。A = P^{1/2}时本式与上式相同。如果A是对称正定的奇异方阵,那么这个集合被称作退化椭球(degenerate ellipsoid),它的仿射维度等于A的秩。退化椭球与椭球都是凸的。

#

锥组合(conic combination)

空间\mathbb{R}^n中的点x \in \mathbb{R}如果满足

x = \sum_{i=1}^n \theta_i x_i \ s.t. \ \forall \theta_i, \theta_i \geq 0

则我们将其成为锥组合(非负线性组合)。

锥集(conic set)

对于集合C,如果其中每一点x \in C并且

\theta \geq 0$,都有$\theta x \in C

那么我们将这个集合C称作一个锥(非负齐次)。

锥包(conic hull)

集合S的锥包是所有该集合的点的锥组合所构成的集合,也即

\{\sum_{i=1}^k \theta_i x_i \mid x_i \in S, \theta_i \geq 0\}

半正定锥#

对称矩阵

\mathbb{S}^n = \{X \in \mathbb{R}^{n \times n} \mid X = X^T\}

对称半正定矩阵

\mathbb{S}^n_+ = \{X \in \mathbb{S}^n \mid X \succeq 0\}

对称正定矩阵

\mathbb{S}^n_{+ +} = \{X \in \mathbb{S}^n \mid X \succ 0\}
试证明\mathbb{S}^n_+是一个凸锥

如果\theta_1, \theta_2 \in \mathbb{R}_+A, B \in \mathbb{S}^n_+,那么\theta_1 A + \theta_2 B \in \mathbb{S}^n_+

范式球与范式锥#

对于\mathbb{R}^n中的任意范数\Vert \cdot \Vert,范式球和范式锥被定义为:

范式球

B(x_c, r) = \{x \mid \Vert x - x_c \Vert \leq r\}

范式锥

C(t) = \{(x, t) \mid \Vert x \Vert \leq t\} \subseteq \mathbb{R}^{n+1}

范式球和范式锥都是凸的。


最后更新: 2021-05-06 19:36:11

评论