最优化方法是机器学习及深度学习的灵魂，前两年之前一直打算写一篇文章记录下新的，但是忘记了，今天无聊，写一下好了。
说到最优化，首先要理解偏导数与梯度的概念，我之前在一篇文章中写了，偏导数、梯度、Jacobian矩阵、Hessian矩阵
除了偏导与梯度，还要理解 泰勒展开式，才能更好的理解最优化深层次的意义。
泰勒展开式
一元n阶可导函数的泰勒展开公式如下：
$$ f(x)=f\left(x_{0}\right)+f^{\prime}\left(x_{0}\right)\left(x-x_{0}\right)+\frac{1}{2} f^{\prime \prime}\left(x_{0}\right)\left(x-x_{0}\right)^{2}+\cdots+\frac{1}{n !} f^{(n)}\left(x_{0}\right)\left(x-x_{0}\right)^{n} \cdots $$
多元函数的泰勒展开式为：
$$ f(x)=f\left(x_{0}\right)+\left(\nabla f\left(x_{0}\right)\right)^{\mathrm{T}}\left(x-x_{0}\right)+\frac{1}{2}\left(x-x_{0}\right)^{\mathrm{T}} H\left(x-x_{0}\right)+o\left(\left\|x-x_{0}\right\|^{2}\right) $$
其中的$H$就是Hessian矩阵，可以用泰勒展开近似代替目标函数。比如：梯度下降是一阶泰勒展开，牛顿法是二阶泰勒展开。
知道了泰勒展开式，就开始具体了解各种优化吧。
梯度下降法
梯度下降法
梯度下降可以说是深度学习的基础了。
之前说了，梯度下降就是多元函数的一阶泰勒展开公式，忽略一阶以上的项，可以得到：
$$ f(x+\Delta x)=f(x)+(\nabla f(x))^{\mathrm{T}} \Delta x+o(\Delta x) $$
变一下形：
$$ f(x+\Delta x)-f(x)=(\nabla f(x))^{\mathrm{T}} \Delta x+o(\Delta x) $$
那么只要是
$$ (\nabla f(x))^{\mathrm{T}} \Delta x<0 $$
就可以推出
$$ f(x+\Delta x)<f(x) $$
这样就能不断地逼近极小值，让函数值"下降"了。当$\Delta x$的模小到一定程度时(当然别太小)，梯度的反方向$\Delta x=-\nabla f(x)$函数值下降的最快。
于是，可以设计一个学习率(learning rate)，让$x+\Delta x$在$x$的邻域内可以忽略泰勒级数的更高项。
因此，按照下面的迭代公式就能逐渐到达极小值
$$ x_{k+1}=x_{k}-\gamma \nabla f\left(x_{k}\right) $$
梯度下降只需要计算几个点的值，计算量很小，所以也是神经网络BP算法的基础。
最速下降法
由于学习率$\gamma$不好确定，提出了一个最速下降法，其同样沿着梯度负方向迭代，但还要计算最佳学习率$\gamma$ ，其他步骤都一样。
牛顿法
之前说了，根据费马定理，函数在点$f$ 处取得极值的必要条件是梯度为0，也就是
$$ \nabla f\left(x^{*}\right)=0 $$
多元函数的泰勒二阶展开为
$$ f(x)=f\left(x_{0}\right)+\nabla f\left(x_{0}\right)^{\mathrm{T}}\left(x-x_{0}\right)+\frac{1}{2}\left(x-x_{0}\right)^{\mathrm{T}} \nabla^{2} f\left(x_{0}\right)\left(x-x_{0}\right)+o\left(\left(x-x_{0}\right)^{2}\right) $$
对两边同时求梯度，得到其梯度向量：
$$ \nabla f(x)=\nabla f\left(x_{0}\right)+\nabla^{2} f\left(x_{0}\right)\left(x-x_{0}\right) $$
由于$f$是多元函数，所以$\nabla^{2} f\left(x_{0}\right)$可以Hessian矩阵$H$代替，令函数的梯度为$0$，则有：
$$ \nabla f\left(x_{0}\right)+\nabla^{2} f\left(x_{0}\right)\left(x-x_{0}\right)=0 $$
解这个线性方程，就可以得到：
$$ x=x_{0}-\left(\nabla^{2} f\left(x_{0}\right)\right)^{-1} \nabla f\left(x_{0}\right) $$
记梯度向量为$g$，那么上面的公式可以写成：
$$ x=x_{0}-H^{-1} g $$
之后使用下面的公式进行迭代：
$$ x_{k+1}=x_{k}-\boldsymbol{H}_{k}^{-1} \boldsymbol{g}_{k} $$
牛顿法不保证收敛，而且迭代成本也更高，还要计算Hessian矩阵和它的逆矩阵。
由于求逆的时间复杂度很高，所以通常转而求
$$ \boldsymbol{H}_{k} \boldsymbol{d}=-\boldsymbol{g}_{k} $$
牛顿法有几个特点：
- 牛顿法具有二阶收敛性，在某些目标函数(线性回归、Logistic回归等) 问题中，它的收敛速度比梯度下降快很多；
- 之前说了牛顿法不保证收敛，所以要求初始点离极小点尽量近，负责可能不会收敛；
- 如果Hessian矩阵奇异(换句话说就是没有逆矩阵)，牛顿方向可能不存在；
- 如果Hessian矩阵不是正定的，牛顿方向有可能是反方向。
拟牛顿法
计算Hessian矩阵需要很高的时间复杂度，所以可以用其他矩阵近似代替Hessian矩阵或者它的逆。
这个矩阵要正定、容易求逆，或者可以通过递推公式计算得到。
之前牛顿法中讲到：
$$ \nabla f(x)=\nabla f\left(x_{0}\right)+\nabla^{2} f\left(x_{0}\right)\left(x-x_{0}\right) $$
把$x$记为$x_k$，把$x_0$记为$x_{k+1}$，那么上面的公式就变成了：
$$ \nabla f(x_k)=\nabla f\left(x_{k+1}\right)+\nabla^{2} f\left(x_{k+1}\right)\left(x_k-x_{k+1}\right) $$
变换一下，就可以得到：
$$ \nabla f(x_{k+1})-\nabla f\left(x_{k}\right)=\nabla^{2} f\left(x_{k+1}\right)\left(x_{k+1}-x_{k}\right) $$
$\nabla f(.)$是梯度，$\nabla^{2} f(.)$则是Hessian矩阵，那么可以简化写为：
$$ g_{k+1}-g_{k} \approx H_{k+1}\left(x_{k+1}-x_{k}\right) $$
令：
$$ \begin{array}{l}{s_{k}=x_{k+1}-x_{k}} \\ {y_{k}=g_{k+1}-g_{k}}\end{array} $$
上面可以简写为：
$$ y_{k} \approx \boldsymbol{H}_{k+1} s_{k} $$
也就是：
$$ s_{k} \approx H_{k+1}^{-1} y_{k} $$
接下来，可以尝试用近似代替Hessian矩阵。
首先，定义如下几个变量：
$$ \left\{\begin{array}{l}{C_{i}=H_{i}^{-1}} \\ {\Delta g_{i}=g_{i}-g_{i-1}} \\ {\Delta \theta_{i}=\theta_{i}-\theta_{i-1}}\end{array}\right. $$
之前的公式就可以改成：
$$ \begin{align} H_{k+1}^{-1}g_{k+1}-g_{k} &\approx\left(x_{k+1}-x_{k}\right) \\ C_i \Delta g_i&\approx \Delta \theta_i \end{align} $$
我们尝试用迭代的方法，每轮用很小的计算量更新$C_i$到$C_{i+1}$，让$C_i$通过加上两个向量$v_i$和$u_i$乘权重组成的矩阵后，变成$C_{i+1}$。
也就是
$$ \left\{\begin{array}{l}{C_{i+1} \Delta g_{i+1}=\Delta \theta_{i+1}} \\ {C_{i+1}=C_{i}+a_{i} v_{i} v_{i}^{T}+b_{i} u_{i} u_{i}^{T}}\end{array}\right. $$
把第二个公式的$C_{i+1}$的更新定义代到第一个公式中，可以推出：
$$ \left(C_{i}+a_{i} v_{i} v_{i}^{T}+b_{i} u_{i} u_{i}^{T}\right) \Delta g_{i+1}=\Delta \theta_{i+1} $$
再把括号拆开，可以得到：
$$ C_{i} \Delta g_{i+1}+a_{i} v_{i} v_{i}^{T} \Delta g_{i+1}+b_{i} u_{i} u_{i}^{T} \Delta g_{i+1}=\Delta \theta_{i+1} $$
其中，$\Delta \theta_{i+1}$是一个列向量，$v_{i}^{T} \Delta g_{i+1}$是一个标量值，所以$a_{i} v_{i} v_{i}^{T} \Delta g_{i+1}$等于一个常数乘$v_{i}$，我们可以让$v_i$这个向量等于$\Delta \theta_{i+1}$。
而$C_i\Delta g_{i+1}$的一个列向量，$b_{i} u_{i} u_{i}^{T} \Delta g_{i+1}$也是一个列向量，那么我们可以让$u_i$等于它，综合起来，也就是：
$$ \left\{\begin{array}{l}{v_{i}=\Delta \theta_{i+1}} \\ {u_{i}=C_{i} \Delta g_{i+1}}\end{array}\right. $$
让$u_i$等于$\Delta \theta_{i+1}$，它的权值为1，让$u_i$与$C_{i} \Delta g_{i+1}$互相抵消，它的权值为$-1$，那么可以推出来：
$$ \left\{\begin{array}{l}{a_{i} v_{i}^{T} \Delta g_{i+1}=1} \\ {b_{i} u_{i}^{T} \Delta g_{i+1}=-1}\end{array}\right. $$
$v_{i}^{T} \Delta g_{i+1}$与$u_{i}^{T} \Delta g_{i+1}$都是已经得到的值，所以只要计算$a_i$与$b_i$就行了，这很容易就能够推导出来：
$$ \left\{\begin{array}{l}{a_{i}=\frac{1}{v_{i}^{T} \Delta g_{i+1}}} \\ {b_{i}=-\frac{1}{u_{i}^{T} \Delta g_{i+1}}}\end{array}\right. $$
于是，更新迭代公式也能够得出来了(该式名为DFP)：
$$ C_{i+1}=C_{i}+\frac{\Delta \theta_{i+1} \Delta \theta_{i+1}^{T}}{\Delta \theta_{i+1}^{T} \Delta g_{i+1}}-\frac{\left(C_{i} \Delta g_{i+1}\right)\left(C_{i} \Delta g_{i+1}\right)^{T}}{\Delta g_{i+1}^{T} C_{i} \Delta g_{i+1}} $$
其中，初始矩阵$C_0$为单位阵$E$，因为这样一来，第一步时，问题等同于梯度下降。
另外一个更新公式是BFGS，假定：
$$ \left\{\begin{array}{l}{C_{i+1} \Delta g_{i+1}=\Delta \theta_{i+1}} \\ {C_{i+1}=(I-A) C_{i}\left(I-A^{T}\right)+a_{i} v_{i} v_{i}^{T}}\end{array}\right. $$
那么， 就可以得到下面这个迭代公式：
$$ C_{i+1}=\left(I-\frac{\Delta \theta_{i} \Delta g_{i}^{T}}{\Delta g_{i}^{T} \Delta \theta_{i}}\right) C_{i}\left(I-\frac{\Delta g_{i} \Delta \theta_{i}^{T}}{\Delta g_{i}^{T} \Delta \theta_{i}}\right)+\frac{\Delta \theta_{i} \Delta \theta_{i}^{T}}{\Delta g_{i}^{T} \Delta \theta_{i}} $$
通常使用BFGS方法，收敛速度通常会比梯度下降快很多。
BFGS需要$n\times n$的方阵$C_k$用于近似Hessian矩阵的逆矩阵，如果特征太多，也就是$n$太大，可以使用L-BFGS方法，存储最近$m$个$(\Delta \theta, \Delta g)$来近似$C_k$即可，$m$取值通常为10~20。
坐标下降法
有些函数可能是非凸的，或者种种原因没法用梯度下降和牛顿法，比如加了$l1$正则化的最优化，这时可以使用坐标下降法来优化。
坐标下降法每次选择一个变量优化，固定住其他变量，用分治法的思想，轮流优化各个变量，直到达到最小值。
最优化面临的问题
无论是梯度下降还是牛顿法，都是为了找梯度为0的点，梯度为0只是取极值的必要条件，而非充分条件。
- 比如遇到鞍点(saddle point)时(如下图)，就会遇到梯度为0而非极小值的情况。
- 再比如，可能找到的是局部极小值，而非全局极小值。
