一种求解包含问题的算法研究.pdf

数理科学与信息科学研究一种求解包含问题的算法研究杨军，李飞艳（咸阳师范学院 数学与统计学院，陕西 咸阳 712000）摘要：一种实希尔伯特空间中求解包含问题的算法被提出，所提出的算法基于向前向后方法、压缩方法、惯性方法和无需搜索的自适应步长。算法的特点为迭代中多次使用惯性加速方法，且自适应步长随着迭代次数增加可能增大。在包含问题解集非空、一个映射极大单调、另一个映射单调且利普希茨连续的假设下，算法的强收敛性被证明。关键词：包含问题；向前向后方法；零点中图分类号：O221.2文献标识码：A文章编号：1672-2914（2024）02-0001-04AnAlgorithm for Solving Inclusion ProblemsYANG Jun，LI Feiyan(School of Mathematics and Statistics,Xianyang Normal University,Xianyang 712000,Shaanxi,China)Abstract：In this work,a new method for solving inclusion problems in real Hilbert space is giv-en.The algorithm is inspired by forward-backward splitting method,contraction method,inertial meth-od and self-adaptive step sizes.The characteristic of the algorithm is that the inertial acceleration meth-od is used many times in the iteration,and the adaptive step size may increase with the increase of thenumber of iterations.Under the assumption that the solution set of the inclusion problem is non-empty,one map is maximally monotone,and the other map is monotone and Lipschitz continuous,the strongconvergence of the algorithm is proved.Key words：inclusion problem;forward-backward splitting method;zero point2024年3月咸阳师范学院学报Mar.2024第39卷 第2期Journal of Xianyang Normal UniversityVol.39 No.2包含问题是一种重要的优化模型，它包括变分不等式问题、纳什平衡问题、互补问题、不动点问题等1-3。为求解包含问题，Passty4、Lions等5提出了向前向后迭代方法，当映射为强制时且步长在一定的范围内时，所提算法的弱收敛性被证明。若映射为利普希茨连续时，Tseng6提出了更为广义的迭代方法，在一定的条件下，所提算法的弱收敛性被证明。近年来，在文献6所提算法的基础上，一些强收敛的算法7-11被提出。惯性方法12近年来被众多学者研究，被认为是一种能加速收敛的方法。本文将结合惯性方法、压缩方法13和一些其他方法14-16，提出一种新的求解包含问题的算法。1 预备知识设H是实希尔伯特空间，A:HH为给定的单值映射，B:H2H为多值映射，包含问题为：寻找xH，满足0(A+B)x。（1）本文将在下面的条件下考虑包含问题（1）的求解方法。条件1 包含问题（1）的解集S非空。条件2 映射A单调且利普希茨连续，映射B极大单调。定 义 117设B:H2H为 多 值 映 射，若x,yH，uBx,vBy0，则称B是单调映射。若B是单调的且对于任意的(x,u)HH，(y,v)Graph(B)，0满足uBx，则B是极大单调映射。定 义 217设D:H2H为 多 值 映 射，若收稿日期：2024-02-07基金项目：陕西省自然科学基础研究计划项目(2023-JC-YB-049)；咸阳师范学院大学生创新创业训练计划项目(XYS-FXY2022093)。作者简介：杨军（1980），男，咸阳师范学院数学与统计学院副教授，博士，研究方向为最优化理论与算法。E-mail：xy-。Dx-Dy2,x,yH，则 称B是紧非扩张映射。定 义 318设B:H2H为 极 大 单 调 映 射 且0，则称JB(x):=(I+B)-1x(x,u)HH为豫解映射。易知JB是单值非扩张映射。引理119若B是极大单调映射且A是单调利普希茨连续映射，则A+B是极大单调映射。引理217设C是实希尔伯特空间H的非空闭凸子集，对于任意xH，令PCx为x在C上的投影，则0,yC。引理 320设 an是非负实序列且满足存在N0,nN,满足an+1(1-n)an+nbn其 中n(0,1)且n=0n=。若 对 于 满 足lim infk(ank+1-ank)0的子列ank都有lim supkbnk0，则limnan=0。2 算法及其收敛性算法 1步骤0 给定10，001，x0,x1,w0,z0H，(0,1，(0,2)。选取非负实序列 pn，使其满足n=1pn+。选取实序列qn1,+)，使其满足limnqn=1。令n=1。步骤1已知xn-1，xn，wn-1，zn-1，计算wn=xn+n(xn-xn-1)+n(wn-1-xn)+n(zn-1-xn)和yn=(I+nB)-1(I-nA)wn。步骤2构造dn=wn-yn-n(Awn-Ayn)和n=dn2,dn01-0(1+0)2,其他步骤3 计算zn=wn-ndn和xn+1=nx0+(1-n)zn。步骤4 计算n+1=minqnwn-ynAwn-Ayn,n+pn,Awn-Ayn0n+pn,其他令n:=n+1返回步骤1。引理 4 设序列 xn是由算法 1 产生的有界序列。若存在子列xnk弱收敛于x*H且limkynk-wnk=limkxnk-wnk=0，则x*S。证明：与文献11中的引理3.2相同。引理5 设序列 zn是由算法1产生且uS，则nNzn-u2wn-u2-(2-)(1-0)2(1+0)2wn-yn2。证明：与文献11中的引理3.5类似。定理1 设序列 xn是由算法1产生的有界序列，且满足01，n0,)01，n0,)，01，n0,)，n(0,1)，limnn=0，n=0n=，limnnnxn-xn-1=limnnnwn-1-xn=limnnnxn-zn-1=0。则 xn强收敛于包含问题的解。证明：由于S是非空闭凸集，故设x*=PSx0，由引理2可得0,zS。（2）根据引理5，nNzn-x*2wn-x*2-(2-)(1-0)2(1+0)2wn-yn2进一步可得zn-x*wn-x*,nN。（3）根据wn的定义，得到wn-x*=xn+n(xn-xn-1)+n(wn-1-xn)+n(zn-1-xn)-x*xn-x*+nnnxn-xn-1+nnnwn-1-xn+nnnzn-1-xn。（4）由于limnnnxn-xn-1=0，limnnnwn-1-xn=0，limnnnzn-1-xn=0，则存在常数M10，满足nnxn-xn-1M13，nnwn-1-xnM13，nnzn-1-xnM13。（5）结合引理5，式（4）和（5），得出nN2咸阳师范学院学报第39卷zn-x*wn-x*xn-x*+nM1。（6）进一步可得，nNxn+1-x*=nx0+(1-n)zn-x*nx0-x*+(1-n)zn-x*n(x0-x*+M1)+(1-n)xn-x*max(x0-x*+M1),xn-x*（7）从而可得序列 xn有界。进一步有序列zn和wn有界。根据xn+1的定义和引理5，得出nNxn+1-x*2=(1-n)(zn-x*)+n(xn-x*)2(1-n)2zn-x*2+n2xn-x*2+2(1-n)nzn-x*,xn-x*(1-n)(wn-x*2-(2-)(1-0)2(1+0)2wn-yn2)+n2xn-x*2+2(1-n)nzn-x*,xn-x*。（8）根据wn的定义，可得wn-x*2=xn+n(xn-xn-1)+n(wn-1-xn)+n(zn-1-xn)-x*2=xn-x*2+2nxn-xn-12+2nwn-1-xn2+2nzn-1-xn2+2nxn-x*,xn-xn-1+2nxn-x*,wn-1-xn+2nxn-x*,zn-1-xn+2nnxn-xn-1,wn-1-xn+2nnzn-1-xn,wn-1-xn+2nnxn-xn-1,zn-1-xnxn-x*2+2nxn-xn-12+2nwn-1-xn2+2nzn-1-xn2+2nxn-x*xn-xn-1+2nxn-x*wn-1-xn+2nxn-x*zn-1-xn+2nnxn-xn-1 wn-1-xn+2nnxn-xn-1 zn-1-xn+2nnwn-1-xn zn-1-xn。（9）令wn-1-xn,zn-1-xn,2xn-x*，结合式（6）（8）（9），可得nNxn+1-x*2(1-n)xn-x*2+2nxn-xn-12+2nwn-1-xn2+2nzn-1-xn2+2nxn-x*xn-xn-1+2nxn-x*wn-1-xn+2nxn-x*zn-1-xn+2nnxn-xn-1 wn-1-xn+2nnxn-xn-1 wn-1-xn+2nnxn-xn-1 zn-1-xn+2nnwn-1-xn zn-1-xn-(1-n)(2-)(1-0)2(1+0)2wn-yn2+n2xn-x*2+2(1-n)nzn-x*,xn-x*(1-n)xn-x*2+nxn-xn-1(xn-xn-1+2xn-x*+wn-1-xn+zn-1-xn)+nwn-1-xn(wn-1-xn+2xn-x*+xn-xn-1+zn-1-xn)+nzn-1-xn(zn-1-xn+2xn-x*+xn-xn-1+wn-1-xn)-(1-n)(2-)(1-0)2(1+0)2wn-yn2+n2xn-x*2+2(1-n)nzn-x*,xn-x*(1-n)xn-x*2-(1-n)(2-)(1-0)2(1+0)2wn-yn2+n(4M2nnxn-xn-1+4M2nnwn-1-xn+4M2nnzn-1-xn+nxn-x*2+4M2nnzn-1-xn+nxn-x*2+2zn-x*,xn-x*。（10）故存在M3，可得nNxn+1-x*2xn-x*2+nM3-(1-n)(2-)(1-0)2(1+0)2wn-yn2。（11）根据式（11），得到nN(1-n)(2-)(1-0)2(1+0)2wn-yn2xn-x*2-xn+1-x*2+nM3。（12）假设xnk-x*是xn-x*的子序列且满足lim infk(xnk+1-x*-xnk-x*)0，则lim infk(xnk+1-x*2-xnk-x*2)=lim infk(xnk+1-x*+xnk-x*)(xnk+1-x*-xnk-x*)0从而可得lim supk(1-nk)(2-)(1-0)2(1+0)2wnk-ynk2=lim supk(xnk-x*2-xnk+1-x*2)+lim supknkM30。（13）故可得limkynk-wnk=0。（14）进一步有limkdnk=0，第2期杨军，等：一种求解包含问题的算法研究3limkznk-wnk=limk|nk|dnk=0。（15）又由于xnk-wnknkxnk-xnk-1+nkwnk-1-xnk+nkznk-1-xnk=nknknkxnk-xnk-1+nknknkwnk-1-xnk+nknknkznk-1-xnk。故可得limkxnk+1-xnk=limkxnk-wnk=limkxnk+1-znk=limkznk-wnk=0。由于xnk有界，则存在子列xnki弱收敛于z0H且满足lim supkx0-x*,xnk-x*=limix0-x*,xnki-x*=x0-x*,z0-x*。根据引理4得到z0S。利用式（2）进一步得到lim supkx0-x*,xnk-x*=x0-x*,z0-x*0。（16）根据式（10）（16），limnn=0和引理3，得到limnxn-x*=0。证毕。3 结论结合向前向后方法、压缩方法、无需搜索的步长等方法，一种求解包含问题的自适应算法被提出。算法使用了更广义的惯性加速方法，在一定的条件下，算法的强收敛性被证明。参考文献：1CHEN G H，ROCKAFELLAR R T.Convergence rates inforward-backward splittingJ.SIAM Journal on Optimiza-tion，1997，7（2）：421-444.2ROCKAFELLAR R T.Monotone operators and the proximalpoint algorithmsJ.SIAM Journal on Control and Optimiza-tion，1976，14（5）：877-898.3MOUDAFI A，THERA M.Finding a zero of the sum of twomaximal monotone operatorsJ.Journal of Optimization The-ory andApplications，1997，94：425-448.4PASSTY G B.Ergodic convergence to a zero of the sum ofmonotone operators in Hilbert spaceJ.Journal of Mathemat-icalAnalysis andApplications，1979，72：383-390.5LIONS P L，MERCIER B.Splitting algorithms for the sumof two nonlinear operatorsJ.SIAM Journal on NumericalAnalysis，1979，16：964-979.6TSENG P.A modified forward-backward splitting methodfor maximal monotone mappingJ.SIAM Journal on Con-trol and Optimization，2000，38：431-446.7GIBALI A，THONG D V.Tseng type methods for solvinginclusion problems and its applicationsJ.Calcolo，2018，55：49.8DONG Q，JIANG D，CHOLAMJIAK P，et al.A strong con-vergence result involving an inertial forward-backward algo-rithm for monotone inclusionsJ.Journal of Fixed Point The-ory andApplications，2017，19：3097-3118.9THONG D V，CHOLAMJIAK P.Strong convergence of aforward-backward splitting method with a new step size forsolving monotone inclusionsJ.Computational and AppliedMathematics，2019，38：94.10SHEHU Y.Convergence results of forward-backward algo-rithms for sum of monotone operators in Banach spacesJ.Results in Mathematics，2019，74：138.11YANG J，ZHAO H L，AN M.Weak and strong conver-gence results for solving inclusion problems and its applica-tionsJ.Journal of Applied Mathematics and Computing，2022，68：2803-2822.12ALVAREZ F.Weak convergence of a relaxed and inertialhybrid projection-proximal point algorithm for maximalmonotone operators in Hilbert spacesJ.SIAM Journal onOptimization，2004，14：773-782.13HE B S.A class of projection and contraction methods formonotone variational inequalitiesJ.Applied Mathematicsand Optimization，1997，35：69-76.14THONG D V，VINH N T，CHO Y J.A strong convergencetheorem for Tseng s extragradient method for solving varia-tional inequality problemsJ.Optimization Letters，2020，14：1157-1175.15YANG J，LIU H W.Strong convergence result for solvingmonotone variational inequalities in Hilbert spaceJ.Numer-icalAlgorithms，2019，80（3）：741-752.16LIU H W，YANG J.Weak convergence of iterative meth-ods for solving quasimonotone variational inequalitiesJ.Computational Optimization and Applications，2020，77：491-508.17BAUSCHKE H H，COMBETTES P L.Convex analysisand monotone operator theory in Hilbert spacesM.NewYork:Springer-Verlag，2010：59-415.18REICH S.Extension problems for accretive sets in BanachspacesJ.Journal of FunctionalAnalysis，1977，26：378-395.19TAN K K，XU H K.Approximating fixed points of nonex-pansive mappings by the Ishikawa iteration processJ.Jour-nal of Mathematical Analysis and Applications，1993，178：301-308.20KIMURA Y，SAEJUNG S.Strong convergence for a com-mon fixed point of two different generalizations of cutter op-eratorsJ.Linear NonlinearAnalysis，2015，1：53-65.责任编辑 赵 正4咸阳师范学院学报第39卷