最优化笔记
[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\)的相对内部上连续。如果有界闭集\(K\subset \text{ri }S\)，那么\(f\)在\(K\)上Lipschitz连续（比一致连续更强的连续）。
函数\(f\)一阶偏导连续，那么它在凸集\(S\)上是凸函数，当且仅当 \[ f(y)\geq f(x)+\nabla f(x)^T(y-x),\forall xy\in S \]
函数\(f\)二阶偏导连续，那么它在内部非空的凸集\(S\)上是凸函数，当且仅当\(\nabla ^2f(x)\)半正定。
函数\(f\)在凸集\(S\)上是凸函数，有：\(\forall c\in \mathbb R,\{x\in S\mid c\geq f(x)\}\)是凸集。即：使得\(f(x)\)小于一个定值的\(x\)的取值范围是凸集，这个范围叫做下水平集。
函数\(f\)在凸集\(S\)上是凸函数，则\(f\)的所有局部极小点都是全局极小点，而且局部极小点组成的集合是凸集。如果\(f\)是严格凸的，那么最多有一个极小点。
和凸集一样，有时候直接确定函数是不是凸函数比较难，因此可以利用保凸运算：
- 【锥组合】凸函数的锥组合是凸函数。即：对于\(\mathbb R^n\)上的凸函数\(f_i(x)\)，\(\forall \alpha_i>0\)，\(F(x)=\sum_i \alpha_if_i(x)\)是凸函数。
- 【仿射替换】对于\(\mathbb R^n\)上的凸函数\(f_i(x)\)，\(x=Ay+b\)是\(\mathbb R^m\to\mathbb R^n\)的仿射，则\(h(y)=f(Ay+b)\)是\(\mathbb R^m\)上的凸函数。
- 【上确界】对于\(\mathbb R^n\)上的凸函数\(f_i(x)\)，\(h(x)=\max _{i}f_i(x)\)是凸函数。
- 【单调复合】\(f(x)\)在\(\mathbb R^n\)上凸，\(h(y)\)在\(\mathbb R\)上凸且单增，则\(h(f(x))\)在\(\mathbb R^n\)上凸。
解和算法的基本性质
本节主要讨论无约束最优化问题 \[ \min_{x\in S}f(x) \] 其中\(f(x)\)是\(n\)元实函数，\(S\)是\(R^n\)的子集（在本章，\(S\)在大部分情况下就是\(R^n\)）。
可行方向和一阶条件
优化的基本思想是目标函数沿着某个方向可以看作一元函数，于是就可以利用一元函数的微积分。对于向量\(x,d\)，如果存在\(\bar \alpha\)，使得\(\forall \alpha\in [0,\bar \alpha],x+\alpha d\in S\)，那么称\(d\)是\(x\)处的可行方向。此时，多元函数转化为一元函数\(\phi(a)=f(x*+ad)\)，其导数（方向导数）为： \[ \phi'(a)=\langle \nabla f(x*+ad),d\rangle \] 【一阶必要条件】设\(S\subset R^n\)，\(f\)是连续可微的，如果\(x*\)是局部极小点，那么对于\(x*\)处的任何可行方向\(d\)，有： \[ \langle \nabla f(x*),d\rangle\geq 0 \] 梯度向量的方向是函数增长最快的方向，其与可行方向的内积非负，表示从\(x*\)出发，在所有可行方向上移动，\(f(x)\)都会增长。
特别的，如果\(x*\)是\(S\)的内点，此时所有方向都是可行方向，所以对所有的\(d\)都有一阶必要条件条件，容易发现这时的一阶必要条件实际上是 \[ \nabla f(x*)=0 \]
对于一元函数来说，它就是「一阶导数为零」。
将满足这种条件的点称为「驻点」。
二阶条件
【二阶必要条件】设\(S\subset R^n\)，\(f\)是二阶连续可微的，如果\(x*\)是局部极小点，那么对于\(x*\)处的任何可行方向\(d\)，有：
- \(\langle \nabla f(x*),d\rangle\geq 0\)
- 如果\(\langle \nabla f(x*),d\rangle= 0\)，则\(d^T\nabla^2f(x*)d\geq 0\)
如果\(x*\)是集合的内点，这两个条件就变成
- \(\langle \nabla f(x*),d\rangle= 0\)
- \(\nabla^2f(x*)\)半正定
如果\(\nabla ^2f(x*)\)正定，那么\(x*\)是严格局部极小点。
线搜索法
线搜索法指的是在当前迭代点处，根据收集到的信息选择一个有待进一步探测的方向，然后在这个方向上进行一维搜索得到合适的步长，进而得到下一个迭代点的过程。后续的梯度下降法、共轭梯度法、牛顿法、拟牛顿法都是线搜索法。
已知初始估计 \(\boldsymbol{x}_0, k=0\).设 \(\boldsymbol{x}_k\) 处 \(\boldsymbol{g}_k=\nabla f\left(\boldsymbol{x}_k\right) \neq \mathbf{0}\) ，则第 \(k\) 次迭代:
- 根据某种近似函数确定设 \(\boldsymbol{x}_k\) 处的搜索方向设 \(\boldsymbol{d}_{\boldsymbol{k}}\),
- 线搜索: 求解关于 \(\alpha\) 的一元函数极小化问题
\[ \min _\alpha \phi(\alpha)=f\left(\boldsymbol{x}_k+\alpha \boldsymbol{d}_k\right) \]
得到步长 \(\alpha_k\)
- 置 \(\boldsymbol{x}_{k+1}=\boldsymbol{x}_k+\alpha_k \boldsymbol{d}_k\)
不同的线搜索法之所以不同，核心区别在于\(\boldsymbol{d}_k\)的选取。具体来说，由函数的二次近似 \[ f(x) \approx f\left(\boldsymbol{x}_k\right)+\boldsymbol{g}_k^T\left(\boldsymbol{x}-\boldsymbol{x}_k\right)+\frac{1}{2}\left(\boldsymbol{x}-\boldsymbol{x}_k\right)^T \boldsymbol{B}_k\left(\boldsymbol{x}-\boldsymbol{x}_k\right) \] 只要\(\boldsymbol{B}_k\)正定，那么\(\boldsymbol{d}_k\)就一定是下降方向。正是不同的\(\boldsymbol{B}_k\)导致了不同的搜索方向。
所谓的精确线搜索，指的是精确求解\(\min _\alpha \phi(\alpha)=f\left(\boldsymbol{x}_k+\alpha \boldsymbol{d}_k\right)\)。其重要性质为： \[ \nabla f(\boldsymbol{x}_{k+1})^T \boldsymbol{d}_k=0 \] 精确线搜索的运算量经常很大，所以大多数情况下都会用非精确线搜索，即不精确求解\(\min _\alpha \phi(\alpha)=f\left(\boldsymbol{x}_k+\alpha \boldsymbol{d}_k\right)\)，转而使用别的方法确定\(\alpha_k\)。如果\(\alpha_k\)的选择不合理，则可能会出现算法无法找到最优解的情况。
对于一元函数\(f(x)=x^2\)，想要求其最小值。选取初始点\(x_0=2\)。
左图中有\(d_k=-1,\alpha_k=2+\dfrac 3 {2^{k+1}}\)，算法收敛于\(1\)。
右图中有\(d_k=(-1)^{k+1},\alpha_k=\dfrac{1}{2^{k+1}}\)，算法有两个聚点\(1,-1\)。
假设\(\bar \alpha\)是使得\(\phi(\alpha)=\phi(0)\)，即\(f(\boldsymbol{x}+\alpha\boldsymbol{d})=f(\boldsymbol{x})\)成立的最小正数，从上述两个例子可以看出，\(\alpha\)的选择不能太过靠近区间\([0,\bar \alpha]\)的两个端点。有一些法则给出了选取\(\alpha\)需要满足的条件。
Armijo条件
定义一次函数 \[ l(\alpha)=\phi(0)+\rho \phi'(0)\alpha \] 其中\(\rho\)是由设计者自由选定的参数。于是这个一次函数是一条完全由\(\rho\)确定的直线，称为「\(\rho\)线」。
如果\(\alpha\)对应的函数值在\(\rho\)线以下，则认为\(\alpha\)不太大。再选取参数「缩短因子」\(\lambda<1\)，如果将\(\alpha\)扩大\(\lambda ^{-1}\)倍以后，对应的函数值不再在\(\rho\)线以下，则认为\(\alpha\)不太小。写成数学表达式，有： \[ \begin{cases} \phi(\alpha) &\leq \phi(0)+\rho \phi^{\prime}(0) \alpha \\ \phi(\alpha / \gamma)&>\phi(0)+\rho \phi^{\prime}(0) \alpha / \gamma \end{cases} \]
Goldstein测验
「不太大」的条件不变，将「不太小」的条件改为： \[ \phi(\alpha) \geq \phi(0)+(1-\rho) \phi^{\prime}(0) \alpha \] 这要求\(\rho \in (0,\dfrac 12)\)。在上面的图中，也就是两条经过\((0,\phi(0))\)的虚线之间的范围，即\([b,c]\)。
Wolfe准则
如果\(\phi\)不是二次函数，则Goldstein测验可能使得真正的极小点不满足条件（看上面的图）。此时仍然保持「不太大」条件不变，把「不太小」条件改为 \[ \phi'(\alpha)\geq \sigma\phi'(0) \] 这就是Wolfe准则。
无约束优化方法
梯度下降法
梯度下降法的基本格式是： \[ \boldsymbol{x}_{k+1}=\boldsymbol{x}_k-\alpha_k \nabla f(\boldsymbol{x}_k) \] 即线搜索法中让\(\boldsymbol{d}_k\)是\(f\)在\(\boldsymbol{x}_k\)处的负梯度。
梯度下降法是怎么想到的呢？其实有两种解释。
函数值在负梯度方向下降最快
极小化函数在\(\boldsymbol{x}_k\)附近的二次泰勒展开 \[ x_{k+1}=\underset{x\in \mathbb{R}^n}{\arg \min} f\left(\boldsymbol{x}_k\right)+\nabla f\left(\boldsymbol{x}_k\right)^T\left(\boldsymbol{x}-\boldsymbol{x}_k\right)+\frac{1}{2 \alpha_k}\left\|\boldsymbol{x}-\boldsymbol{x}_k\right\|_2^2 \]
梯度下降法有全局收敛性：假设与初始点 \(x_0\) 关联的 \(f\) 的下水平集
\[ S=\left\{\boldsymbol{x}: f(\boldsymbol{x}) \leq f\left(\boldsymbol{x}_0\right)\right\} \]
是紧的(有界闭集), 并且 \(f\) 在包含 \(S\) 的某开集上连续可微. 那么对于步长满足Armijo法则的梯度下降法来说，
- 迭代轨迹不离开 \(S: \boldsymbol{x}_i \in S \forall i\)
- 除非得到驻点；否则 \(\left\{f\left(\boldsymbol{x}_i\right)\right\}\) 严格单调递减
- 轨迹有聚点, 并且每个聚点均是 \(f\) 的驻点.
接下来分析\(f(\boldsymbol{x})\)在满足三种特殊情况的条件下，梯度下降法的复杂性。所谓的复杂性一般指的是一个不等式，衡量了迭代\(k\)步时，所得到的值有多接近局部极小点。这三种特殊情况分别是：
- 任何具有Lipschitz（李普希茨）梯度的函数
- 任何具有李普希茨梯度的凸函数
- 任何具有李普希茨梯度的强凸函数
在此之前，需要定义「李普希茨梯度」和「强凸函数」。
【Lipschitz梯度】 设 \(L \geq 0\). 称函数 \(f\) 的梯度在开集 \(U\) 上是 \(L-\) Lipschitz的，如果
\[ \|\nabla f(\boldsymbol{x})-\nabla f(\boldsymbol{y})\| \leq L\|x-y\| \forall x, y \in U . \]
称 \(f\) 的梯度在集合 \(S\) 上是 \(L-\) Lipschitz的，如果存在开集 \(U \supseteq S\)使得 \(f\) 的梯度在开集 \(U\) 上是 \(L-\) Lipschitz的.
Lipschitz梯度这个名字可能有点容易让人误解。它并不是一种特殊的梯度，而指的是函数的梯度满足某种条件。
如果函数的梯度满足\(L-\)Lipschitz条件，也称为这个函数是\(L-\)光滑的。函数是\(L-\)光滑的等价于函数的Hesse矩阵的谱范数不大于\(L\)，即： \[ \forall \boldsymbol{x},||\nabla ^2f(\boldsymbol{x})||_2\leq L \] 从直观上来说，\(L\)-光滑性质保证了函数的梯度的变化速率是受限的，可以理解为函数的斜率在任意两点之间的变化都有一个上界，这使得优化算法在更新变量时，能对目标函数的变化有一定的控制。
【强凸函数】设 \(l>0\). 称定义在凸集 \(S\) 上的函数 \(f(\) 关于范数 \(\|\cdot\|)\)是 \(l\) —强凸的(strong convex), 如果对每个 \(x_0, x_1 \in S\) 和每个\(\theta\in(0,1)\) \[ \quad f\left((1-\theta) x_0+\theta x_1\right) \leq(1-\theta) f\left(x_0\right)+\theta f\left(x_1\right)-\frac{l}{2} \theta(1-\theta)\left\|x_0-x_1\right\|^2 . \] 其实就是比凸函数的定义多了一个\(\dfrac{l}{2} \theta(1-\theta)\left\|x_0-x_1\right\|^2 .\)
从直观上来说，强凸性是凸性的加强版，它要求函数不仅仅是凸的，还得有一定的曲率（例如：\(|x|\)不是强凸函数），这样的曲率保证了函数在全局上有唯一的最优解，一般来说，强凸函数的\(l\)越大，函数的「盆地」越深，优化算法收敛的也越快。
具有Lipschitz（李普希茨）梯度的函数
【二次上界】：设\(f\)的梯度是L-Lipschitz的，那么： \[ f(\boldsymbol{y}) \leq f(\boldsymbol{x})+\nabla f(\boldsymbol{x})^T(\boldsymbol{y}-\boldsymbol{x})+\frac{L}{2}\|\boldsymbol{y}-\boldsymbol{x}\|^2 \forall \boldsymbol{x}, \boldsymbol{y} \in \mathbb{R}^n . \] 如果设\(\phi(\alpha)=f(\boldsymbol{x}+a(\boldsymbol{y-x}))\)，则上面的式子可以写作（按项对应）： \[ \phi(1)\leq \phi(0)+\phi'(0)+\frac L2\|\boldsymbol{y-x}\|^2 \] 由二次上界，可以得到关于梯度下降法的两个结论：
对于常数步长\(\alpha\in \left(0,\dfrac 2L\right)\)，梯度下降法是下降算法
对于常数步长\(\alpha\in\left(0,\dfrac 1L\right)\)，梯度下降法满足 \[ f\left(\boldsymbol{x}_{s+1}\right) \leq f\left(\boldsymbol{x}_s\right)-\frac{\alpha}{2}\left\|\nabla f\left(\boldsymbol{x}_s\right)\right\|^2 \quad \forall s \geq 0 \]
为了证明这个结论，只需要让二次上界定理中的\(\boldsymbol{x}=\boldsymbol{x}_s,y=\boldsymbol{x}_{s+1}=\boldsymbol{x}_s-\alpha_s \nabla f(\boldsymbol{x}_s)\)即可。 \[ f\left(\boldsymbol{x}_{s+1}\right)-f\left(\boldsymbol{x}_s\right) \leq \alpha\left(\frac{\alpha L}{2}-1\right)\left\|\nabla f\left(\boldsymbol{x}_s\right)\right\|^2 \quad \forall s \geq 0 \] 当\(\alpha\leq \dfrac 2L\)，右式为负；当\(\alpha\leq \dfrac 1L\)，\(\dfrac {\alpha L}{2}\leq \dfrac 12\)。
由这两个结论，可以推出具有Lipschitz（李普希茨）梯度的函数上梯度下降法的复杂度：
设 \(f\) 的梯度是 \(L-\) Lipschitz的, 且 \(f\) 存在极小点 \(\boldsymbol{x}_*\).记 \(f_*=f\left(\boldsymbol{x}_*\right)\), 则步长为 \(1 / L\) 的 GD 迭代满足
\[ \min _{0 \leq s \leq k-1}\left\|\nabla f\left(\boldsymbol{x}_s\right)\right\| \leq \sqrt{\frac{2 L}{k}\left(f\left(\boldsymbol{x}_0\right)-f_*\right)} \] 这里的「复杂度」是用「前\(k-1\)步中函数的梯度的最小范数」表示的。当这个范数是零时，意味着找到了驻点。这个范数越小，就越接近驻点。
将\(\alpha=1/L\)代入\(f\left(\boldsymbol{x}_{s+1}\right) \leq f\left(\boldsymbol{x}_s\right)-\dfrac{\alpha}{2}\left\|\nabla f\left(\boldsymbol{x}_s\right)\right\|^2\),有： \[ \frac{1}{2 L}\left\|\nabla f\left(\boldsymbol{x}_s\right)\right\|^2 \leq f\left(\boldsymbol{x}_s\right)-f\left(\boldsymbol{x}_{s+1}\right) \] 对于\(s=0\sim k-1\)，写出这个不等式然后求和，消除中间的项，有： \[ \begin{align} f(\boldsymbol{x}_0)-f(\boldsymbol{x}_s)&\geq \frac 1{2L}\sum_{s=0}^{k-1}\|\nabla f(\boldsymbol{x}_s)\|^2\\ &\geq \frac k{2L} \min _{0 \leq s \leq k-1}\left\|\nabla f\left(\boldsymbol{x}_s\right)\right\| ^2 \end{align} \] 证毕。
具有李普希茨梯度的凸函数
设 \(f\) 是凸函数, 梯度是 \(L-\) Lipschitz的, 且 \(\boldsymbol{x}_*\) 是它的极小点. 那么步长为 \(1 / L\) 的 GD迭代满足
\[ f\left(\boldsymbol{x}_k\right)-f\left(\boldsymbol{x}_*\right) \leq \frac{L\left\|\boldsymbol{x}_0-\boldsymbol{x}_*\right\|^2}{2 k}, k \geq 1 . \] 这里的「复杂度」是用「当前迭代点的函数值和局部极小值的差」表示的。这个差越小，就越接近驻点。
具有李普希茨梯度的强凸函数
关于强凸函数有如下结论：
- \(f\) 是 \(l\) 强凸的当且仅当 \(f(\boldsymbol{x})-\frac{l}{2}\|\boldsymbol{x}\|^2\) 是凸的.
- 设 \(f \in C^1\). 则 \(f\) 在凸集 \(S\) 上是1强凸的当且仅当
\[ f(\boldsymbol{y}) \geq f(\boldsymbol{x})+\nabla f(\boldsymbol{x})^T(\boldsymbol{y}-\boldsymbol{x})+\frac{l}{2}\|\boldsymbol{y}-\boldsymbol{x}\|^2, \quad \forall \boldsymbol{x}, \boldsymbol{y} \in S . \]
- 设 \(f \in C^2\). 则 \(f\) 在内部非空的凸集 \(S\) 上是 \(l\)-强凸的当且仅当
\[ \nabla^2 f(\boldsymbol{x}) \succeq l \boldsymbol{I}, \quad \forall \boldsymbol{x} \in S . \]
设 \(f\) 是 \(l\)-强凸的, 它的梯度是 \(L-\) Lipschitz的, 且 \(\boldsymbol{x}_*\) 是 \(f\) 的极小点. 那么步长为 \(1 / L\) 的 GD迭代满足
\[ \left\|\boldsymbol{x}_k-\boldsymbol{x}_*\right\|^2 \leq\left(1-\frac{1}{k}\right)^k\left\|\boldsymbol{x}_0-\boldsymbol{x}_*\right\|^2 \quad \forall k \geq 1, \]
其中 \(\kappa=L / l\).
牛顿法
考虑二次连续可微的函数，对其进行泰勒展开： \[ f(x)\approx q_k(x)=f(\boldsymbol{ x_k})+(\boldsymbol{x-x_k})^T\nabla f(\boldsymbol{x_k})+\dfrac 12 (\boldsymbol{x-x_k})^T\nabla^2f(\boldsymbol{x}_k)(\boldsymbol{x-x_k}) \] 当\(\nabla^2f(x_k)\)正定时，\(q_k\)有唯一极小点。将极小点作为新迭代，由此得到基本牛顿法： \[ \boldsymbol{x_{k+1}}=\boldsymbol {x}_k-(\nabla ^2f(\boldsymbol{x}_k))^{-1}\nabla f(\boldsymbol x_k) \] 关于牛顿法，有二次收敛定理：假设 \(\nabla^2 f(\boldsymbol{x})\) 在 \(\mathbb{R}^n\) 上是 \(M\)-Lipschitz的，且局部极小点 \(x_*\) 处的Hesse矩阵 \(\nabla^2 f\left(x_*\right)\) 正定, 即存在 \(l>0\) 使得 \(\nabla^2 f\left(x_*\right) \geqslant l I\). 如果初始点 \(x_0\) 满足
\[ \left\|x_0-x_*\right\| \leq \frac{l}{2 M} \]
那么 \(\forall k \geq 0\), 牛顿法是良定义的, 且由它产生的序列至少二次收敛到 \(\boldsymbol{x}_*\).
但是在使用上，基本牛顿法存在一些问题。
- \(\nabla^2f(x_k)\)正定，但是牛顿增量很大，导致局部二次近似失效
- \(\nabla f(x_k)\)不正定
在这两种情况下，基本牛顿法会失效，因此需要寻求将其修正的方法。常用方法是对于\(\epsilon_k>0\)，取 \[ M_k=[\nabla^2f(x_k)+\epsilon_kI]^{-1} \] 计算\(\nabla^2f(x_k)\)的特征值，设\(\epsilon_k\)是让\([\nabla^2f(x_k)+\epsilon_kI]\)特征值大于常数\(\delta\)的最小非负整数，然后沿方向 \[ d_k=-M_k\nabla f(x_k) \] 进行线搜索。
共轭梯度法
【定义：\(G-\)正交/共轭】已知对称正定矩阵\(G\)，定义两个向量的\(G-\)内积： \[ \langle\boldsymbol{u}, \boldsymbol{v}\rangle_G=\boldsymbol{u}^T \boldsymbol{G} \boldsymbol{v} \] 如果两个向量的\(G-\)内积为\(0\)，则称其为\(G-\)正交或者\(G-\)共轭向量。