论坛 › 技术讨论 Technology Answers › 最优化方法复习笔记（一）梯度下降法、精确线搜索与非精确 ...

FeastSC 发表于 2021-12-5 06:52

最优化方法复习笔记（一）梯度下降法、精确线搜索与非精确 ...

最优化方法期中考试考得并不理想=_=。
算了~~~多余的时间想给自己来一次非常不地道的哈尔莫斯教学法，算是对大二咸鱼生活的一点补充吧。
大概就是把最优化方法的知识点整理一遍，写一个十篇文章的系列。
如果你也是正在学习最优化方法的本科生或者研究生（或者高中生），欢迎多多交流。<hr/>目录


[*]梯度下降法
[*]精确线搜索
[*]精确线搜索的程序实现
[*]精确线搜索的缺点
[*]非精确线搜索
[*]Goldstein准则
[*]Goldstein准则非精确线搜索算法
[*]Wolfe准则
[*]强Wolfe准则
[*]Wolfe准则非精确线搜索算法
<hr/>梯度下降法

梯度下降法又称为最速下降法，是最优化方法中最基本的一种方法。不过随着ML的热火，梯度下降这个名词估计也满街飞了。
所有的无约束最优化问题无非是在求解如下的无约束优化问题：

https://www.zhihu.com/equation?tex=%5Cmin+_%7Bx%5Cin+R%5En%7D+f%28x%29%5C%5C 如果我们想要通过迭代的方式，将初始点 https://www.zhihu.com/equation?tex=x_0 逐步迭代到最优解所在的点 https://www.zhihu.com/equation?tex=x%5E%2A ，那么我们就会考虑这样的一个搜索点迭代过程：

https://www.zhihu.com/equation?tex=x_%7Bt%2B1%7D%3Dx_t%2B%5Cgamma_t+d_t%5C%5C 其中是我们根据目标函数在的情况确定的搜索方向，而则称为迭代点沿搜索方向的步长。因此，我们需要寻求一种算法，在已知函数和迭代点的情况下，能够算出搜索方向，使得在这个搜索方向下得到的点能够使得变小，即：

https://www.zhihu.com/equation?tex=f%28x_%7Bt%2B1%7D%29%3Cf%28x_t%29%5C%5C 如果只是单纯地希望得到的新迭代点能够使得的值变小，那么新的迭代点很好找，直接通过坐标下降法这种无梯度的方法就可以达到目的。然而梯度下降法希望得到一个在该点下降最快的方向，来使得我们的迭代过程尽可能的高效。
如何确定这个式子中的将是我们所有含梯度下降法的思路出发点。初等微积分的知识告诉我们，某一点处的梯度方向是函数值增长最快的方向，那么梯度的反方向就是函数值下降最快的方向。因此在函数一阶可微的情况下，我们直接求取 https://www.zhihu.com/equation?tex=%5Cnabla+f%28x_t%29 ，那么就是函数下降方向最快的方向了。
需要说明的是，下降最快不代表下降幅度最大下面我们证明这一点：
设目标函数连续可微，将在处Taylor展开：

https://www.zhihu.com/equation?tex=f%28x%29%3Df%28x_t%29%2B%5Cnabla+f%28x_t%29%5ET%28x-x_t%29%2Bo%28%7C%7Cx-x_t%7C%7C%29%5C%5C 令 https://www.zhihu.com/equation?tex=x%3Dx_%7Bt%2B1%7D ，结合 https://www.zhihu.com/equation?tex=x_%7Bt%2B1%7D%3Dx_t%2B%5Cgamma_t+d_t 迭代法可得：

https://www.zhihu.com/equation?tex=f%28x_%7Bt%2B1%7D%29%3Df%28x_t%29%2B%5Cgamma_t+%5Cnabla+f%28x_t%29%5ET+d_t%2Bo%28%7C%7Cx_%7Bt%2B1%7D-x_t%7C%7C%29%5C%5C若我们的迭代过程是切实可行的、能够收敛的，那么很显然有 https://www.zhihu.com/equation?tex=x_%7Bt%2B1%7D-x_t%5Cto+0%28t%5Cto%5Cinfty%29 。因此，我们有： https://www.zhihu.com/equation?tex=f%28x_%7Bt%2B1%7D%29%3Df%28x_t%29%2B%5Cgamma_t%5Cnabla+f%28x_t%29%5ET+d_t 。
为了使得本次迭代能够使得 https://www.zhihu.com/equation?tex=f%28x_%7Bt%2B1%7D%29%3Cf%28x_t%29 ，需要确保随着的增大而减小（的小领域内），即 https://www.zhihu.com/equation?tex=%5Cfrac%7B%5Cpartial+f%7D%7B%5Cpartial+%5Cgamma%7D%3D%5Cnabla+f%28x_t%29%5ET+d_t%3C0 ，而且我们希望下降得尽可能快，也就是我们想要的满足：

https://www.zhihu.com/equation?tex=d_t%5E%2A%3D%5Carg%5Cmin_%7Bd_t%7D%5Cfrac%7B%5Cpartial+f%7D%7B%5Cpartial+%5Cgamma%7D%3D%5Carg%5Cmax_%7Bd_t%7D-%5Cfrac%7B%5Cpartial+f%7D%7B%5Cpartial+%5Cgamma%7D%5C%5C 由Cauchy不等式：

https://www.zhihu.com/equation?tex=-%5Cfrac%7B%5Cpartial+f%7D%7B%5Cpartial+%5Cgamma%7D%3D-%5Cnabla+f%28x_t%29%5ETd_t%5Cle+%7C%7C%5Cnabla+f%28x_t%29%7C%7C%5Ccdot%7C%7Cd_t%7C%7C%5C%5C
根据Cauchy不等式成立的条件，需要与同向。所以我们想要寻找的下降最快的方向 https://www.zhihu.com/equation?tex=d_t%5E%2A 与同向。
因此，梯度下降法只考虑了当前的函数关于下降最快的方向。
于是我们找到了一种可行的搜索方向。因此，梯度下降法也就容易得出了：（此处线搜索会在后面提到）

