一種基于再開始技術求解無約束優化問題的共軛梯度法

洪云飛 (長江大學期刊社，長江大學信息與數學學院，湖北 荊州 434023)

陳 忠，呂一兵 (長江大學信息與數學學院，湖北 荊州 434023)

一種基于再開始技術求解無約束優化問題的共軛梯度法

洪云飛 (長江大學期刊社，長江大學信息與數學學院，湖北 荊州 434023)

陳 忠，呂一兵 (長江大學信息與數學學院，湖北 荊州 434023)

無約束優化問題；共扼梯度法；再開始技術；收斂性

考慮無約束優化問題：

(1)

其中，F:Rn→R為連續可微函數，求解該問題的一種迭代算法形式為：

xk+1=xk+αkdkk=1,2,…

(2)

(3)

其中gk=f(xk)，dk為搜索方向，而akgt;0是通過某種線搜索獲得的步長。純量βk的選取應滿足共軛性，即當f(x)為嚴格凸二次函數且采用精確線搜索時，搜索方向dk關于f(x)的海賽陣共軛。此外，當f(x)為嚴格凸二次函數時，共扼梯度法在精確線搜索下具有有限步終止性，但對一般連續可微目標函數，這一性質很難保證。 當βk選取不同的公式就得到不同的共軛梯度法，比較著名的是FR[1]方法、PRP[1]方法、HS[1]方法和LS[1]方法：

(4)

(5)

(6)

(7)

(8)

其中μ∈(0,1)，這樣就定義了一族帶參數μ的共軛梯度法。顯然如果取μ為0和1，則分別對應了HS方法和LS方法。對αk的選擇一般有精確線搜索和非精確線搜索2種。下面著重考慮非精確線搜索的情形。

設αk滿足強Wolfe線搜索原則，即：

1 算法描述

算法描述如下：

步1 給定x1∈Rn，ε∈(0,1)，選取μ∈(0,1)；-d1=-g1=-f(x1)，令k=1；

步2 若‖g(xk)‖lt;ε，則停止。求得αk使其滿足強Wolfe條件，由式(2)求得xk+1。

2 收斂性分析

引理1[2]設目標函數f(x)在D?Rn上連續可微且下方有界，其導數g(x) Lipchitz連續即Mgt;0，對y,z∈D，均有‖g(y)-g(x)‖≤M‖y-z‖，則對滿足Wolfe條件的任何αkgt;0均有：

(9)

證明用反證法。不失一般性，設對任意k均有gk≠0，假設結論不成立，則?γgt;0，使得‖gk‖ gt;γ，對所有k≥1。

根據引理1有：

將上式累加，由于f(x)在D上下方有界，故有：

因此當k充分大后，|βk|lt;clt;1成立，則：

‖dk+1‖=‖-gk+1+βk+1dk‖≤‖gk+1‖+|βk+1|‖dk‖≤L+c‖dk‖

這與Zoutendijk條件[3]矛盾，故結論得證。

f(xk)-f(xk+αkdk)≥m‖αkdk‖2

對于一致凸函數，算法還有如下結論：

又由引理2可知：

f(xk)-f(xk+1)≥m‖xk-xk+1‖2

將上式累加，由于f(x)下有界，所以有：

故有：

‖xk-xk+1‖→0

0≥f(xk)-f(x1)≥g(x1)T(xk-x1)+c‖xk-x1‖2

[1]戴或虹,袁亞湘.非線性共扼梯度法[M].上海：上?？萍汲霭嫔?2000.

[2]洪云飛，喻娟，陳忠. 對共軛梯度法中標量βk的一種修正[J].青海師范大學學報(自然科學版)，2008(4)：18-20.

[3]Zoutendijk G.NonlinearProgramming,ComputationalMethods[M].Amsterdam:North-Holland,1970：37-86.

[4]喻娟，陳忠.求解無約束優化問題的一種新的共軛梯度法[J].長江大學學報(自然科學版)，2007，4(4)：N12-13.

[編輯] 李啟棟

10.3969/j.issn.1673-1409(N).2012.03.002

O224

A

1673-1409(2012)03-N004-03

2012-01-17

國家自然科學基金項目(10926168)。

洪云飛(1979-)，男，2001年大學畢業，碩士，講師，現主要從事最優化理論與算法方面的教學與研究工作。