解非單調(diào)變分不等式投影算法的擾動分析

唐南春，葉明露

(西華師范大學 數(shù)學與信息學院，四川 南充　637009)

常見的求解變分不等式的數(shù)值算法有投影算法、牛頓算法、鄰近點算法等，見參考文獻[1-3]及其引用文獻。其中投影算法因為易于實施的特點得到了廣泛的關(guān)注。為了求解不同的凸優(yōu)化問題，變分不等式的算法也不同，可參考文獻[1,4-9]。

文獻[10]介紹了一種二次投影算法來解偽單調(diào)非Lipschitz連續(xù)變分不等式問題。該算法的下一迭代點是通過向可行集與一個半空間的交的投影來實施。但在使用MATLAB計算投影時可能會因為精度問題而產(chǎn)生誤差(特別是投影不易計算時)。因此，文獻[11]給出該算法在擾動情形下的收斂性分析。

2015年Ye和He在文獻[12]中介紹了求解非單調(diào)的變分不等式投影算法。該算法的第k+1個迭代點由第k個迭代點向可行集與前k個半空間的交的投影來實施。因此，隨著k的增加，投影計算也越來越復雜。因此，有必要對該算法的新的迭代點的生成做一個擾動分析。

1　算法和預備知識

考慮的變分不等式問題VI(C,F)是指:尋找一個點x*∈C, 使得

〈F(x*),y-x*〉≥0,?y∈C。

(1)

其中C?Rn,C非空的閉凸集，F(xiàn)∶Rn→Rn是一個連續(xù)映射，‖·‖ 和〈·,·〉分別為Rn中通常的范數(shù)和內(nèi)積。

設(shè)VI(C,F)的解集為S，其對偶變分不等式的解集記為SD，即：

(2)

本文總假設(shè)SD≠?和F在Rn上連續(xù)，又因為C是凸集，則有

SD?S。

(3)

記x到C上的投影定義為PC(x)∶=argmin{‖y-x‖|y∈C}。記x到C上的距離為d(x,C)∶=inf{‖y-x‖|y∈C}。注意到C是Rn中的閉凸集，從而有d(x,C)∶=‖x-PC(x)‖。記自然殘差映射r(x)∶=x-PC(x-F(x))。

算法1選取初始點x0∈C，和參數(shù)σ∈(0,1),γ∈(0,1),k從0開始取。

第一步計算r(xk),如果r(xk)=0，那么停止，否則執(zhí)行第二步。

第二步找出滿足下列式子的最小非負整數(shù)m并令其為mk，

〈F(xk)-F(xk-γmr(xk)),r(xk)〉≤σ‖r(xk)‖2。

(4)

令ηk=γmk,zk=xk-ηkr(xk)。

(5)

令k=k+1，再回到第一步。

注2算法1的第二步是合理的，如果‖r(xk)‖=0，則xk是(1)的解，此時程序停止，若‖r(xk)‖≠0，若{xk}是算法生成的無窮的序列，我們總有‖r(xk)‖>0。

下面我們說明算法的線搜索(即第二步)是合理的，假設(shè)對任意的非負整數(shù)m都不滿足(4)式，即

〈F(xk)-F(xk-γmr(xk)),r(xk)〉>σ‖r(xk)‖2。

因為γ∈(0,1)，F(xiàn)連續(xù)，隨著m趨近于，F(xiàn)(xk)-F(xk-γmr(xk))收斂到0，那么〈F(xk)-F(xk-γmr(xk)),r(x)〉也趨于0。從而有0≥σ‖r(xk)‖2>0。得到矛盾，故總存在一個非負整數(shù)mk使得(4)式成立。

引理1[4]若C是Rn中的非空閉凸集且x∈Rn，則有以下結(jié)論成立

(i)z=PC(x)?〈z-x,y-z〉≥0,?y∈C;

(ii)〈PC(x)-PC(y),x-y〉≥0,?x,y∈Rn;

(iii)‖PC(x)-PC(y)‖‖x-y‖,?x,y∈Rn;

(iv)‖PC(x)-z‖2‖x-z‖2-‖PC(x)-x‖2,?x∈Rn,?z∈C。

引理2[4]若x*∈S，當且僅當‖r(x*)‖=0。

引理3[8]對?x∈C,有

〈F(x),r(x)〉≥‖r(x)‖2。

(6)

引理4[8]設(shè)C是Rn中的閉凸集，h是Rn上的實值函數(shù)，K∶={x∈C∶h(x)≤0}。如果K≠?,h在C上Lipschitz連續(xù)，其Lipschitz系數(shù)為L(即：?x,y∈C,‖h(x)-h(y)‖≤L‖x-y‖)，則有

d(x,K)≥L-1max{h(x),0},?x∈C。

為了閱讀的方便，我們列其證明如下：

證明(i)當x∈K時，d(x,K)=0,h(x)≤0，故d(x,K)≥L-1max{h(x),0}成立。

(ii)當x∈CK時，因為K是閉集(h在C上連續(xù)，C為閉集),所以存在y(x)∈K,滿足‖x-y(x)‖=d(x,K),由h的Lipschitz連續(xù)性有

‖h(x)-h(y(x))‖≤L‖x-y(x)‖=Ld(x,K)。

因為x?K,y(x)∈K,則h(x)>0,h(y(x))≤0。所以