https://www.zhihu.com/equation?tex=%5Cbegin%7Balign%7D+%E5%B7%B2%E7%9F%A5%26%E8%BF%AD%E4%BB%A3%E7%9A%84%E7%BB%88%E6%AD%A2%E6%9D%A1%E4%BB%B6%E5%8F%82%E6%95%B0%5Cepsilon%E3%80%82%E5%88%9D%E5%A7%8B%E8%BF%AD%E4%BB%A3%E7%82%B9%E4%B8%BAx_0%EF%BC%8C%E9%87%8D%E5%A4%8D%E4%BB%A5%E4%B8%8B%E6%93%8D%E4%BD%9C%3A%5C%5C+%261.%E8%AE%A1%E7%AE%97d_t%3D-%5Cnabla+f%28x_t%29%EF%BC%8C%E8%8B%A5%7C%7Cd_t%7C%7C%3C%5Cepsilon%EF%BC%8C%E8%BF%AD%E4%BB%A3%E7%BB%88%E6%AD%A2%5C%5C+%262.%E9%80%9A%E8%BF%87%E7%BA%BF%E6%90%9C%E7%B4%A2%E7%A1%AE%E5%AE%9A%E6%AD%A5%E9%95%BF%5Cgamma_t%5C%5C+%263.%E9%80%9A%E8%BF%87%E8%BF%AD%E4%BB%A3%E5%BC%8Fx_%7Bt%2B1%7D%3Dx_t%2B%5Cgamma_t+d_t%E6%9B%B4%E6%96%B0%E5%BE%97%E5%88%B0%E4%B8%8B%E4%B8%80%E4%B8%AA%E8%BF%AD%E4%BB%A3%E7%82%B9+%5Cend%7Balign%7D%5C%5C
当然，假设目标函数在搜索空间上是连续的，则终止条件也可以写成 https://www.zhihu.com/equation?tex=%7Cx_%7Bt%2B1%7D-x_t%7C%3C%5Cepsilon 或者上述梯度下降法的描述中，线搜索是什么还没有说。其实线搜索是一个和最优化方法捆绑销售的一个概念。你完全可以把线搜索放在梯度下降法中来理解。
我的理解是这样的：当梯度下降发进行到第二步时，更新迭代式https://www.zhihu.com/equation?tex=f%28x_%7Bt%2B1%7D%29%3Df%28x_t%29%2B%5Cgamma_t+d_t 中我们只有不知道其具体的值，所以我们必须得通过某种方法来确定的值，而确定的方法称为线搜索。为什么叫做线索搜呢？个人理解为是正实数，而正实数在三维空间中张成的搜索空间是一条与坐标轴平行的射线。
我们确定的方式有两种：精确线搜索和非精确线搜索。精确线搜索的目的是找到 https://www.zhihu.com/equation?tex=g%28%5Cgamma%29%3Df%28x_t%2B%5Cgamma+d_t%29 在 https://www.zhihu.com/equation?tex=%5Cgamma%5Cin+R%5E%2B 上的最小值。


如上图，精确线搜得到是一个具体的值，这个值往往可以通过研究 https://www.zhihu.com/equation?tex=g%28%5Cgamma%29%3Df%28x_t%2B%5Cgamma+d_t%EF%BC%89 在 https://www.zhihu.com/equation?tex=%280%2C%2B%5Cinfty%29 上的极值点来确定。但是很多时候 https://www.zhihu.com/equation?tex=g%28%5Cgamma%29 的极值点没有解析解，只有数值解，那么为了确定唯一的最小值点，我们只能遍历的整个搜索空间，但这会极大提高梯度下降法的时间复杂度，此时精确线搜会让我们的优化算法变得极其低效（比如Python的scipy的优化方法子库，默认使用0.618法进行精确线搜索）。这个时候，就需要使用非精确线搜来确定。不同于精确线搜索，非精确线搜不要求一定要在每一次迭代中找到那个使得 https://www.zhihu.com/equation?tex=f%28x_%7Bt%2B1%7D%29%3Df%28x_t%2B%5Cgamma+d_t%29 最小的，而是通过某些非精确线搜准则来找到一个接近最佳搜索步长的步长 https://www.zhihu.com/equation?tex=%5Chat+%5Cgamma ，这个步长能够使得目标函数在该次迭代中下降和差不多的幅度。


如上图，非精确线搜索确定了 https://www.zhihu.com/equation?tex=%5Chat%5Cgamma 的大致区间其实除了以上两种，还有一种最朴素的方法：固定步长。也就是选取一个不变的量（一般很小）作为的值。
其实熟悉机器学习的同学应该发现了，此处的步长和ML中的学习率非常类似，而随着机器学习的发展，业内也提出了一些随着迭代次数动态变化步长的方法，本文就懒得写了=_=了，感兴趣的同学可以看看我之前的拙笔：
<hr/>精确线搜索

精确线搜索的方法比较局限，只适用于能够得到 https://www.zhihu.com/equation?tex=%5Cunderset%7B%5Cgamma%7D%7B%5Carg%5Cmin%7Df%28x_t%2B%5Cgamma+d_t%29 的迭代过程。不过一般的研究都是从简单的函数开始的，继而启发之后的奇思妙想的，对吧？
所以我们可以研究研究简单的函数在梯度下降法中的精确线搜索。下面我们可以研究研究简单的函数正定二次型：

https://www.zhihu.com/equation?tex=f%28x%29%3D%5Cfrac12x%5ETQx%2Bb%5ETx%2Bc%5C%5C
其中是 https://www.zhihu.com/equation?tex=n 维列向量，是实对称正定矩阵， https://www.zhihu.com/equation?tex=b 是与维度相同的列向量， https://www.zhihu.com/equation?tex=c 是实数。
我们记 https://www.zhihu.com/equation?tex=g_t%3D%5Cnabla+f%28x_t%29 。当我们已经得到 https://www.zhihu.com/equation?tex=%5Cnabla+f%28x_t%29%3DQx_t%2Bb 时，就可以开始在的方向上实施精确线搜索，从而得到最优步长了：

