EE364A Lecture 1 and Lecture 2

课程主页：https://see.stanford.edu/Course/EE364A

最近开始学习凸优化，公开课为斯坦福的凸优化公开课，主页如下。这次回顾凸优化第一第二讲，这部分介绍了凸集的概念。

Lecture 1 Introduction

主要介绍凸优化的历史和应用，这里从略。

Lecture 2 Convex sets

仿射集

穿过$x_1,x_2$的直线可以表示为

$$x=\theta x_{1}+(1-\theta) x_{2} \quad(\theta \in \mathbf{R})$$

仿射集：包含过集合中任意两点的直线的集合。

例子：

$$\{x | A x=b\}$$

凸集

过$x_1, x_2$的线段可以表示为

$$x=\theta x_{1}+(1-\theta) x_{2}$$

其中$0\le \theta \le 1$

凸集：包含过集合中任意两点的线段的集合，即

$$x_{1}, x_{2} \in C, \quad 0 \leq \theta \leq 1 \quad \Longrightarrow \quad \theta x_{1}+(1-\theta) x_{2} \in C$$

凸组合和凸壳

$x_{1}, \ldots, x_{k}$的凸组合：

$$x=\theta_{1} x_{1}+\theta_{2} x_{2}+\cdots+\theta_{k} x_{k}$$

其中

$$\theta_{1}+\cdots+\theta_{k}=1, \theta_{i} \geq 0$$

凸壳$\operatorname{conv} S$：包含集合中所有点的凸组合的集合，例如

凸锥

$x_1, x_2$的锥（非负）组合：

$$x=\theta_{1} x_{1}+\theta_{2} x_{2}$$

其中$\theta_{1} \geq 0, \theta_{2} \geq 0$

凸锥：包含集合中所有点的锥组合的集合

超平面和半平面

超平面：$\left\{x | a^{T} x=b\right\}(a \neq 0)$

半平面：$\left\{x | a^{T} x \leq b\right\}(a \neq 0)$

其中

• $a$是单位向量
• 超平面是仿射和凸的；半平面是凸的

欧式球和椭球

中心为$x_c$，半径为$r$的欧式球：

$$B\left(x_{c}, r\right)=\left\{x |\left\|x-x_{c}\right\|_{2} \leq r\right\}=\left\{x_{c}+r u |\|u\|_{2} \leq 1\right\}$$

椭球：

$$\left\{x |\left(x-x_{c}\right)^{T} P^{-1}\left(x-x_{c}\right) \leq 1\right\}$$

其中$P \in \mathbf{S}_{++}^{n}$（$P$为对称正定矩阵）。

另一种表示为：$\left\{x_{c}+A u ||u|_{2} \leq 1\right\}$，其中$A$为非奇异方阵。

范数球和范数锥

中心为$x_c$，半径为$r$的范数球：

$$\left\{x |\left\|x-x_{c}\right\| \leq r\right\}$$

范数锥：

$$\{(x, t) |\|x\| \leq t\}$$

多面体

多面体为有限多个线性不等式和方程组的交集

$$A x \preceq b, \quad C x=d$$

其中$A \in \mathbf{R}^{m \times n}, C \in \mathbf{R}^{p \times n}, \preceq$为元素不等号。

不难看出多面体为有限多个半平面和超平面的交集。

正定对称锥

记号：

• $\mathbf{S}^{n}$为$n\times n$对称矩阵

• $\mathbf{S}_{+}^{n}=\left\{X \in \mathbf{S}^{n} | X \succeq 0\right\}$：对称半正定$n\times n$矩阵

  $$X \in \mathbf{S}_{+}^{n} \Longleftrightarrow z^{T} X z \geq 0 \text { for all } z$$

  $\mathbf{S}_{+}^{n}$为凸锥

• $\mathbf{S}_{++}^{n}=\left\{X \in \mathbf{S}^{n} | X \succ 0\right\}$：对称半正定$n\times n$矩阵

保凸运算

有些运算可以保持集合的凸性：

• 交集
• 仿射函数
• 透视函数
• 线性分式函数

交集

凸集的交集为凸集。

仿射函数

$f : \mathbf{R}^{n} \rightarrow \mathbf{R}^{m}$为仿射函数，如果$f(x)=A x+b,A \in \mathbf{R}^{m \times n}, b \in \mathbf{R}^{n}$

• 凸集在$f$下的像为凸集

  $$S \subseteq \mathrm{R}^{n} \text { convex } \quad \Longrightarrow \quad f(S)=\{f(x) | x \in S\}$$

