均衡問題的一種改進(jìn)不精確次梯度算法

黨亞崢, 沈 忱, 劉雯雯

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

均衡問題的一種改進(jìn)不精確次梯度算法

黨亞崢, 沈 忱, 劉雯雯

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

針對采用精確次梯度算法求解均衡問題中的穩(wěn)固非擴張算子的不動點集問題(EP(f,Fix(T)))時計算復(fù)雜且收斂性較差這一情況,提出了一種改進(jìn)的不精確次梯度算法.首先,由事先選擇的參數(shù)確定一個凸集;其次,通過不精確次梯度投影算法構(gòu)造中間迭代點;最后,將當(dāng)前迭代點和中間迭代點的線性組合在穩(wěn)固非擴張算子的映射作為下一次迭代點.在合適條件下驗證了算法的全局收斂性.

均衡問題; 次梯度; 穩(wěn)固非擴張映射; 全局收斂

1 問題描述

穩(wěn)固非擴張算子的不動點集上的均衡問題[1](EP(f,Fix(T)))即找一個點

(1)

EP(f,Fix(T))問題是非空閉凸約束集中有關(guān)均衡問題的特殊類型,主要包括:最優(yōu)化問題、納什均衡問題、互補問題、不動點問題、變分問題及向量極小化問題等,其在碼分多址聯(lián)系方式(CDMA)[2]的系統(tǒng)能量控制問題和庫洛特-納什寡頭市場均衡模型[3]中也有應(yīng)用.文獻(xiàn)[4-9]中提出了許多解決這類問題的迭代算法.近年來出現(xiàn)了很多求解問題(1)的改進(jìn)次梯度投影算法[10-15].本文提出了求解穩(wěn)固非擴張映射不動點集中均衡問題的一種新的有效的全局收斂算法.通過選擇合適的正則參數(shù),保證算法產(chǎn)生的序列全局收斂到EP(f,Fix(T))問題中的一個解.相對而言,本文提出的算法只需在每次迭代中作一次不精確的投影,比較容易實施.

2 預(yù)備知識

定義1 如果算子T滿足

(2)

則稱算子T非擴張.

PC表示從Rn到Rn上非空閉凸子集C的投影,則有

(3)

易知PC(x) 有如下性質(zhì):

〈x-PCx,z-PCx〉≤0, ?z∈C,x∈Rn

(4)

故PC非擴張.

定義2 雙函數(shù)f:C×C→R∪{+∞}.

a. 如果對每個x,y∈C,有

f(x,y)+f(y,x)≤0,則稱f在子集C上是單調(diào)的.

b. 對于每個x,y∈C,有

f(x,y)≥0 ?f(y,x)≤0,則稱f在子集C上是偽單調(diào)的.

定義3 雙函數(shù)f在點x∈C處的ε次微分?εf(x,·)(x)定義為

設(shè)E為巴拿赫空間,S是定義在E中的一個非空凸子集,E滿足Opial性質(zhì)[16],如果存在任意的序列{xk}都屬于E,xk→x*,則

(5)

現(xiàn)使用引理1和引理2對算法進(jìn)行收斂性分析.

引理2 非負(fù)實數(shù)θ,β滿足不等式θ2-βθ≤0,則

(6)

證明 考慮二次函數(shù)s(θ)=θ2-βθ,當(dāng)s(θ)≤0時,有

用β乘上面的不等式,即可得

證畢.

在收斂性分析中,假定式(1)的解集包含其對偶問題的解集,即

當(dāng)x*∈Fix(T)時,有

(7)

這個問題的解集可以表示為Sd(f,Fix(T)).

函數(shù)f表示C上的偽單調(diào)雙函數(shù)(如果x,y∈C和f(x,y)≥0,則可知f(y,x)≤0),有S(f,C)?Sd(f,C).這個結(jié)論對單調(diào)雙函數(shù)也有效,即f(x,y)+f(y,x)≤0.

3 不精確次梯度算法及其全局收斂性

3.1 不精確次梯度算法

(8)

(9)

步驟2 計算

(10)

令k:=k+1,轉(zhuǎn)步驟1.

(11)

3.2 收斂性分析

引理3 對任意k,下列不等式成立:

證明 由式tk=Pck(xk-αkgk)和式(4)得

(12)

由步驟1得

(13)

將x=xk代入式(12),由Cauchy-Schwarz不等式和式(13)可得

假設(shè) A1S(f,C)的解集是非空的.

命題1 假設(shè)Sol(f,Fix(T))是非空的,則對任意的k,x*∈Sol(f,Fix(T)),下列不等式成立:

(15)

證明 顯然

當(dāng)x=x*時,由式(11)和式(13)可知

由Cauchy-Schwarz不等式及引理3的a可得

利用式(18)和引理3的b可得

2αk〈gk,x*-xk〉≤2αkf(xk,x*)+2αkεk

(20)

顯然,由式(19)和式(20)可得式(15).

現(xiàn)證明在假設(shè)A1成立的情況下,由改進(jìn)不精確次梯度算法生成的序列{xk}是有界的.

證明 對任意的x*∈Sol(f,Fix(T)),已知

由式xk+1=T(λkxk+(1-λk)tk),算子的非膨脹性和式(15)易知

由假設(shè)A1得f(xk,x*)≤0,由命題1可知

由命題1和假設(shè)A1可知

則

當(dāng)m→+∞時,有

由參數(shù)的已知條件可知

(25)

利用參數(shù)定義可得

因此

(26)