https://www.zhihu.com/equation?tex=%5Cbegin%7Baligned%7D+%5Cgamma%5E%2A%26%3D%5Carg%5Cmin_%7B%5Cgamma%7D+f%28x_t%2B%5Cgamma+d_t%29%5C%5C+%26%3D%5Carg%5Cmin_%7B%5Cgamma%7D+f%28x_t-%5Cgamma+g_t%29%5C%5C+%26%3D%5Carg%5Cmin_%7B%5Cgamma%7D+%5CBig%28+%5Cfrac12g_t%5ETQg_t%5Cgamma%5E2-+g_t%5ETg_t%5Cgamma+%2Bf%28x_t%29%5CBig%29%5C%5C+%5Cend%7Baligned%7D%5C%5C
注意到上述函数是关于的二次函数，故最优步长为：

https://www.zhihu.com/equation?tex=%5Cgamma%5E%2A%3D%5Cfrac%7Bg_t%5ET+g_t%7D%7Bg_t%5ETQg_t%7D%5C%5C
因此在对正定二次型做梯度下降时，通过上述上述的精确线搜索得到最优步长后，更新迭代式为：

https://www.zhihu.com/equation?tex=x_%7Bt%2B1%7D%3Dx_t-%5Cfrac%7Bg_t%5ETg_t%7D%7Bg_t%5ETQg_t%7D%28Qx_t%2Bb%29%5C%5C
那么，对于正定二次型来说，其精确线搜的梯度下降法便得到了：

https://www.zhihu.com/equation?tex=%5Cbegn%7Balign%7D+%E5%B7%B2%E7%9F%A5%26%E8%BF%AD%E4%BB%A3%E7%9A%84%E7%BB%88%E6%AD%A2%E6%9D%A1%E4%BB%B6%E5%8F%82%E6%95%B0%5Cepsilon%E3%80%82%E5%88%9D%E5%A7%8B%E8%BF%AD%E4%BB%A3%E7%82%B9%E4%B8%BAx_0%EF%BC%8C%E8%AE%B0g_t%3D%5Cnabla+f%28x_t%29%2C%E9%87%8D%E5%A4%8D%E4%BB%A5%E4%B8%8B%E6%93%8D%E4%BD%9C%3A%5C%5C+%261.%E8%AE%A1%E7%AE%97d_t%3D-%5Cnabla+f%28x_t%29%EF%BC%8C%E8%8B%A5%7C%7Cd_t%7C%7C%3C%5Cepsilon%EF%BC%8C%E8%BF%AD%E4%BB%A3%E7%BB%88%E6%AD%A2%5C%5C+%262.%E8%AE%A1%E7%AE%97%E7%B2%BE%E7%A1%AE%E7%BA%BF%E6%90%9C%E7%B4%A2%E7%9A%84%E6%AD%A5%E9%95%BF%5Cgamma_t%3D%5Cfrac%7Bg_t%5ETg_t%7D%7Bg_t%5ETQg_t%7D%5C%5C+%263.%E9%80%9A%E8%BF%87%E8%BF%AD%E4%BB%A3%E5%BC%8Fx_%7Bt%2B1%7D%3Dx_t%2B%5Cgamma_t+d_t%E6%9B%B4%E6%96%B0%E5%BE%97%E5%88%B0%E4%B8%8B%E4%B8%80%E4%B8%AA%E8%BF%AD%E4%BB%A3%E7%82%B9++%5Cend%7Balign%7D%5C%5C
<hr/>精确线搜索的程序实现

好吧，让我们假设这个方法能够收敛到真实的全局最小值，且在任意给定的初始迭代点，这个优化方法都能确保迭代序列最终收敛到全局最小值点（也就是梯度下降法具有全局收敛性），我想在下一篇文章中论述梯度下降法的全局收敛性和收敛速率。此处先假设我们的方法可以达到预期的效果。
那我们可以使用Python的numpy和matplotlib子库来编程实现对正定二次型函数使用精确线搜索的梯度下降法，并将搜索过程可视化：
假设我们需要优化的目标如下：

https://www.zhihu.com/equation?tex=f%28x%29%3D%5Cfrac12x%5ETQx%2Bb%5ETx%2CQ%3D%5Cbegin%7Bpmatrix%7D10%26-9%5C%5C-9%2610%5Cend%7Bpmatrix%7D%2Cb%3D%284%2C-15%29%5ET%5C%5C
先引入需要的库：
import numpy as np
import matplotlib.pyplot as plt我们需要申明函数中的 https://www.zhihu.com/equation?tex=Q%2Cb 还有原本的函数和函数梯度 https://www.zhihu.com/equation?tex=%5Cnabla+f 的映射func和gradient。
直接拿之前的作业代码了，懒得把注释写成中文了=_=Q = np.array([, [-9, 10]], dtype="float32")
b = np.array(, dtype="float32").reshape([-1, 1])
# function and its gradient defined in the question
func = lambda x: 0.5 * np.dot(x.T, np.dot(Q, x)).squeeze() + np.dot(b.T, x).squeeze()
gradient = lambda x: np.dot(Q, x) + b为了检验迭代点的可靠程度，我们需要先计算出这个二次型的最优点：

