梯度下降法
梯度下降法是机器学习里面最常用的优化方法，简单直接效果还好，因此被广泛应用。今天就来回顾下梯度下降法。
梯度下降法有一个很trivial的想法，比如你在山上，你想要最快的下山，那么你就要走最陡的路下山，即坡度最大的路下山。反映在数学里面，山高为一个目标函数$f(x)$, 你当前的位置是$x_0 $, 当前坡度最大的路对应于当前位置$x$梯度最大的方向，但是由于我们是要下山，我们要反着方向走，即方向为
确定了方向之后，我们需要确定要走的步长$\alpha$, 由于梯度是在$x_0 $处得到的，它只能够表示$f(x)$在点$x_0$出的陡峭程度，如果我们走的步伐太大，脱离的点$x_0$的邻域，那么这个梯度并不会是一个很好的下山方向。因此我们要保证这个步长$\alpha$足够小，此时，我们迈出了下山的第一步：
一次类推，只要我们一小步一小步的走陡峭的路，很快就能下山：
下面用稍微严谨一点的数学说明下为什么要走负梯度的方向。假设我们在$f(x)$的$x_0 $处走一小步$\Delta x$，
我们的目标是走了这一步后的$f(x_0 + \Delta x)$相比$f(x_0)$下降的最多。首先，我们先在$x_0$处对$f(x)$进行一阶泰勒展开：
让$f(x)$下降的最多的点即为$x_1$,让要想让近似后的$f(x)$ 最小的话，就要让$f’(x_0)\Delta x$的值最小，考虑到两个向量的内积最小的问题，便要求$\Delta x$ 和梯度是反向的。实际上，只要$\Delta x$和梯度的夹角是大于90度的时候，上面的$argmin \ f(x)$就可以比$f(x_0)$小，当$\Delta x$和梯度的夹角是90度或者$\Delta x$是0的时候，$argmin \ f(x)$和$f(x_0)$相等。此时令$f(x)$最小的$x$即为$x_{1}$,同时有$x_1 = x_0 + \Delta x$.
更一般的，考虑在$x_k$处对函数$f(x)$进行一阶泰勒展开，则能到的迭代更新公式为：
牛顿法
梯度下降法只是用到了一阶的导数信息，而牛顿法可以用到二阶的导数信息。
首先，我们先在$x_k$处对$f(x)$进行二阶泰勒展开,$\Delta x = x - x_k$：
让$f(x)$下降的最多的点即为$x_{k+1}$，即要$f(x)$取$f’(x)=0$的点，即让：
可得：
假设$f’(x_k) = g, f’’(x_k)=H$为一个hessian矩阵，那么$\Delta x$的矩阵形式为：
此时$x$的更新公式为：
拟牛顿法
牛顿法的迭代中，需要计算hessian矩阵的逆，这个计算很耗时。而拟牛顿法考虑使用一个矩阵$G$来近似hessian矩阵$H_{x_k}^{-1}$ 。考虑何种的矩阵能够近似hessian矩阵。
按上面的等式(9)。取$x=x_{k+1}$,有：
即
这个是hessian矩阵满足的条件，被称为拟牛顿条件。
如果$H_k$矩阵是正定的，那么可以保证牛顿法搜索是下降的，这个是因为根据（11）有
因为$H_k$矩阵是正定的，$H^{-1}_k$也会是正定的，那么有$g_k^TH^{-1}_kg_k$大于0，总有$f(x)<f(x_k)$，即牛顿法是下降的。
拟牛顿法是牛顿法的近似，选择$G_{k}$作为$H^{-1}_k$的近似，要求矩阵$G_k$满足同样的条件。首先$G_k$是正定的，其次，$G_k$满足上面的拟牛顿条件，即
这样子的方法被统称为拟牛顿法。同时可以使用下面的方式来更新$G_{k+1}$:
下面介绍BFP算法
假设每一步中的$G_{k+1}$是由$G_{k}$加上两个附加项构成的：
要求：
可以让$P_k (g_{k+1} - g_k )=\Delta x$且$Q_k(g_{k+1} - g_k )=-G_k(g_{k+1} - g_k )$ 使得更新后$G_{k+1}$满足拟牛顿条件。
事实上，这样子的满足条件的$P_k$和$Q_k$并不难找。例如取：
那么可以得到
BFGS算法是一个很常见的算法，用的是用一个正定矩阵$B_k$ 来近似$H_k$ ,同样需要满足上面说的拟牛顿条件。类似BFP算法，也有
考虑使$P_k,Q_k$满足：
找到满足条件的$P_k,Q_k$，得到BFGS的算法矩阵$B_{k+1}$ 的迭代公式：
实际的BFGS的算法中，有一个确定步长的步骤，即首先确定更新的方向$-B_k^{-1} g_k$, 然后求一个步长$\alpha $,求法如下：