均衡問題的一種改進不精確次梯度算法

黨亞崢, 沈 忱, 劉雯雯

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

均衡問題的一種改進不精確次梯度算法

黨亞崢, 沈 忱, 劉雯雯

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

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

均衡問題; 次梯度; 穩固非擴張映射; 全局收斂

1 問題描述

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

(1)

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

2 預備知識

定義1 如果算子T滿足

(2)

則稱算子T非擴張.

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

(3)

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

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

(4)

故PC非擴張.

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

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

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

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

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

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

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

(5)

現使用引理1和引理2對算法進行收斂性分析.

引理2 非負實數θ,β滿足不等式θ2-βθ≤0,則

(6)

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

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

證畢.

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

當x*∈Fix(T)時,有

(7)

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

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

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

3.1 不精確次梯度算法

(8)

(9)

步驟2 計算

(10)

令k:=k+1,轉步驟1.

(11)

3.2 收斂性分析

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

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

(12)

由步驟1得

(13)

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

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

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

(15)

證明 顯然

當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).

現證明在假設A1成立的情況下,由改進不精確次梯度算法生成的序列{xk}是有界的.

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

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

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

由命題1和假設A1可知

則

當m→+∞時,有

由參數的已知條件可知

(25)

利用參數定義可得

因此

(26)

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

(27)

假設A3 當存在y∈C時,f(·,y)是上半連續的.

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

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

(28)

(29)

從假設A2和定理1可知

(30)

(31)

4 結 論

提出了一種求解均衡問題中關于穩固非擴張映射T上的不動點集問題的不精確次梯度迭代算法.通過選擇適當的正則參數,驗證不精確次梯度算法的全局收斂性.相對于精確次梯度算法,減少了計算工作量,同時提高了算法的收斂性.

[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] 宇振盛,張麗娜,秦毅.非線性優化問題的光滑化序列二次規劃方法[J].上海理工大學學報,2015,37(4):317-321.

[10] 陳元媛,高巖.一種非線性擴展混合共軛梯度算法的全局收斂性[J].上海理工大學學報,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

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

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

O 221

A