https://www.zhihu.com/equation?tex=x%5E%2A%3D-Q%5E%7B-1%7Db%3D%285%2C+6%29%5ET%5C%5C
于是，我们可以申明这个最优点：
x_0 = np.array().reshape([-1, 1])然后编写精确线搜的梯度下降法：
# GD algorithm
def gradient_descent(start_point, func, gradient, epsilon=0.01):
    """
    :param start_point: start point of GD
    :param func: map of plain function
    :param gradient: gradient map of plain function
    :param epsilon: threshold to stop the iteration
    :return: converge point, # iterations
    """
    assert isinstance(start_point, np.ndarray)# assert that input start point is ndarray
    global Q, b, x_0   # claim the global varience
    x_k_1, iter_num, loss = start_point, 0, []
    xs =

    while True:
      g_k = gradient(x_k_1).reshape([-1, 1])
      if np.sqrt(np.sum(g_k ** 2)) < epsilon:
            break
      alpha_k = np.dot(g_k.T, g_k).squeeze() / (np.dot(g_k.T, np.dot(Q, g_k))).squeeze()
      x_k_2 = x_k_1 - alpha_k * g_k
      iter_num += 1
      xs.append(x_k_2)
      loss.append(float(np.fabs(func(x_k_2) - func(x_0))))
      if np.fabs(func(x_k_2) - func(x_k_1)) < epsilon:
            break
      x_k_1 = x_k_2
    return xs, iter_num, loss函数准备好后，我们假设此处的迭代初值为 https://www.zhihu.com/equation?tex=x_0%3D%284%2C4%29%5ET ，进行梯度下降法，并可视化迭代过程：
x0 = np.array(, dtype="float32").reshape([-1, 1])
xs, iter_num, loss = gradient_descent(start_point=x0,
                                     func=func,
                                     gradient=gradient,
                                     epsilon=1e-6)
print(xs[-1])        # last point of the sequence
plt.style.use("seaborn")
plt.figure(figsize=)
plt.plot(loss)
plt.xlabel("# iteration", fontsize=12)
plt.ylabel("Loss: $|f(x_k) - f(x^*)|$", fontsize=12)
plt.yscale("log")
plt.show()out:
[
]

可以看到最终迭代点到达了目标 https://www.zhihu.com/equation?tex=%285%2C+6%29%5ET 。当纵坐标取时，收敛速率几乎是线性的。这些都说明了梯度下降法用于优化貌似是可行的，而且还有不错的收敛速率（很快）。
收敛速率定义为 https://www.zhihu.com/equation?tex=%7C%5Cfrac%7Bf%28x_%7Bk%2B1%7D%29-f%28x%5E%2A%29%7D%7Bf%28x_k%29-f%28x%5E%2A%29%7D%7C ，其中 http://www.zhihu.com/equaton?tex=x%5E%2A 是真实的最优点但是一切都不能高兴得太早。我们可以多试几组不同的迭代初值，然后看看结果会怎么样。我们再取四个迭代点： https://www.zhihu.com/equation?tex=%280%2C0%29%2C%280.4%2C0%29%2C%2810%2C0%29%2C%2811%2C0%29 。
# create the list of all starting point x_0
starting_points = ).astype(np.float).reshape([-1, 1]) for num in ]

plt.figure(dpi=150)

xss = []
# implement GD
for idx, start_point in enumerate(starting_points):
    xs, iter_num, losses = gradient_descent(start_point, func, gradient, epsilon=1e-6)
    target_point = xs[-1]
    xss.append(xs)
    # plot the losses of $|f(x_k) - f(x^*)|$
    plt.plot(np.arange(len(losses)), np.array(losses), label=f"start point: ({start_point}, {start_point})")

    loss = np.fabs(func(target_point) - func(x_0))
    print(f"{idx + 1}: start point:{np.round(start_point, 5).tolist()}, "
          f"point after GD:{np.round(target_point, 5).tolist()}, "
          f"loss:{np.round(loss, 16)}, # iterations: {iter_num}")
    print("-" * 60)

plt.grid(True)
plt.legend()
plt.xlabel("# iteration", fontsize=12)
plt.ylabel("Loss: $|f(x_k) - f(x^*)|$", fontsize=12)
plt.yscale("log")
plt.title("Loss-iteration given to different starting points of GD", fontsize=18)
plt.show()out:
1: start point:[, ], point after GD:[, ], loss:2.9518850226e-06, # iterations: 60
------------------------------------------------------------
2: start point:[, ], point after GD:[, ], loss:1.6873629107e-06, # iterations: 42
------------------------------------------------------------
3: start point:[, ], point after GD:[, ], loss:1.33369e-11, # iterations: 4
------------------------------------------------------------
4: start point:[, ], point after GD:[, ], loss:0.0, # iterations: 1
------------------------------------------------------------

可以看到，虽然对于不同的初值点，其收敛速率都是线性的，但是随着迭代初值的不同，收敛速率不相同。甚至对于 https://www.zhihu.com/equation?tex=%2811%2C0%29%5ET 来说，直接一步迭代就直接到了最优点。
为了更好地让读者明晓迭代初值对于过程的影响，我们可以把上述过程在二维平面内可视化出来：
plt.figure(dpi=150)
X = np.linspace(-2, 12, 200)
Y = np.linspace(-2, 12, 200)
XX, YY = np.meshgrid(X, Y)
Z = , YY], dtype="float32").reshape([-1, 1])).tolist() for i in range(200) for j in range(200)]
Z = np.array(Z).reshape()
plt.contourf(XX, YY, Z, cmap=plt.cm.BuGn)

plt.annotate(f"$(5.0, 6.0)$",
               xy=(5, 6),
               xytext=(5 - 2, 6 + 2),
               arrowprops={
                     "color" : "black",
                     "shrink" : 0.1,
                     "width" : 0.6
               })

# plot the scatter
for idx, start_point in enumerate(starting_points):
    xx = for i, _ in enumerate(xss)]
    yy = for i, _ in enumerate(xss)]
    plt.plot(xx, yy, "o--", label=f"start point: ({start_point}, {start_point})")
    # add some tips for start point
    plt.annotate(f"$({start_point}, {start_point})$",
               xy=(start_point, start_point),
               xytext=(start_point - 1.5, start_point + idx + 2),
               arrowprops={
                     "color" : "black",
                     "shrink" : 0.1,
                     "width" : 0.6
               })

plt.grid(True)
plt.title("Line Search For Two-dimensional Diagrams", fontsize=18)
plt.xlabel("$x_1$", fontsize=12)
plt.ylabel("$x_2$", fontsize=12)
plt.legend()
plt.show()out:


