李靖雅，歐宜貴

(海南大學(xué) 信息科學(xué)技術(shù)學(xué)院，海南 ?？?570228)

一類非線性方程組的無(wú)導(dǎo)數(shù)投影法的收斂速度分析

李靖雅，歐宜貴

(海南大學(xué) 信息科學(xué)技術(shù)學(xué)院，海南 ?？?570228)

在局部誤差界條件下，分析了一類非線性方程組的無(wú)導(dǎo)數(shù)投影法的收斂速度，證明了序列{dist(xk,X*)}Q-線性收斂于0，從而序列{xk}R-線性收斂于x*；對(duì)更一般的4種方法進(jìn)行了討論，分別得到了其收斂速度.

非線性方程組； 無(wú)導(dǎo)數(shù)法； 投影法； 收斂速度

本文考慮如下的非線性方程組問(wèn)題

(1)

其中,X是Rn空間中的一個(gè)非空閉凸集，F(xiàn)：Rn→Rn是連續(xù)的映射，且滿足下列特性

(2)

其中，X*是問(wèn)題(1)的解集，本文假設(shè)X*非空. 為方便起見(jiàn)，在迭代點(diǎn)xk處，本文以下用‖·‖表示Rn中Euclidean范數(shù)，用Fk表示函數(shù)值F(xk).

無(wú)導(dǎo)數(shù)投影法是一類求解非線性方程組問(wèn)題的有效方法. 對(duì)問(wèn)題(1)，文獻(xiàn)[1]提出了一種無(wú)導(dǎo)數(shù)投影法(DFPA)，詳細(xì)的算法描述如下

DFPA算法

Step 2計(jì)算Fk, 若‖F(xiàn)k‖≤ε，停止計(jì)算；

Step 3利用遞推公式構(gòu)造搜索方向dk，

(3)

其中，βk滿足條件

(4)

Step 4計(jì)算試驗(yàn)點(diǎn)zk=xk+αkdk，其中αk=βρlk，這里lk是滿足下列線搜索方案的最小非負(fù)整數(shù)l，

-F(xk+βρldk)Tdk≥σβρl‖dk‖2；

(5)

Step 5利用迭代式

xk+1=PX[xk-ξk(vFk+F(zk))],

(6)

計(jì)算新的迭代點(diǎn)xx+1，其中

Step 6令k：=k+1，轉(zhuǎn)Step 1.

文獻(xiàn)[1]分析了DFPA算法的整體收斂性. 數(shù)值試驗(yàn)結(jié)果及其相關(guān)的一些比較表明：DFPA算法是求解大規(guī)模非線性方程組問(wèn)題的一種比較有效的方法.但是文獻(xiàn)[1]并未對(duì)DFPA算法的收斂速度從理論上進(jìn)行討論.事實(shí)上，其他關(guān)于非線性方程組的無(wú)導(dǎo)數(shù)投影法也尚未分析其收斂速度，請(qǐng)參考文獻(xiàn)[2-3].

在局部誤差界的條件下，Yamashita和Fukushima[4]于2001年證明了求解無(wú)約束非線性方程組的Levenberg-Marquardt(LM)方法具有局部超線性或二階的收斂性，同時(shí)還指出，局部誤差界條件要比非奇異性條件弱. 隨后，這一條件被許多學(xué)者用來(lái)研究某些優(yōu)化方法的局部收斂率問(wèn)題，參考文獻(xiàn)[5-9].

基于上述討論并受文獻(xiàn)[4-5]的思想啟發(fā)，筆者在局部誤差界等適當(dāng)?shù)募僭O(shè)條件下，給出了文獻(xiàn)[1]所提出的DFPA算法具有線性收斂速度，并對(duì)更一般的情形進(jìn)行了一些討論.

1 預(yù)備知識(shí)

本節(jié)給出對(duì)后面討論有用的定義和結(jié)果，可參考文獻(xiàn)[1,4-5].

定義1設(shè)N是Rn空間中的一子集，且滿足N∩X*≠?，稱‖F(xiàn)(x)‖在N內(nèi)對(duì)問(wèn)題(1)提供了一個(gè)局部誤差界，若存在正常數(shù)c>0，使得

(7)

定義2設(shè)Ω是Rn空間中的一非空閉凸子集，則從Rn到Ω的投影PΩ[x]定義為

(8)

注1 定義2中的投影PΩ[x]具有非擴(kuò)張性[1]，即

(9)

顯然，由式(3)和(4)定義的搜索方向dk具有下列特性，詳見(jiàn)文獻(xiàn)[1]中的Remark2.1.

引理1 DFPA算法構(gòu)造的搜索方向dk滿足

