解變分不等式的簡(jiǎn)單牛頓法的收斂性

周　彪，李素蘭

(浙江工業(yè)大學(xué) 理學(xué)院，浙江 杭州 310023)

解變分不等式的簡(jiǎn)單牛頓法的收斂性

周彪，李素蘭

(浙江工業(yè)大學(xué) 理學(xué)院，浙江 杭州 310023)

摘要：牛頓法作為求解變分不等式問(wèn)題的一個(gè)重要方法，它的收斂性一直是各位學(xué)者研究的一個(gè)核心問(wèn)題.當(dāng)變分不等式中的函數(shù)F在內(nèi)滿足γ-條件時(shí)，證明了由牛頓法產(chǎn)生的迭代點(diǎn)列是適定的，而且解的序列可以被構(gòu)造出來(lái)的{tn}序列控制收斂到一個(gè)變分不等式的最優(yōu)解.考慮到F在內(nèi)滿足γ-條件這個(gè)區(qū)域性條件給進(jìn)一步的研究帶來(lái)了困難，因此引入了解析函數(shù)，給出了F是解析函數(shù)條件下的牛頓法的收斂性結(jié)果.數(shù)值實(shí)驗(yàn)表明算法是有效的.

關(guān)鍵詞：牛頓法；變分不等式；γ-條件；半局部收斂；解析函數(shù)

變分不等式(Variational inequality)首先由Hartman和Stampacchia[1]在1966年提出，最初是用來(lái)研究偏微分方程的，它在數(shù)學(xué)、工程、物理和經(jīng)濟(jì)等領(lǐng)域有著廣泛的應(yīng)用背景.作為非線性互補(bǔ)問(wèn)題的推廣，它的提出統(tǒng)一了優(yōu)化問(wèn)題和均衡問(wèn)題的研究，并且在數(shù)學(xué)領(lǐng)域中作為大量數(shù)學(xué)問(wèn)題實(shí)際求解的統(tǒng)一框架.實(shí)際生活中的許多問(wèn)題都可以歸結(jié)為(或松弛成)一個(gè)凸優(yōu)化問(wèn)題，而凸優(yōu)化的一階必要性條件就是一個(gè)單調(diào)變分不等式.因此用變分不等式研究凸優(yōu)化的求解問(wèn)題，就像微積分中用導(dǎo)數(shù)求一元函數(shù)的極值，常常會(huì)帶來(lái)很大的方便，這使得它成為數(shù)學(xué)規(guī)劃中一個(gè)十分熱門的研究課題[2-6].

1理論基礎(chǔ)與符號(hào)說(shuō)明

1.1符號(hào)說(shuō)明

1)Rn表示n維歐式向量空間，令Ω→Rn，F(xiàn):Ω→Rn表示映射F的值域和定義域都是Rn的非空子集.

2)‖x‖：向量x的2-范數(shù).

3)‖A‖：矩陣A的2-范數(shù).