可以看到靠近椭圆（等高线是一个椭圆族）的 https://www.zhihu.com/equation?tex=%280%2C0%29 和 https://www.zhihu.com/equation?tex=%280.4%2C0%29 是以锯齿状的轨迹蛇形靠近最优点的，而 https://www.zhihu.com/equation?tex=%2810%2C0%29 和则是几乎一步就跳到了最优点旁边。这张图就很好解释了为什么四个迭代点的迭代步数相差那么大了。
精确线搜索的缺点

事实上，从我们最开始推导梯度下降法时，我们在某一迭代点处选择最优的下降方向就有一定的问题：我们只追求了 https://www.zhihu.com/equation?tex=%7C%5Cfrac%7B%5Cpartial+f%7D%7B%5Cpartial+%5Cgamma%7D%7C 的最大，也就是该点下降“最陡”的方向，但是最陡可不意味着一定能下降得最多，毕竟所谓的“最陡”也只是 https://www.zhihu.com/equation?tex=x_k 这一点的小领域内的最陡，超出这个小领域可就不生效了。而且加上精确线搜的要求，使得整个算法变得很不灵活，因为程序会每步都强行找到 https://www.zhihu.com/equation?tex=g%28%5Cgamma%29%3Df%28x_k%2B%5Cgamma+d_t%29 的最小值。这也就使得精准线搜索的梯度下降法在一些稍显复杂的函数优化问题上会迭代非常多的步骤才能找到最优点，甚至有时还找不到。
比如还是拿简单的二次型来说，随着条件数（条件数大小为矩阵的最大特征值与最小特征值的比值）的增大，等高线的椭圆族会越来越扁，那么靠近椭圆长轴的迭代初值迭代到最优点会更加困难；或者说，精确线搜的梯度下降法的迭代次数会对迭代初值的选取越来越敏感。这可不是我们希望的，毕竟实际工程中，迭代点的选取很多情况下都是随机的。
读者可是尝试修改上述二次型的的条件数的大小，看看会有什么变化既然梯度下降法并不是下降幅度最大的方法，那么很多时候我们也没有必要花大力气把最优的迭代步长找到，找到一个差不多的就行。于是乎，引出下面的非精确线搜。
<hr/>非精确线搜索

之前的精确线搜索就是解决单变量问题

https://www.zhihu.com/equation?tex=g%28%5Cgamma%29%3Df%28x_k%2B%5Cgamma+d_k%29%5C%5C 的精确极小值点。
这么做不仅计算量大，而且很多时候过于精确的迭代过程也没有必要。因此，我们可以在保证函数下降的前提下放宽对的要求，从而降低算法的时间复杂度。
Goldstein准则

基本思路：通过迭代点处引出的两条直线来约束一段可供取值的区间，具体可以看如下的图：


从 https://www.zhihu.com/equation?tex=%280%2Cf%28x_k%29%29 处引出的两条射线，我们希望我们选取的于原单值函数上的映射值位于在这两条直线上的映射值之间，由是构成它们约束的区间，那么这一步我们要寻找的步长就位于之间。
这两条线的构成的约束也很好写，设 https://www.zhihu.com/equation?tex=%5Cvarphi%28%5Cgamma%29%3Df%28x_k%2B%5Cgamma+d_k%29 ，则上述两条线的约束可写成：

https://www.zhihu.com/equation?tex=%5Cbegin%7Balign%7D+%5Cvarphi%28%5Cgamma_k%29%26%5Cle+%5Cvarphi%280%29%2B%5Crho%5Cgamma_k%5Cvarphi%27%280%29%5Cquad%5Cquad%5Cquad%5Cquad%5C+%5C+%E2%91%A0%5C%5C+%5Cvarphi%28%5Cgamma_k%29%26%5Cge+%5Cvarphi%280%29%2B%281-%5Crho%29%5Cgamma_k%5Cvarphi%27%280%29%5Cquad%5Cquad%E2%91%A1+%5Cend%7Balign%7D%5C%5C 其中 https://www.zhihu.com/equation?tex=0%3C%5Crho%3C%5Cfrac12 .
结合上图可知，满足①式的构成区间 https://www.zhihu.com/equation?tex=%280%2C+c%5D ，而满足②式的构成区间 https://www.zhihu.com/equation?tex=%5Bb%2Ca%5D ，因此两个式子构成的约束为 https://www.zhihu.com/equation?tex=%5Cgamma_k%5Cin%5Bb%2Cc%5D 。
其实取这两条直线构成约束的原因也很简单：

[*]①式保证了取到的步长能够 https://www.zhihu.com/equation?tex=f%28x_%7Bk%2B1%7D%29%3Cf%28x_k%29 成立，也就是保证了充分的下降条件。
[*]②式保证了取到的步长不会特别小，过小的步长会使得 https://www.zhihu.com/equation?tex=f%28x_%7Bk%2B1%7D%29%5Capprox+f%28x_k%29 ，从而该步迭代失去了意义。
Goldstein准则非精确先搜索算法

于是，我们可以根据①②式得到 Goldstein准则非精确先搜索算法：

