本文最后更新于2020年4月18日,已超过 5 个月没更新!


优化算法 是在面对没有最优解或计算最优解需要很大计算量的问题时,利用迭代的思想来尽可能的逼近问题的最优解的方法。

近期学习激光SLAM理论知识,其中用到了一些优化算法,然而当年计算方法那门课没有太重视,所以对这些优化算法都是似懂非懂的,因此专门整理一下常用的几种优化算法,巩固一下理论基础。

1. 梯度下降法(Gradient descent)

1.1 简述

梯度下降法是一种一阶最优化算法,也是最为常用的优化方法。简单来说就是一种寻找目标函数最小化的方法。
梯度下降法的实现简单,当目标函数是凸函数时,梯度下降法的解是全局解。一般情况下,其解不保证是全局最优解,梯度下降法的速度也未必是最快的。梯度下降法的优化思想是用当前位置负梯度方向作为搜索方向,越接近目标值,步长越小,前进越慢。

1.2 数学描述

如果实值函数F(x)在点a处可微且有定义,那么函数F(x)a点沿着梯度相反方向-{\bigtriangledown}F(a)下降最多。
因此,若

    \[b = a - \gamma{\bigtriangledown}F(a)\]

对于\gamma > 0为一个够小数值时成立,则F(a) \ge F(b)
考虑到这一点,我们可以从函数F(x)的局部最小值的初始估计x_0出发,并考虑如下序列x_0,x_1,x_2,...使得:

    \[x_{n+1} = x_n - {\gamma}_n{\bigtriangledown}F(x_n), n \ge 0\]

因此可得到:

    \[F(x_0) \ge F(x_1) \ge F(x_2) \ge \cdot \cdot \cdot\]

顺利的话序列(x_n)收敛到期望的局部最小值,每次迭代步长\gamma可以改变。


上图表示了这一过程,假设F(x)定义在平面上,并且函数图像是一个碗形。蓝色的曲线是等高线(水平线),即函数F(x)为常数的集合构成的曲线。红色的箭头指向该点梯度的反方向。(一点处的梯度方向与通过该点的等高线垂直)。沿着梯度下降方向,最终到达碗底,即函数F(x)局部最小值。

1.3 常用梯度下降算法

  • 批量梯度下降算法(batch gradient descent,BGD)
  • 随机梯度下降算法(stochastic gradient descent,SGD)
  • 小批量梯度下降算法(mini-batch gradient descent,MBGD)
  • 动量优化(Momentum optimization)
  • NAG(Nesterov Accelerated Gradient)
  • AdaGrad
  • Adadelta
  • RMSprop
  • Adam(Adaptive moment estimation)

1.4 代码实现

求解函数f(x) = 3x^2 - 9x + 6的最小值。

# 简单的梯度下降法示例
# 目标函数
def f(x):
    return 3*x**2-9*x+6
# 目标函数一阶导
def df(x):
    return 6*x-9
# 梯度下降法
def gradient_descent(grad, cur_x=0.1, learning_rate=0.01, precision=0.0001, max_iters=10000):
    for i in range(max_iters):
        grad_cur = grad(cur_x)
        if abs(grad_cur) < precision:
            break  # 当梯度趋近为 0 时,视为收敛
        cur_x = cur_x - grad_cur * learning_rate
        print("第", i, "次迭代:x =", cur_x)

    print("局部最小值点 x =", cur_x)
    return cur_x

if __name__ == '__main__':
    print("局部最小值为: ",f(gradient_descent(df, cur_x=10, learning_rate=0.2, precision=0.000001, max_iters=10000)))

1.5 扩展链接

常见的梯度下降算法

