梯度方法type
status
date
slug
summary
tags
category
icon
password
Property
水平集指的是能够满足的所有组成的集合，为常数。因此，对于点 , 如果则可以说该点是水平为的水平集中的元素。
如果函数在处的梯度不是零向量，那么它与水平集中任意一条经过处的光滑曲线的切向量正交。因此，一个实值可微函数在某点处函数值增加最快的方向正交于经过该点的函数水平集。也就是说，在梯度方向上，自变量的细微变动，所导致的目标函数值的增加幅度要超过其他任意方向。
证明：
函数在点 处，在方向上增长率记为： ，。由于，由柯西-施瓦茨不等式可得：
若令 ，则有：
可看出，梯度方向 就是函数 在 处增加最快的方向。反之，梯度负方向就是函数在处减少最快的方向。在梯度方向上，自变量的细微变动，所导致的目标函数值的增加幅度超过其他任意方向。如果需要搜索函数极小点，梯度负方向是优选方向。
令作为初始搜索点，并沿着梯度负方向构造一个新点 ，由泰勒定理可得
如果那么当 足够小时，有：
这意味着，从搜索目标函数极小点的角度来看，相对于 有所改善。
给定一搜索点 ，由此点出发，根据向量 指定的方向和幅值运动构造新点 。其中， 是一个正实数，称为步长。可得迭代公式：
称为梯度下降法。
在搜索过程中，梯度不断变化，当接近极小点时，梯度应该趋近于0 。可以设定很小的步长，每次迭代都重新计算梯度；也可以设置很大的步长。前者的工作量非常大，而后者则容易在极小点附近产生锯齿状的收敛路径，优势在于梯度的计算次数要少一些。
最速下降法
最速下降法是梯度方法的一种具体实现，其理念为在每次迭代中选择合适的步长使得目标函数值得到最大程度的减少。
可认为是函数的极小点，即
在每次迭代中，从迭代点 出发，沿着梯度负方向 开展一维搜索，直到找到步长的最优值，确定新的迭代点。
最速下降法搜索函数的极小点，迭代过程产生的序列为 ，则 与 正交对于所有的 都成立。 平行于水平集在处的切平面
最速下降法搜索函数 的极小点，迭代过程产生的序列为 ，如果 ，则
迭代停止规则
- 如果，则 满足局部极小点一阶必要条件，此时
- 计算梯度的范数，如果 ，其中 为预设阈值，则迭代停止
- 计算相邻迭代点对应的目标函数值差的绝对值，如果 ，其中 为预设阈值，则迭代停止
- 计算相邻迭代点差值的范数，如果 ，其中 为预设阈值，则迭代停止
- 计算规则3的相对值作为停止规则，即 其中 为预设阈值，则迭代停止。为避免父母过小，可进行以下修正：
- 计算规则4的相对值作为停止规则，即 其中 为预设阈值，则迭代停止。为避免父母过小，可进行以下修正：
由于相对停止规则5和6是尺度无关的，所以优于绝对停止规则3和4
例题：利用最速下降法求解函数的极小点。初始搜索点为，开展3次迭代
目标函数的梯度为：
处的梯度为：
确定处的步长：
利用割线法开展一维搜索，可得
接下来计算 。首先计算：
确定处的步长 ：
利用割线法开展一维搜索，可得
接下来计算 ，同理，略。
最速下降法应用到二次型函数
目标函数为
为对称正定矩阵，
二次型函数的梯度
由于 且 ，得
记 ，对于二次型函数最速下降法的迭代公式为
其中，
当目标函数为二次型函数时，可确定 处步长 的解析式。假设 ，迭代继续。由于 是函数 的极小点，利用局部极小点一阶必要条件，可得
当 时， 。由于
因此
由此可见，目标函数为二次型函数时，最速下降法的迭代公式为
其中， 。
梯度方法性质分析
收敛性
全局收敛：如果对于任意起始点，算法都能够保证产生一组迭代点序列，最终收敛到满足局部极小点一阶必要条件的点；
局部收敛：如果要求初始点足够靠近极小点，算法产生的迭代点序列才能收敛到满足局部极小点一阶必要条件的点；
对于最速下降法，对于任意的初始点 ，都有
对于步长固定梯度法，当且仅当步长 时， 。 为矩阵 的特征值中的最大值。
收敛率（收敛阶数）
存在一个序列 ，能够收敛到 ，即 。如果
则序列 的收敛阶数为 ，其中， 。
如果对于所有 ，有 ，则称收敛阶数为 。
收敛阶数越高，收敛速度越快，任意收敛序列的收敛阶数不会小于1
如果 （一阶收敛）， ，则称收敛是拟线性的。
如果 （一阶收敛）， ，则称收敛是线性的。
如果 ，则称收敛是超线性的。
如果 （二阶收敛），则称收敛是二次型的。
在最坏情况下，最速下降法的收敛阶数为1