https://www.zhihu.com/equation?tex=%5Cbegin%7Balign%7D+1.%26%E9%80%89%E5%8F%96%E5%88%9D%E5%A7%8B%E6%95%B0%E6%8D%AE%2C%E5%9C%A8%E5%88%9D%E5%A7%8B%E6%90%9C%E7%B4%A2%E5%8C%BA%E9%97%B4%5B0%2C%5Csup%28%5Cgamma%29%5D%E4%B8%AD%E9%80%89%E5%8F%96%E5%88%9D%E5%A7%8B%E7%82%B9%5Cgamma_0%2C%E6%90%9C%E7%B4%A2%E5%8C%BA%E9%97%B4%5Ba_0%2Cb_0%5D%5C%5C+%26%E8%AE%A1%E7%AE%97%5Cvarphi%280%29%2C%5Cvarphi%27%280%29%2C%E7%BB%99%E5%87%BA%5Crho%5Cin%280%2C%5Cfrac12%29%2C+t%3E1%2C+k%3D0.%5C%5C+2.%26%E8%8B%A5%5Cgamma_k%E6%BB%A1%E8%B6%B3%E2%91%A0%E5%BC%8F%2C%E5%88%99%E8%BD%AC%E7%C%AC3%E6%AD%A5%3B%5C%5C+%26%E5%90%A6%E5%88%99%E4%BB%A4a_%7Bk%2B1%7D%3Da_k%2Cb_%7Bk%2B1%7D%3D%5Cgamma_k%2C%E8%BD%AC%E7%AC%AC4%E6%AD%A5.%5C%5C+3.%26%E8%8B%A5%5Cgamma_k%E6%BB%A1%E8%B6%B3%E2%91%A1%E5%BC%8F%2C%E5%88%99%E8%BE%93%E5%87%BA%5Cgamma_k%2C%E7%BB%93%E6%9D%9F%E8%BF%AD%E4%BB%A3%3B%5C%5C+%26%E5%90%A6%E5%88%99%E4%BB%A4a_%7Bk%2B1%7D%3D%5Cgamma_k%2Cb_%7Bk%2B1%7D%3Db_k.%5C%5C+%26%E8%8B%A5b_%7Bk%2B1%7D%3C%5Csup%28%5Cgamma%29%2C%E8%BD%AC%E7%AC%AC4%E6%AD%A5%3B%E5%90%A6%E5%88%99%2C%E4%BB%A4%5Cgamma_%7Bk%2B1%7D%3Dt%5Cgamma_k%2Ck%3Dk%2B1%EF%BC%8C%E8%BD%AC%E7%AC%AC2%E6%AD%A5.%5C%5C+4.%26%E4%BB%A4%5Cgamma_%7Bk%2B1%7D%3D%5Cfrac%7Ba_%7Bk%2B1%7D%2Bb_%7Bk%2B1%7D%7D%7B2%7D%2Ck%3Dk%2B1%2C%E8%BD%AC%E7%AC%AC2%E6%AD%A5++%5Cend%7Balign%7D%5C%5C
算法本身就是通过二分法来搜寻
Wolfe准则

Goldstein准则有一个很大问题，就是其约束的区间内可能没有我们最终想要找的最优点。



此处的α就是下面的γ

还是刚才那张图，极小值点在 https://www.zhihu.com/equation?tex=%5Be%2Cb%5D 之间，但是该步确定的区间却为，很显然 https://www.zhihu.com/equation?tex=%5Cgamma%5E%2A%5Cnot%5Cin+%5Bb%2Cc%5D 。为了克服Goldstein算法的缺点，Wolfe提出了使用以下的条件来代替Goldstein中的②式：

https://www.zhihu.com/equation?tex=g_%7Bk%2B1%7D%5ETd_k%5Cge+%5Csigma+g_k%5ET+d_k%2C%5Csigma%5Cin%28%5Crho%2C1%29%5C%5C 也就是

https://www.zhihu.com/equation?tex=%5Cvarphi%27%28%5Cgamma_k%29%5Cge+%5Csigma+%5Cvarphi%27%280%29%2C%5Csigma%5Cin%28%5Crho%2C1%29%5C%5C
几何解释：上述条件刻画了在可接受点处切线的斜率大于或者等于初始斜率的倍（注意初始斜率小于0）。在图中，这个切点与起始点都在极值点的同侧，因此这个条件直观上可以保证将极值点包裹在约束的区间内。这个条件也叫作曲率条件。因此，我们得到了Wolfe准则：

https://www.zhihu.com/equation?tex=%5Cbegin%7Balign%7D+%5Cvarphi%28%5Cgamma_k%29%26%5Cle+%5Cvarphi%280%29%2B%5Crho%5Cgamma_k%5Cvarphi%27%280%29%5Cquad+%E2%91%A2%5C%5C+%5Cvarphi%27%28%5Cgamma_k%29%26%5Cge+%5Csigma%5Cvarphi%27%280%29%5Cquad%5Cquad%5Cquad%5Cquad%5Cquad+%E2%91%A3+%5Cend%7Balign%7D%5C%5C 应该指出，由于 https://www.zhihu.com/equation?tex=%5Csigma%5Cvarphi%280%29%5Cle%5Cvarphi%27%28%5Cgamma_k%29 且 https://www.zhihu.com/equation?tex=%5Csigma%5Cvarphi%27%280%29%3C0 ，而精确线搜索的满足 https://www.zhihu.com/equation?tex=%5Cvarphi%27%28%5Cgamma_k%29%3D0 ，所以Wolfe准则实际上是对精确线搜索的近似。但是需要注意的是，既然Wolfe准则是对精确线搜索的近似，我们希望搜索出的满足如下：

https://www.zhihu.com/equation?tex=%5Csigma%5Cvarphi%280%29%5Cle%5Cvarphi%27%28%5Cgamma_k%29%3C0%5C%5C 这样做的话当 https://www.zhihu.com/equation?tex=%5Csigma%5Cto0 时，根据夹逼准则，就会有 https://www.zhihu.com/equation?tex=%5Cvarphi%27%28%5Cgamma_k%29%5Cto0 ，这样就满足真正的近似了。而我们之前的Wolfe准则得到不一定小于0.
而满足上述更强的约束条件的准则就是强Wolfe准则。

强Wolfe准则

强Wolfe准则在Wolfe准则的基础上将约束到小于0，以确保完成真正的对精确线搜索的近似：

