无约束优化问题 — 最速下降法
本文主要介绍 最速下降法，在介绍之前先了解其他一些基本概念。一、基本概念
1. 无约束优化问题
最速梯度下降法解决的问题是无约束优化问题，而所谓的无约束优化问题就是对目标函数的求解，没有任何的约束限制的优化问题，比如求下方最小值： https://www.zhihu.com/equation?tex=minf%28x%29
其中的函数 https://www.zhihu.com/equation?tex=f%3AR%5En%5Crightarrow+R .
求解这类的问题可以分为两大类：最优条件法和迭代法。
最速下降法属于迭代法。
2. 线性搜索
线性搜索定义：在利用迭代的方法解决无约束优化问题：
时，如果我们想要通过迭代的方式，将初始点https://www.zhihu.com/equation?tex=x_0逐步迭代到最优解所在的点https://www.zhihu.com/equation?tex=x%5E%2A，那么我们就会考虑一个搜索点迭代过程，其中第k步迭代的公式是：
https://www.zhihu.com/equation?tex=x_%7Bk%2B1%7D+%3D+x_%7Bk%7D++%2B+%5Calpha_%7Bk%7D+d_%7Bk%7D+ 。
其中，其中是我们根据目标函数在的情况确定的搜索方向，而https://www.zhihu.com/equation?tex=%5Calpha_k则称为迭代点沿搜索方向的步长。因此，我们需要寻求一种算法，在已知函数和迭代点的情况下，能够算出搜索方向，使得在这个搜索方向下得到的点能够使得变小。
而所谓的线性搜索的方法，就是指的是在迭代方向 https://www.zhihu.com/equation?tex=d_%7Bk%7D+ 已知的情况下，求解合适的步长的问题。关于的确定精确与否又分为精确线性搜索和非精确线性搜索的方法。
3. 梯度下降法
梯度下降法（Gradient descent），顾名思义，就是自变量沿着梯度向量的反方向进行移动，因为梯度的方向是上升的方向。对于一个 https://www.zhihu.com/equation?tex=R%5E%7Bm%7D+%5Crightarrow+R 的函数y=f(x)，初始时 https://www.zhihu.com/equation?tex=x%3Dx%5E%7B%280%29%7D ，我们想要得到函数y=f(x)的极小值点 https://www.zhihu.com/equation?tex=x%5E%7B%2A%7D，如果能够求得f(x)的梯度f(x)，那么我们就可以用梯度下降法进行迭代求极小值的近似解。
记自变量 x 在第k迭代后的值为 https://www.zhihu.com/equation?tex=x%5E%7B%28k%29%7D ，则自变量的更新公式为： https://www.zhihu.com/equation?tex=x%5E%7B%28k%2B1%29%7D+%3D+x%5E%7Bk%7D+-+%5Calpha%5Ccdot%E2%88%87f%28x%5E%7B%28k%29%7D%29 ，其中α
为步长，也被称为学习率（learning rate），控制了梯度下降速度的快慢。
二、最速下降法
1. 概念
最速下降法（Steepest descent）是梯度下降法的一种更具体实现形式，其理念为在每次迭代中选择合适的步长，使得目标函数值能够得到最大程度的减少。
每一次迭代，沿梯度的反方向，我们总可以找到一个 https://www.zhihu.com/equation?tex=x%5E%7B%28k%2B1%29%7D+%3D+x%5E%7Bk%7D+-+%5Calpha_%7Bk%7D%5Ccdot%E2%88%87f%28x%5E%7B%28k%29%7D%29 ,使得在这个方向 https://www.zhihu.com/equation?tex=f%28x%5E%7B%28k%2B1%29%7D%29 取最小值，即
https://www.zhihu.com/equation?tex=%5Calpha_%7B%28k%29%7D+%3Dargmin+f%28+x%5E%7Bk%7D+-+%5Calpha%5Ccdot%E2%88%87f%28x%5E%7B%28k%29%7D%29%29
有意思的是，最速下降法每次更新的轨迹都和上一次垂直。
2. 步骤
下面先给出最速下降法的计算步骤：
其中，确定最优步长https://www.zhihu.com/equation?tex=t_%7Bk%7D的方法如下：
简单来说：
第1步：迭代法的初始点选择；
第2步：给出终止条件（到达了局部最优解）；
第3步：从当前点选取迭代的方向（梯度负方向）（梯度的负方向是局部下降最快的方向）；
第4步：在确定迭代方向的前提上，确定在该方向上使得函数值最小的迭代步长（选择一个合适的步长是非常最重要的，这直接决定我们的收敛速度）。
3. 缺点
某点的负梯度方向，通常只是在该点附近才具有这种最速下降的性质。
最速下降法利用目标函数一阶梯度进行下降求解，易产生锯齿现象（如下图 ），在开始几步，目标函数下降较快；但在接近极小点时，收敛速度长久不理想了。特别适当目标函数的等值线为比较扁平的椭圆时，收敛就更慢了。
因此，在实用中常用最速下降法和其他方法联合应用，在前期使用最速下降法，而在接近极小值点时，可改用收敛较快的其他方法。
4. 最速下降法与梯度下降法的区别
准确来说，它们并不是完全等价。
对于梯度下降法，我们需要预先设定步长α。
5. 具体例子
例子1（代码见第6小节）：
因此我们找到了近似最优解：，然后将带入中，即可得到要求的最小值。
例子2：
6. 代码实现（以例子1为例）
import numpy as np
import sympy
import math
# 定义预定值
x0 = np.array([, ])# 初始值
E = 0.29 # 10 ** (-6)# 到达精度就停止
# 定义函数及导数
f = lambda x: np.array(x - x + 2*(x**2) + 2*x*x + x**2) # 定义原函数
f_d = lambda x: np.array([ 1 + 4*x + 2*x, -1 + 2*x + 2*x])# 导数
n = 0 # 迭代次数
ee = f_d(x0) # 导数值
e=(ee**2+ee**2)**0.5 # 初始迭代精度
a=sympy.Symbol('a',real=True) # 最速下降法中的namita
print ('第%d次迭代：e=%d' % (n, e))输出：
第0次迭代：e=1然后，开始迭代：
print("x0为：", x0)
print("初始x0梯度为：", f_d(x0))
print("\n")
while e > E:
n = n + 1
yy = f(x0 - a * f_d(x0))# f(x-ad)
yy_d = sympy.diff(yy, 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, 2) + math.pow(ee, 2), 0.5)
print('第%d次迭代：e=%s' % (n, e))
print("f(x-ad)为：", yy)
print("f(x-ad)以a为未知数，求导数为：", yy_d)
print("得出a为：", a0)
print("更新迭代 新的x1为：", x0)
print("新的导数为：", ee)
print("\n") 输出：
x0为： [
]
初始x0梯度为： [[ 1]
[-1]]
第1次迭代：e=1.4142135623730951
f(x-ad)为：
f(x-ad)以a为未知数，求导数为： 2*a - 2
得出a为：
更新迭代 新的x1为： [[-1]
]
新的导数为： [[-1]
[-1]]
第2次迭代：e=0.28284271247461906
f(x-ad)为：
f(x-ad)以a为未知数，求导数为： 10*a - 2
得出a为：
更新迭代 新的x1为： [[-4/5]
]
新的导数为： [
[-1/5]]
第二次迭代后时，精度为0.2828， 此时x为[[-4/5],]，带入中，即可得到要求的最小值：
# 输出结果
x_finally = np.array([[-4/5],])
f(x_finally) # array([-1.2])
参考
重点感谢：忆臻：【最优化】一文搞懂最速下降法
【机器学习之数学】02 梯度下降法、最速下降法、牛顿法、共轭方向法、拟牛顿法
最优化算法(2):线搜索
最优化：线搜索中有最速下降法、牛顿法、拟牛顿法、共轭梯度法，那么他们分别时候用啊？？
本章要点： 最速下降法的基本思想及特点 牛顿方向 Newton 法基本思想及特点 共轭方向、共轭方向法的基本定理 共轭梯度法基本思想 拟 Newton 法的基本思想
如果觉得对你有帮助，可以给我点个赞~
页:
[1]