Banach空間中廣義方程的限制型牛頓算法*

趙天晶， 歐陽薇

(云南師范大學(xué)數(shù)學(xué)學(xué)院,650500,云南省昆明市)

0 引 言

考慮如下 Robinson[12]意義下的廣義方程

0∈f(x)+F(x),

(1)

其中f:X→Y是一個(gè)連續(xù)函數(shù),F:X?Y是有閉圖的集值映射,X和Y是Banach空間.眾所周知,許多優(yōu)化相關(guān)問題,如非線性規(guī)劃、均衡問題等,均可轉(zhuǎn)化為廣義方程(1)并受到許多學(xué)者廣泛關(guān)注[4-6].特別地,當(dāng)(1)中集值映射為某個(gè)凸集的次微分映射時(shí),該廣義方程就轉(zhuǎn)化為通常的變分不等式問題.

為了逼近廣義方程(1)的解,在度量正則性假設(shè)下,多種牛頓型算法及其改進(jìn)形式被廣泛研究[2,3,7-9].當(dāng)廣義方程(1)中f光滑時(shí),Josephy[10]引入牛頓型算法的策略是線性化單值映射f,而集值映射F保持不變.對(duì)于任意給定的初始點(diǎn)x0,通過求解下面局部線性化方程構(gòu)造序列{xk}:

0∈f(xk)+Df(xk)(xk+1-xk)+F(xk+1),k=0,1,…,

(2)

其中Df表示f的Fréchet導(dǎo)算子.在f+F具有度量正則性的假設(shè)下,當(dāng)Df連續(xù)時(shí),牛頓型算法(2)具有線性收斂性;當(dāng)f是Lipschitz連續(xù)時(shí),牛頓型算法(2)具有二次收斂性,關(guān)于牛頓型算法(2)更詳細(xì)的收斂性結(jié)論,參見文獻(xiàn)[5].

當(dāng)廣義方程(1)中f非光滑時(shí),我們考慮如下迭代過程構(gòu)造序列{xk}:

0∈Ak(xk,xk+1)+F(xk+1),

(3)

其中函數(shù)序列Ak:X×X→Y及起始點(diǎn)x0∈X. 當(dāng)f光滑時(shí),令A(yù)k(x,u)=f(u)+Df(u)(x-u),則迭代過程(3)退化為(2).如果令A(yù)k(x,u)=γk(u-x)+f(u)(k=0,1,…),其中{γk}是正數(shù)列,此時(shí)迭代過程(3)退化為鄰近點(diǎn)算法,其基本形式為

0∈γk(xk+1-xk)+f(xk+1)+F(xk+1),k=0,1,2,….

關(guān)于改進(jìn)型牛頓算法的更多詳細(xì)信息,參見文獻(xiàn)[1,4,5,7,9]. 一般地,在正則性假設(shè)下,僅能保證牛頓型算法(3)或(2)至少產(chǎn)生一個(gè)收斂序列,并不能得出牛頓型算法(3)或(2)所產(chǎn)生的任意序列均收斂. 為此,Rashid和Yuan[11]在正則性假設(shè)下研究了限制型牛頓算法. 受此啟發(fā),針對(duì)廣義方程(1)及其對(duì)應(yīng)的牛頓型算法(3),本文給出一種限制型牛頓算法,并在度量正則性假設(shè)下,給出了幾種收斂性條件. 作為應(yīng)用,我們還考慮了一種特殊形式——限制型鄰近點(diǎn)算法,并給出了對(duì)應(yīng)收斂性條件.

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

在本節(jié),主要介紹本文所需要的相關(guān)符號(hào)、定義和已知結(jié)論,用來作為后續(xù)論證的統(tǒng)一記法和必要準(zhǔn)備.我們總是假設(shè)所考慮的空間為Banach空間,用BX代表空間X的閉單位球及用Br(x)表示以x∈X為中心,r>0為半徑的閉球.給定子集C,D?X,定義

并且有

定義集值映射F:X?Y的圖為:gph(F):={(x,y)∈X→Y:y∈F(x)}.如果gph(F)在空間X×Y是閉的,那么稱F在此空間有閉圖;記F-1:Y?X為F的逆映射,即F-1(y):={x∈X:y∈F(x)}(對(duì)任意的y∈Y).

定義1.2稱映射序列Ak:X×X→Y是f關(guān)于非負(fù)常數(shù)列{μk}及{εk}的點(diǎn)基近似,如果對(duì)于任意的x,y,u,v∈X都有

(4)

及

(5)

為證明本文的主要結(jié)論,我們還需要如下集值形式的不動(dòng)點(diǎn)定理.

2 主要結(jié)論

考慮廣義方程(1),本節(jié)主要討論限制型牛頓算法在點(diǎn)基近似和度量正則性的假設(shè)下的收斂性分析. 設(shè)η>1,引入如下限制型牛頓算法:

(6)

在開始收斂性分析的主要定理的闡述之前,需要給出以下引理來作為后面論證的支撐工具.給定k∈及u∈X,定義如下輔助函數(shù)gk(·,u)=f(·)-Ak(u,·)及Rk,u(·):=Ak(u,·)+F(·),其中函數(shù)序列Ak:X×X→Y.

(7)

(8)

(9)

(10)

從而對(duì)任意的y∈Bb(0),都有(f+F)-1(y)≠?.令Φk:X?X(k∈)使得

Φk(x)=(f+F)-1(gk(x,u))，?x∈X.

由(4)式可得

(11)

和

(12)

由ε的任意性可得(7)成立.證畢.

至此,我們已經(jīng)做好了主要結(jié)論的準(zhǔn)備工作,那么下面給出廣義方程(1)在度量正則性假設(shè)下的收斂性結(jié)論.

(13)

注2.1上述定理不僅給出了線性收斂性條件,而且給出了限制型牛頓算法(6)產(chǎn)生的序列所在范圍的半徑與度量正則性的常數(shù)之間的確切關(guān)系.特別地,當(dāng)f光滑時(shí),定理2.2依然改進(jìn)了主要結(jié)論.

若取Ak(u,x)=γk(x-u)+f(x)(k=0,1,2，…),其中{γk}是一正數(shù)序列,則限制型牛頓算法(6)退化為如下限制型臨近點(diǎn)算法

(14)

由定理2.2可得如下推論.

證明令A(yù)k(u,x)=γk(x-u)+f(x)(k=0,1,2，…),容易看出Ak是f的點(diǎn)基近似,即(4)和(5)式對(duì)于μk=γk,εk=0 成立. 從而由定理2.2可得結(jié)論成立. 證畢.

下面,在度量正則性假設(shè)下,我們給出另一種收斂性條件.

(15)

(16)

(17)

(18)

(19)

(20)

(21)

(22)