https://www.zhihu.com/equation?tex=%5Cbegin%7Balign%7D+%5Cvarphi%28%5Cgamma_k%29%26%5Cle%5Cvarphi%280%29%2B%5Crho%5Cgamma_k%5Cvarphi%27%280%29%5Cquad%E2%91%A4%5C%5C+%7C%5Cvarphi%27%28%5Cgamma_k%29%7C%26%5Cle%5Csigma%7C%5Cvarphi%27%280%29%7C%5Cquad%5Cquad%5Cquad%5Cquad%5C+%5C+%E2%91%A5+%5Cend%7Balign%7D%5C%5C 其中 https://www.zhihu.com/equation?tex=0%3C%5Crho%3C%5Csigma%3C1 .
我们注意到的大小在一定程度上决定了搜索出来的离极值点有多近。越小，搜索出的越精准，但是计算量更大（因为越小，符合要求的组成的区间也会越小，搜索目标小区间当然比搜索大的更加费时）。因此，强Wolfe准则的不能取得太小，否则强Wolfe准则下的非精确线搜索不就和精确线搜索没有区别了吗？
一般来说，会取 https://www.zhihu.com/equation?tex=%5Crho%3D0.1%2C%5Csigma%5Cin%5B0.6%2C+0.8%5D .

Wolfe准则非精确先搜索算法


https://www.zhihu.com/equation?tex=%5Cbegin%7Balign%7D+1.%26%E9%80%89%E5%8F%96%E5%88%9D%E5%A7%8B%E6%95%B0%E6%8D%AE%E3%80%82%E7%BB%99%E5%AE%9A%E5%88%9D%E5%A7%8B%E6%90%9C%E7%B4%A2%E5%8C%BA%E9%97%B4%5B0%2C%5Cgamma_%5Ctext%7Bmax%7D%5D%2C%E7%A1%AE%E5%AE%9A%E5%8F%82%E6%95%B0%5Crho%5Cin%280%2C%5Cfrac12%29%E5%92%8C%5Csigma%5Cin%28%5Crho%2C1%29.%5C%5C+%26%E4%BB%A4%5Cgamma_1%3D0%2C%5Cgamma_2%3D%5Cgamma_%5Ctext%7Bmax%7D%2C%E8%AE%A1%E7%AE%97%5Cvarphi_1%3Df%28x_k%29%2C%5Cvarphi_1%27%3Dg%28x_k%29%5ETd_k.%E5%8F%96%5Cgamma%5Cin%280%2C%5Cgamma_2%29.%5C%5C+2.%26%E8%AE%A1%E7%AE%97%5Cvarphi%3D%5Cvarphi%28%5Cgamma%29%3Df%28x_k%2B%5Cgamma+d_k%29.%E8%8B%A5%5Cvarphi%28%5Cgamma%29-%5Cvarphi_1%5Cle%5Crho%5Cgamma%5Cvarphi_1%27%2C%E8%BD%AC%E7%AC%AC3%E6%D%A5.%5C%5C+%26%E5%90%A6%E5%88%99%2C%E7%94%B1%E4%B8%A4%E7%82%B9%E4%BA%8C%E6%AC%A1%E6%8F%92%E5%80%BC%E5%85%AC%E5%BC%8F%E8%AE%A1%E7%AE%97%5Cbar%7B%5Cgamma%7D%3D%5Cgamma_1%2B%5Cfrac%7B%5Cgamma-%5Cgamma_1%7D%7B2%281%2B%5Cfrac%7B%5Cvarphi_1-%5Cvarphi%7D%7B%28%5Cgamma-%5Cgamma_1%29%5Cvarphi_1%27%7D%29%7D.%5C%5C+%26%E4%BB%A4%5Cgamma_2%3D%5Cgamma%2C%5Cgamma%3D%5Cbar%7B%5Cgamma%7D.%E8%BD%AC%E7%AC%AC2%E6%AD%A5.%5C%5C+3.%26%E8%AE%A1%E7%AE%97%5Cvarphi%27%3D%5Cvarphi%28%5Cgamma%29%3Dg%28x_k%2B%5Cgamma+d_k%29%5ETd_k.%E8%8B%A5%5Cvarphi%27%5Cge%5Csigma%5Cvarphi_1%27%2C%E5%88%99%E4%BB%A4%5Cgamma_k%3D%5Cgamma%2C%E8%BE%93%E5%87%BA%5Cgamma_k%2C%E5%81%9C%E6%AD%A2%E8%BF%AD%E4%BB%A3%3B%5C%5C+%26%E5%90%A6%E5%88%99%2C%E7%94%B1%E4%B8%A4%E7%82%B9%E4%BA%8C%E6%AC%A1%E6%8F%92%E5%80%BC%E5%85%AC%E5%BC%8F%E8%AE%A1%E7%AE%97%5Cbar%7B%5Cgamma%7D%3D%5Cgamma%2B%5Cfrac%7B%28%5Cgamma-%5Cgamma_1%29%5Cvarphi%27%7D%7B%5Cvarphi_1%27-%5Cvarphi%27%7D.%5C%5C+%26%E4%BB%A4%5Cgamma_1%3D%5Cgamma%2C%5Cvarphi_1%3D%5Cvarphi%2C+%5Cvarphi_1%27%3D%5Cvarphi%27%2C%5Cgamma%3D%5Cbar%7B%5Cgamma%7D%2C%E8%BD%AC%E7%AC%AC2%E6%AD%A5.+%5Cend%7Balign%7D%5C%5C

