无约束优化问题 — 最速下降法

ainatipen · 发表于 2021-12-24 15:13

本文主要介绍最速下降法，在介绍之前先了解其他一些基本概念。
一、基本概念

1. 无约束优化问题

最速梯度下降法解决的问题是无约束优化问题，而所谓的无约束优化问题就是对目标函数的求解，没有任何的约束限制的优化问题，比如求下方最小值： $minf(x)$
其中的函数 $f:R^n\rightarrow R$ .
求解这类的问题可以分为两大类：最优条件法和迭代法。
最速下降法属于迭代法。

2. 线性搜索

线性搜索定义：在利用迭代的方法解决无约束优化问题：

时，如果我们想要通过迭代的方式，将初始点 $x_0$ 逐步迭代到最优解所在的点 $x^*$ ，那么我们就会考虑一个搜索点迭代过程，其中第k步迭代的公式是：

$x_{k+1} = x_{k} + \alpha_{k} d_{k}$ 。
其中，其中是我们根据目标函数在的情况确定的搜索方向，而 $\alpha_k$ 则称为迭代点沿搜索方向的步长。因此，我们需要寻求一种算法，在已知函数和迭代点的情况下，能够算出搜索方向，使得在这个搜索方向下得到的点能够使得变小。
   而所谓的线性搜索的方法，就是指的是在迭代方向 $d_{k}$ 已知的情况下，求解合适的步长  的问题。关于  的确定精确与否又分为精确线性搜索和非精确线性搜索的方法。

3. 梯度下降法

梯度下降法（Gradient descent），顾名思义，就是自变量沿着梯度向量的反方向进行移动，因为梯度的方向是上升的方向。对于一个 $R^{m} \rightarrow R$ 的函数y=f(x)，初始时 $x=x^{(0)}$ ，我们想要得到函数y=f(x)的极小值点 $x^{*}$ ，如果能够求得f(x)的梯度f(x)，那么我们就可以用梯度下降法进行迭代求极小值的近似解。
记自变量 x 在第k迭代后的值为 $x^{(k)}$ ，则自变量的更新公式为： $x^{(k+1)} = x^{k} - \alpha\cdot∇f(x^{(k)})$ ，其中α
为步长，也被称为学习率（learning rate），控制了梯度下降速度的快慢。

二、最速下降法

1. 概念

最速下降法（Steepest descent）是梯度下降法的一种更具体实现形式，其理念为在每次迭代中选择合适的步长  ，使得目标函数值能够得到最大程度的减少。
每一次迭代，沿梯度的反方向，我们总可以找到一个 $x^{(k+1)} = x^{k} - \alpha_{k}\cdot∇f(x^{(k)})$ ,使得在这个方向 $f(x^{(k+1)})$ 取最小值，即

$\alpha_{(k)} =argmin f( x^{k} - \alpha\cdot∇f(x^{(k)}))$
有意思的是，最速下降法每次更新的轨迹都和上一次垂直。

2. 步骤

下面先给出最速下降法的计算步骤：

其中，确定最优步长 $t_{k}$ 的方法如下：

简单来说：
第1步：迭代法的初始点选择；
第2步：给出终止条件（到达了局部最优解）；
第3步：从当前点选取迭代的方向（梯度负方向）（梯度的负方向是局部下降最快的方向）；
第4步：在确定迭代方向的前提上，确定在该方向上使得函数值最小的迭代步长（选择一个合适的步长是非常最重要的，这直接决定我们的收敛速度）。

3. 缺点

某点的负梯度方向，通常只是在该点附近才具有这种最速下降的性质。
最速下降法利用目标函数一阶梯度进行下降求解，易产生锯齿现象（如下图），在开始几步，目标函数下降较快；但在接近极小点时，收敛速度长久不理想了。特别适当目标函数的等值线为比较扁平的椭圆时，收敛就更慢了。

因此，在实用中常用最速下降法和其他方法联合应用，在前期使用最速下降法，而在接近极小值点时，可改用收敛较快的其他方法。