h(x)≤h(x)-h(y(x))=|h(x)-h(y(x))|≤Ld(x,K)

。

結(jié)論得證。

ai+1≤ai+δi,?i≥i0。

(7)

那么{ai}收斂。

引理6{xk}是由算法1產(chǎn)生的序列，則有以下的結(jié)論：

(8)

‖xk+1-εk-x*‖≤‖xk-x*‖。

從而由范數(shù)的性質(zhì)有：

‖xk+1-x*‖-‖εk‖≤‖xk-x*‖。

所以

‖xk+1-x*‖≤‖xk-x*‖+‖εk‖。

所以有

(9)

(9)式可等價地寫為

(10)

引理7設(shè)函數(shù)hk通過(5)式定義，{xk}是由算法1產(chǎn)生的無窮序列，如果SD≠?，

(i)對任意的k，有

hk(xk)≥(1-σ)ηk‖r(xk)‖2>0。

(11)

(ii)如果x*∈SD,對任意的k，有

hk(x*)≤0。

證明(i)zk=xk-ηkr(xk)，由算法1里的(5)式hk的定義，有

hk(xk)=〈F(zk),xk-zk〉=〈F(xk-ηkr(xk)),ηkr(xk)〉

=ηk〈F(xk-ηkr(xk)),r(xk)〉

=ηk〈F(xk-ηkr(xk))-F(xk)+F(xk),r(xk)〉

=ηk[〈F(xk-ηkr(xk))-F(xk),r(xk)〉+〈F(xk),r(xk)〉]

≥ηk[-σ‖r(xk)‖2+〈F(xk),r(xk)〉]

≥ηk(1-σ)‖r(xk)‖2>0。

其中第一個不等式由線搜索(4)式可得，第二個不等式由引理3的(6)式可得。

(ii)由(5)式hk的定義有：

hk(x*)=〈F(zk),x*-zk〉。

又因為xk∈C且C是凸集，所以有zk∈C。從而由(2)式及x*∈SD,可得：

〈F(zk),x*-zk〉≤0。

那么對任意的k，都有hk(x*)≤0。

2　算法的收斂性

定理2.1如果F在C上連續(xù)且SD≠?且{xk}為算法1生成的序列，則要么算法1在有限步終止(此時停止點為變分不等式的解)；要么{xk}收斂到 問題(1)的解。

證明因為{xk}有界，且F(x)和r(x)在Rn上連續(xù)，所以{zk}有界，再由F的連續(xù)性，可得{F(zk)}是有界序列，設(shè)此界為M>0,即：

‖F(xiàn)(zk)‖≤M,?k。

則對任意k,M均為函數(shù)hk(v)在Rn上的Lipschitz常數(shù)，由引理4知

d(x,C∩Hk)≥M-1max{hk(x),0},?k,?x∈C。

再結(jié)合(11)式，有

d(xk,C∩Hk)≥M-1hk(xk)≥M-1(1-σ)ηk‖r(xk)‖2。

(12)

又由引理6里的(ii)有：

(13)

(14)

由(13)和(14)式，顯然有

(15)

再聯(lián)立(13)和(15)，從而有

(16)

〈F(xkj)-F(xkj-γ-1ηkjr(xkj)),r(xkj)〉>σ‖r(xkj)‖2。

(17)

又因為F(x)和r(x)都是連續(xù)的，并且序列{xk}有界，當j→時，(17)式左邊極限趨于0，有

(18)

參考文獻：

[1]SOLODOV M V,SVAITER B F.A new projection method for variational inequality problems[J].SIAM Joural on Contral and Optimization,1999,37(3):765-776.

[2]MARCOTTE P,DUSSAULT J P.A modified newton method for solving variational inequalities[C]//Decision and Control,IEEE Conference on.IEEE Xplore,1985:1433-1436.

[3]BURACHIK R S,IUSEM A N.A generalized proximal point algorithm for the variational inequality problem in a Hilbert space[J].SIAM Journal on Optimization,2006,8(1):197-216.

[4]XIU N,ZHANG J.Some recent advances in projection-type methods for variational inequalities[J].J Computational and Applied Mathematics,2003,152(1):559-585.

[5]何詣然.一個關(guān)于混合變分不等式問題的投影算法[J].數(shù)學物理學報,2007,27(2):215-220.

[6]BAUSCHKE H H,COMBETTES P L.Convex analysis and monotone operator theory in Hilbert space[M].New York:Springer New York,2011.

[7]LI F,HE Y.An algorithm for generalized variational inequality with pseudomonotone mapping[J].Journal of Computational and Applied Mathematics,2009,228(1):212-218.

[8]ALBER Y I,IUSEM A N,SOLODOV M V.On the projected subgradient method for nonsmooth convex optimization in a Hilbert space[J].Mathematical Programming,1998,81(1):23-35.

[9]XIA F Q,HUANG N J,LIU Z B.A projected subgradient method for solving generalized mixed variational inequalities[J].Operations Research Letters,2008,36(5):637-642.

[10]HE Y.A new double projection algorithm for variational inequalities[J].Journal of Computational and Applied Mathematics,2006,185(1):166-173.

[11]邱濤,何詣然.二次投影算法的擾動分析[J].四川師范大學學報(自然科學版),2012,35(1):8-11.

[12]YE M,HE Y.A double projection method for solving variational inequalities without monotonicity[J].Computational Optimization and Applications,2015,60(1):141-150.