(10)

及

‖F(xiàn)k‖≤‖dk‖≤(1+2t)‖F(xiàn)k‖ ?k.

(11)

1) 對(duì)任意的k，有

(12)

2) 序列{‖xk‖}和{‖zk‖}均有界；

注2 引理2的證明同文獻(xiàn)[1]中引理1.2的證明，本文在此略去.

2 DFPA算法的收斂速度分析

本節(jié)將從理論上分析DFPA算法的收斂速度,為此，需要如下假設(shè)：

假設(shè)1 映射F在非空的閉凸集X內(nèi)Lipschitz連續(xù)，即存在Lipschitz常數(shù)L>0，使得

(13)

(14)

引理3 假設(shè)1成立，則存在常數(shù)γ>0，使得DFPA算法由線搜索方案(5)所確定的步長(zhǎng)αk滿足

(15)

利用上式，并結(jié)合式(10)和假設(shè)1，可以推出

為了分析DFPA算法的收斂速度，還需要其整體收斂性結(jié)論，詳見(jiàn)文獻(xiàn)[1]中的Theorem2.1.

利用上述結(jié)論，分析DFPA算法的收斂速度，在一定的條件下，可以得到下列結(jié)果.

定理2設(shè){xk}是DFPA算法產(chǎn)生的序列，則在假設(shè)1和假設(shè)2滿足的條件下，序列{dist(xk,X*)}Q-線性收斂于0，從而序列{xk}R-線性收斂于x*.

(16)

(17)

顯然，利用式(11)和(15)可推知存在常數(shù)c1>0，使得

(18)

‖xk-zk‖=αk‖dk‖≥c1‖F(xiàn)k‖≥c1c0dist(xk,X*)=c2dist(xk,X*),

(19)

其中c2=c1c0.同時(shí)，由式(11)，(16)，假設(shè)1和αk≤β，?k，即得

(20)

以及

(21)

上式表示序列{dist(xk,X*)}Q-線性收斂于0，從而序列{xk}R-線性收斂于x*.

3 進(jìn)一步的討論

從以上分析可以看出搜索方向dk的構(gòu)造對(duì)DFPA算法的收斂速度具有重要作用. 實(shí)際上，dk還有其他的構(gòu)造方法，只要其滿足下列方向假設(shè)(參考文獻(xiàn)[10])：存在常數(shù)μ1>0和μ2>0，使得

(22)

及

‖dk‖≤μ2‖F(xiàn)k‖ ?k ,

(23)

在采用相同的線搜索方案(5)的情形下，則得到求解問(wèn)題(1)的相應(yīng)算法仍然與DFPA算法具有相同的收斂特性，下面給出的集中構(gòu)造dk的方法.

方法1 構(gòu)造如下的搜索方向dk，

(24)

其中，

(25)

其中，m表示算法記憶先前迭代的步數(shù).

上述構(gòu)造dk的方法是受文獻(xiàn)[11]的啟發(fā)而得到的. 類似于文獻(xiàn)[11]中引理1和引理2的證明方法，可推出下列結(jié)論：

(26)

和

‖dk‖≤(1+ρ)‖F(xiàn)k‖ ?k.

(27)

方法2 構(gòu)造如下的搜索方向dk，

(28)

(29)

符號(hào)a+由下式定義

而ψki的選取滿足關(guān)系式

(30)

其中，ν>-1.

上述構(gòu)造dk的方法是受文獻(xiàn)[12]的啟發(fā)而得到的. 類似文獻(xiàn)[12]中引理2.1和引理3.2的證明方法，可推出下列結(jié)論：存在常數(shù)ω1>0和ω2>0，使得

(31)

和

‖dk‖≤ω2‖F(xiàn)k‖ ?k ,

(32)

特別地，若映射F：Rn→Rn滿足下列單調(diào)性假設(shè)，則可構(gòu)造另外2種搜索方向dk.

假設(shè)3 映射F滿足

注4 若映射F：Rn→Rn是單調(diào)的，則滿足特性(2)，但逆命題一般不成立，詳見(jiàn)文獻(xiàn)[13].

方法3 構(gòu)造如下的搜索方向dk，

dk=-θkFk,

(33)

其中，

其中，sk-1=xk-xk-1,yk-1=Fk-Fk-1+τsk-1(τ>0).

上述構(gòu)造dk的方法同文獻(xiàn)[2],利用單調(diào)性及假設(shè)1，可推出下列結(jié)論

(35)

和

(36)

方法4 構(gòu)造如下的搜索方向dk，

(37)

其中，對(duì)i=1,2,…n,

(38)

(39)

