梯度

本节我们来讲梯度方法，非常常用的最优化方法。

这个概念我们应该都是理解的，梯度就是一个方向，就是$f(x)$变化最大的方向，沿着这个方向，我们更加可能获取一个极值。

下面介绍一种梯度下降的方法

最速下降法

追速下降法是梯度方法的一个具体实现，其理论为每次迭代中选择合适的步长使得目标函数能够最大程度的减少。

中间我们跳过无数理论概念，直接举出一个例子来说明最速下降法的过程。

利用最速下降法求解函数

$$f(x_1,x_2,x_3)=(x_1-4)^4+(x_2-3)^2+4(x_3+5)^4$$

的极小值点，其中初始搜索点$x_0=[4,2,-1]$

让我们来解答这个问题

目标函数的梯度

$$\Delta f(x)=[4(x_1-4)^3,2(x_2-3),16(x_3+5)^3]$$

带入$x_0$

则$x_0$的梯度为

$$\Delta f(x)=[0, -2, 1024]$$

重点来了，确定$x_1$处的步长。

$$\alpha_0=arg\ min\ f(x_0-\alpha \Delta f(x_0))$$

$$\alpha_0=arg\ min\ (0+(x+2\alpha-3)^2+4(-1-1024\alpha+5)^4)$$

$$=arg\ min\ f(\alpha)$$

这个时候我们是可以用到上篇文章提到的割线发进行一维搜索

$$\alpha=3.967x10^{-3}$$

以此类推 就能够获取极小值点的一个取值。

上面这个最速下降法仅仅用到可一阶导数，接下来我们会介绍更加有效的方式。

牛顿法

最速度下降法只用到目标函数的一阶导数，这种方法并非是最高效的。在某些情况下我们需要引入目标函数的高阶导数，它的效率要优于最优下降法。这个就是我们要说的牛顿法也叫做牛顿-拉夫森方法。

下面我们来看看牛顿法的数学描述。

当目标函数$f$是二阶可微的，那么将函数$f$在$x^k$出进行泰勒展开，忽略三次以上的项，可以得到二次型近似函数。其中$x^k$表示目标函数在k处的取值。

$$f(x)\approx f(x^k)+f(x-x^k)g^k+\frac{1}{2}(x-x^k)F(x^k)(x-x^k)$$

为了简化描述

$$g^k=\Delta f(x^k)$$

将局部最小值的一阶必要条件用户函数q，可以得到

$$0=\Delta q(x)=g^k+F(x^k)(x-x^k)$$

如果$F(x^k)>0$，函数q的极小值点为

$$x^{k+1}=x^k-F(x^k)^{-1}g^k$$

以上就是牛顿的迭代公式，太复杂了咱们直接举例子吧。

牛顿法的应用

利用牛顿法求解以下函数的极小值点

$$f(x_1,x_2,x_3,x_4)=(x_1-10x_2)^2+5(x_3-x_4)^2+(x_2-2x_3)^4+10(x_1-x_4)^4$$

初始点为$x_0=[3,-1,0,1]$

下面我们来看这个题的解法

首先将$x_0$带入原方程 $f(x_0)=215$

梯度为

$$\Delta f(x)=\\ [2(x_1+10x_2)+40(x_1-x_4)^3,\\ 20(x_1+10x_2)+4(x_2-2x_3)^3,\\ 10(x_3-x_4)-8(x_2-x_3)^3,\\ -10(x_3-x_4)-40(x_1-x_4)^3]$$

黑塞矩阵 $F(x)$为

$$a=[2+120(x_1-x_4)^2, 20, 0, -120(x_1-x_4)^2]$$

$$b=[20, 200+12(x_2-2x_3)^2, -24(x_2-2x_3)^2, 0]$$

$$c=[0,-24(x_2-2x_3)^2, 10+48(x_2-2x_3)^2, -10]$$

$$d=[-120(x_1-x_4)^2,0, -10, 10+120(x_1-x_4)^2]$$

$$F(x)=[a,b,c,d]^T$$

第一次迭代

