局部模型为何需要保障?
牛顿(Newton)法在目前位置最小化一个二次模型。设 二次连续可微,记 、。若 正定,则
的唯一极小点为 。在非退化极小点附近,这方向十分有效;离得远时,对小位移准确的模型却未必能预测完整步长的结果。线搜索保留方向,利用真正的函数值检查步长。
下文的“全局收敛”指在所列假设下,由任意起点出发,梯度趋于零;这并不表示找到全局最小值。“局部二次收敛”则描述足够接近合适极小点时的更快速收敛。第一项结论本身不保证迭代点收敛至某个驻点。
下降方向与 Armijo 条件
定义 1.8.1
(回溯线搜索)
选定 、。给定 和满足 的方向 ,先取 。只要
尚未成立,就把 换成 。接受第一个通过测试的步长,并令 。式 (1) 称为 Armijo 充分下降条件。
因右边严格小于 ,接受的步骤必定降低函数值。条件要求取得线性项预测下降量的 倍,而非整个二次模型的预测量。若 且 对称正定,则 满足 ,确为下降方向。若 ,应停止;此时严格下降条件不适用。
定理 1.8.2
(回溯必定终止)
若 的梯度在 上为 -Lipschitz,,且 ,则回溯必定终止。事实上,只要
就满足 (1)。
证明
(沿射线的二次上界)
沿线段积分梯度,再利用 Lipschitz 不等式,得到
当步长不大于上述界时,后两项之和至多为 。由于 ,测试的步长最终必小于这个正数。这只是充分界,并非声称所有较长步骤都会失败。
全局驻点保证
定理 1.8.3
(一致正定牛顿矩阵下的梯度收敛)
设 的梯度为 -Lipschitz,并在初始水平集 上有下界。假设存在常数 ,使所有 满足
在每个非驻点使用牛顿方向与固定 的 Armijo 回溯,则迭代或于有限步到达驻点,或满足 。
这些 Hessian 界是强假设,不能单凭极小点存在便断定成立。它们令方向在整个水平集内受到一致控制。单说每一步均使 下降并不够:每次下降可能太小,总下降量有限时梯度仍可能很大。
证明
(一致下降量与可求和级数)
每次接受的步骤都下降,故迭代点留在 。由特征值界可得
因此上一个定理的充分步长界至少为 。若 ,第一个步长已被接受;否则,第一个被接受的步长大于 ,除非它本来就是 1。所以所有接受步长均满足 。Armijo 条件给出
从 加至 后,左边相消,且至多为 。故 ,其非负项必趋于零。
证明透视
每个假设换来哪一个不等式
论证把每步的下降转化为一致的下降,而每个假设都用在一个环节上。上界 使牛顿方向足够陡,;下界 使它不会太长,。两者连同 Lipschitz 常数,在可接受步长之下放了一个与 无关的下限 ;以固定因子 回溯,至多越过这个下限一个因子,于是得到 。Armijo 条件再把下限变成与 成正比的下降量。单调下降还用了一次:保证每个迭代点都留在 Hessian 界成立的 内。收尾的一步是裂项求和:有下界使总下降量有限,所以 可求和。去掉 ,下限可能崩溃;去掉有下界,总和未必有限。
证明用到精确求解线性方程。若以近似方向代替,仍须另证相应的下降及长度界;不定 Hessian 和信赖域方法也需要各自的保障,不能直接套用此定理。
何时恢复完整牛顿步?
定理 1.8.4
(严格极小点附近的完整步与二次收敛)
设 为驻点, 正定,Hessian 在其邻域内为 Lipschitz,并取 。则对每个充分接近 的 ,回溯在每一步都接受 ,迭代二次收敛到 。
证明
(三次余项最终被压倒)
当 充分接近 时,Hessian 仍一致正定。令 ,由二阶展开,
由 至少是 的正倍数,当 够小,三次余项小于 ,完整步便通过 (1)。要求 是为余项留出空间;它是充分条件,并非对每个函数都必要。
为分析速度,记 。由梯度的积分式及 ,
逆矩阵在局部有界,加上 Hessian 的 Lipschitz 条件,得到 。因此起点足够接近时,迭代留在该邻域,使用完整步并二次收敛。全局梯度收敛结论本身不保证迭代进入此邻域。
证明透视
为什么完整步会被接受,之后误差又会平方
证明分为两个互不依赖的部分。接受性:由于 ,二次项恰好抵消线性项的一半,,所以实际下降量是线性预测下降量的一半,只差一个由 Lipschitz Hessian 控制的三次余项。在 附近的正定性使 与 同阶,而 留出的余量 在 足够小时吸收这个余项。收敛阶:误差恒等式把 写成 乘以大小为 的 Hessian 之差作用在 上。论证以归纳收尾:一旦 ,下一个迭代点更近,两部分便可再次应用。全局定理的假设一个也没有用到。
常见错误
(选取 却期望完整步)
限制 并非装饰。对 ,完整牛顿步恰好落在极小点,,而 。取 的 Armijo 条件要求 ,这不成立,所以精确的一步被拒绝。接着 被接受,因为 ,迭代变成 :在二次函数上也只有线性收敛。
必须缩短的步长
例题 1.8.5
(指数目标函数)
取 、、、。由 、,唯一极小点为 。牛顿方向为
完整步到达 ,函数值大幅上升。取 时,,,虽低于 ,却大于 Armijo 右边约 ,故仅有下降并不足够。取 ,则 、,右边约为 ,所以接受。此函数的梯度在整个 上并非 Lipschitz,因此不能直接引用以上所述的全局定理处理此例。
常见错误
(接受任何下降)
上例取 时, 确实从约 降到 。接受这类步骤,无法得到用 表示的下降量下界,而这正是驻点证明所需要的;Armijo 拒绝它,因为它达不到所预测线性下降量的四分之一。
例题 1.8.6
(靠近极小点时完整步接手)
从已接受的点 起改用完整步。此时牛顿更新为 。在 ,完整步给出 ,低于 Armijo 右边约 ,所以接受 ,之后的完整步也全部被接受。迭代约为
比值 约为 、、 及 :每步误差都被平方,常数趋于 。全局阶段只需缩短一次步长,之后便由局部定理描述。
例题 1.8.7
(强凸目标函数的一致步长下限)
令 。在整个 上 ,故 、,且 为 -Lipschitz; 有下界 。取 、,证明给出 及 ,因此保证下降至少为 。从 出发:、、。完整步给出 、,低于 Armijo 右边 ,所以接受 。实际下降 远大于保证的 :定理的常数保证的是收敛,而不是速度。
反例模式
下降方向的论证不能省掉正定性
令 ,在 有 、。牛顿方程给出 ,因此 ,这是上升方向。当正的 充分小时,,而 Armijo 右边也高于 。下降方向下的终止证明不适用。取 时,回溯循环其实永不停止:,而 在 处取得的最小值约为 ,所以对每个 都为正。算法必须检测或修正这类方向。
练习与解答
快速检查
(设 、、,求牛顿方向并测试 。)
比较 与 。
解答 · 答案
、,所以 。新函数值是 0,而 Armijo 右边为 ,故接受完整步。
快速检查
(若对称矩阵 的特征值都在 中,其中 ,证明 。)
使用 。
解答 · 答案
正交对角化 ; 的特征值都在 中,故 。
快速检查
(为什么 下降且有下界,仍不足以推出 ?)
想一想函数值收敛对每次下降量说明了什么。
解答 · 答案
函数值收敛只能推出相邻两步的下降量趋于零;若没有把下降量与 联系起来的下界,就无法断言梯度趋于零。例如 、,函数值下降且有下界,但梯度恒为 1。此例只说明逻辑缺口,并不是满足定理的牛顿序列。
快速检查
(设 、。完整牛顿迭代会怎样?)
计算 。
解答 · 答案
,故 、,但 没有有限极限, 也没有驻点。沿序列的 Hessian 没有一致的正下界;梯度收敛不自动意味着迭代点收敛。