偽單調(diào)均衡問題的一種加速投影算法

,

( 上海理工大學(xué) 管理學(xué)院,上海 200093)

1 問題的提出

均衡問題EP(f,C)[1]是:尋找點(diǎn)x*∈C,使對(duì)?y∈C,下面不等式成立:

f(x*,y)≥0

(1)

式中:C∈Rn是非空閉凸集,f:C×C→R為一個(gè)雙重函數(shù),即對(duì)?x∈C,f(x,x)=0恒成立.

當(dāng)f(x,y)=〈F(x),y-x〉,其中,F:C→Rn為一個(gè)連續(xù)函數(shù),那么,EP(f,C)就轉(zhuǎn)化成變分不等式問題VI(F,C),即尋找點(diǎn)x*∈C,使對(duì)?y∈C,下面不等式成立:

〈F(x*),y-x〉≥0

(2)

顯然,f連續(xù),F也連續(xù).如果f關(guān)于x*∈C是偽單調(diào)的,則F關(guān)于x*∈C也是偽單調(diào)的.

EP(f,C)在電力市場、交通運(yùn)輸、經(jīng)濟(jì)及網(wǎng)絡(luò)等問題中都有廣泛的應(yīng)用[2-5].求解EP(f,C)的方法主要有三類:a.近似點(diǎn)法,該方法由Martinet[6]提出并首次應(yīng)用在求解VI(F,C),后來Moudafi[7]在假設(shè)映射f單調(diào)的前提下將該算法推廣到求解EP(f,C);b.gap函數(shù)法[8],利用連續(xù)可微的gap函數(shù)將EP(f,C)轉(zhuǎn)化為最優(yōu)化問題,但是,算法的收斂性建立在f強(qiáng)單調(diào)的基礎(chǔ)上;c.輔助問題原理法,Cohen[9]提出x*∈C是EP(f,C)的一個(gè)解,當(dāng)且僅當(dāng)x*∈C是強(qiáng)凸問題

的唯一解,其中,ck>0,但這需要f強(qiáng)單調(diào)且Lipschitz連續(xù).隨后,Antipin[10]在文獻(xiàn)[9]的基礎(chǔ)上,在每次迭代過程中增加一個(gè)外推步,提出了一種改進(jìn)算法,具體過程如下:

式中:D是Bregman距離函數(shù);C是一個(gè)多面凸集.

該算法減弱了f的單調(diào)性,其收斂性建立在f偽單調(diào)且Lipschitz連續(xù)的基礎(chǔ)上.

本文借助于輔助問題原理法,結(jié)合Solodov等[11]提出的求解變分不等式的改進(jìn)投影算法,運(yùn)用Armijo型線搜索,通過改進(jìn)投影區(qū)域,使每次迭代結(jié)果更接近均衡問題的解.在f偽單調(diào)并連續(xù)(非Lipschitz連續(xù))的前提下,證明了算法的收斂性.

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

定義1設(shè)C?Rn,f:C×C→R∪{+}是雙重函數(shù),

a.若對(duì)?x,y∈C,?ρ>0,使得f(x,y)+f(y,x)≤-ρ‖x-y‖2,則稱f在C上是強(qiáng)單調(diào)的.

b.若對(duì)?x,y∈C,f(x,y)+f(y,x)≤0,則稱f在C上是單調(diào)的.

c.若對(duì)?x,y∈C,f(x,y)≥0?f(y,x)≤0,則稱f在C上是偽單調(diào)的.

顯然,(1)?(2)?(3).

定義2若存在正常數(shù)c1,c2,使得f(x,y)+f(y,z)≥f(x,z)-c1‖x-y‖2-c2‖y-z‖2,則稱f在C上Lipschitz連續(xù).

定義3設(shè)X?Rn,實(shí)值函數(shù)f:X→R,

a.若對(duì)?x,y∈X,?λ∈[0,1],有f(λx+(1-λ)y)≤max{f(x),f(y)},則稱f(x)為X上的擬凸函數(shù).

b.若對(duì)?x,y∈X,〈f(y),x-y〉≥0蘊(yùn)涵f(x)≥f(y),或者f(x)

定義4對(duì)?z∈C,?2f(z,z)表示凸函數(shù)f(z,·)在z處的次梯度,其中,?2f(z,z)滿足:

引理1[12]設(shè)PC(·)是C上的投影映射,則

a.‖PC(x)-PC(y)‖≤‖x-y‖,?x,y∈Rn;

b.‖PC(x)-PC(y)‖2≤〈PC(x)-PC(y),x-y〉,?x,y∈Rn;

c.〈x-PC(x),y-PC(y)〉≤0,?y∈C,x∈Rn;

d.‖PC(x)-y‖2≤‖x-y‖2-‖PC(x)-x‖2,?y∈C,x∈Rn;

e.‖PC(x)-PC(y)‖2≤‖x-y‖2-‖PC(x)-x+y-PC(y)‖2,?x,y∈Rn.

引理2[13]設(shè)f(x,y)關(guān)于y是Gateaux可微的,如果x*是EP(f,C)的解,即f(x*,y)≥0,?y∈C,則x*也是變分不等式〈G(x*),y-x*〉≥0,?y∈C的解,其中,G(x)=?f2(x,x).進(jìn)一步,如果對(duì)每個(gè)x∈C,f(x,y)關(guān)于y是偽凸的,則逆命題也成立.

3 加速投影算法

