精确线搜索只在当前直线上选最好的位置,并非一次找出未来所有步骤的最佳路径。在狭长的二次函数等高线上,新的负梯度可能再次横越谷底。我们可以定量分析这一现象,而不必假设算法有限步终止。
方法与几何
设 为实对称正定的 矩阵,定义
定义 3.2.1
(二次函数上的精确最速下降法)
目标值差为 。若 ,便停止:此时 。否则,精确最速下降法取
分母为正。沿直线对目标函数求导,可见 是所有实步长中唯一的最小化步长,而且为正。又因 ,所以 。连续梯度在欧氏内积下正交,但这本身既不保证它们 -共轭,也不保证新梯度为零。
精确下降界
定理 3.2.2
(正定二次函数的精确线搜索收敛率)
假设 的特征值均在 内,其中 ,并设 。每个尚未终止的精确最速下降步都满足
在精确算术下,重复 步所得的界为初始差乘以 。若 ,一步便到达最小点。
证明
(由谱界推导下降因子)
暂略迭代下标,设 。把精确步长代入二次式,得到
除以初始目标值差,得到比值
要控制分母,将 在 的一组标准正交特征向量基底展开。令 为各系数的平方除以 ,则 。每个 均满足
因为 。令 、,取加权平均可得 。由 ,有 ,因此
代入比值,并用 ,便得所述因子。反复应用单步不等式;若已终止,其后保留最小点。当 时,对称性给出 ,精确步长是 。
证明透视
谱区间在哪里起作用
证明分为两个独立部分。第一部分是精确恒等式:一步下降量 只用到步长沿直线最小化以及 ,不涉及任何特征值界。谱只在第二部分出现,即界 。其关键一步是 上的逐点不等式 :它对权重 是线性的,所以取平均后仍成立;再用初等不等式 ,把和的界转为积的界。两个不等式同时取等号,当且仅当权重只落在两个极端特征值上且各为 ,所以这个界是精确的。正定性贯穿全程,因为要除以 ,须有 。
这个界衡量的是目标值差,不是欧氏误差或残差范数。它使用极端特征值;实际下降可以快得多。 大会令最坏情况的因子接近一,但不代表每个起点都收敛缓慢。
精确算出最坏情况路径
例题 3.2.3
(正交梯度与反复的锯齿路径)
取 、、。此时 、、,故
初始目标值为 ,下一个为 ,比值 正好等于 、 时的 。下一步的步长也为 ,而 。因此路径以缩小的尺度重复:精确线搜索不会在两步内解出这个二维问题。虽然 ,却有 ,两个搜索方向并非 -共轭。
例题 3.2.4
(最坏情况何时恰好出现)
证明显示了在 时比值何时等于 。 取等号,迫使每个带正权重的特征值都是 或 。记其权重为 ; 取等号要求 ,即
因此 :梯度沿 的一个特征向量与沿 的一个特征向量的分量平方相等,其他方向没有分量。对 ,这就是 ;上面的 与 都是这种形式,所以那条路径的每一步都达到上界。
例题 3.2.5
(优于上界的起点)
仍取 、,并取 。则 、、、,故
验算:下降量为 。比值为 ,远低于 ,因为梯度分量的平方 与 相差很大。
反例模式
条件数大不代表必然收敛缓慢
沿用同一个 ,但取 ,梯度是特征向量。使目标函数最小的步长为 ,故 。条件数描述最坏情况的保证,并不是每个初始误差实际观察到的速度。本定理亦不能用于负定 Hessian:例如 在 沿负梯度的直线限制无下界,所以精确线上的最小点不存在。
下面的交互图以精确分数执行精确最速下降法,并把每步的比值 与 比较:在 上从 出发恰好达到 ,从其他起点出发则更好。
常见错误
常见错误
(精确线搜索不会在 n 步内终止)
连续梯度互相正交,容易让人以为会像共轭方向那样在 步后终止。第一个例题否定了这一点:在二维问题上,路径以 的比例无限重复,因为 。
常见错误
(收敛率针对目标值差,而非误差)
定理收缩的是 ,其中 。由于 ,欧氏误差只满足 ;若对 只写 ,就漏掉了因子 。
练习与解答
快速检查
(若 是 的特征向量,特征值为 ,求 和 。)
解答 · 答案
,,一步便到达二次函数的唯一最小点。
快速检查
(若 、,初始目标值差为 ,求三步后的上界。)
解答 · 答案
,所以目标值差至多 ;实际值可以更小,甚至已为零。
快速检查
(设 、、。它们是否欧氏正交?是否 -共轭?)
解答 · 答案
,但 ,所以不是 -共轭。