求解非线性互补问题的光滑化ODE-型信赖域方法
|
摘要
结合信赖域技术和ODE型方法,本文提出了一个求解非线性互补问题的混合算法,该方法在每一步迭代过程中仅需求解一线性方程组系统,从而避免了求解带信赖域界的二次规划子问题,并在F为P_O函数的假设下,得到了它的全局收敛性与超线性收敛性,数值实验表明,该算法可行、有效。
This paper presents a new hybrid method for solving nonlinear complementarity problem with P0-functions.It can be regarded as a combination of smoothing trust region method with ODE-based method.A feature of the proposed algorithm is that at each iteration,a linear system is only solved once to obtain a trial step,thus avoiding solving a trust region subproblem.Under some conditions, the method is proven to be globally and superlinearly convergent. Preliminary numerical results indicate that the proposed method is promising.
This paper presents a new hybrid method for solving nonlinear complementarity problem with P0-functions.It can be regarded as a combination of smoothing trust region method with ODE-based method.A feature of the proposed algorithm is that at each iteration,a linear system is only solved once to obtain a trial step,thus avoiding solving a trust region subproblem.Under some conditions, the method is proven to be globally and superlinearly convergent. Preliminary numerical results indicate that the proposed method is promising.
引文
[1]韩继业,修乃华,戚厚铎.非线性互补理论与算法[M]。上海：上海科学技术出版社,2006.
[2]Qi L,Chen X.A globally convergent successive approximation method for nonsmooth equations[J].SIAM Journal on Control and Optimization,1995,38:402-418.
[3]Kanzow C.Some noninterior continuation methods for linear complementarity problems[J].SIAM Journal Matrix Analysis and Application,1996,17:851-868.
[4]Chen X,Qi L,Sun D.Global and superlinear of the smoothing Newton methods and its application to general box constrained Variational inequalities[J].Mathematics of Computation,1998,222:519-540.
[5]Kanzow C,Pieper H.Jacobian smoothing methods for nonlinear complementarity problems[J].SIAM Journal on Optimization,1999,9:342-373.
[6]Deng N Y,Xiao Y,Zhou F T.Nonmonotonic trust region algorithm[J].JOTA,1993.26:259-285.
[7]Coleman T F,Li Y.An interior trust region approach for nonlinear minimization subject to bounds[J].SIAM J.on optimization,1996,6:418-445.
[8]Nocedal J,Yuan Y X.Combing trust region and line search techniques in Advances in Nonlinear Programming[J].Kluwer,1998,153-175.
[9]Y.F.Yang and L.Q.Qi, Smoothing trust region methods for nonlinear complementarity problems with PO-functions[J]. Annals of Operations Research,2005,133:99-117.
[10]马昌凤.求解非线性互补问题的一个光滑信赖域算法[J].工程数学学报.2006,23(1)：20-28.
[11]陈为民,杨余飞.求解一般非线性互补问题的光滑化方法[J].运筹学学报,2008,12(1)：93-103.
[12]Ying Zhou.A smoothing conic trust region filter method for the nonlinear complementarity problem[J]. Journal of Computational and Applied Mathematics.229(2009):248-263.
[13]C.F.Ma and X.H.Chen, The convergence of one-step smoothing Newton method for PO-NCP based on a new smoothing NCP-function[J]. Journal of Computational and Applied Mathematics,2008,216:1-13.
[14]袁亚湘,孙文瑜.最优化理论与方法[M]。北京：科学出版社,2003.
[15]A.A.Brown and M.C.Biggs, Some effective methods for unconstrained optimization based on the solution of system of ordinary differentiable equations [J]. Journal of Optimization Theory and Application, 1989,62:211-224.
[16]Y.GOu, Q.Zhou and H.C.Lin, An ODE-based trust region method for unconstrained optimization problems [J]. Journal of Computational and Applied Mathematics,2009,232:318-326.
[17]F.H.Clarke, Optimization and Nonsmooth Analysis. NewYor:John Wiley,1983.
[18]L.Q.Qi, Convergence analysis of some algorithms for solving nonsmooth equations[J]. Mathematics of Operations Research,1993,18:227-244.
海南大学硕士学位论文 参考丈献
[19]Y.G.Ou, Trust region algorithm for a class of nonlinear complementarity problem [J]. Chinese Quarterly Journal of Mathematics,2007,22(4):558-566.
[20]俞吴东,非线性互补问的非单调信赖域算法[D].上海同济大学硕士学位论文,2008.
[21]J.L.Zhang and X.S.Zhang, A smoothing Levenberg-Marquardt method for NCP [J]. Applied Mathematics and Computation,2006,178:212-228.
[22]张忠桢.凸规划[M].武汉：武汉大学出版社,2004.
[2]Qi L,Chen X.A globally convergent successive approximation method for nonsmooth equations[J].SIAM Journal on Control and Optimization,1995,38:402-418.
[3]Kanzow C.Some noninterior continuation methods for linear complementarity problems[J].SIAM Journal Matrix Analysis and Application,1996,17:851-868.
[4]Chen X,Qi L,Sun D.Global and superlinear of the smoothing Newton methods and its application to general box constrained Variational inequalities[J].Mathematics of Computation,1998,222:519-540.
[5]Kanzow C,Pieper H.Jacobian smoothing methods for nonlinear complementarity problems[J].SIAM Journal on Optimization,1999,9:342-373.
[6]Deng N Y,Xiao Y,Zhou F T.Nonmonotonic trust region algorithm[J].JOTA,1993.26:259-285.
[7]Coleman T F,Li Y.An interior trust region approach for nonlinear minimization subject to bounds[J].SIAM J.on optimization,1996,6:418-445.
[8]Nocedal J,Yuan Y X.Combing trust region and line search techniques in Advances in Nonlinear Programming[J].Kluwer,1998,153-175.
[9]Y.F.Yang and L.Q.Qi, Smoothing trust region methods for nonlinear complementarity problems with PO-functions[J]. Annals of Operations Research,2005,133:99-117.
[10]马昌凤.求解非线性互补问题的一个光滑信赖域算法[J].工程数学学报.2006,23(1)：20-28.
[11]陈为民,杨余飞.求解一般非线性互补问题的光滑化方法[J].运筹学学报,2008,12(1)：93-103.
[12]Ying Zhou.A smoothing conic trust region filter method for the nonlinear complementarity problem[J]. Journal of Computational and Applied Mathematics.229(2009):248-263.
[13]C.F.Ma and X.H.Chen, The convergence of one-step smoothing Newton method for PO-NCP based on a new smoothing NCP-function[J]. Journal of Computational and Applied Mathematics,2008,216:1-13.
[14]袁亚湘,孙文瑜.最优化理论与方法[M]。北京：科学出版社,2003.
[15]A.A.Brown and M.C.Biggs, Some effective methods for unconstrained optimization based on the solution of system of ordinary differentiable equations [J]. Journal of Optimization Theory and Application, 1989,62:211-224.
[16]Y.GOu, Q.Zhou and H.C.Lin, An ODE-based trust region method for unconstrained optimization problems [J]. Journal of Computational and Applied Mathematics,2009,232:318-326.
[17]F.H.Clarke, Optimization and Nonsmooth Analysis. NewYor:John Wiley,1983.
[18]L.Q.Qi, Convergence analysis of some algorithms for solving nonsmooth equations[J]. Mathematics of Operations Research,1993,18:227-244.
海南大学硕士学位论文 参考丈献
[19]Y.G.Ou, Trust region algorithm for a class of nonlinear complementarity problem [J]. Chinese Quarterly Journal of Mathematics,2007,22(4):558-566.
[20]俞吴东,非线性互补问的非单调信赖域算法[D].上海同济大学硕士学位论文,2008.
[21]J.L.Zhang and X.S.Zhang, A smoothing Levenberg-Marquardt method for NCP [J]. Applied Mathematics and Computation,2006,178:212-228.
[22]张忠桢.凸规划[M].武汉：武汉大学出版社,2004.