2. 牛顿法(Newton's method)

2.1 简述

牛顿法(Newton's method)的基本思想是利用迭代点处的一阶导数(梯度)和二阶导数(Hessen矩阵)对目标函数进行二次函数近似,然后把二次模型的极小点作为新的迭代点,并不断重复这一过程,直至求得满足精度的近似极小值。牛顿法的速度相当快,而且能高度逼近最优值。牛顿法分为基本的牛顿法和全局牛顿法。

2.2 数学描述

选择一个接近函数f(x)零点的x_0,计算相应的f(x_0)和切线斜率f'(x_0)。之后计算穿过点(x_0,f(x_0))并且斜率为f'(x_0)的直线和x轴的交点的x坐标,也就是求如下方程的解:

    \[0 = {(x - x_0)}\cdot f'(x_0) + f(x_0)\]

将新求得的点的x坐标命名为x_1,通常x_1会比x_0更接近方程f(x)=0的解。因此我们现在可以利用x_1开始下一轮迭代。迭代公式可化简为如下所示:

    \[x_{n+1} = x_n + \frac{f(x_n)}{f'(x_n)}\]

已有证明牛顿迭代法的二次收敛必须满足以下条件:

  • f'(x) \neq 0
  • 对于所有x \in I,其中I为区间[\alpha - r , \alpha +r],且x_0在区间其中I内,即r \ge |a - x_0|
  • 对于所有x \in If''(x)是连续的;
  • x_0足够接近根\alpha

2.3 基本牛顿法流程

  1. 给定终止误差值0 < \varepsilon \ll 1,初始点x_0 \in R^n,令k = 0
  2. 计算g_k = {\bigtriangledown}f(x_k),若||g_k|| \le \varepsilon,则停止,输出x* \approx x_k
  3. 计算G_k = {{\bigtriangledown}^2}f(x_k),并求解线性方程组得解d_k : {G_k}d = -g_k
  4. x_{k+1} = x_k + d_kk=k+1,转向第二步,不断进行迭代。

2.4 全局牛顿法

由于基本牛顿法初始点需要足够“靠近”极小点,否则,有可能会导致算法不收敛。因此引入了全局牛顿法。

2.4.1 流程

  1. 给定终止误差值0 \le \varepsilon \ll 1\delta \in (0,1)\sigma \in (0,0.5),初始点x_0 \in R^n,令k=0
  2. 计算g_k = {\bigtriangledown}f(x_k),若||g_k|| \le \varepsilon,则停止,输出x* \approx x_k
  3. 计算G_k = {{\bigtriangledown}^2}f(x_k),并求解线性方程组得解d_k : {G_k}d = -g_k
  4. m_k是不满足下列不等式的最小非负整数m: f(x_k + {\delta}^m{d_k}) \le f(x_k) + {\sigma}{{\delta}^m}{g^T_k}{d_k}
  5. {\alpha}<em>k = {\delta}^{m_k}x</em>{k+1} = x_k + {{\alpha}_k}d_kk=k+1,转向第二步,不断进行迭代。

2.4.2 Armijo搜索

全局牛顿法是基于Armijo的搜索,满足Armijo准则:
给定\beta \in (0,1)\sigma \in (0,0.5),令步长因子{\alpha}_k = {\beta}^{m_k},其中m_k是满足下列不等式的最小非负整数:

    \[f(x_k + {{\beta}^m}{d_k} \le f(x_k) + {\sigma}{{\beta}^m}{g^T_k}{d_k})\]

2.5 代码实现

求解方程3x^2 - 9x + 6 = 0的根。

# 牛顿法简单示例
# 目标函数
def f(x):
    return 3*x**2-9*x+6
# 目标函数一阶导
def df(x):
    return 6*x-9
#牛顿法
def newtons(f,df,x0,e):
    xn = float(x0)
    e_tmp = e+1
    loop = 1
    while e_tmp>e:
        print ('第'+str(loop)+'次迭代:')
        k = df(xn)
        xm = f(xn)
        print ('xn='+str(xn)+',k='+str(k)+',y='+str(xm))
        q = xm/k
        xn = xn-q
        e_tmp = abs(0-f(xn))
        print ('new xn='+str(xn)+',e='+str(e_tmp)+',q='+str(q))
        loop=loop+1
    return xn  

if __name__ == '__main__':
    print ('\n局部解为:  '+str(newtons(f,df,20,0.0001)))

2.6 扩展链接

优化算法——牛顿法(Newton Method)
深度学习中的优化算法


Try and fail, but don't fail to try.