一類(lèi)推廣的非單調(diào)擬牛頓算法

徐瑩瑩,陳 陽(yáng)

(鄭州工業(yè)應(yīng)用技術(shù)學(xué)院基礎(chǔ)教學(xué)部，河南 鄭州 451150)

一類(lèi)推廣的非單調(diào)擬牛頓算法

徐瑩瑩,陳 陽(yáng)

(鄭州工業(yè)應(yīng)用技術(shù)學(xué)院基礎(chǔ)教學(xué)部，河南 鄭州 451150)

目的為了更有效地利用擬牛頓算法求解無(wú)約束優(yōu)化問(wèn)題,提高擬牛頓算法的收斂速度，并在數(shù)值實(shí)驗(yàn)上得到最優(yōu)解。方法針對(duì)擬牛頓方程進(jìn)行修正，在修正的擬牛頓方程基礎(chǔ)上添加參數(shù)，利用修正BFGS校正公式,采用非單調(diào)線(xiàn)性搜索準(zhǔn)則，提出一類(lèi)新的非單調(diào)擬牛頓算法。結(jié)果新算法推廣了已有的擬牛頓方程，在一定條件下，具有全局收斂性,利用Matlab編制程序?qū)π滤惴ㄟM(jìn)行數(shù)值實(shí)驗(yàn)。結(jié)論通過(guò)數(shù)值試驗(yàn)，選取測(cè)試函數(shù)，得到了最優(yōu)解。證明了推廣的非單調(diào)擬牛頓算法是有效的。利用新算法可以更有效地求解無(wú)約束優(yōu)化問(wèn)題。

無(wú)約束優(yōu)化；非單調(diào)；擬牛頓方程；線(xiàn)性搜索；全局收斂性

本文基于Z.X.Wei[6],W.Xiao,F.J.Sun[7]提出的修正的擬牛頓方程，利用修正的BFGS校正公式[8]，結(jié)合非單調(diào)線(xiàn)性搜索準(zhǔn)則[9]，提出了一類(lèi)新的非單調(diào)擬牛頓算法，并根據(jù)文獻(xiàn)[8]的證明思路,證明了新的非單調(diào)擬牛頓算法具有全局收斂性[10]。

1 算 法

(1)

并給出了矩陣的3種選擇：

(2)

其中γk=2(fk-fk+1)+(gk+gk+1)Tsk。

(3)

其中γk=2(fk-fk+1)+(gk+gk+1)Tsk。

通過(guò)以上分析，本文提出的算法步驟如下：

Step1 給出初始點(diǎn)x0∈Rn和初始正定矩陣B0∈Rn×n，令k∶=0;

Step2 若‖gk‖=0則停止，否則計(jì)算Bkdk=-gk得到搜索方向dk;

Step3 利用非單調(diào)線(xiàn)性搜索[9]得到步長(zhǎng)αk。

(4)

(5)

利用xk+1=xk+αkdk得到下一個(gè)迭代點(diǎn)。

Step4 令sk=xk+1-xk,如果‖xk+1-xk‖=0，則停止;否則計(jì)算

(6)

其中ε充分小。利用文獻(xiàn)[8]中改進(jìn)的BFGS校正公式

(7)

得到對(duì)稱(chēng)正定矩陣Bk+1。

Step5 令k=k+1，轉(zhuǎn)第二步。

2 收斂性分析

做如下假設(shè)：

假設(shè)(1)：水平集Ω={x|f(x)≤f(x0)}包含于一個(gè)有界凸集D上；

假設(shè)(2)：目標(biāo)函數(shù)f(x)是一致凸的，即存在正常數(shù)c1,c2， 使得c1‖z‖2≤zTG(x)z≤c2‖z‖2,?x,z∈Rn;

假設(shè)(3)：目標(biāo)函數(shù)f(x)是二階連續(xù)可微的。

(8)

其中ε=xk+θsk,ε3=xk+θ1ksk,ε4=xk+θ2ksk,θ、θ1k、θ2k∈(0,1)。

(10)

證明

(11)

引理4[7]若假設(shè)(3)成立，則存在ε0(ε0gt;0)滿(mǎn)足

(12)

定理2 若假設(shè)(1)、(2)、(3)成立，如果x0是初始點(diǎn)，B0是任意對(duì)稱(chēng)正定矩陣，且序列{xk}由算法產(chǎn)生，其中步長(zhǎng)αk由非單調(diào)線(xiàn)搜索決定。則lim inf‖gk‖=0。

證明根據(jù)引理4和(5)式可得

f(xk+1)≤f(xh(k))-ε1‖sk‖rk

根據(jù)引理6可得

(13)

由于xk∈Ω,Ω是有界的，則存在cngt;0，滿(mǎn)足‖gk‖≤cn。故

(14)

下面用反證法來(lái)證明。假設(shè)lim inf‖gk‖gt;0，即假設(shè)存在常數(shù)c′gt;0，使得

‖gk‖≥c′,k=0,1,…

(15)

(16)

因此lim inf‖gk‖=0。

3 數(shù)值實(shí)驗(yàn)

