景書杰,張小亮

解線性約束優(yōu)化問題的自適應(yīng)-BFGS信賴域算法

景書杰,張小亮

(河南理工大學(xué)數(shù)學(xué)與信息科學(xué)學(xué)院,河南焦作454003)

針對線性約束優(yōu)化問題,在每次迭代時充分利用當(dāng)前迭代點及其一階導(dǎo)數(shù)的信息自動生成一個信賴域半徑,結(jié)合BFGS算法的優(yōu)點,構(gòu)造了線性約束優(yōu)化問題的一種具有全局收斂性的自適應(yīng)-BFGS算法.在一定條件下,給出了算法的全局收斂性的證明.

線性約束優(yōu)化;自適應(yīng)信賴域算法;BFGS校正;全局收斂性

0 引言

信賴域算法是一類重要的數(shù)值計算方法,由于具有較好的可靠性和很強的收斂性,因而在近30年來受到最優(yōu)化研究界的重視,特別是近幾年來,一直是最優(yōu)化領(lǐng)域中的一個研究熱點.

本文主要考慮下列線性約束問題

其中f(x)和ci(i=1,…,m)是定義在Rn上的實值連續(xù)可微函數(shù).信賴域方法是一種迭代的方法,每次迭代要求計算信賴域子問題;設(shè)第k次迭代得到的當(dāng)前迭代點xk是可行點,信賴域的子問題是其中g(shù)k=▽f(xk),B0為對稱正定矩陣,Bk是由BFGS校正公式產(chǎn)生的對稱正定矩陣,Δk是信賴域半徑.文獻[1]中Sartenaer給出了一個自動確定初始信賴域半徑的ITRR算法,文獻[2,3]給出了一些自適應(yīng)信賴域半徑的選取機制,具體如下:

張華等[4]將一種基于函數(shù)值平均權(quán)重的非單調(diào)線搜索技術(shù)與自動確定信賴域半徑的方法相結(jié)合,提出求解無約束優(yōu)化問題的一個新的非單調(diào)自動確定信賴域半徑的算法.

楊揚、李紅等[5,6]提出了帶線搜索的信賴域算法,利用線搜索取代求解函數(shù)的子問題,大大減少了計算量,提高了計算效率.

楊揚、張雅琴等[7,8]基于錐模型提出了新的信賴域算法,擴展了信賴域算法的范圍,促進了信賴域算法的發(fā)展.

以上算法均為作者解決線性約束問題提供可靠的理論基礎(chǔ)和研究思路.

BFGS校正公式是非常好的一種擬牛頓方法,利用BFGS公式我們可以得到對稱正定的校正矩陣Bk,從而保證算法的總體收斂性.BFGS校正公式為

其中sk=xk+1-xk,yk=gk+1-gk,gk和gk+1分別是f(x)在xk和xk+1處的梯度值.

在這里我們將自適應(yīng)算法和BFGS校正方法相結(jié)合應(yīng)用到線性約束優(yōu)化問題,構(gòu)造了線性約束優(yōu)化問題的一種具有全局收斂性的自適應(yīng)-BFGS算法.顯然信賴域子問題是二次規(guī)劃問題,我們可以通過已有的方法求解信賴域的子問題(2)得到試探步dk.這里我們定義實際下降量為Aredk=f(xk)-f(xk+dk),預(yù)測下降量,我們給出如下算法.

1 自適應(yīng)-BFGS信賴域算法

步驟0:給定x0∈Rn,對稱矩陣B0∈Rn×n,Δ0>0,ε>0,0

步驟1:計算dk,若‖dk‖≤ε,則終止;否則轉(zhuǎn)步驟2;

步驟4:如果rk≥uk,則令xk+1=xk+dk;否則,令i=i+1轉(zhuǎn)步驟1;

2 算法的收斂性分析

假設(shè)(1)對任意的k,存在有界閉集Ω使得xk,xk+1∈Ω;

(2)f(x)連續(xù)可微,▽f(x)一致連續(xù),▽2f(x)和Bk是一致有界的.