下面直接调用Python的scipy.optimize子库来实现强Wolfe准则：
def gradient_descent_wolfe(start_point, func, gradient, epsilon=1e-6):
    """
    :param start_point: start point of GD
    :param func: map of plain function
    :param gradient: gradient map of plain function
    :param epsilon: threshold to stop the iteration
    :return: converge point, # iterations
    """
    assert isinstance(start_point, np.ndarray)# assert that input start point is ndarray
    global Q, b, x_0# claim the global varience
    x_k_1, iter_num, loss = start_point, 0, []
    xs =

    while True:
      g_k = gradient(x_k_1).reshape([-1, 1])
      if np.sqrt(np.sum(g_k ** 2)) < epsilon:
            break
      alpha_k = linesearch.line_search_wolfe2(f=func,
                                                myfprime=lambda x: np.reshape(np.dot(Q, x) + b, ),
                                                xk=x_k_1,
                                                pk=-g_k)
      if alpha_k == None:
            break
      elif isinstance(alpha_k, float):
            alpha_k = alpha_k
      else:
            alpha_k = alpha_k.squeeze()

      x_k_2 = x_k_1 - alpha_k * g_k
      iter_num += 1
      xs.append(x_k_2)
      loss.append(float(np.fabs(func(x_k_2) - func(x_0))))
      if np.fabs(func(x_k_2) - func(x_k_1)) < epsilon:
            break
      x_k_1 = x_k_2
    return xs, iter_num, lossscipy.optimize封装了许多最优化中的算法，比如Wolfe非精确线搜索算法，后面的共轭梯度法都有对应的API。不了解的同学，可以去看看源代码了解一下。对于程序的这个片段：
      if alpha_k == None:
            break
      elif isinstance(alpha_k, float):
            alpha_k = alpha_k
      else:
            alpha_k = alpha_k.squeeze()稍作说明。在梯度下降法实施的过程中，随着迭代点逐步收敛到最优点，为了保证函数下降的可行的步长组成的区间会越来越小。因此，在迭代的结尾时，强Wolfe算法不一定能够找到可行的，也就是算法无法收敛，如果算法无法收敛，则alpha_k==None。为了程序的鲁棒性，我们需要判断一下，如果alpha_k==None，则说明迭代到末尾了，直接break就完事了。
out:
[]


强Wolfe准则非精确线搜的梯度下降法的下降曲线

可以看到非精确线搜刚开始貌似下降缓慢，但整体还是保证了纵坐标取后的线性下降速率。
同上，使用 https://www.zhihu.com/equation?tex=%280%2C0%29%2C%280.4%2C0%29%2C%2810%2C0%29 和作为四个迭代初值，对这四个迭代初值使用强Wolfe非精确线搜索的梯度下降，打印结果，并可视化：
# create the list of all starting point x_0
starting_points = ).astype(np.float).reshape([-1, 1]) for num in ]

plt.figure(dpi=150)

xss = []
# implement GD
for idx, start_point in enumerate(starting_points):
    xs, iter_num, losses = gradient_descent_wolfe(start_point, func, gradient, epsilon=1e-6)
    target_point = xs[-1]
    xss.append(xs)
    # plot the losses of $|f(x_k) - f(x^*)|$
    plt.plot(np.arange(len(losses)), np.array(losses), label=f"start point: ({start_point}, {start_point})")

    loss = np.fabs(func(target_point) - func(x_0))
    print(f"{idx + 1}: start point:{np.round(start_point, 5).tolist()}, "
          f"point after GD:{np.round(target_point, 5).tolist()}, "
          f"loss:{np.round(loss, 16)}, # iterations: {iter_num}")
    print("-" * 60)

plt.grid(True)
plt.legend()
plt.xlabel("# iteration", fontsize=12)
plt.ylabel("Loss: $|f(x_k) - f(x^*)|$", fontsize=12)
plt.yscale("log")
plt.title("Loss-iteration given to different starting points of GD", fontsize=18)
plt.show()out:
1: start point:[, ], point after GD:[, ], loss:2.9518850226e-06, # iterations: 60
------------------------------------------------------------
2: start point:[, ], point after GD:[, ], loss:1.6873629107e-06, # iterations: 42
------------------------------------------------------------
3: start point:[, ], point after GD:[, ], loss:0.0, # iterations: 3
------------------------------------------------------------
4: start point:[, ], point after GD:[, ], loss:0.0, # iterations: 1
------------------------------------------------------------

plt.figure(dpi=150)
X = np.linspace(-2, 12, 200)
Y = np.linspace(-2, 12, 200)
XX, YY = np.meshgrid(X, Y)
Z = , YY], dtype="float32").reshape([-1, 1])).tolist() for i in range(200) for j in range(200)]
Z = np.array(Z).reshape()
plt.contourf(XX, YY, Z, cmap=plt.cm.BuGn)

plt.annotate(f"$(5.0, 6.0)$",
               xy=(5, 6),
               xytext=(5 - 2, 6 + 2),
               arrowprops={
                     "color" : "black",
                     "shrink" : 0.1,
                     "width" : 0.6
               })

# plot the scatter
for idx, start_point in enumerate(starting_points):
    xx = for i, _ in enumerate(xss)]
    yy = for i, _ in enumerate(xss)]
    plt.plot(xx, yy, "o--", label=f"start point: ({start_point}, {start_point})")
    # add some tips for start point
    plt.annotate(f"$({start_point}, {start_point})$",
               xy=(start_point, start_point),
               xytext=(start_point - 1.5, start_point + idx + 2),
               arrowprops={
                     "color" : "black",
                     "shrink" : 0.1,
                     "width" : 0.6
               })

plt.grid(True)
plt.title("Line Search For Two-dimensional Diagrams", fontsize=18)
plt.xlabel("$x_1$", fontsize=12)
plt.ylabel("$x_2$", fontsize=12)
plt.legend()
plt.show()

to be continued...

下一章传送门：

Zephus 发表于 2021-12-5 07:02

请问作者用的是哪一本最优化教材嘞？

acecase 发表于 2021-12-5 07:12

我们这门课没教材[捂脸]

unityloverz 发表于 2021-12-5 07:13

学弟你好强 请问贵校是哪所学校
[害羞]

RecursiveFrog 发表于 2021-12-5 07:21

翠屏山男子技术学院（狗头）

RecursiveFrog 发表于 2021-12-5 07:29

不应该是b的转置gty吗

RedZero9 发表于 2021-12-5 07:37

你在说哪一部分？

BlaXuan 发表于 2021-12-5 07:39

wolfe条件与强wolfe条件能保证最小值在区间内吗？

ainatipen 发表于 2021-12-5 07:49

极小值[飙泪笑]

zt3ff3n 发表于 2021-12-5 07:58

好问题，从夹逼结果来看，强Wolfe准则是可以保证的。不过这个我没看过相关证明，建议去Google上搜搜wolfe。

查看完整版本: 最优化方法复习笔记（一）梯度下降法、精确线搜索与非精确 ...