4. 最速下降法与梯度下降法的区别

准确来说，它们并不是完全等价。
对于梯度下降法，我们需要预先设定步长α。

5. 具体例子

例子1（代码见第6小节）：

因此我们找到了近似最优解：，然后将带入中，即可得到要求的最小值。

例子2：

6. 代码实现（以例子1为例）

import numpy as np
import sympy
import math

# 定义预定值
x0 = np.array([[0], [0]])  # 初始值
E = 0.29 # 10 ** (-6)  # 到达精度就停止

# 定义函数及导数
f = lambda x: np.array(x[0] - x[1] + 2*(x[0]**2) + 2*x[0]*x[1] + x[1]**2) # 定义原函数
f_d = lambda x: np.array([ 1 + 4*x[0] + 2*x[1], -1 + 2*x[0] + 2*x[1]])  # 导数

n = 0 # 迭代次数
ee = f_d(x0) # 导数值
e=(ee[0]**2+ee[1]**2)**0.5 # 初始迭代精度
a=sympy.Symbol(&#39;a&#39;,real=True) # 最速下降法中的namita
print (&#39;第%d次迭代：e=%d&#39; % (n, e))输出：
第0次迭代：e=1然后，开始迭代：
print(&#34;x0为：&#34;, x0)
print(&#34;初始x0梯度为：&#34;, f_d(x0))
print(&#34;\n&#34;)

while e > E:
n = n + 1
yy = f(x0 - a * f_d(x0))  # f(x-ad)
yy_d = sympy.diff(yy[0], a)  # 以a为未知数，求导数
a0 = sympy.solve(yy_d)  # a的值
x0 = x0 - a0 * f_d(x0)  # 更新迭代新的x
ee = f_d(x0)  # 新的导数
e = math.pow(math.pow(ee[0, 0], 2) + math.pow(ee[1, 0], 2), 0.5)

print(&#39;第%d次迭代：e=%s&#39; % (n, e))
print(&#34;f(x-ad)为：&#34;, yy)
print(&#34;f(x-ad)以a为未知数，求导数为：&#34;, yy_d)
print(&#34;得出a为：&#34;, a0)
print(&#34;更新迭代新的x1为：&#34;, x0)
print(&#34;新的导数为：&#34;, ee)
print(&#34;\n&#34;) 输出：
x0为： [[0]
[0]]
初始x0梯度为： [[ 1]
[-1]]

第1次迭代：e=1.4142135623730951
f(x-ad)为： [a**2 - 2*a]
f(x-ad)以a为未知数，求导数为： 2*a - 2
得出a为： [1]
更新迭代新的x1为： [[-1]
[1]]
新的导数为： [[-1]
[-1]]

第2次迭代：e=0.28284271247461906
f(x-ad)为： [2*(a - 1)**2 + (a + 1)**2 + (a + 1)*(2*a - 2) - 2]
f(x-ad)以a为未知数，求导数为： 10*a - 2
得出a为： [1/5]
更新迭代新的x1为： [[-4/5]
[6/5]]
新的导数为： [[1/5]
[-1/5]]
第二次迭代后时，精度为0.2828，此时x为[[-4/5],[6/5]]，带入中，即可得到要求的最小值：
# 输出结果
x_finally = np.array([[-4/5],[6/5]])
f(x_finally) # array([-1.2])
参考

重点感谢：忆臻：【最优化】一文搞懂最速下降法
【机器学习之数学】02 梯度下降法、最速下降法、牛顿法、共轭方向法、拟牛顿法
最优化算法(2):线搜索
最优化：线搜索中有最速下降法、牛顿法、拟牛顿法、共轭梯度法，那么他们分别时候用啊？？
本章要点：最速下降法的基本思想及特点牛顿方向 Newton 法基本思想及特点共轭方向、共轭方向法的基本定理共轭梯度法基本思想拟 Newton 法的基本思想

如果觉得对你有帮助，可以给我点个赞~

		自动登录	找回密码
密码			立即注册

无约束优化问题 — 最速下降法

本帖子中包含更多资源