引理2.1[10]若假設(shè)(2)成立則有A redk-Predk=o(‖dk‖2).

引理2.2[11]設(shè)dk是子問題(2)的解,則有

證明 根據(jù)dk的定義,則對任意α∈[0,1]都有

則有

證明 假設(shè)結(jié)論不成立,則{f(xk)}下方有界,且存在正常數(shù)ε1,使得對所有的k,

由假設(shè)Bk是一致有界的,則存在ε>0,使得對所有的k,有Bk≤ε,

再由引理2.2可得

又由于{f(xk)}單調(diào)下降有下界,且ε,ε1,η,μ都是正整數(shù),由上式可得當(dāng)k充分大時,我們有

則

由引理2.2可知

對于充分大的k∈K1都成立.

又由于f(x)是連續(xù)可微以及{Bk}一致有界,由引理2.1我們有

由(5),(6)兩式可得

這顯然與(4)式相矛盾,則假設(shè)錯誤,原定理為真.

[1] SARTENAER A.Automatic Detemination of an Initial Trust Region in Nonlinear Rogramming[J].Siam J Sci Com put,1997,18 (6):1788-1803.

[2] ZHANG X S,CHEN ZW,L I AO L Z.A Self-adaptive Trust RegionMethod for Unconstrained Opti mization[J].Operate Reserch Transactions,2001,5(2):53-62.

[3] ZHANG X S,ZHANG J L,L I AO Z.An Adaptive Trust Region Method and Its Convergence[J].Science in China(Series A), 2002,45(4):620-631.

[4] 張 華,焦寶聰.一個基于函數(shù)值平均權(quán)重的新的非單調(diào)自適應(yīng)信賴域算法[J].首都師范大學(xué)學(xué)報(自然科學(xué)版), 2008,29(3):1-6.

[5] YANG Y,SUN W Y.A New Nonmonotonic Self-adaptive Trust Region Algorithm with line Search[J].Chinese Journal of Engineering M athem atics,2007,24(5):788-794.

[6] 李 紅,焦寶聰.一類帶新搜索的自適應(yīng)信賴域算法[J].運籌學(xué)報,2008,12(2):97-104.

[7] 楊 揚,孫文瑜.求解非線性最小二乘問題的自適應(yīng)錐模型信賴域算法[J].南京師范大學(xué)報(自然科學(xué)版),2007,30 (1):13-21.

[8] 張雅琴,王希云.一個基于錐模型的自適應(yīng)信賴域算法[J].五邑大學(xué)學(xué)報(自然科學(xué)版),2008,22(2):65-69.

[9] 袁功林,韋增欣.一個新的BFGS信賴域算法[J].廣西科學(xué),2004,11(3):195-196.

[10] FU J H,SUN W.NonmonotoneAdaptive Trust-regionMethod forUnconstrainedOpti mization Problems[J].AppliedM athem atics and Com putation,2005,163(5):489-504.

[11] 袁亞湘,孫文瑜.最優(yōu)化理論與方法[M].北京:科學(xué)出版社,1997.

Adaptive-BFGS Trust-region M ethod for L inear Constra ined Opti m ization Problem s

J I NG Shu-jie,ZHANG Xiao-liang
(School of M athem atics and Infor mation Science,Henan Polytechnic University,Jiaozuo454003,China)

A adaptive-BFGS trust-region method for linear constrained optimization is introduced.Not only the trustregion radius in thismethod is automatically detemined with first order information,but also combiningwith the advatage of the BFGS algorithm.Under the certain conditions,the global convergence of the algorithm is proved.

linear constrained optimization;adaptive trust algorithm;BFGS update;global convergence

O224

A

0253-2395(2010)04-0500-04

2010-03-05;

2010-06-10

國家自然科學(xué)基金(10671057)

景書杰(1965-),男,河南長垣人,博士,副教授,主要從事最優(yōu)化理論及應(yīng)方面研究.E-mail:jsj-jjj@bpu.deu. cn