B(x0,ρ)∶={y∈Rn|y-x0

1.2理論基礎(chǔ)

下面給出變分不等式的一般形式：

給定一個(gè)Rn中的非空子集Ω和一個(gè)函數(shù)F:Ω→Rn,變分不等式問(wèn)題記為VIP(Ω,F),是指求x*∈Ω，使得

(y-x*)TF(x*)≥0?y∈Ω

(1)

文獻(xiàn)[13]中提到了很多數(shù)值解法，其中牛頓法是最重要的方法之一.牛頓法解函數(shù)F(x)=0時(shí)的一般迭代格式為

F′(xn-1)T(xn-xn-1)=-F(xn-1)

n=1,2,3,…,∞

(2)

而在求解變分不等式時(shí)，序列{xn}是由以下不等式的解產(chǎn)生的：假設(shè)已知迭代起點(diǎn)x0∈Ω，則x1的解為

(y-x1)T(F(x1)+F′(x0)(x1-x0))≥0

?y∈Ω

那么假設(shè)xn-1存在，則xn為

(y-xn)T(F(xn-1)+F′(xn-1)(xn-xn-1))≥0

?y∈Ω

(3)

的解.

定義1設(shè)Ω是Rn的一個(gè)非空的凸閉集，令ρ>0，γ>0，ργ<1.函數(shù)F:Ω→Rn在Ω上二階可微且存在一個(gè)x0∈Ω，F(xiàn)′(x0)-1存在，若不等式

(4)

定義2數(shù)學(xué)上如果一個(gè)函數(shù)在鄰域內(nèi)的每個(gè)點(diǎn)都能夠展開成冪級(jí)數(shù)，且收斂半徑大于零，則我們稱函數(shù)在鄰域內(nèi)是解析的.

2由牛頓法產(chǎn)生的序列{xn}的收斂性

2.1γ-條件

給定一個(gè)Rn中的非空子集Ω和一個(gè)函數(shù)F:Ω→Rn,變分不等式問(wèn)題記為VIP(Ω,F)是指求x*∈Ω，使得

(y-x*)TF(x*)≥0?y∈Ω

(5)

牛頓法作為求解變分不等式(5)最重要的方法之一，在求解xn時(shí)文獻(xiàn)[13]考慮的是F在xn-1處的一階導(dǎo)數(shù)信息，將算法簡(jiǎn)化為每次迭代都只考慮F在x0處的一階導(dǎo)數(shù)信息.故其迭代格式如下:

假設(shè)已知迭代起點(diǎn)x0∈Ω，則x1的解為

(y-x1)T(F(x1)+F′(x0)(x1-x0))≥0

?y∈Ω

(6)

那么假設(shè)xn-1存在，則xn為

(y-xn)T(F(xn-1)+F′(x0)(xn-xn-1))≥0

?y∈Ω

(7)

的解.即xn為VIP(Ω,Fn-1)的一個(gè)解.記Fn-1(xn)∶=F(xn-1)+F′(x0)(xn-xn-1).

王興華和韓丹夫教授[15]通過(guò)引入函數(shù)

(8)

改進(jìn)了Smale點(diǎn)估計(jì)的結(jié)論.其中β>0,R滿足

此時(shí)若將式(8)中的函數(shù)L定義為

則函數(shù)h(t)為

(9)

并且定義了一個(gè)序列{tn}為

t0=0,n=0,1,…

(10)

其中h(t)滿足式(9).

引理1假設(shè)A∈Rn×Rn是一個(gè)正定矩陣，x∈Rn，則有

證明回顧矩陣2-范數(shù)的定義

‖xn+1-xn‖

(11)

且{xn}收斂到變分不等式的一個(gè)解x*.

證明首先證明由牛頓法產(chǎn)生的序列{xn}是適定的：因?yàn)镕′(x0)是正定的，那么顯然Fn-1(x)是嚴(yán)格遞增的.而Ω是Rn的一個(gè)非空的凸閉集，所以VIP(Ω,Fn-1)有一個(gè)唯一解xn.即如果F′(x0)是正定的，則由式(7)牛頓法產(chǎn)生的序列是有意義的[12].

(xn+1-xn)TFn-1(xn)=(xn+1-xn)T·

(F(xn-1)+F′(x0)(xn-xn-1))≥0

(12)

(xn-xn+1)TFn(xn+1)=(xn-xn+1)T·

(F(xn)+F′(x0)(xn+1-xn))≥0

(13)

合并式(12，13)，并移項(xiàng)得

(xn-xn+1)TF′(x0)(xn-xn+1)≤

(xn-xn+1)T[F(xn)-F(xn-1)-

F′(x0)(xn-xn-1)]

(14)

(xn-xn+1)TF′(x0)(xn-xn+1)≥

(15)

結(jié)合式(14，15)，有

(xn-xn+1)≤

(xn-xn+1)T[F(xn)-

F(xn-1)-F′(x0)·

(xn-xn-1)]

移項(xiàng)化簡(jiǎn)得

‖xn+1-xn‖≤‖F(xiàn)′(x0)-1‖‖F(xiàn)(xn)-F(xn-1)-

F′(x0)(xn-xn-1)‖=

t(xn-xn-1))-F′(x0)‖·

‖xn-xn-1‖dt

(16)

‖xn-xn + 1‖‖xn - 1+ t(xn-xn - 1)-x0‖dλdt =

tn+1-tn

(y-x*)T(F(x*)+F′(x0)(xn-xn-1))=

(y-x*)T(F(x*))≥0成立，即{xn}收斂到變分不等式的一個(gè)解x*.得證.

2.2 在解析函數(shù)上的應(yīng)用

(17)

如果F′(x0)不可逆，則定義γ(F,x0)=∞.因此，若

F′(x0)可逆，則由解析性得γ(F,x0)有界.以下引理說(shuō)明當(dāng)函數(shù)F是解析的，則F一定滿足γ-條件.

證明因?yàn)楹瘮?shù)F是解析的,可以寫成冪級(jí)數(shù)的形式為

所以

又因?yàn)镕′(x0)可逆，結(jié)合(17)式得

(18)

(19)再次對(duì)(19)等式兩邊同時(shí)乘以γ(x-x0)，并相減，得

移項(xiàng)得

再結(jié)合(18)式得

接下來(lái)，我們得到了一個(gè)關(guān)于函數(shù)F是解析函數(shù)的牛頓法序列收斂性的推論.

‖xn+1-xn‖

(20)

且{xn}收斂到變分不等式的一個(gè)解x*.

3數(shù)值結(jié)果

任意x=(ξ1,ξ2)∈R2

表1牛頓迭代的次數(shù)與數(shù)值結(jié)果

Table1ThenumberofiterationsandNumericalresultsofNewton

