牛顿法
一元函数
牛顿法要求函数二阶可导.
牛顿法利用二次函数对目标函数进行拟合,
利用二次函数的极值点作为目标函数的极值点的近似.
利用Taylor展开有: 于是在点
处我们可以用
来对 进行拟合, 并用 的极值点 对应的点 处对 用Taylor展开做下次拟合.
记选择的点的序列为 则 和 的关系求解如下:
对于函数 它的一阶导数的零点为 即 于是
是拟合函数的极值点, 作为目标函数极值点的近似.
牛顿法解方程
牛顿法也可以看作是在求一阶导函数的零点, 于是令 我们可以用牛顿法求 的零点.
割线法
牛顿法对函数的要求较高, 即二阶可导.
由于某一点的导数的定义是切线的斜率, 于是我们可以取两个点,
利用这过这两个点的割线的斜率近似切线的斜率, 这得到了割线法.
为了充分利用已经计算过的点, 我们用 和点
这两点连线的斜率近似 令
代入牛顿法的式子得 此时需要两个初始点
同样地, 割线法也可用于求函数的零点.
按照割线法的思想, 我们能否继续进行下去,
即继续利用割线分别近似割线法迭代公式中的
得到下面的迭代公式呢?
但这是不对的, 因为不管是牛顿法还是割线法,
它们都是对目标函数的二次函数的拟合:
牛顿法保证
割线法的拟合函数为 可以验证
而上述直接用割线斜率代替
的方式得到的拟合函数是: 可以验证它不满足
于是它并非在当前条件下对目标函数的完美拟合.
而要达到比较好的拟合效果我们显然需要
这启发我们用插值法拟合: 这里用拉格朗日插值法构造 用 的极值点近似
的极值点. 整理即得
其中
这种方法对目标函数要求比较低.
收敛性分析在多元函数部分.
多元函数
和一维搜索的牛顿法一样,
高维函数的牛顿法也是使用二次型函数去拟合目标函数,
用该二次型函数的极值点近似目标函数的极值点.
并以该点为初始点进行下一次迭代.
已知点 , 现欲求
对 进行Taylor展开有: 令黑塞矩阵为 取 于是
即 解得 当然, 这前提是 可逆.
黑塞矩阵不可逆时牛顿法将失效, 我们将在后文提出修正的方法.
对二次型函数直接应用牛顿法时, 不论初值为何值,
只需要迭代一次就能得到极小值点
下面就懒得用粗体了(
牛顿法的修正
不下降的问题
作为迭代算法,
牛顿法在收敛的情况下得到的点的序列对应的函数值虽然整体是呈下降趋势收敛至极小值的,
但是我们没办法保证序列 是严格递减的,
这也就是说牛顿法不具有下降特性(当然,
这一般出现在离极小点比较远的情况).
一个好的算法在迭代过程中对极小点应该是"步步紧逼"的,
我们想把牛顿法修正成为这样的算法. 幸运的是,
牛顿法每次迭代前进的方向是一个下降方向, 这表述为下面的命题:
命题1 令 且黑塞矩阵正定, 则
是一个下降方向, 即存在 使得 都有
PROOF 置 于是由黑塞矩阵正定可得
由连续函数的保号性可得存在 当 时 即 在 上递减, 于是对任意 都有 这就是要证的.
这意味着我们可以像最速下降法那样,
在这个下降方向上选择一个最优步长来修正牛顿法, 即下面这样的修正: 这样就可以防止牛顿法"走弯路".
不正定的问题:
Levenberg-Marquardt修正
黑塞矩阵不正定会导致的问题是,
牛顿法确定的搜索方向不是下降方向(虽然正定也可能会产生这样的问题,
不过我们在上述的修正中已经解决了), 那么我们便考虑修正先使黑塞矩阵正定,
这就有LM修正. LM修正看起来似乎有些随便粗暴: 既然 不正定, 它有非正的特征值,
只需要让所有特征值加上一个数让所有特征值都为正即可,
这就是LM修正(同时用步长修正保证下降特性): 其中
当然要说明一下若 是 的特征值, 则 是 的特征值: 若 为 的一个特征向量, 那么 除此之外, 我们可以证明
也是一个下降方向( 足够大时),
这样才可以使用步长修正.
REMARK : 时LM修正接近牛顿法,
时LM修正接近步长较小的最速下降法, 因为此时
为梯度, 于是步长为 实际应用中在迭代开始时 可以选择较小的值,
并在迭代过程中使其缓慢增加直至算法出现下降特性.
不可逆的问题
黑塞矩阵不可逆时我们将不能使用牛顿法.
不过我们很少会碰到黑塞矩阵奇异的情况, 要恰好使 并不是件容易的事.
当然碰到这种情况时我们在该步利用最速下降法, 或者使用类似LM修正的方法对
进行微扰使其可逆即可.
牛顿法的收敛性
这里仅讨论未修正的牛顿法.
定理1 函数 三阶连续可微,
为 的驻点且黑塞矩阵非奇异,
则对所有足够接近 的点
牛顿法收敛并且至少以阶数为
的收敛率收敛至
PROOF 这里仅提供大致的思路. 只需证明
即可. 对 在 处进行Taylor展开有 借助大 记号的含义,
对于足够接近 的 有 可以代入:
牛顿法迭代公式两边减
取范数, 且黑塞矩阵的逆矩阵连续, 有: 由归纳法可得 即
同时迭代有
时, 只有保证 才可以使 也即对足够接近 的点 收敛.
REMARK : 从定理1中我们知道:
- 收敛的牛顿法总是会收敛至驻点而不仅仅是极小点;
- 牛顿法在初值点足够接近极小点时才会有效;
牛顿法的优缺点
优点不言而喻: 收敛速度快.
然而虽然牛顿法在接近驻点时收敛速度至少为 阶,
但是它的两个致命的缺点是要解决计算黑塞矩阵及其逆矩阵逆矩阵,
计算黑塞矩阵至少需要求导 次, 比较大时运算量也比较大;
求逆矩阵方法之一是解线性方程组 复杂度一般为
后面的算法可以有效解决这些问题.
