从一步学习曲率
Newton 方向解方程 ,其中 。当 Hessian 计算代价高时,拟 Newton 法改为保存其逆的对称近似 ,取 。只要 正定且 ,这就是下降方向。我们希望利用已计算的梯度改进 。
设 、。若目标是 Hessian 为 的二次函数,则 ,真正的逆满足 。更新要求新近似重现这次观察到的作用,对非二次函数也是如此。
定义 7.4.1
(割线方程与 DFP 更新)
设 、。若矩阵 满足 ,称它满足割线方程。若 ,称向量对 满足曲率条件。对对称正定矩阵 及这样的向量对,Davidon–Fletcher–Powell(DFP)更新为
割线方程不能决定整个矩阵:一个方向的观察无法揭示全部曲率。曲率条件保证 非零,两个分母都为正;它是对实际使用的向量对的条件,并非单由 正定得出。
定理 7.4.2
(割线方程与正定性)
若 对称正定且 ,则 (1) 所得 对称正定,并满足 。
证明
(代入与加权 Cauchy–Schwarz 不等式)
(1) 的三项都是对称矩阵,所以 对称。把 (1) 乘以 ,得
对任意非零 ,
由于 正定, 是内积,Cauchy–Schwarz 不等式给出 ,且等号恰在 与 平行时成立。因此方括号非负;若 不是 的倍数,方括号严格为正,而最后一项非负,所以 。若 且 ,方括号为零,最后一项等于 。两种情况涵盖所有非零 ,故 正定。
证明透视
减去一项后为何仍正定
证明把非零向量分成两种情况,每个假设各有分工。 的正定性用于方括号:它使 成为内积,于是在过 的直线以外,Cauchy–Schwarz 不等式严格成立。在这条直线上,减去的一项抵消了 的全部贡献,这正是它的用途: 必须忘掉旧的作用 。那里只剩下新加的一项,曲率条件就用在这一项上。取 可见这个条件也是必要的,因为 ;若 ,方向 本身就说明 不正定。论证之所以闭合,是因为两种情况穷尽一切,而不是因为某一项占优。
此更新移除旧矩阵在 方向的作用 ,换成 。它不一定保留每个先前的割线方程;以上证明也没有保证迭代收敛或整个矩阵的准确度。
常见错误
(把逆矩阵更新用于 Hessian 近似)
公式 (1) 更新的是逆 Hessian 的近似 ,并强制 。若把同一公式用于 Hessian 本身的近似 ,强制的是 ,这是错误的割线方程;Hessian 近似必须满足 。在 (1) 中互换 与 的角色,得到 ,这是另一个更新( 的 BFGS 公式),而不是用 写出的 DFP 更新。
完整计算一步
例题 7.4.3
(二维二次函数)
令 、、。则 ,。精确线搜索最小化 ,其导数 在 处为零。因此
由 ,公式 (1) 给出
直接相乘可验证 。其行列式为 ,第一个对角元为正,与定理一致。它还不是真正的逆 :割线方程只约束矩阵在 上的作用。
从 继续,可以看到第二次观察带来什么。
例题 7.4.4
(同一二次函数的第二步)
在 处梯度为 ,而
沿 , 的导数为 ,所以精确线搜索到达 ,即最小点。新向量对为 、,且 、、。于是
每个元素都以公分母 核对。在这个例子中,两次精确线搜索步到达最小点,而 正是真正的逆 Hessian,所以它也满足第一个割线方程 。这只是对此二次函数的计算;本页没有证明一般的有限步终止定理。
曲率从何而来
若 在整条步长线段上二次连续可微,微积分基本定理给出
因此,非零步长沿线若有一致的正曲率下界,便有 。另一条途径是弱 Wolfe 曲率条件。
命题 7.4.5
(弱 Wolfe 条件给出可用的向量对)
设 、、,且 。若 ,则
证明
(两个方向导数相减)
由 及 ,
其中不等式就是曲率条件,最后的等式用到 。三个因子都为正。
这个计算假设符合条件的步长存在且被接受,并未证明线搜索必定终止。
例题 7.4.6
(一维情形:更新忘掉旧值)
在一维中,(1) 化为 ,与所用的正数 无关。取 ,则 ;设 、、,试探步长 。于是 、。取 ,曲率条件成立,因为 。此时 、、,大于命题的下界 。因此 ,即 在 上平均斜率 的倒数。它不是 :割线向量对记录的是沿步长的平均曲率,而不是新点处的曲率。
反例模式
割线向量对的符号可能不合要求
取 、、;这一步使 由 降到 。由 得 、,所以 。一维割线方程迫使 ,因此没有正定更新可满足它。单靠下降并不提供曲率:实际方法必须处理这类向量对,例如跳过或修改更新;这些做法需要另行分析。
练习与解答
快速检查
(若 、、,由 (1) 求 。)
把数值代入 (1) 的三项。
解答 · 答案
,与割线方程要求的 相同。
快速检查
(若 ,对称正定的 能否满足 ?)
把割线方程左乘 。
解答 · 答案
只有退化情形 可以。若 ,则 ,矛盾;若 ,割线方程迫使 ,不提供曲率信息。
快速检查
(若 、、,可得 的什么下界?)
运用关于弱 Wolfe 条件的命题。
解答 · 答案
;实际接受的步长可能得到更大的值。
快速检查
(二维中若 , 是否必等于产生此向量对的二次函数的真正逆 Hessian?)
比较第一个例题中的两个矩阵。
解答 · 答案
不必。在第一个例题中, 与 都把 映到 ,但两者不同。要决定矩阵,需要额外的观察与假设。