最优化笔记
[toc]
凸性
集合
凸集
【定义】集合\(C\subseteq \mathbb R^n\)凸，指的是\(\forall x_0,x_1\in C,\forall \theta\in [0,1],(1-\theta)x_0+\theta x_1\in C\)。
其中，「\((1-\theta)x_0+\theta x_1\)」指的是「\(x_1,x_0\)两点连接成的线段」，这是一个常用的表述技巧。那么，凸集的定义的人话版本，就是「一个集合中任意两点连接成的线段，也在集合中」。
对于一些凸集 \(\{C_i\}_{i\in I}\)，以下运算的结果仍然是凸集，这样的运算叫「保凸运算」：
【交】\(C=\cup_{i\in I}C_i\)是凸集。即：任意个凸集的交集是凸集。这里的「任意个」可以是不可数无穷个。
【直积】\(C=C_1\times C_2=\{(\boldsymbol {x_1,x_2})\mid \boldsymbol x_1\in C_1,\boldsymbol x_2\in C_2\}\) 是\(\mathbb R^{n_1+n_2}\)上的凸集。
【加权和】如果 \(C_i\) 都是\(\mathbb R^n\)上的凸集，\(\beta\in \mathbb R\)，那么 \[ C=\sum_{i=1}^I \beta_iC_i=\{\beta_1 x_1+\beta_2 x_2+\cdots +\beta_Ix_I,x_i\in C_i\} \] 是凸集。
【仿射】如果\(C\)是\(\mathbb R^n\)上的凸集，\(A\in \mathbb R^{m\times n},b\in \mathbb R^m\)，则\(D=\{Ax+b,x\in C\}\)是凸集。其实，所谓仿射，也就是线性变换再加上一个平移。
有一些比较常见的凸集，需要知道他们的表示方法：
【超平面】\(H=\{x\in \mathbb R^n\mid w^Tx=b\}\)，其中\(w\in \mathbb R^n,b\in \mathbb R\)。称\(w\)为超平面的法向量。
【半空间】\(H=\{x\in \mathbb R^n\mid w^Tx\geq b\}\)，也就是一个超平面把空间分成两个半空间（以及超平面自身）
【多面体】\(H=\{x\in \mathbb R^n\mid Ax\leq b\}\)，也就是有限多个半空间的交集。
【子空间】\(L\in \mathbb R^n,\forall x,y\in L,\alpha x+\beta y\in L\).这个和高代里面的子空间是一个意思，也就是元素的线性组合仍在子空间中。
【仿射集/线性流形/仿射子空间】对于子空间\(L\)，存在\(\alpha\in\mathbb R^n\)，\(M=\alpha+L\)，则\(M\)是仿射集。称\(L\)的线性维数为\(M\)的仿射维数，记作\(\dim M\)。其实就是说，子空间不是必须要通过\(0\)点吗，那么把子空间平移了以后，它不通过\(0\)点了，虽然不再是子空间了，但是仍然是线性的，也是凸集。
例如： \[ M=\{x\in R^n\mid Ax=b\}\\\\ L=\{x\in R^n\mid Ax=0\} \] \(\alpha\) 为 \(Ax=b\) 的任意一个特解。\(\dim M=n-\text{rank} A\)。所以说，一般来说可以用一个非齐次线性方程组\(Ax=b\)的解集来表示仿射集。
【球体】\(H=\{x\in \mathbb R^n\mid ||x-\alpha||\leq r\}\)，其中\(||\cdot||\)是范数，\(\alpha\in\mathbb R^n,r\in \mathbb R\).
【椭球体】\(H=\{x\in \mathbb R^n\mid x^TEx\leq r\}\)，其中\(E\)是对称正定矩阵，\(r\geq 0\)。
例如：\(S=\{x\in \mathbb R^2\mid x_1^2+ix_1x_2+i^2x_2^2\leq 1\}\)
令 \[ E_i=\begin{pmatrix} 1 & \dfrac i2\\ \dfrac i2 & i^2 \end{pmatrix} \] 则\(E_i\)是对称正定矩阵，且\(S=\{x\in \mathbb R^2\mid x^TE_xx\leq 1\}\)，故\(S\)是凸集。
【凸函数的下水平集】\(H=\{x\in S\mid f(x)\leq \alpha\}\)，其中\(f\)是凸函数，\(S\)是凸集，\(\alpha\in R\)
还有一类特殊的集合，叫做「锥」。
【定义】称\(K\in \mathbb R^n\)为「锥形的」，当且仅当\(\forall x\in K,\forall \alpha>0,\alpha x\in K\)。如果\(K\)还是凸集，称\(K\)为「锥」。
常见的锥有：
- 【第一卦限】\(K=\{x\in \mathbb R^n\mid \forall i,x_i>0\}\)
- 【二阶锥】\(K=\{x\in \mathbb R^n\mid x_n\geq\sqrt{\sum_{i=1}^{n-1} x_i^2}\}\)
- 【对称矩阵、半正定矩阵、正定矩阵】
集合的内部和闭包
集合的闭包记作\(cl X\)，指的是集合中的点列的极限的集合。
例如：对于集合\(x>0\)，点列\(1/n\)，其极限为\(\lim_{n\to \infty} \dfrac 1n=0\)，所以\(0\)在集合\(X\)的闭包中。
闭包是包含\(X\)的最小闭集。
集合的内部记作\(\text{int} X\)，指的是集合中，存在以其为中心的球体也在集合中的点构成的集合。
例如：对于集合\(x>0\)，对于点\(0\)，无论半径\(r\)取何值，球体中的一点\(r\)总是大于\(0\)，从而不在集合中，所以\(0\)不在\(X\)的内部。
内部是包含在\(X\)中的最大开集。
但是有时候，对于一个凸集，其内部是空集。比如在\(R^3\)中的平面。此时，无法用内点来对\(X\)进行分析，但是就直观来看，\(X\)并不是一个很「空」的集合。这时候需要定义「相对内部」，也就是在\(X\)的仿射包中定义\(X\)的内部。例如，在\(R^3\)中有一个集合\(X\)，它是一个圆形。那么它的仿射包就是包含这个圆形的二维平面。在\(R^3\)中，这个圆形集合的内部是空集。但是如果只在仿射包中看，这个圆形集合的内部就不是空集了。从仿射包看的所谓「内部」，就是「相对内部」。
对于集合\(X\in \mathbb R^n\)，其仿射包为\(M\)，定义相对内部： \[ \text{ri }X=\left\{x\in X\mid \exists r_x>0 s.t.\{y\in M\mid ||y-x||_2<r_x)\subseteq X\} \right\} \] 看这个可能很晕。其实就是说，在\(X\)中存在一些点，它们满足一个条件，这个条件就是「在\(M\)中存在以这些点为中心的球包含于\(X\)」。我们把这些点的集合称为\(X\)的相对内部。相对内部和内部的区别，就是把「球」所存在的空间，从\(\mathbb R^n\)变成了\(X\)的仿射包。
组合和包
点\(x_1\cdots x_k\in \mathbb R^n\)的凸组合指的是： \[ \sum_{i=1}^k \theta_i x_i \] 其中\(\theta>0,\sum \theta=1\)。有没有发现这个定义特别像前面「凸集定义」的一部分。在二维空间中，凸组合可以看作经过两个点的线段。所以凸集的定义也可以表示为：\(C\)中的点的凸组合也都属于\(C\)，那么\(C\)是凸集。
如果集合\(X\)不是凸集，那么称包含\(X\)的最小凸集\(C\)为\(X\)的凸包，记作\(C=\text{conv} X\)。可以证明： \[ \text{conv} X=\left\{\sum_{i=1}^k\theta_ix_i\mid k\in \mathbb Z_{++}，x_i\in X,\sum_{i=1}^k\theta_i=1\right\} \] 看着很复杂，其实就是\(X\)中的任意有限个点的凸组合的集合。
点\(x_1\cdots x_k\in \mathbb R^n\)的仿射组合指的是： \[ \sum_{i=1}^k \theta_i x_i \] 其中\(\sum \theta=1\).相比于「凸组合」，「仿射组合」只是删去了「\(\theta>0\)」的条件。在二维空间中，仿射组合相当于经过两个点的直线。
对于仿射包的定义和生成，也和凸包类似。仿射包记作\(C=\text{aff} X\)。
通过仿射包，可以定义任意集合的维数。对于任意非空集合\(X\in \mathbb R^n\)，称其仿射包\(\text {aff}X\)的仿射维数是\(X\)的仿射维数，记作\(\dim X\)。
点\(x_1\cdots x_k\in \mathbb R^n\)的锥组合指的是： \[ \sum_{i=1}^k \theta_i x_i \] 其中\(\theta>0\).相比于「凸组合」，「锥组合」只是删去了「\(\sum\theta=1\)」的条件。在二维空间中，锥组合相当于经过两个点的射线。
对于锥包的定义和生成，也和凸包类似。锥包记作\(C=\text{cone} X\)。
可以总结一下：
| 组合类型 | 系数限制 | 集合名称 | 样例 |
|---|---|---|---|
| 线性组合 | 无限制 | 向量子空间 | \(\mathbb R^n\) |
| 仿射组合 | \(\sum \theta=1\) | 仿射集/线性流形/仿射子空间 | 仿射超平面 |
| 锥组合 | \(\theta>0\) | 锥 | 第一卦限 |
| 凸组合 | \(\theta>0,\sum \theta=1\) | 凸集 | 单纯形 |
凸函数
梯度和海森矩阵
这俩东西后面有用。
梯度： \[ \nabla f(\boldsymbol{x})=\left[\begin{array}{c} \frac{\partial f}{\partial x_1} \\ \vdots \\ \frac{\partial f}{\partial x_n} \end{array}\right] \] 海森矩阵： \[ \nabla^2 f(\boldsymbol{x})=\left[\begin{array}{ccc} \frac{\partial^2 f}{\partial x_1^2} & \cdots & \frac{\partial^2 f}{\partial x_n \partial x_1} \\ \vdots & \ddots & \vdots \\ \frac{\partial^2 f}{\partial x_1 \partial x_n} & \cdots & \frac{\partial^2 f}{\partial x_n^2} \end{array}\right] \] 简单理解，梯度就是一阶导，海森矩阵就是二阶导（曲率）。
凸函数
对于凸集\(S\)上的函数\(f\)，如果： \[ f(\theta x_0+(1-\theta)x_1)\leq \theta f(x_0)+(1-\theta)f(x_1) \] 其实就是：函数线上的两点之间的连线，一定在函数线以上。
凸函数的性质有：
函数\(f\)在凸集\(S\)上是凸函数，等价于其上镜图是凸集。 \[ \text{epi} f=\{(x,r)\in S\times \mathbb R\mid r\geq f(x)\} \]
函数\(f\)在凸集\(S\)上是凸函数，则有Jensen不等式： \[ f\left(\frac{\sum_{i=1}^m \alpha_i \boldsymbol{x}_{\boldsymbol{i}}}{\sum_{s=1}^m \alpha_s}\right) \leq \frac{\sum_{i=1}^m \alpha_i f\left(\boldsymbol{x}_{\boldsymbol{i}}\right)}{\sum_{s=1}^m \alpha_s} \] 其中\(x_i\in S,\alpha>0\)。
证明：令 \[ \theta_i=\frac{\alpha_i}{\sum_{i=1}^m \alpha_i} \] 因为\(f\)是凸函数，所以其上镜图是凸集，所以其上镜图上的点的凸组合是在上镜图里，有： \[ \begin{align} &\sum_{i=1}^m\theta_i(x_i,f(x_i))\in \text{epi} f\\ &\to \left(\sum_{i=1}^m \theta x_i,\sum_{i=1}^m \theta_i f(x_i)\right)\in \text{epi} f\\ &\to f\left(\sum_{i=1}^m \theta_i x_i\right)\leq \sum_{i=1}^m \theta_i f(x_i) \end{align} \]
函数\(f\)在\(\mathbb R^n\)上凸，当且仅当，\(\forall x_0\in \mathbb R^n,\forall d\in \mathbb R^n,\phi(\alpha)=f(x_0+\alpha d)\)关于\(\alpha\)在\(\mathbb R\)上凸。
函数\(f\)在凸集\(S\)上是凸函数，则其在\(S\)的相对内部上连续。
函数\(f\)一阶偏导连续，那么它在凸集\(S\)上是凸函数，当且仅当 \[ f(y)\geq f(x)+\nabla f(x)^T(y-x),\forall xy\in S \]
函数\(f\)二阶偏导连续，那么它在内部非空的凸集\(S\)上是凸函数，当且仅当\(\nabla ^2f(x)\)半正定。