箱约束变分不等式的一种非精确半光滑算法.pdf

第44卷第2期2023年6月淮北师范大学学报（自然科学版）Journal of Huaibei Normal University(Natural Sciences)Vol.44 No.2Jun.2023箱约束变分不等式的一种非精确半光滑算法张杰，蔡玉玉，王翀（淮北师范大学 数学科学学院，安徽 淮北 235000）摘要：为提高求解箱约束变分不等式问题的效率，文章在一个互补函数的基础上，将原问题转化为与之等价的方程组，给出一种非精确半光滑算法。在该算法的每步迭代中，相应的线性方程组都采用非精确求解方法。算法的全局收敛性被证明，数值试验表明，算法对求解该类问题稳定可靠。关键词：箱约束变分不等式；非精确牛顿方法；大规模问题中图分类号：O 221.0文献标识码：A文章编号：2095-0691（2023）02-0026-040引言变分不等式是一类重要的非线性问题，在物理、工程和金融等领域都有广泛应用。目前变分不等式问题仍然受到广泛关注，众多学者对其解的存在性和求解方法做出了诸多贡献1-6。变分不等式问题的一般表达式为：设XRn，F:RnRn，求xX，使F(x)T(y-x)0，yX。本文主要研究箱约束变分不等式，即设X=a,b:=|xRnaixibi,iN，记为VI(a,b,F)。如果X=|xRnx0，VI(a,b,F)就是非线性互补问题，即：求xR，使之满足x0,F(x)0,xTF(x)=0。箱约束变分不等式尽管是变分不等式的一种特殊情形，但其在许多领域有着广泛应用7-8。对于变分不等式的研究主要集中在2方面：一是解的相关理论，另一个是求解算法。本文主要关注箱约束变分不等式算法。关于箱约束变分不等式的求解算法已经有了一些较好的结果9-13，其中光滑化方法是一类重要方法，其基本思想是通过互补函数，将问题转化为与之等价的光滑或非光滑方程组，进而求出原问题近似解。往往在实际问题中，待求实际问题转化得到的变分不等式或互补问题规模都较大，如果直接采用上述光滑化方法，往往会影响求解效率，其原因主要是精确求解子问题效率不高。因此，在文献 14 所给出的互补函数基础上，采用非精确技术求解转化后的子问题，得到一种求解箱约束变分不等式的非精确半光滑方法。由于该方法避免精确求解转化后的大规模子问题，所以提高了求解效率。1算法本文利用文献 14 中的互补函数：i(u,v)=(u-ai)(u-bi)2+v2+(u-bi)(u-ai)2+v2+(bi-ai)v，i(u,v)=-(u-ai)(u-ai)2+v2+v)+(u-bi)+(u-bi)2+v2-v)，这里t+=max0,t，t-=min0,t，tR。由文献 14 结果，求解箱约束变分不等式VI(a,b,F)就等价于求解i()xi,Fi()x+i()xi,Fi()x=0。定义向量函数H:Rn+1Rn+1：收稿日期：2022-11-18基金项目：安徽省高等学校自然科学研究项目（KJ2020A0024）；淮北师范大学实验室开放项目（2022sykf016）作者简介：张杰（1979），女，安徽淮北人，硕士，副教授，研究方向为优化理论、算法与应用。第2期张杰等：箱约束变分不等式的一种非精确半光滑算法H()z=1()x1,F1()x+x1+1()x1,F1()x+x12()x2,F2()x+x2+2()x2,F2()x+x2n()xn,Fn()x+xn+n()xn,Fn()x+xn，这里z(,x)。于是若H()z=0，则=0，x即为箱约束变分不等式VI(a,b,F)的解。记()z=H(z)2，则求解箱约束变分不等式VI(a,b,F)的非精确半光滑方法可以设计如下：算法选取参数()0,1，()0,1以及()0,1。任取()0,x0R+Rn（R+表示正数）。另取序列满足k0,，0,1-0，令k=0。步1若H()zk=0，停止；步2计算zk=()k,xk,满足H()zk+Vkzk=k0rk,其中VkH()zk，k=()zkmin1,(zk)，rkkH()zk。步3令lk为满足下式的最小非负数：()zk+lzk1-()1-0-kl()zk。步4令zk+1=zk+lkzk，k=k+1，转步1。2收敛性本节讨论算法的收敛性，为了分析需要，首先给出P0-函数概念和几个结论。定义 1设F:RnRn，若对任意x,yRn，xy，有maxxiyi()xi-yi()Fi()x-Fi(y)0，则称F为P0-函数。命题1如果F:RnRn是连续可微的P0-函数，则任意VH(z)可逆。命题1在文献 14 中有详细证明。据命题1，算法第2步成立，从而可以得到算法是适定的。命题2如果F是连续可微的P0-函数，则对任意k0，由算法产生的无穷序列 zk=()k,xk，满足zk|()k,xkk()zk0。命题3如果对任意z=(),x R+Rn，都有VH(z)非奇异，那么存在z 的一闭邻域N(z)和正数(0,1，使得对z=(,x)N(z)，0,1-0，()0,1以及0,，有R+，VH(z)非奇异，且()z+z 1-()1-0-()z。命题2和命题3的证明类似于文献 10 中引理3和文献 15 中引理5，为简单计，本文从略。下面证明算法的全局收敛性，假设水平集L()z0=|zRn+1()z()z0有界，此即保证由算法产生的序列 zk有界，从而有聚点。定理1设F是连续可微的P0-函数，则由算法产生的序列 zk的任何聚点都是方程组H()z=0的解。证明设序列 zk由本文算法产生，z为 zk的任一聚点。不失一般性，假设序列 zk收敛于点z。根据算法设计数列()zk单调递减，所以由()z的连续性，有(zk)(z)0。如果()z=0，那么定理得证。下设()z0，由命题2知，zk，k()zk0=min1,(zk)0，故zR+。再由命题3可知，存在z的一闭邻域N(z)和正数(0,1，使得对z=(,x)N(z)，0,1-0，()0,1以及0,，()z+z 1-()1-0-()z成立。故对充分大的k，存在满足l(0,的正整数l，使()zk+lzk1-()1-0-kl()zk。对上式两边关于k+求极限，则有(z)0，这与所设()z0矛盾。此即说明上述2种情况都有27淮北师范大学学报（自然科学版）2023年H()z=0，从而定理得证。定理1证明了算法的全局收敛性，实际上还可以证明算法具有局部线性甚至超二次收敛性，类似于文献 10 和 15 中的讨论，本文从略。3数值算例为了测试非精确半光滑牛顿方法的求解效率，本节将对3个算例进行测试，所有试验程序都是用Matlab编写完成。算法参数按如下选取：=0.86,=0.001,0=0.1,=0.9，终止条件设为()z 10-6。算例 1F:R4R4为严格单调映射，F()x=x31-8x2-x3+x32+3x2+x3+2x33-3x4+2x34。（1）a=()0,0,0,0T，b=(5,5,5,5)T；（2）a=()-1,-1,-1,-1T，b=(1,1,1,1)T。算 例 2F:R4R4为 严 格 单 调 映 射，F()x=4x1+2x2+2x3+x4-82x1+4x2+x4-62x1+2x3+2x4-4-x1-x2-2x3+3。（1）a=()-5,-5,-5,-5T,b=()5,5,5,5T；（2）a=()-1,-1,-1,-1T，b=(1,1,1,1)T。算例3（线性互补问题）F()x=Mx+q，其中q=(-1,-1,-1)T，矩阵M选取方式和文献 10 类似，即M=122201220012 0001，该问题的解为x=()0,0,0T，算法中初始点选取为x0=()1,1,1T。算例13的计算结果列在表1和表2中，No.it表示迭代次数、CPU表示时间、Res表示算法终止时值。另外，表2中的n代表问题的维数。从计算结果来看，非精确半光滑牛顿方法求解此类箱约束变分不等式效率很好，特别是算例3的测试结果说明，对较大规模问题，算法仍然具有很好的效率，总的来说，本文算法可靠、有效。表1算例1、2计算结果算例1(1)1(2)2(1)2(2)No.it2322CPU/s0.001 30.002 20.001 30.002 8Res2.736 1e-0105.139 1e-0113.339 2e-0104.291 1e-010表2算例3计算结果n100300500No.it446CPU/s0.167 10.212 12.571 9Res1.175 1e-0103.781 2e-0104.891 2e-0114结语变分不等式与互补理论有着广泛应用背景。本文主要设计了一种求解箱约束变分不等式的非精确半光滑求解算法，并给出了数值试验。实际上，这种非精确求法可以推广到各种互补问题上去，甚至可以28第2期张杰等：箱约束变分不等式的一种非精确半光滑算法建立起求解变分与互补问题的非精确方法的统一框架。这种框架可以用来改善大规模问题的求解效率，从而大大拓宽锥优化的应用范围。综上，对于变分和互补的有效算法研究将是一个长期的、重要的研究方向。参考文献：1BIANCHI M，KASSAY G，PINI R.Regularization of brezis pseudomonotone variational inequalities J.Set-valued andVariational Analysis，2021，29（1）：175-190.2HAI T N.Dynamical systems for solving variational inequalities J.Journal of Dynamical and Control Systems，2022，28（4）：681-696.3SALEHNEJAD M，AZHINI M.Vector variational inequalities in G-convex spaces J.Tamkang Journal of Mathematics，2022，53（2）：147-161.4LARA F.Characterizations of nonconvex optimization problems via variational inequalitiesJ.Optimization，2022，71（9）：2471-2490.5BARBAGALLO A，BIANCO S G.A new tensor projection method for tensor variational inequalitiesJ.Journal ofNonlinear and Variational Analysis，2022，6（3）：213-226.6 LAMPARIELLOL，PRIORIG，SAGRATELLAS.On the solution of monotone nested variational inequalitiesJ.Mathematical Methods of Operations Research，2022，96（3）：421-446.7FERRIS M C，PANG J S.Engineering and economic applications of complementarity problems J.SIAM Review，1997，39（4）：669-713.8DIRKSE S P，FERRIS M C.The path solver：a non-monotone stabilization scheme for mixed complementarity problemsJ.Optimization Method and Software，1995，5（2）：123-156.9QI H D.A regularized smoothing Newton method for box constrained variational inequality problems withP0-functionsJ.SIAM Journal on Optimization，2000，10（2）：315-330.10 RUI S P，XU C X.A smoothing inexact Newton method for nonlinear complementarity problemsJ.Journal ofComputational and Applied Mathematics，2010，33（9）：2332-2338.11KEBAILI Z，BENTERKI D.A Penalty approach for a box constrained variational inequality problemJ.Applicationsof Mathematics，2018：63（4）：439-454.12 MA C F，KNAG T.A Jacobian smoothing method for box constrained variational inequality problemsJ.AppliedMathematics and Computation，2005，162（3）：1397-1429.13 WANG L，LI Y，ZHANG L W.A differential equation method for solving box constrained variational inequalityproblems J.Journal of Industrial and Management Optimization，2011，7（1）：183-198.14CHEN G Q，CAO B.A new NCP-function for box constrained variational inequality and related Newton-type methodJ.Mathematica Numerica Sinica，2002，24（1）：91-104.15QI L Q，SUN D F，ZHOU G L.A new look at smoothing Newton methods for nonlinear complementarity problems andbox constrained variational inequalities J.Mathematics Programming，2000，87（1）：1-35.An Inexact Semismooth Algorithm for Solving BoxConstrained Variational InequalityZHANG Jie，CAI Yuyu，WANG Chong（School of Mathematical Sciences，Huaibei Normal University，235000，Huaibei，Anhui，China）Abstract：In order to improve the efficiency of solving variational inequality problems with box constraints，the original problems transformed into equivalent equations and an inexact semismooth Newton method isproposed based on a complementarity function.In each iteration of the algorithm，the corresponding linearequations are solved by an inexact method.The global convergence of the algorithm is proved，andnumerical experiments show that the algorithm is stable and reliable for solving this kind of problem.Key words：box constrained variational inequalities；inexact Newton method；large-scale problems29