• 凸集的原像$f^{-1}(C)$为凸集

  $$C \subseteq \mathrm{R}^{m} \text { convex } \Longrightarrow \quad f^{-1}(C)=\left\{x \in \mathrm{R}^{n} | f(x) \in C\right\}$$

透视函数和线性分式函数

透视函数：$P : \mathbf{R}^{n+1} \rightarrow \mathbf{R}^{n}$，其中

$$P(x, t)=x / t, \quad \operatorname{dom} P=\{(x, t) | t>0\}$$

凸集在透视函数下的像以及原像都是凸集。

线性分式函数：$f : \mathbf{R}^{n} \rightarrow \mathbf{R}^{m}$

$$f(x)=\frac{A x+b}{c^{T} x+d}, \quad \text { dom } f=\left\{x | c^{T} x+d>0\right\}$$

凸集在线性分式函数下的像以及原像都是凸集。

广义不等式

凸锥$K \subseteq \mathrm{R}^{n}$是正规锥，如果

• $K$是闭集（包含其边界）
• $K$是实的（具有非空内部）
• $K$是尖的（不包含直线，即$x \in K,-x \in K \Longrightarrow x=0$）

正规锥$K$定义的广义不等式：

$$x \preceq_{K} y \quad \Longleftrightarrow \quad y-x \in K, \quad x\prec_K y \quad \Longleftrightarrow \quad y-x \in \operatorname{int} K$$

例子

• 元素不等号（$K=\mathrm{R}_{+}^{n}$）

  $$x \preceq_{\mathbf{R}_{+}^{n} } y \quad \Longleftrightarrow \quad x_{i} \leq y_{i}, \quad i=1, \ldots, n$$

• 矩阵不等号（$K=\mathrm{S}_{+}^{n}$）

  $$X \preceq_{\mathbf{S}_{+}^{n} } Y \quad \Longleftrightarrow \quad Y-X半正定$$

性质：$\preceq_{K}$的很多性质类似于$\mathbf R$上的$\le $，例如

$$x \preceq_{K} y, \quad u \preceq_{K} v \quad \Longrightarrow \quad x+u \preceq_{K} y+v$$

最小和极小

$\preceq_{K}$一般不是线性序：我们可以有$x \not\preceq_{K} y$以及$y \not\preceq_{K} x$。

$x \in S$是$S$（关于$\preceq_{K}$）的最小元，如果

$$y \in S \quad \Longrightarrow \quad x \preceq_K y$$

$x \in S$是$S$（关于$\preceq_{K}$）的极小元，如果

$$y \in S, \quad y \preceq_{K} x \quad \Longrightarrow \quad y=x$$

例子：考虑$K=\mathrm{R}_{+}^{2}$

那么$x_1$是$S_1$的最小元，$x_2$是$S_2$的极小元。

超平面分离定理

超平面分离定理：

如果$C,D$是不交凸集，那么存在$a \neq 0, b$，使得

$$a^{T} x \leq b \text { for } x \in C, \quad a^{T} x \geq b \text { for } x \in D$$

图示如下：

即超平面$\left\{x | a^{T} x=b\right\}$分离了$C$和$D$

支撑超平面定理

集合$C$在$x_0$处的支撑超平面为：

$$\left\{x | a^{T} x=a^{T} x_{0}\right\}$$

其中$a \neq 0$以及对于所有$x\in C, a^{T} x \leq a^{T} x_{0}$

支撑超平面定理：如果$C$是凸集，那么在$C$边界上每点都存在支撑超平面

对偶锥和广义不等式

锥$K$的对偶锥为

$$K^{*}=\left\{y | y^{T} x \geq 0 \text { for all } x \in K\right\}$$

正规锥的对偶锥也正规，因此定义广义不等式：

$$y \succeq_{K^{*} } 0 \quad \Longleftrightarrow \quad y^{T} x \geq 0 \text { for all } x \succeq_{K} 0$$

对偶不等式定义的最小元和极小元

关于$\preceq_{K}$的最小元：

$x$是$S$的最小元当且仅当对于任意$\lambda \succ_{K^{*} } 0$，$x$是在$S$上最小化$\lambda^T z$的唯一点。

关于$\preceq_{K}$的极小元：

• 如果对于某个$\lambda \succ_{K^{*} } 0$，$x$在$S$上最小化$\lambda^T z$，那么$x$是极小元