對一類隨機線性互補問題的信賴域線搜索擬牛頓法

董朝麗，謝亞君

(1.福建師范大學數(shù)學與計算機科學學院，福建福州 350007;2.福建江夏學院信息系，福建福州 350108)

對一類隨機線性互補問題的信賴域線搜索擬牛頓法

董朝麗1，謝亞君2

(1.福建師范大學數(shù)學與計算機科學學院，福建福州 350007;2.福建江夏學院信息系，福建福州 350108)

研究了一類隨機線性互補問題的解法，采用信賴域線搜索與擬牛頓方法相結(jié)合的方法對其進行求解，在適當?shù)募僭O條件下進行收斂性分析，得到了算法的全局收斂性，表明了算法的可行性和有效性.

隨機線性互補問題;信賴域;線搜索;擬牛頓法

考慮一個概率空間(Ω，F(xiàn)，P)，其中Ω?Rn.假設概率分布P是已知的，隨機線性互補問題［1－3］就是找一個滿足

本文提出信賴域線搜索擬牛頓算法來求解隨機線性互補問題.把信賴域算法和線搜索方法相結(jié)合，最早是由NOCEDAL J和袁亞湘［9］提出來的思想，其后，鄧乃陽［10］首次提出一類非單調(diào)信賴域算法，在一定條件下證明了其全局收斂性和超線性收斂性.文獻［11－13］又對其進行了推廣和修正.本文利用了NCP函數(shù)的性質(zhì)，將隨機線性互補問題轉(zhuǎn)化為無約束的最小化問題，通過求出無約束最小化問題的解，得到原問題的最優(yōu)解.在適當?shù)募僭O下，筆者證明了該算法的全局收斂性.

1 算法

將問題(2)轉(zhuǎn)化為一個無約束的最小化問題.筆者主要利用了Fischer Burmeister(F-B)函數(shù)

由 NCP函數(shù)的性質(zhì):φ(a，b)=0?a≥0，b≥0，ab=0.易知，如果問題(2)有解，那么解問題(2)等價于解如下的線性方程組

對于無約束最優(yōu)化問題

步驟3 求解子問題(11)的近似最優(yōu)解dk，且dk滿足

2 算法的收斂性

首先做如下假設:

引理4若在假設1，2成立的條件下，數(shù)列{fk}非增且收斂.

證明由于迭代中采用Wolf線搜索求下一迭代點，由引理3，可知{fk}非增.由假設1，2知{fk}有下界，因此{fk}非增且收斂.

則對任意k，存在常數(shù)α ＞0，滿足 αk＞α.

證明由于αk滿足式(16)，則

［1］LIN G H，CHEN X J，F(xiàn)UKUSHIMA M.New restricted NCP functions and their applications to stochastic NCP and stochastic NPEC［J］.Optimization，2007，56:641 －653.

［2］LIN G H，F(xiàn)UKUSHIMA 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，F(xiàn)UKUSHIMA 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］席少霖.非線性最優(yōu)化方法［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］李正鋒，鄧乃陽.一類新的非單調(diào)信賴域算法及其收斂性［J］.應用數(shù)學學報，1999，22(3):458－465.

［13］柯小伍，韓繼業(yè).一類新的信賴域算法的全局收斂性［J］.應用數(shù)學學報，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，F(xiàn)ujian Teachers’University，F(xiàn)uzhou 350007，China;2.Information Department，Jiangxia University of Fujian ，F(xiàn)uzhou 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－)，女，山西陽城人，福建師范大學數(shù)學與計算機科學學院2008級碩士研究生.