一種基于再開始技術(shù)求解無約束優(yōu)化問題的共軛梯度法

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

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

一種基于再開始技術(shù)求解無約束優(yōu)化問題的共軛梯度法

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

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

無約束優(yōu)化問題；共扼梯度法；再開始技術(shù)；收斂性

考慮無約束優(yōu)化問題：

(1)

其中，F(xiàn):Rn→R為連續(xù)可微函數(shù)，求解該問題的一種迭代算法形式為：

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

(2)

(3)

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

(4)

(5)

(6)

(7)

(8)

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

設(shè)α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]設(shè)目標(biāo)函數(shù)f(x)在D?Rn上連續(xù)可微且下方有界，其導(dǎo)數(shù)g(x) Lipchitz連續(xù)即Mgt;0，對y,z∈D，均有‖g(y)-g(x)‖≤M‖y-z‖，則對滿足Wolfe條件的任何αkgt;0均有：

(9)

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

根據(jù)引理1有：

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

因此當(dāng)k充分大后，|βk|lt;clt;1成立，則：

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

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

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

對于一致凸函數(shù)，算法還有如下結(jié)論：

又由引理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]洪云飛，喻娟，陳忠. 對共軛梯度法中標(biāo)量βk的一種修正[J].青海師范大學(xué)學(xué)報(自然科學(xué)版)，2008(4)：18-20.

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

[4]喻娟，陳忠.求解無約束優(yōu)化問題的一種新的共軛梯度法[J].長江大學(xué)學(xué)報(自然科學(xué)版)，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

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

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