迭代數(shù)/次序列{xn}0(0.95,0.96)1(0.9463,0.9421)2(0.9397,0.9377)3(0.9333,0.9308)4(0.9298,0.9285)5(0.9255,0.9266)6(0.9229,0.9232)7(0.9214,0.9221)8(0.9210,0.9219)9(0.9209,0.9213)10(0.9206,0.9206)11(0.9202,0.9205)12(0.9201,0.9203)13(0.9201,0.9202)14(0.9201,0.9202)

算法在第14步趨于最優(yōu)解x*=(0.92,0.92).說(shuō)明牛頓算法是有效的.

4結(jié)論

參考文獻(xiàn)：

[1]HARTMAN P, STAMPACCHIA G. On some nonlinear slliptic differential functional equations[J]. Acta mathematica,1966,115:153-188.

[2]FAROUQ N E. Pseudomonotone variational inequatlities: convergence of proximal methods[J]. Journal of optimization theory and applications,2001,109(2):311-326.

[3]SALMON G, NGUYEN V H,STRODIOT J J. Coupling the auxiliary problem principle and epiconvergence theory to solve general variational inequalities[J]. Journal of optimization theory and applications,2000,104(3):629-657.

[4]PENG J M, FUKUSHIMA M. A hybrid Newton method for solving the variational inequalities problems via the d-gap functiona[J]. Mathmatical programming,1999,86:367-386.

[5]WU J H. Long-step primal path-following algorithm for monotone variational inequalities problems[J]. Journal of optimization theory and applications,1998,99(2):509-531.

[6]FAROUQ N E. Pseudomonotone variational inequalities: convergence of the auxiliary problem method[J]. Journal of optimization theory and applications,2001,111(2):305-326.

[7]KANTOROVICH L V,AKILOV G P. Functional analtsis[M].Qxford:Pergamon,1982.

[8]KANTOROVICH L V. Functional analysis and applied mathematics[J]. Uspekhi matematicheskikh nauk, 1948(3)：89-185.

[9]SMALE S. Newton’s method estimates from data at one point[M]. New York: Spring,1986：185-196.

[10]SMALE S. Compexity theory and numerical analysis[J] Acta number，1997(6):523-551.

[11]WANG X H, HAN D F. Criterion α and Newton’s method[J]. Applied mathematics-a journal of chinese universities，1997,19:96-105.

[12]CHANG D C, WANG J H, YAO J C. Newton’s method for variational inequality problems: Smale’s point estimate theory under the -condition[J]. Applicable analysis,2013(1):44-55.

[13]FACCHINEI F, PANG J S. Finite-dimensioanl variation inequalities and complementarity problems[M]. New York: Springer-Verlag，2003.

[14]王興華，韓丹夫.弱條件下的α判據(jù)和Newton法[J].計(jì)算數(shù)學(xué)，1997(2):103-112.

[15]WANG X H. Convergence of Newton’s method and inverse function theorem in banach space[J]. Mathematics of computation,1999，68(1):169-186.

[16]WANG X H. Convergence of Newton's method and uniqueness of the solution of equations in Banach space[J]. IMA journal of numberical analysis，2000(20):123-134.

[17]鮑吉鋒.平衡問(wèn)題和優(yōu)化問(wèn)題若干算法的收斂性分析[D].杭州：浙江大學(xué)，2013.

(責(zé)任編輯：陳石平)

Convergence of Newton method for solving variational inequalities

ZHOU Biao, LI Sulan

(College of Science, Zhejiang University of Technology, Hangzhou 310023, China)

Abstract:Newton method is an important method for solving the problem of variational inequalities, the convergence of the algorithm has been a core issue for the scholars. When the function F in variational inequalities satisfies γ-conditions in , it is proved that the iterative dot sequence produced by the Newton method is valid and can be controlled to converge to an optimal solution of the variational inequalities by a sequence {tn}, which is constructed out. Taking into account that the regional conditions of the function F satisfies γ-conditions in makes more difficult for further study, analytic functions is introduced. The convergence of Newton method under the condition that the F is analytic function is given. Numerical experiments show that the algorithm is effective.

Keywords:Newton method; variational inequalities; γ-conditions; semilocal convergence; analytic functions

收稿日期：2015-12-17

基金項(xiàng)目：國(guó)家自然科學(xué)基金資助項(xiàng)目(11371325 )

作者簡(jiǎn)介：周彪(1991—)，男，浙江臺(tái)州人，碩士研究生，研究方向?yàn)樽顑?yōu)化算法與理論，E-mail：zhoubiaozjut@163.com.通信作者：李素蘭副教授，E-mail：sulanli@zjut.edu.cn.

中圖分類號(hào)：O224

文獻(xiàn)標(biāo)志碼：A

文章編號(hào)：1006-4303(2016)04-0461-05