一步所提供的信息
拟 Newton 方法利用相邻迭代点的数据建立 Hessian 近似。令 、,割线方程 要求新矩阵沿着步长重现观察到的梯度变化。这只限制一个方向,并不能决定整个矩阵;观察值亦可能显示负曲率或受误差影响。若逆矩阵近似 正定,则对非零梯度, 必为下降方向,因为 。保持这个性质,与证明整个算法收敛,是两件不同的事。
若 对称正定(SPD),而 ,BFGS 更新为
它满足 ,并保持正定。若 ,则不存在满足原割线方程的正定矩阵:在方程左乘 就会得到矛盾 。阻尼是改变割线方程的目标,并非令此矛盾消失。
曲率保护
选定 ,假设 ,记 及 。定义
在 (1) 中以 代替 。第一种情况下观测数据已达到阈值,故保持不变;第二种情况下 ,所以 。此时 混合实际梯度变化和旧模型的预测 。阈值是相对于模型曲率 ,并不是梯度误差的绝对界。
定理 7.2.1
(阻尼 BFGS 保持正定)
设 为 SPD、、 且 。按 (2) 构造 ,并令
则 、,而且 为 SPD。在实际启用阻尼时,第一个不等式取等号。
证明
(先计算 ,再检验二次型)
不修改时,。否则代入得
的前两项互相抵消,最后一项给出 。对任意非零 ,
内积的 Cauchy–Schwarz 不等式说明前两项之和非负,取等号当且仅当 是 的倍数。对非零倍数,因 ,最后一项严格为正。故 正定。这并未证明它接近真实 Hessian,也未证明迭代点收敛。
证明透视
保护步骤究竟证明了什么
证明有两个相互独立的部分。第一部分是关于 的代数:由于 是 的仿射函数, 的公式正是方程 的解,而分情形定义保证 ,所以 确实是 与 的混合。阈值使 不只为正,而且不小于模型曲率 的固定比例。第二部分是未阻尼 BFGS 的正定性论证,只是把 换成 ;保护步骤只在 Cauchy–Schwarz 取等号的情形出现:此时 是 的倍数, 使最后一项严格为正。两部分都没有涉及 ,所以定理对 Hessian 的近似程度或收敛均无任何断言。
例题 7.2.2
(需要阻尼的一对数据)
取 、、 及 。此时 、,所以 ,,。直接代入得到
可验证 。首个对角元素为正,行列式为 ,也确认此二维矩阵正定。原数据的曲率虽然为正,却低于选定的相对阈值;正曲率本身不一定使阻尼闲置。
反例模式
原割线方程可能无解
对 ,取 、,则 。没有正的标量 满足 。取 、,(2) 给出 、。这是正定模型,但它使用修改后的割线数据,并不代表 的实际负曲率。
有限记忆的逆矩阵运算
存储密集的 矩阵可能很昂贵。改为选择易于与向量相乘的 SPD 初始矩阵 ,并按时间次序保留 对 ,每对都满足 。令 ,概念上的逆矩阵更新为
不必实际构造 ,可用以下双循环递推计算 :
- 设 。按 计算并存储 ,再以 取代 。
- 设 。按 计算 ,再以 取代 。
- 输出 ;可用 作搜索方向。
把 (3) 的分解形式逐层展开,就可以证明这个递推。
命题 7.2.3
(双循环递推实现逆矩阵更新)
设保留的每一对都满足 。在精确运算下,双循环递推输出 ,其中 由 (3) 定义,过程中不需要构造任何 矩阵。
证明
(为什么两个循环的次序不同)
令 ,则 (3) 为 。将最新更新作用于 时,先把 作用于 ,所得向量再输入较早的逆矩阵更新。重复此步得到反向循环,因为 。回程时,,恰好是正向循环。因此在精确算术下,结果等于 。若 ,两个循环都是空的,结果为 。
(3) 每次更新均保持正定:对非零 ,二次型为 。若它为零,则 且 ;但后者使 ,矛盾。因此非零 对应的方向严格下降。数据对及暂存向量需要 空间;计算量为 加上套用 的成本。常见选择是单位矩阵的正倍数。下次迭代可以丢弃最旧的一对,并以指定的新基底和剩余数据重新定义概念矩阵;这通常不同于保留全部历史更新的完整 BFGS。
例题 7.2.4
(一对数据的双循环)
取 、、、。则 、,反向循环给 。令 ,得到 ,正向循环输出 。直接由 (3) 得 ,其与 的乘积相同。因此 。
例题 7.2.5
(两对数据重现对角牛顿步)
取 ,以及两对 、,它们正是 的梯度变化;再令 。则 、。反向循环从最新的一对开始: 给出 ,接着 给出 。因此 。正向循环给出 及 ,再得 及 。这等于 ,正是 的精确牛顿(Newton)步;事实上 (3) 给出 及 。由于反向循环后 ,初始矩阵 对这个结果毫无影响。
常见错误
(阻尼后仍存储原始数据对)
阻尼更新满足的是 ,而不是 。若有限记忆的历史存储 而不是 ,就不能重现阻尼后的矩阵;而且 的原始数据对会使 为负或无定义,(3) 的正定性论证就不再适用。在上面负曲率的例子中,应存储的是 ,而不是 。
即使曲率为正,有限精度和极小分母仍促使实现中采用明确的数值保护;以上是精确算术,没有指定数值容许误差。下降方向本身不能保证全局收敛:线搜索条件、目标函数假设和方向质量的控制都须另行处理。
习题与解答
快速检查
(设 、、、。求 。)
比较 与 。
解答 · 答案
,,故 、。
快速检查
(在一维取 、、、。计算 、、。)
这里 。
解答 · 答案
、,所以 。因此 ,一维割线方程给出 ,与原目标 不同。
快速检查
(设 、、、。求输出。)
只有一对数据,所以每个循环只有一步。
解答 · 答案
、,所以 。接着 、,最终向量为 ;等价地,更新后的逆矩阵为 。
快速检查
(为什么每个 正定,仍不能单凭此推出 ?)
考虑 与 的夹角。
解答 · 答案
对非零 ,正定性只给 ;它并不给出远离 的方向夹角界,也不控制步长。下降法的收敛论证需要额外性质,单靠正定性不足。