所以,由式(25)和式(26)可知

(27)

假設(shè)A3 當(dāng)存在y∈C時,f(·,y)是上半連續(xù)的.

定理2 設(shè)C是在Rn上的非空閉凸子集,T:C→Rn表示一個穩(wěn)固非擴張性映射,序列{gk}有界,若假設(shè)A1,A2,A3成立,令Fix(T)有界且其上界M>0,均衡函數(shù)f:Rn×Rn→Rn對于所有的x∈Rn滿足f(x,x)=0,序列{gk}有界,則可知由算法1產(chǎn)生的序列{xk}收斂到EP(f,Fix(T))的一個解.

證明 設(shè) x*∈S(f,C),由定理1易知,存在序列{xk}的子序列{xkj},滿足

(28)

(29)

從假設(shè)A2和定理1可知

(30)

(31)

4 結(jié) 論

提出了一種求解均衡問題中關(guān)于穩(wěn)固非擴張映射T上的不動點集問題的不精確次梯度迭代算法.通過選擇適當(dāng)?shù)恼齽t參數(shù),驗證不精確次梯度算法的全局收斂性.相對于精確次梯度算法,減少了計算工作量,同時提高了算法的收斂性.

[1] BLUM E,OETTLI W.From optimization and variational inequalities to equilibrium problems[J].Mathematics Student,1994,63(1):123-145.

[2] IIDUKA H,YAMADA I.An ergodic algorithm for the power-control games for CDMA data networks[J].Journal of Mathematical Modelling and Algorithms,2009,8(1):1-18.

[3] IIDUKA H.Fixed point optimization algorithm and its application to power control in CDMA data networks[J].Mathematical Programming,2012,133(1/2):227-242.

[4] ANH P N.A hybrid extragradient method extended to fixed point problems and equilibrium problems[J].Optimization:A Journal of Mathematical Programming and Operations Research,2013,62(2):271-283.

[5] ANH P N,KIM J K.Outer approximation algorithms for pseudomonotone equilibrium problems[J].Computers & Mathematics with Applications,2011,61(9):2588-2595.

[6] BIGI G,CASTELLANI M,PAPPALARDO M.A new solution method for equilibrium problems[J].Optimization Methods and Software,2009,24(6):895-911.

[7] NOOR M A.Auxiliary principle technique for equilibrium problems[J].Journal of Optimization Theory and Applications,2004,122(2):371-386.

[8] QUOC T D,ANH P N,MUU L D.Dual extragradient algorithms extended to equilibrium problems[J].Journal of Global Optimization,2012,52(1):139-159.

[9] 宇振盛,張麗娜,秦毅.非線性優(yōu)化問題的光滑化序列二次規(guī)劃方法[J].上海理工大學(xué)學(xué)報,2015,37(4):317-321.

[10] 陳元媛,高巖.一種非線性擴展混合共軛梯度算法的全局收斂性[J].上海理工大學(xué)學(xué)報,2013,35(2):113-115.

[11] NGUYEN T T V,STRODIOT J J,NGUYEN V H.A bundle method for solving equilibrium problems[J].Mathematical Programming,2009,116(1/2):529-552.

[12] TRAN D Q,DUNG L M,NGUYEN V H.Extragradient algorithms extended to equilibrium problems[J].Optimization,2008,57(6):749-776.[13] VAN NGUYEN T T,STRODIOT J J,NGUYEN V H.The interior proximal extragradient method for solving equilibrium problems[J].Journal of Global Optimization,2009,44(2):175-192.[14] IIDUKA H,YAMADA I.A subgradient-type method for the equilibrium problem over the fixed point set and its applications[J].Optimization,2009,58(2):251-261.

[15] SANTOS P,SCHEIMBERG S.An inexact subgradient algorithm for equilibrium problems[J].Computational & Applied Mathematics,2011,30(1):91-107.

[16] OPIAL Z.Weak convergence of the sequence of successive approximations for nonexpansive mappings[J].Bulletin of the American Mathematical Society,1967,73(4):591-597.

[17] CROMBEZ G.A geometrical look at iterative methods for operators with fixed points[J].Numerical Functional Analysis and Optimization,2005,26(2):157-175.

(編輯:石 瑛)

Improved Subgradient Algorithm for Equalization Problems

DANG Yazheng, SHEN Chen, LIU Wengweng

(BusinessSchool,UniversityofShanghaiforScienceandTechnology,Shanghai200093,China)

The exact subgradient algorithm for solving the equilibrium problem (EP(f,Fix(T))) of sets over the fixed point of non-expansive operator causes computational complexity and poor convergence.To overcome the defect,an inexact subgradient algorithm for theEP(f,Fix(T)) was presented.A convex set assured by given parameter was selected,the intermediate iterative point was constructed by using the non-accurate subgradient projection algorithm and the image,under firmly non-expansive operator of the linear combination of the current iterative point and middle iterative point was taken as the next iteration point.Under suitable conditions,the global convergence of the algorithm was verified.

equilibriumproblem;sub-gradient;firmlynon-expansivemapping;globalconvergence

1007-6735(2016)06-0523-04

10.13255/j.cnki.jusst.2016.06.003

2016-04-01

上海市自然科學(xué)基金資助項目(14ZR1429200);上海市教育委員會科研創(chuàng)新項目(15ZZ073)

黨亞崢(1973-),女,副教授. 研究方向:可行問題、均衡問題、智能電網(wǎng)電力市場.E-mail:jgdyz@163.com

O 221

A