从二次函数走向一般目标函数
对称正定二次函数的共轭梯度法(CG)利用上一个方向,避免抵消已取得的进展。其简短递推与有限步终止依赖固定曲率及精确运算。目标函数不是二次函数时,能否保留节省内存的递推?非线性共轭梯度法正是这样做;但“共轭”只是名称的由来,不代表新方向必然对某个固定矩阵全部共轭。
定义 7.3.1
(Fletcher–Reeves 非线性共轭梯度法)
设 连续可微,,取 。若 便停止。否则选正步长 ,令 ,再取
的点是驻点,但非凸函数的驻点未必是极小点。由于 时已停止, 的分母非零。实现时只需存储少量向量并计算梯度,不必计算 Hessian。其他 选法定义不同的方法,其保证不能自动当作 FR 的保证。
我们希望 。对 在零处求导,得到 ;因此这个值严格为负,就保证充分小的正步长使函数下降。单看 前的负号并不够:从旧方向继承的部分可能压过它。
精确线搜索与二次函数的计算
假设 是可微线函数的内点精确极小点,则
所以只要 ,下一个 FR 方向便严格下降。这里的正交是对“上一个方向”而言;对非线性目标函数,它不一定同时正交于所有更早的方向。精确线极小点可能难以求出,甚至在正射线上不存在,故此观察本身并不是实际线搜索的保证。
对特殊二次函数 ,其中 对称正定,梯度变化满足 ,而精确步长产生了方法名称所指的共轭性。
定理 7.3.2
(二次函数上精确 Fletcher–Reeves 步的共轭性)
设 , 对称正定,并以精确线搜索执行 FR,直到梯度为零。则所得方向两两 -共轭,而每个梯度 都正交于 。
证明
(对步数归纳)
第一步有 及 ,所以 。假设直到 的方向两两 -共轭,而且 正交于所有更早的方向。精确搜索给出 ;梯度更新及共轭性则给出 时 。因 时 ,也有 。于是利用 ,得
因此 FR 选择使 。若 ,由 及刚证得的正交性,得 : 和 都在 张成的空间中。故 。以 为起点便完成归纳。
标准线性 CG 理论进一步指出此二次问题至多 步终止;一般非线性 并不随之具有两两共轭或有限步终止的性质。
完整二维算例
例题 7.3.3
(对角二次函数上的两个精确 FR 步)
取 ,即 ,并取 ,则 、,精确线搜索给出
由 和 ,得 、。直接计算可见 。第二次精确步长为 ,得到 。这个有限步终止展示的是二次函数定理,而不是对一般非线性问题的预测。
步只是上界;从坐标轴上的点出发即可看到这一点。
例题 7.3.4
(少于 n 步便终止)
对同一个 ,从 出发。则 、,且 ,所以 、。方法一步后即停止;分母将为 的 从未计算。初始误差只落在 的一个特征向量上,因此一个搜索方向已经足够。
非精确搜索:强 Wolfe 条件的作用
实践中通常接受足够好的步长,而不精确最小化线函数。
定义 7.3.5
(强 Wolfe 条件)
设 是下降方向,。若步长 满足
则称它满足强 Wolfe 条件。
第一式是 Armijo 充分下降条件。第二式控制新方向导数的绝对值,即使导数已改变符号也适用。条件针对实际接受的步长;只选定 并不说明搜索已找到合格步长。
定理 7.3.6
(Fletcher–Reeves 的一致下降界)
假设 连续可微、,每个接受的步长都满足固定常数 的强 Wolfe 条件。按上式构造 FR 方向,梯度为零时停止。停止前每个方向都满足
因此每个方向都是下降方向。这个结论本身并不断言迭代收敛到极小点。
证明
(对归一化斜率归纳)
在 时定义 ,初值为 。把 FR 递推式与 作内积,再除以 ,得
令 ,并假设 且 ;于是 是下降方向,强 Wolfe 条件适用于它的步长。强曲率条件给出 ,所以第二项的绝对值不超过 。因此
这组界给出 及 。因 满足两者,归纳即完成证明。
证明透视
控制继承的旧方向
证明只追踪一个标量,即归一化斜率 ;危险完全来自继承项 。强 Wolfe 条件就用在这里,而且只有带绝对值的形式才有用:普通 Wolfe 曲率条件只从下方限制 ,一个很大的正值仍可把 推到零以上。归纳假设必须携带两件事:界 ,因为曲率估计与 成正比;以及下降性 ,因为 Wolfe 条件只对下降方向有定义。关键一步是把 选为 的不动点,使区间的下端自我重现。假设 用在上端: 等价于 ,即 。论证完全没有用到 Armijo 不等式;该条件影响的是收敛,而不是这个符号估计。
要区分逐步下降性与收敛性:后者还涉及步长、光滑性、水平集及其他假设。对非凸目标函数,即使每一步方向都下降,算法仍可能趋近不是极小点的驻点。
例题 7.3.7
(同一二次函数上的强 Wolfe 步)
回到 、、,取 、。线函数 满足 、。试用 ,而不是精确的 。Armijo 条件成立,因为 ;强曲率条件也成立,因为 。于是 、、,且
因此 ,落在 时定理给出的区间 内,但不等于精确搜索的值 。
下降界在非精确步之后仍然成立;假设精确搜索的二次函数定理却不再成立。
反例模式
非精确步失去有限步终止
一个诱人的说法是:在二维对称正定二次函数上,只要步长满足强 Wolfe 条件,FR 仍会在两步内终止。在上例中 ,所以
两个方向并不共轭。即使第二步是精确的,,所得 ,仍未到达最小点。有限步终止需要每一步(不只是最后一步)都是精确线搜索,并且需要精确运算。
常见误解与实现选择
常见错误
(在 Wolfe 步后套用精确搜索的等式)
精确搜索后有 ,因而 。Wolfe 步只限制 ,一般不使其为零,上例的 就是明证。同样,有限步终止定理需要固定的对称正定二次函数及精确运算;舍入误差、非精确搜索和变化的 Hessian 都可能破坏其正交等式。
常见错误
(小梯度不能证明极小)
对 , 处梯度为零,但零是严格局部极大点。以小梯度停止只表示近似驻点;它本身不能证明局部或全局极小性。
重启是把 设为 ,不再沿用旧方向。只要 ,它就恢复下降性,但也丢弃了已累积的方向信息。对满足上述定理假设的 FR 方法,证明下降性不需要重启;实际的重启规则及数值停止容差则需另行选择。应计算结果的目标函数值与梯度;若需要最优性证书,还要利用凸性或合适的二阶论证。
练习
练习 7.3.8
(在第一个例题中,直接验证 和 。为什么后者使用 而不是普通内积?)
基础
解答(3)
- 1
检查与上一个方向正交
。
- 2
检查共轭性
,因此 。
- 3
说明 的作用
二次函数的曲率由双线性形式 衡量;欧氏正交是另一个条件。此处 。
练习 7.3.9
(设 FR 方向满足 ,接受的步长以 满足强 Wolfe 条件。若 ,求 的界。)
核心
解答(3)
- 1
写出归一化递推式
,其中 。
- 2
限制继承项
关键一步
。
依据: 强曲率条件给出 。
- 3
得出结论
,严格为负。这个局部计算不要求题中比值一定由此前的 FR 迭代产生。
练习 7.3.10
(设 、、。 是否为下降方向?重启有什么作用?)
基础
解答(2)
- 1
计算所给方向
,与 的内积是 ,所以是上升方向。
- 2
重启
重启得到 ,内积为 ,是下降方向。
练习 7.3.11
(在内点精确线极小点处,对任意有限标量 (不只是 FR)证明 。为什么这不足以证明收敛?)
核心证明
解答(3)
- 1
在线上使用一阶条件
。
依据: 线函数可微,且 是内点极小点。
- 2
把递推式与 作内积
。
- 3
结论的局限
∎方向下降本身既不给出总进展的界,也不判定极限驻点的性质。