$$g^0=\Delta f=[306,-144,-2,-310]$$

$$a=[482, 20, 0, -480]$$

$$b=[20, 212,-24,0]$$

$$c=[0,-24,58,-10]$$

$$d=[-480,0,-10,490]$$

$$F(x^0)=[a,b,c,d]^T$$

这个时候很容易求的$F(x^0)^{-1}$

进而求得

$$F(x^0)^{-1}g^0=[1.4127, -0.8413, -0.2540, 0.7460]$$

所以

$$x^1=x^0-F(x^0)^{-1}g^0=[1.58, -0.1587, 0.2540, 0.2540]$$

$$f(x^1)=31.8$$

后面这里就不一一列举，都是迭代的过程了，如果你每次都算一下的话，你会发现$f(x)$确实越来越小

$$f(x^2)=6.28$$

$$f(x^3)=1.24$$

这里不要将$f(x^k)$当成x的k次幂哦，是x的第k吃迭代哦

注意事项

如果在单变量下，如果函数的二阶导数小于0，牛顿法是无法收敛到最小值的。与这种情况类似的是，如果目标函数的黑塞矩阵非正定的，牛顿法确定的搜索方向并不一定是目标函数的下降方向。

牛顿方法的修正

看到上面的注意事项，是不是有些修正的方法解决这个问题呢？

首先我来给出相关的定理

定理1

当函数f三阶连续可微，满足$\Delta f(x)=0$,且$F(x)$可逆，那么对于所有与x足够接近$x^0$,牛顿方法是可以正常使用的

定理2
$x^k$为了利用牛顿方法求解目标函数$f(x)$极小值时得到的迭代序列，如果$F(x^k)>0$，且$g^k=\Delta f(x^k) \ne 0$,那么从$x^k$到点$x^{k+1}$的搜索方向

$$d^k=-F(x^k)^{-1}g^k=x^{x+1}-x^{k}$$

是一个下降方向，即存在一个$\bar{\alpha}>0$,使得对于所有$\alpha \in (0,\bar{\alpha})$,都有

$$f(x^k+\alpha d^k)<f(x^k)$$

成立

那么问题又来了，如果初始点离最优值远怎么办呢？让我来看一下牛顿方的的修正方法

如果黑塞矩阵不正定，那么搜索方向$d^k=-F(x^k)^{-1}g^k$可能不会是下降方向

levenberg-martquardt修正

为了克服以上的问题，levenberg-martquardt修正能够解决这一问题，保证每次产生的方向是下降的方向，修正后的迭代公式为

$$x^{k+1}=x^k-(F(x^k)+\mu_kI)^{-1}g^k$$

其中$\mu_k\ge0$

根据定理2，是不是能将上面的修正方法改造成以下形式

$$x^{k+1}=x^k-\alpha_k(F(x^k)+\mu_kI)^{-1}g^k$$

也就是加上一个步长。所以梯度下降中将这个$\alpha$步长合并成一个值。

其中F为对称矩阵，并不要求正定。当$\mu_k$趋近与0，这个修正就趋近与牛顿方法。令$\mu_k$趋近无穷，以上修正方法又会表现出步长较小时梯度方法的特性。在实际应用中一开始可以为$\mu_k$选择一个较小的值，然后逐渐增加，直到出现下降的特性。即$f(x^{k+1})<f(x^k)$

后续

面对牛顿法的问题，后面会有很多方法解决类似问题，但是需要你来一一求解，例如共轭方向法，拟牛顿法，拟牛顿法主要解决牛顿法中黑塞矩阵的近似，拟牛顿方法还包括很多方法，例如DFP算法。BFGS算法等。

结语

将上面的过程还原回来，你基本上就知道每次有人和你说各种梯度下降算法的时候，里面是怎么计算的了，都是依赖目标函数的一阶、二阶导数，算起来很复杂，但是原理相对简单，很多工具是直接支持的，详细是不是也知道为什么用用GPU加速计算了，可以看到上面的计算过程是有大量的矩阵计算的，这就是GPU的作用。