董朝丽，谢亚君

(1.福建师范大学数学与计算机科学学院，福建福州 350007;2.福建江夏学院信息系，福建福州 350108)

对一类随机线性互补问题的信赖域线搜索拟牛顿法

董朝丽1，谢亚君2

(1.福建师范大学数学与计算机科学学院，福建福州 350007;2.福建江夏学院信息系，福建福州 350108)

研究了一类随机线性互补问题的解法，采用信赖域线搜索与拟牛顿方法相结合的方法对其进行求解，在适当的假设条件下进行收敛性分析，得到了算法的全局收敛性，表明了算法的可行性和有效性.

随机线性互补问题;信赖域;线搜索;拟牛顿法

考虑一个概率空间(Ω，F，P)，其中Ω⊆Rn.假设概率分布P是已知的，随机线性互补问题［1－3］就是找一个满足

本文提出信赖域线搜索拟牛顿算法来求解随机线性互补问题.把信赖域算法和线搜索方法相结合，最早是由NOCEDAL J和袁亚湘［9］提出来的思想，其后，邓乃阳［10］首次提出一类非单调信赖域算法，在一定条件下证明了其全局收敛性和超线性收敛性.文献［11－13］又对其进行了推广和修正.本文利用了NCP函数的性质，将随机线性互补问题转化为无约束的最小化问题，通过求出无约束最小化问题的解，得到原问题的最优解.在适当的假设下，笔者证明了该算法的全局收敛性.

1 算法

将问题(2)转化为一个无约束的最小化问题.笔者主要利用了Fischer Burmeister(F-B)函数

由 NCP函数的性质:φ(a，b)=0⇔a≥0，b≥0，ab=0.易知，如果问题(2)有解，那么解问题(2)等价于解如下的线性方程组

对于无约束最优化问题

步骤3 求解子问题(11)的近似最优解dk，且dk满足

2 算法的收敛性

首先做如下假设:

引理4若在假设1，2成立的条件下，数列{fk}非增且收敛.

证明由于迭代中采用Wolf线搜索求下一迭代点，由引理3，可知{fk}非增.由假设1，2知{fk}有下界，因此{fk}非增且收敛.

则对任意k，存在常数α ＞0，满足 αk＞α.

证明由于αk满足式(16)，则

［1］LIN G H，CHEN X J，FUKUSHIMA M.New restricted NCP functions and their applications to stochastic NCP and stochastic NPEC［J］.Optimization，2007，56:641 －653.

［2］LIN G H，FUKUSHIMA M.New reformulations for stochastic nonlinear complementarity problems［J］.Optim Methods Soft，2006，21:551－564.

［3］ZHOU G L，CACCETTA L.Feasible semismooth Newtonmethod for a class of stochastic linear complementarity［J］.J Optim Theory Appl.，2008，139:379 －392.

［4］COTTLE R W，PANG J S，STONE R E.The linear complementarity problem［M］.New York:Academic press，1992.

［5］LIU X W，SUN J.Global convergence analysis of line search interior-point methods for nonlinear programming without reqularity assumptions［J］.J Optim Theory Appl.，2005，125:609 － 628.

［6］CHEN X，FUKUSHIMA M.Expected residual minimization method for stohastic linear complementarity problems［J］.Math oper RES，2005，30:1022 －1038.

［7］ZHANG Li-ping，GAO Zi-you.Superlinner/quadratic one-stepsmoothing Newton methlod for P0-NCP without strict complementarity［J］.Mathematical Methods of Operation Reserch，2002，56:231－241.

［8］席少霖.非线性最优化方法［M］.北京:高等教育出版社，1992.

［9］NOCEDAL J，YUAN Y X.Combining trust region and line search techniques［M］∥YUAN Y.Advances in nonlinear programming.Dordrecht:Kluwer Academic Publishers，1998:153 －176.

［10］DENG N Y，XIAO Y，ZHOU F J.A nonmontonic trust region algorithm［J］.Journal of optimization Theory and Applications，1993，76(2):259 －285.

［11］TOINT P.A nonmonotone trust region algorithm for nonlinear optimization subject to convex constraints［J］.Mathematical Programming，1997，77(1):69 －94.

［12］李正锋，邓乃阳.一类新的非单调信赖域算法及其收敛性［J］.应用数学学报，1999，22(3):458－465.

［13］柯小伍，韩继业.一类新的信赖域算法的全局收敛性［J］.应用数学学报，1995，18(4):608－615.

A Line Search Quasi-Newton Trust-region Algorithm for a Class of Stochastic Linear Complementarity Problems

DONG Zhao-li1，XIE Ya-jun2

(1.School of Mathematics and Computer Sciences，Fujian Teachers’University，Fuzhou 350007，China;2.Information Department，Jiangxia University of Fujian ，Fuzhou 350108，China)

A method of solving a class of stochastic linear complementarity problem was discussed，which combined quasi-Newton trust region method with line search techniques，and the global convergence of the algorithm was proved under some suitable assumptions.The result showed that the algorithm was feasible and effective.

stochastic linear complementarity problem;trust-region;line search;quasi-Newton method

O 224 < class="emphasis_bold">文献标志码:A

A

1004－1729(2011)01－0020－05

2010－08－30

董朝丽(1985－)，女，山西阳城人，福建师范大学数学与计算机科学学院2008级硕士研究生.