今天,应该是正式研究共轭梯度法的开始。如果只是运用共轭梯度法,而不去了解其算法的内在含义,这也不是我在《简书》上面写作的意义。所以从现在开始我们探讨 FR 共轭梯度法。
摘要:主要介绍了 FR 共轭梯度法的收敛性,包括精确线搜索和非精确线搜索。精确线搜索选自 Zoutendijk 和 Powell 的收敛性证明,虽然都是精确线搜索,但是假定条件不同。非精确线搜索选自 Al-Baali 证明在强 Wolfe 条件下且时满足充分下降性,并给出全局收敛性。戴彧虹 和 袁亚湘 提出了推广的 Wolfe 线搜索,并证明,则 FR共轭梯度法满足下降性和具有全局收敛性。最后还给出反列,表明这一条件不能进一步放宽,不过反列我没有看太懂,就没有给出。
1、简介
共轭梯度法是求解无约束优化问题常用的方法
其一般的迭代格式为
其中是参数。不同的决定不同的共轭梯度法。
1964 年,Fletcher 和 Reeves 首次提出了解决非线性函数的共轭梯度法,我们称为 FR 共轭梯度法,其形式为
1970 年 Zoutendijk 和 1984 年 Powell 分别给出了 FR 共轭梯度法在精确线搜索下的全局收敛性()。1985 年,AI-Baali 给出了 FR 共轭梯度法在强 Wolfe 线搜索下
其中的全局收敛性。1993 年,刘光辉,韩继页,阴红霞 把这一结果推广到。1996 年,戴彧虹 和 袁亚湘进一步延申,证明在推广的 Wolfe 线搜索下,即是 (5) 式和
其中,若,可以证明 FR共轭梯度法在推广的 Wolfe 线搜索下的全局收敛性。显然可以看出,推广的 Wolfe 线搜索是强 Wolfe 线搜索的一种推广。
值得注意的是,AI-Baali 的在证明全局收敛性的同时给出了充分下降性,而 戴彧虹 和 袁亚湘 虽然推广了结果,但是只是满足下降性。为了力求全面,本文给出 FR 共轭梯度法的四种证明,分别是 Zoutendijk 和 Powell 在精确线搜索下的收敛性, AI-Baali 和 戴彧虹在非精确线搜索下的收敛性。
2、 FR 在 精确线搜索下的收敛性(Zoutendijk)
定理 1:给定,假定水平集有界,是由 (2), (3) 和 (4) 产生的点列。若是一阶连续可微的,则 FR 共轭梯度法或有限步终止,或者
证明:当序列是有穷点列时,结论是显然的。现假设序列是无穷点列,这时有,由于,故
从而是下降方向,是单调下降序列,,所以是有界点列,因此必有聚点。
设是的一个聚点,则存在子列收敛到,这里是子序列的指标集。由的连续性知,对于 有
类似地,也是有界点列,故存在子列收敛到,这里是无穷序列,并且对于,有
于是
现在,用反证法证明,假定,则对于充分小的,有
由于
故对于,令,可得
与上矛盾,从而证明,即是的驻点。
3、 FR 在 精确线搜索下的收敛性(Powell)
引理 2:设目标函数有下界,导数满足 Lipschitz 条件
考虑一般方法,其中满足,满足 (5) 和
则有
上述关系式也被称为 Zoutendijk 条件.
证明:由 (8) 知
另一方面,由 Lipschitz 条件有
利用以上两式得
利用上式和 (6) 式得
其中,对上式从求和,注意下方有界,即知 Zoutendijk 条件成立。
定理 3:设目标函数有下界,导数 Lipschitz 连续。考虑 FR 共轭梯度法 (2) , (3) 和 (4),其中步长因子由精确线搜索求出,如果对,则
证明:由于采用的是精确线搜索,令即有
利用上面两式和 (4) 式,消除,可得
将上式平方,并注意到,便有
利用上式递推,得
若定理不真,则必存在某常数,使得对所有的都有
在 (9) 式中运用上式,可得
上式表明
利用夹角的定义,可将 Zoutendijk 条件写成
由上式和 (10) 式可知
故对充分大的,有
利用上式和 (11) 式,有
上式和 (12) 式相矛盾,故假设不成立,命题得证。
4、FR共轭梯度法在强 Wolfe 线搜索的收敛性(AI-Baali)
引理 4:考虑 FR 共轭梯度法 (2)、(3) 和 (4),其中步长因子满足 (5) 和 (6). 如果参数,则对所有的,有下式成立:
证明:用归纳法,当时,因为,结论显然成立。现在假设对任何结论都成立。将 (3) 式与作内积,并利用 (4) 式,得
在上式中利用 (6) 式,得
利用上式和归纳假设,我们有
故结论对所有的都成立,引理得证。
定理 5:设目标函数有下界,导数 Lipschitz 连续,考虑 FR 共轭梯度法 (2)、(3) 和 (4),其中步长因子满足强 Wolfe 线搜索 (5) 和 (6)。如果参数,则有。
证明:对 (3) 式两端取模平方,得
上式除以,记,并利用 (5) 式
利用 (6) 式和 引理 4 知
则有
注意到,递推
若定理不真,则必存在常数,使得
结合上面两式得
可见,最多线性增长。于是
上式和 引理 3 矛盾,故结论成立。
注: 从 引理 4 中,我们可以看出,结论对仍然成立,但此时我们仅仅能推出
此时,充分下降条件就不再成立。虽然如此,我们可以证明,只要每一个方向均下降,则采取强 Wolfe 线搜索的 FR 共轭梯度法每相邻两个迭代点列中必有一个使得充分下降成立成立,进而可证 FR 方法的全局收敛性。
5、FR共轭梯度法在推广的 Wolfe 线搜索的收敛性(戴彧虹 和 袁亚湘)
定理 6:设目标函数有下界,导数 Lipschitz 连续,考虑 FR 共轭梯度法 (2)、(3) 和 (4),其中步长因子满足推广的 Wolfe 线搜索 (5) 和 (7),如果
则有
证明:因为时,,利用 (4) 式,则有
利用 (7) 式,定义,则有
根据上面的第一个不等式,我们有
利用第二个不等式,有
利用上式和,我们有
记,利用上式,有
由于,所以上式有
假设,即存在,对任意的,都有
从而有
其中
上式表明
则有
与 Zoutendijk 条件相矛盾,故假设不成立,命题得证。
定理 7:设目标函数有下界,导数 Lipschitz 连续,考虑 FR 共轭梯度法 (2)、(3) 和 (4),其中步长因子满足推广的 Wolfe 线搜索 (5) 和 (7),若,则
证明:当时,,则。假设结论对时成立,则
若,则,从而是下降方向,命题得证
6、参考文献
[1] Fletcher R, Reeves C. Function minimization by conjugate gradients. Comput J, 1964, 7 ,149-154.
[2] Zoutendijk. Nonlinear programing, computational methods. Integer and Nonlinear Programming. Amsterdam: North-Holland, 1970,37-86.
[3] Powell. Nonconvex minimization calculations and the conjugate gradient method. Lecture Notes in Mathematics, 1984, 122-141.
[4] Liu G H, Han J Y, Yin H X. global convergence of the Fletcher-Reeves algorithm with an inexcat line search. Institute of Applied Mathematics, 1993.
[5] Dai Y H, Yuan Y X. Convergence properties of the Fletcher-Reeves method. IMA Journal of Numerical Analysis, 1996,16,155-164