内层求解法需要交付什么
信赖域模型是大问题内的一个小型优化问题。上一单元已推导其全局最小点的平移 Hessian 证书,但找出该点的工作量可能超过外层迭代的需要。若矩阵只能通过与向量的乘积取得,对角化尤其不合算。因此我们先问一个较适度的问题:能否用有限次矩阵向量乘积,求得一个可行而且有明确模型下降量的步?
负梯度射线给出一个基准,即 Cauchy 点。截断共轭梯度法(CG)在曲率仍为正时改善这个基准,在球面停止,并把检测到的非正曲率转成沿下降方向走向球面的步。“检测到”这一点很重要:Krylov 子空间未必会遇到整个空间中其他位置的负曲率方向。我们会证明模型下降保证,而不把这个算法误当成二次模型的全局求解法。
以下略去模型的常数项,写成
范数是 Euclidean 范数,矩阵范数是其诱导谱范数。除另有说明外,,而算法的所有运算均采用精确算术。若 ,下述一阶程序返回零;它不作二阶最优性的声称。
Cauchy 点及其下降量
记 、。在射线 上,可行性等价于 ,且
若 ,这个函数在可行区间上严格递减,故选右端点。若 ,不受限制的最小值在 取得。因此
Cauchy 点只在一条射线上最小化,并非在整个球上最小化。然而,它的下降量具有全局一阶论证所需的尺度。
命题 10.2.1
(Cauchy 下降量)
若 ,令 ,则
证明
(与一个短射线步比较)
把 与可行射线点 比较,其中 。由于 在射线的可行部分上最小化 ,且 、,
因为 、,该值为正。
采用 可避免在 时另订除法惯例。比较点正是上一单元有保障的射线步。Cauchy 点可能较长;自动沿用的是下降量,而非该步的长度上界。
到达边界而不越界
设 、。恰有一个正数 满足 。令
这是 的正根;两根的乘积是 ,所以另一根为负。球的凸性保证到正根为止的线段仍可行。浮点运算时,若 ,等价公式 可避免相减消去误差;但此处的证明使用精确正根。若以容许误差判定已碰到边界,便改变了实现规则,必须另外交代误差。
明确的截断 CG 规则
选相对残差容许值 ,从
开始。这里 是二次模型的梯度,不是原目标问题的可行性量度。当 时,依以下次序处理。
- 计算 。若 ,返回 。零曲率与负曲率采用同一规则。
- 若 ,计算 。若 ,返回 。等号也视为边界返回,先于任何残差检查。
- 否则令 、。若 ,返回 ;这包括残差恰为零的情况。
- 若残差仍非零,令 、,然后继续。
残差停止检查在完成一步后才进行,故算法至少会完成与 Cauchy 点的比较。每次取新方向时,当前点都严格位于球内,所以边界根公式总有 。在非正曲率方向上,这个规则选向前的交点。比较两个交点可能进一步降低模型值,但下述保证不需要这样做。
定理 10.2.2
(有限步终止与 Cauchy 下降)
对称 、、、 下,上述精确算术程序至多经 个方向迭代便返回。其输出 可行,且满足 。因此,若 ,则
此声明不断言 是球约束模型的全局最小点。
截断前,CG 恒等式为何仍成立
证明
(用归纳法证明共轭性与正交性)
在正曲率步仍严格留在球内时证明所需恒等式。归纳假设已有方向互相 -共轭,当前残差则与所有较早方向正交。递推式给出 。因此精确线最小化步使
对 ,由 和 ,同样有 。新残差遂与截至当时的全部方向正交。较早残差都在这些方向的张成空间内,因为 ,且 。因此非零残差互相正交。
要证明新方向的共轭性,使用 。对 ,刚证得的正交性给出 ,再用前一方向的共轭性便得 。对相邻方向,
所以 中的两项相消,完成归纳。这里没有使用整个空间上的正定性,只用了已完成步的正方向曲率。
互相共轭且 的方向线性无关:把一个线性关系分别左乘各 ,每个系数都必为零。若已完成 个正曲率内点步,这些方向张成 ,而 与整个空间正交,故必为零。否则,程序早已在容许误差、边界或非正曲率检查时返回。因此不会走到除以零残差的运算。
概念视角代数
内部 CG 迭代点在 Krylov 子空间上极小化模型
记 。只要每个已完成的步都在内部且 ,对递推关系作归纳便知 张成 。在这组 共轭基下, 分解成严格凸的一维项之和,而 使 恰为其所属项的极小点。因此 是 在 上的唯一极小点。下面的反例正是 始终不离开一条坐标轴的情形。
后续步为何不会抵消第一步的下降
证明
(从 Cauchy 步开始的单调下降)
每个方向开始时,沿该方向的模型导数为
若 ,它在整条向前射线上严格为负。若 ,它在 之前保持非正;边界截断所取的 满足 。每一段返回或完成的线段都降低模型值。首方向是 ,故首步正好到达 Cauchy 点:不是射线最小点,就是边界。若程序继续,其后各段把值再降低。这便同时证明 和定理中的下降量下界。
证明透视
终止定理的两个独立部分
有限步终止与充分下降由不同机制证明。终止方面,归纳法保持非零残差两两正交,所以 中至多容纳 个;微妙之处在于只用到已完成步的曲率 ,从不需要 在整个空间上正定。下降方面,关键一步是首方向为 ,所以第一段正好停在 Cauchy 点,无论是射线最小点 还是边界。此后导数 在每段实际走过的线段上都非正: 时在整条向前射线上如此, 时则直到 。这正是边界规则取向前根的原因。两部分都不涉及全局最优性:边界返回的残差可以很大,零残差也可能错过生成子空间以外的负曲率。
逐步算例
例题 10.2.3
(两个内点步解出正定模型)
取 、、、。此时 、、,且 的范数为 。残差是 ,而 给出 。其曲率是 ,故 。所以 、,且 。模型值是 ,预测下降量为 。
若同一模型的半径改成 ,首个不受限制的射线最小点在球外。从零出发的边界根为 ,得到 ,预测下降量为 。程序不会形成第二个方向。
例题 10.2.4
(一个正曲率步后检测到负曲率)
令 、、、。首方向是 ,曲率为 ,所以 ,而 在球内。接着 、、。其曲率为 ,触发非正曲率规则。
此时 、、。边界根为 ,故返回点是 ,范数为五。模型值从 降至 。这是有用的下降步,却不是精确全局解: 的第一个坐标会要求 ,违反乘子非负的必要条件。
反例模式
零残差也可能错过困难情形
设 、、。CG 只探索第二个坐标,走到 后便以 返回,且 。但 的范数为一,值为 。平移 Hessian 证书在此以 、 成立。未被探索的第一坐标带有负曲率。要修正“残差小便证明找到全局模型解”这个错误说法,必须加入有效的曲率和边界证书;否则只能保留截断 CG 实际已证的充分下降结论。
残差能证明什么
命题 10.2.5
(正定模型的残差上界)
对正定 ,若已知 ,令 、,则
证明
(在驻点附近展开)
两个上界都来自 :首先 ;又因为 ,在 附近展开得 。
若 可行,它也是球上的最小点。即使 在球外,任何可行 相对于约束最小点的模型差,也不超过上述无约束模型差。
常见错误
(把相对残差检查当作误差界)
上述上界依赖正的谱下界;相对条件 本身并不提供该下界。除非已知这样的下界,截断 CG 以小残差返回并不说明它离解有多远。
例题 10.2.6
(未平移残差非零的边界最小点)
取 、、、,于是在 上 。由于在 上 ,最小点是边界点 ,且 。其未平移残差为 ,所以在边界上检查未平移的驻点方程并不正确。取乘子 ,则 、,而由于 ,互补项 为零。因此下面的近似证书把差距的上界定为 :该点正是全局最小点。
若有明确曲率信息,可得到有用的近似证书。
命题 10.2.7
(近似最优性证书)
设 可行、、,并令 。则对任何全局球最小点 ,
证明
(用平移 Hessian 展开)
把 展成 ,舍去非负二次项,再用 。
若点精确位于可行球面,最后一项为零。只有小的 ,却没有半正定检查或互补项控制,便不构成这个证书。截断 CG 不会自动计算合适的 ,也不会证明全空间上的半正定性。
与外层收敛证明的连接
上一单元证明有保障射线步的梯度收敛。
常见错误
(对未受保障的截断 CG 引用外层定理)
未作修改的截断 CG 沿用其 Cauchy 下降下界,却未必沿用长度上界 。因此,不能只因两者都叫信赖域方法便引用该定理。
有一个明确的受保障版本:外层第 次迭代在较小的球
上执行上述程序。输出同时满足
保持上一单元的外层接受及半径规则,包括只有满足原来的 边界条件才扩大半径。在同样的全局 Lipschitz 梯度、目标下界及对称模型范数一致有界假设下,该单元的证明适用于这两个不等式:模型误差估计使用可行性,小半径接受使用下降量不等式,而有限往返论证使用长度上界。因此,这个受保障版本也有 ,或在驻点停止。此论证明确保留长度限制;它不证明未受限制的截断 CG 外层方法,也不证明二阶驻点定理。
练习
快速检查
(对 、、,计算 Cauchy 点及截断 CG 的首次返回。)
先计算 。
解答 · 答案
,所以 、。在 CG 中, 且 ,于是非正曲率规则返回同一边界点,其模型值为 。
快速检查
(若 、、,计算正边界根,并解释为何不取负根。)
写出边界二次方程的 、、。
解答 · 答案
此时 、、,两根是 。向前根为 ,得到球上的 。负根沿方向往后走,而下降证明控制的是向前线段。
快速检查
(设 ,某内点近似解有 。给出它到无约束二次模型最小点的距离及目标差上界。)
用 代入残差上界。
解答 · 答案
给出距离至多 ,目标差至多 。这些是利用已知谱下界的严格上界;仅凭残差大小不能确定它们。
快速检查
(在标量边界模型 、、 中,取 、。计算 及近似证书的两项。仅有 是否足以使互补误差为零?)
把证书与到最小点 的真实差距比较。
解答
、。残差项为 ,互补项为 。上界虽松但有效:实际差是 。非负乘子未必满足互补性;此处点严格在球内,而乘子为正。
快速检查
(当 、、 时,求受保障半径及保证的预测下降量。解释保障额外提供了哪个假设。)
受保障半径是 。
解答
、。保证下降量是 。除了通常的球可行性与充分下降,保障还提供 ,使已陈述的外层有限往返证明适用。