而sk-1及yk-1的定義同方法3.

上述構(gòu)造dk的方法同文獻(xiàn)[3],利用單調(diào)性及假設(shè)1，可推出下列結(jié)論

(40)

和

(41)

利用遞推式(24)或(28)或(33)或(37)來(lái)構(gòu)造搜索方向dk，并分別用其來(lái)代替DFPA算法在Step 2中所構(gòu)造的dk，而其他步驟不變. 記此時(shí)所得到的相應(yīng)算法分別記為SMA，NSMA，SPA和MSPA. 對(duì)4種算法，類似于定理1和2的證明，可推出下列結(jié)論.

注5 當(dāng)v=0時(shí)，SPA算法和SMPA算法分別同文獻(xiàn)[2]和[3]中的算法，但是，文獻(xiàn)[2]和文獻(xiàn)[3]并未從理論上討論算法的收斂速度，因此本文定理4的結(jié)論解決了該問(wèn)題.

[1] Sun M, Liu J. Three derivative-free projection methods for nonlinearequations with convex constraints[J]. Journal of Applied Mathematics and Computing, 2015, 47: 265-276.

[2] Yu Z S, Lin J, Sun J, et al. Spectral gradient projection method for monotone nonlinear equations with convex constrains[J]. Applied Numerical Mathematics, 2009, 59: 2 416-2 423.

[3] Yu G H, Niu S Z, Ma J H. Multivariate spectral gradient projection method for nonlinear monotone equations with convex constraints[J]. Journal of Industrial and Management Optimization, 2013, 9: 117-129.

[4] Yamashima N, Fukushima M. On the rate of convergence of the Levenberg-Marquardt method[J]. Computing(Suppl), 2001, 15:237-249.

[5] Fan J Y. On the Levenberg-Marquardt methods for convex constrained nonlinear equations[J]. Journal of Industrial and Management Optimization, 2013, 9: 227-241.

[6] Li D H, Fukushima M, Qi L Q. Regularized Mewton methods for convex minimization problems with singular solutions[J]. Computational Optimization and Applications, 2004, 28: 131-147.

[7] Ma C, Wang C Y. A nonsmooth Levenberg-Marquardt method for solving semi-infinite programming problems[J]. Journal of Computational and Applied Mathematics, 2009,230: 633-642.

[8] Ling C, Wang C F, He H J. A new Levenberg-Marquardt type algorithm for solving nonsmooth constrained equations[J]. Applied Mathematics and Computation, 2014, 229: 107-122.

[9] Yu H D, Pu D G. Smoothing Levenberg-Marquardt method for general nonlinear complementarity problems under local error bound[J]. Applied Mathematical Modelling,2011,35(3):1 337-1 348.

[10] Zhang H C, Hager W W. A nonmonotone line search technique and its application to unconstrained optimization[J].SIAM Journal on Optimization, 2004, 14: 1 043-1 056.

[11] 劉元文, 歐宜貴, 馬巍. 一個(gè)基于定步長(zhǎng)技術(shù)的超記憶梯度法[J]. 應(yīng)用數(shù)學(xué), 2014, 28(1): 74-82.

[12] Narushina Y. A nonmonotone memory gradicut method for unconstrained optimization[J]. Journal of the Operations Research Society of Japan，2007，50:31-45.

[13] Solodov M V, Svaiter B F.A new projection method for variational inequality problems[J]. SIAM Journal on Control and Optimization, 1999, 37: 765-776.

Convergence Rate of A Derivative-free Projection Method for Nonlinear Equations

Li Jingya, Ou Yigui

(College of Information Science and Technology, Hainan University, Haikou 570228, China)

In the report, under the local error bound condition, the convergence rate of the derivative-free projection method for a class of nonlinear equations was analyzed, and the sequence {dist(xk,X*)} Q-linearly converges to 0 was proved. So, the whole sequence {xk} R-linearly converges to x*. Moreover, the four general methods are discussed, and their convergence rates are obtained.

nonlinear equations; derivative-free method; projection method; convergence rate

2016-05-31

國(guó)家自然科學(xué)基金(11261015)；海南省自然科學(xué)基金(111001， 20167246)

李靖雅(1993-)，女，甘肅隴南人，海南大學(xué)2015級(jí)碩士研究生，研究方向：最優(yōu)化方法，E-mail:373965516@qq.com

歐宜貴(1965-)，男，湖北鐘祥人，博士，教授，研究方向：最優(yōu)化方法，E-mail:ouyigui@126.com

1004-1729(2016)04-0324-06

O 221.2

A DOl：10.15886/j.cnki.hdxbzkb.2016.0049