基于上述的理論基礎(chǔ),現(xiàn)提出求解偽單調(diào)均衡問題的一種加速投影算法.該算法的基本思想是運(yùn)用Armijo型線搜索得到一個(gè)預(yù)估點(diǎn)并以此構(gòu)造一個(gè)超平面,進(jìn)一步通過適當(dāng)選擇步長和減小投影域使得算法產(chǎn)生的序列快速收斂.現(xiàn)介紹具體算法.

算法1

步驟1計(jì)算

令zk=xk-γmkrk,其中,mk是使得

〈?2f(zk,zk),rk〉≥σ‖rk‖2

的最小非負(fù)數(shù).

步驟3令k=k+1,返回步驟1.

4 收斂性分析

用SOL(f,C)表示均衡問題EP(f,C)的解集,由文獻(xiàn)[14],若f是連續(xù)的,則SOL(f,C)是閉合集合;若f是偽單調(diào)的,則SOL(f,C)是凸集.為了證明算法1的收斂性,首先作出如下假設(shè):

A1f在C上偽單調(diào);

A2f(x,y)是C×C上的連續(xù)可微凸函數(shù)且關(guān)于y是偽凸的,?2f(x,x)在C上是上半連續(xù)的;

根據(jù)上述假設(shè)可知,SOL(f,C)是一個(gè)閉凸集.

0∈?2f(x,x)+NC(xk)

其中,NC(xk)是xk處的外法向錐.因此,有

〈ωk,x-xk〉≥0,?x∈C

(3)

其中,ωk∈?2f(x,x).由于f(xk,yk)是凸函數(shù),則

(4)

結(jié)合式(3)和式(4),又因?yàn)?f(xk,xk)=0,所以,f(xk,x)≥0對(duì)?x∈C都成立,即xk是EP(f,C)的解.

定理2若rk≠0,則對(duì)?k≥0,存在非負(fù)數(shù)mk使得〈?2f(zk,zk),rk〉≥σ‖rk‖2成立.

證明假設(shè)〈?2f(zk,zk),rk〉-σ‖rk‖2<0,即有〈F(xk-γmkrk),xk-yk〉-σ‖rk‖2<0,因?yàn)?γ∈(0,1),當(dāng)m→,取極限,根據(jù)f(x,y)的連續(xù)性,可以得到〈F(xk),xk-yk〉-σ‖rk‖2≤0.

由引理2,即

f(xk,yk)+σ‖rk‖2≥0

(5)

當(dāng)y=xk時(shí),

(6)

(7)

證明將xk+1代入式(7)的左邊,可得

由引理1和引理3可得

其中,第1個(gè)不等式由引理1得到,第2個(gè)不等式由偽單調(diào)條件得到.根據(jù)引理3,可得

‖xk+1-x*‖2≤‖xk-x*‖2-

另一方面,由zk=xk-γmkrk,即xk-zk=γmk(xk-yk),顯然,由輔助問題原理,當(dāng)k→時(shí),所以,

當(dāng)j→時(shí),則有

因?yàn)?對(duì)?x∈C,f(x,x)=0恒成立,所以,

5 結(jié) 論

通過改進(jìn)投影區(qū)域,給出了求解偽單調(diào)均衡問題的一種加速投影算法,由以上述證明可知,此算法不要求雙重函數(shù)f是Lipschitz連續(xù)的,且在偽單調(diào)條件下是全局收斂的.

[1] GIANNESSI F,MAUGERI A,PARDALOS P M.Equilibrium problems:nonsmooth optimization and variational inequality models[M].Boston,MA:Springer,2001.

[2] OLIVEIRA H A E JR.Coalition formation feasibility and Nash-Cournot equilibrium problems in electricity markets:a Fuzzy ASA approach[J].Applied Soft Computing,2015,35:1-12.

[3] HO W,WONG S C,YING L B.Sequential optimization aproach for the mulit-class user equilibrium problem in continus transportation system[J].Journal of Advanced Transportation,2010,38(3):323-345.

[4] BOGDAN M.Applications of parametric abstract equilibrium problems in economics[J].Procedia Economics and Finance,2012,3:99-104.

[5] DE CEA J,FERNNDEZ J E,V DEKOCK,et al.Solving network equilibrium problems on multimodal urban transportation networks with multiple user classes[J].Transport Reviews,2005,25(3):293-317.

[6] MARTINET B.Regularization d″inéquations variationnelles par approximations successives[J].Rev Fr Inform Rech Opér,1970,4(3):154-159.

[7] MOUDAFI A.Proximal point algorithm extended to equilibrium problems[J].Journal of Natural Geometry,1997,15(1/2):91-100.

[8] MASTROENI G.Gap functions for equilibrium problems[J].Journal of Global Optimization,2003,27(4):411-426.

[9] COHEN G.Auxiliary problem principle extended to variational inequalities[J].Journal of Optimization Theory and Applications,1988,59(2):325-333.

[10] ANTIPIN A S.The convergence of proximal methods to fixed points of extremal mappings and estimates of their rate of convergence[J].Computational Mathematics and Mathematical Physics,1995,35(5):539-551.

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

[12] ANH P N,LE THI H A.An Armijo-type method for pseudomonotone equilibrium problems and its applications[J].Journal of Global Optimization,2013,57(3):803-820.

[13] 徐慶,朱道立,魯其輝.Nash均衡、變分不等式和廣義均衡問題的關(guān)系[J].管理科學(xué)學(xué)報(bào),2005,8(3):1-7.

[14] KONNOV I.Combined relaxation methods for variational inequalities[J].Berlin Heidelberg:Springer,2001:77-92.

[15] WANG Y J,XIU N H,WANG C Y.Unified framework of extragradient-type methods for pseudomonotone variational inequalities[J].Journal of Optimization Theory and Applications,2001,111(3):641-656.