為檢驗(yàn)新算法的實(shí)驗(yàn)效果，選取文獻(xiàn)[15]中的部分測(cè)試函數(shù)，利用Matlab編制程序?qū)π滤惴ㄟM(jìn)行了數(shù)值實(shí)驗(yàn)，新算法中參數(shù)設(shè)置同文獻(xiàn)[7]。k表示迭代次數(shù)，依次為：文獻(xiàn)[7]中Ak5、文獻(xiàn)[6]中Ak2和新算法。fk表示測(cè)試函數(shù)最優(yōu)解。

算例維數(shù)Kfk1464/64/60918e-22/256e-18/258e-172475/71/74249e-21/977e-20/822e-213325/31/25346e-15/104e-18/283e-154322/21/21-0501/-0501/-050152155/145/156123e-32/493e-32/0

數(shù)值實(shí)驗(yàn)結(jié)果表明本文提出的算法是有效的，并且新算法相對(duì)文獻(xiàn)中算法的數(shù)值實(shí)驗(yàn)效果有所改善。

[1] 袁亞湘，孫文瑜.最優(yōu)化理論與方法[M].北京：科學(xué)出版社，1997：183-218.

[2] 劉光輝,尹紅婷.BFGS算法的全局收斂性分析[J].曲阜師范大學(xué)學(xué)報(bào),1994(01):1-8.

[3] 李文鈺.一類(lèi)求解無(wú)約束優(yōu)化的自適應(yīng)擬牛頓型信賴(lài)域算法[J].北華大學(xué)學(xué)報(bào),2014(06):715-717.

[4] WEI Z X．Convergence properties of class of quasi-Newton algorithm[J].Guangxi Sci,2006(13)：282-287.

[5] 牛瀟萌.非線(xiàn)性互補(bǔ)問(wèn)題光滑化擬牛頓算法[J].計(jì)算機(jī)工程與應(yīng)用,2013(18):33-35.

[6] WEI Z X,LI GUO Y,QI L Q.New quasi-Newton methods for unconstrained optimization problems[J].Appl Math Comp,2006:1156-1188.

[7] XIAO W，SUN F J．On quasi-Newton methods with modified quasi-Newton equation[C]//Jiang Yong,Li Jianliang Information Science and Engineering.Proceeding of 2008 International Pre-Olympic Congress on Computer Science.World Academic Press,2008:359-363.

[8] 張華軍,趙金,羅慧.基于擬牛頓法的同時(shí)擾動(dòng)隨機(jī)逼近算法[J].華中科技大學(xué)學(xué)報(bào),2014(09):1-3.

[9] SUN W Y,Zhou QunYan.An unconstrained method using non-monotone second-order Goldstein’s line search[J].Sci China Series A Math,2007(10):1389-1400.

[10] 易君君,汪寶,顏倩倩.基于新擬牛頓方程的優(yōu)化算法設(shè)計(jì)及應(yīng)用[J].寧波工程學(xué)院學(xué)報(bào),2015(03):12-18.

[11] YUAN G L，WEI Z X．The superlinear convergence analysis of a non-monotone BFGS algorithm on convex objectivefunctions[J].Acta Math Sinica Engl Series,2008(01):35-42.

[12] 鮑瑩瑩,王希蕓,程翠梨.一種基于弱擬牛頓方程的對(duì)角擬牛頓法[J].寧夏師范學(xué)院學(xué)報(bào),2013(03):15-19.

[13] 王海濱.改進(jìn)的BFGS算法在一種新搜索下的收斂性[J].河北理工學(xué)院學(xué)報(bào),2006(02):103-106.

[14] MORE J J,GARBOW BS,HILLSTROM KE.Testing unconstrained optimization software[J].ACM Trans Math Softw,1981(07):17-41.

[15] 孫清瀅,徐琳琳,劉麗敏，等.基于稀疏對(duì)角擬牛頓方向的非單調(diào)超記憶梯度算法[J].工程數(shù)學(xué)學(xué)報(bào),2012(03):375-383.

[責(zé)任編輯：劉志媛英文編輯：劉彥哲]

AGeneralizedNon-monotoneQuasi-NewtonAlgorithm

XUYing-ying,CHENYang

(Zhengzhou University of Industrial Technology,Zhengzhou,Henan 451150,China)

ObjectiveTo make the quasi-Newton method suitable for solving the non-constrained optimization problems,and improve the convergence speed of this method and get the optimal solution in the numerical experiment.MethodsBased on modified quasi-Newton equation with parameters and the BFGS updated,using non-monotone linear search criteria,a new quasi-Newton method with non-monotone is proposed.ResultsThe new algorithm,which has popularized the quasi-Newton method,is verified by numerical experiments programmed in the Matlab language and has global convergence under certain conditions.ConclusionsBy giving suitable test functions,global optimal solution is found.And it is demonstrated that this approach effectively solves some problems with unconstrained optimization.

unconstrained optimization；non-monotone；quasi-Newton equation；linear search；global convergence

來(lái)稿日期：2016-12-14

徐瑩瑩(1988-)，女，河南焦作人，鄭州工業(yè)應(yīng)用技術(shù)學(xué)院基礎(chǔ)教學(xué)部教師，碩士研究生，研究方向?yàn)樽顑?yōu)化理論與算法。

O 224

A

10.3969/j.issn.1673-1492.2017.11.003