非线性互补问题的一种光滑牛顿法
|
摘要
通过将非线性互补问题转化为光滑方程组,本文给出求解非线性互补问题NCP(F)的一种光滑牛顿法.在F为P0+R0函数时,证明了算法的全局收敛性.然而,由于相应光滑方程组的Jacobi矩阵在解上为零矩阵,算法理论上不保证局部超线性收敛率.借鉴A. O. Griewank[38]和任玉芳[53]的工作,本文提出一个扰动策略,在迭代点列靠近NCP(F)之解时,使扰动点进入能保证快速线性收敛到NCP(F)某个近似解的星形域,继续单位步长的光滑牛顿迭代,可保证算法能够快速线性收敛到]NCP(F)的某个近似解.数值算例表明,任意初始点,算法能较快迭代到解附近,再结合保证快速线性收敛的扰动策略,实际计算中获得很好的数值结果.相对现有非光滑牛顿法和光滑化牛顿法本文所提出的光滑牛顿法构造简单,便于实际应用.
In this dissertation, a smooth damped Newton method for solving the nonlinear comple-mentarity problem NCP(F) is presented by reformulating NCP(F) to a system of smooth equa-tions. The algorithm is proved to be globally convergent under the assumption that F is P0+R0 function. However, the local superlinear convergence is not guaranteed since the Jacobian ma-trix of the system of smooth equations at the solution is a zero matrix. To overcome this defect, a perturbation strategy is given by which an iterative point xk can be perturbed to xk which belong to the star-like region presented in A. O. Griewank[38] and Ren Yufang[53],it can be proved that the sequence generated by the smooth Newton iteration with unit step size starting from xk is quickly linearly convergent to an approximate solution of NCP(F). Numerical re-sults show that, starting from any initial point x0∈Rn, the sequence {xk} generated by the smooth damped Newton method is quickly convergent to near the solution, and starting from the perturbation point xk the sequence generated by the smooth Newton iteration with unit step size is quickly convergent to an approximate solution. Compared with the existing non-smooth or smoothing Newton methods, the smooth Newton method presented in this dissertation is simple and easy to the practical applications.
In this dissertation, a smooth damped Newton method for solving the nonlinear comple-mentarity problem NCP(F) is presented by reformulating NCP(F) to a system of smooth equa-tions. The algorithm is proved to be globally convergent under the assumption that F is P0+R0 function. However, the local superlinear convergence is not guaranteed since the Jacobian ma-trix of the system of smooth equations at the solution is a zero matrix. To overcome this defect, a perturbation strategy is given by which an iterative point xk can be perturbed to xk which belong to the star-like region presented in A. O. Griewank[38] and Ren Yufang[53],it can be proved that the sequence generated by the smooth Newton iteration with unit step size starting from xk is quickly linearly convergent to an approximate solution of NCP(F). Numerical re-sults show that, starting from any initial point x0∈Rn, the sequence {xk} generated by the smooth damped Newton method is quickly convergent to near the solution, and starting from the perturbation point xk the sequence generated by the smooth Newton iteration with unit step size is quickly convergent to an approximate solution. Compared with the existing non-smooth or smoothing Newton methods, the smooth Newton method presented in this dissertation is simple and easy to the practical applications.
引文
[1]P. T. Harker and J. S. Pang, Finite-dimensional variational inequality and nonlinear complementarity prob-lem:Asurvey of theory, algorithms and application, Mathematical Programming,1990,48:161-220.
[2]J. M. Peng, Unconstrained optimization methods for nonlinear complementarity problem, Journal of Com-putational Mathematics,1995,13(3):259-266.
[3]修乃华,高自友,互补问题算法的新进展,数学进展,1999,28(3)：193-208.
[4]X. Naihua, Tangent projection equation and general variational inequalities, Journal of Mathematical Anal-ysis and Applications,2001,258:755-762.
[5]A. Fischer, A special Newton-Type optimization method, Optimization,1992,24:269-284.
[6]O. L. Mangasarian, Equivalence of the complementarity problems to a system of nonlinear equations, SIAM Journal on Applied Mathematics,1976,31:89-92.
[7]L. T. Watson, Solving the nonlinear complementarity problem by a homotopy method, SIAM Journal of Control and Optimization,1979,17:36-46.
[8]P. K. Subramanian, Gauss-Newton methods for the complementarity problem, Journal of Optimization The-ory and Applications,1993,77:467-482.
[9]C. Kanzow, Global convergence of some iterative methods for linear complementarity problems, SIAM Journal on Optimization,1996,6:326-341.
[10]S. M. Robinson, Strongly regular generalized equations, Mathematics of Operations Research,1980,5: 43-62.
[11]T. Luca, F. Facchinei, C. Kanzow, Theoretical and numerical comparison of some semismooth algorithms for complementarity problems, Computational Optimization and Applications,2000,16(2):173-205.
[12]J. Houyuan, Smoothed Fischer-Burmeister equation method for the complementarity problem, Technical Report, Department of Mathematics, The University of Melbourne, Parkvile, Victoria, Australia, June,1997.
[13]J. S. Pang, A B-differentiable equation based globally and locally quadratically convergent algorithm for nonlinear programs, complementarity and variational inequality problems. Mathematical Programming, 1991,51:101-131.
[14]J. S.Pang, S. A. Gabriel, A robust algorithm for the nonlinear complementarity proble, Mathematical Pro-gramming,1993,60:295-337.
[15]H. Jiang and L. Qi, A new nonsmooth equations approach to nonlinear complementarity problems, SIAM Journal on Control and Optimization,1997,35:178-193.
[16]T. D. Luca, F. Facchinei, and C. kanzow, A semismooth equation aproach to the solution of nonlinear complementarity problems, Mathematical Programming,1996,75:407-439.
[17]N. Yamashita and M. Fukushima, Modified Newton methods for solving a semismooth reformulation of monotone complementarity problems, Mathematical Programming,1997,76:469-491.
[18]B. Chen, X. Chen, C. Kanzow, A penalized Fischer-Burmeister NCP-function:Theoretical investigation and numerical results, Mathematical Programming,2000,88:211-216.
[19]T. Kouichi, M. Miyamoto, A globally convergent smoothing Newton method for nonlinear equations and its application to complementarity problems, Computational Optimization and Applications,2002,22(1): 81-101.
[20]J. Houyuan, Global convergence analysis of the generalized Newton and Gauss-Newton methods of the Fischer-Burmeister equation for the complementarity problem, Mathematics of Operations Research,1999, 24(3):529-543.
[21]Q. Houduo, L. LiZhi, A Smoothing Newton method for general nonlinear complementarity problems, Com-putational Optimization and Applications,2000,17(2-3):231-253.
[22]D. L. Mangasarian, V. Solodov, Nonlinear complementarity as unconstrained and constrainde minimization, Mathematical Programming,1993,62:277-297.
[23]N. Yamashita and M. Fukushima, On stationary points of the implicit Lagrangian for nonlinear complemen-tarity problem, Journal of Optimization Theory and Applications,1995,84:653-663.
[24]J. J. More, Global methods for nonlinear complementarity problems, MCS-P429-0494, Mathematics and Computer Division, Argonne National Laboratory, Argonne, Illinois, April 1994.
[25]A. Friedlander, J. M. Martinez and S A. Santos, Solution of the linear complementarity problems using minimization with simple bounds, Journal of Global Optimization,1995,6:1-15.
[26]C. Kanzow, Q. Houduo. A QP-free constrained Newton-type method for variational inequality problems, Mathematical Programming,1999,85:81-106.
[27]D. Sun, A new step-size skill for solving a class of nonlinear projection equations, Journal of Computational Mathematics,1995,13(4):357-368.
[28]D. Sun, Algorithms and convergence analysis for nonsmooth optimization and nonsmooth equations, Insti-tute of Applied Mathematics, Beijing, hina,1995.
[29]M. V. Solodov, P. Tseng, Modified projection-type methods for monotone variational inequalities, SIAM Journal on Control and Optimization,1996,34:1814-1830.
[30]M. Kojima, S. Mizuno, A. Yoshise, An iteration potential Reduction Algorithm for Linear Complementarity Problems, Mathematical Programming,1991,50:331-342.
[31]B. Chen, P. Harker, A non-interior-point continuation method for linear complementarity problems, SIAM Journal on Matrix Analysis and Applications,1993,14(4):1168-1190.
[32]K. Hotta, A. Yoshise, Global convergence of a class of non-interior-point algorithms using Chen-Harker-Kanzow functions for nonlinear complementarity problems, Mathematical Programming,1999,86:105-133.
[33]J. Burke, S. Xu, The global linear convergence of a noninterior path-following algorithm for linear comple-mentarity problems, Mathematics of Operations Research,1998,23(3):719-734.
[34]L. Qi, D. Sun, Improving the convergence of non-interior point algorithms for nonlinear complementarity problems, Mathematics of Computation,2000,69(229):283-304.
[35]S. Xu, V. J. Burke, A polynomial time interior-point path-following algorithm for LCP based on Chen-Harker-Kanzow smoothing techniques, Mathematical Programming,1999,86(1):91-103.
[36]G. W. Reddien, On Newton's method for singular problems, SIAM Journal Numerische Analysis,1978, 15(5):993-996.
[37]G. H. Golub, C. F. Van Loan, Matrix Computations, third edn. The Johns Hopkins University Press, Balti-more,1996.
[38]A. Griewank, Starlike domains of convergence for Newton's method at singularities, Numerische Mathe-matic,1980,35(1):95-111.
[39]J. M. Ortega, W. C. Reinboldt, Iterative solution of nonlinear equations in several variables, Academic Press, New York(1970).
[40]C. Oberlin, S. J. Wright, An accelerated Newton method for equations with semismooth Jacobians and nonlinear complementarity problems:Extended version, Optimization technical report, Computer Sciences Department, University of Wisconsin-Madison (2006, Revised January 2007).
[41]陈公宁,矩阵理论与应用,高等教育出版社,北京,1990.
[42]N. H. Xiu, J. Z. Zhang, Some recent advances in projection-type methods for variational inequalities, Journal of Computational and Applied Mathematics,2003,152:559-585.
[43]乌力吉,博士学位论文,内蒙古,内蒙古大学,2004.
[44]R. Mifflin, Semismooth and semiconvex functions in constrained optimization,SIAM Journal on Control and Optimization,1977,15:959-972[English Translation:Matecon,1977,1335-49].
[45]L. QI, J. SUN, A nonsmooth version of Newton's method, Mathematical Programming,1993,58:353-368.
[46]T. Deluca, F. Facchinei, C. Kanzow, A theoretical and numerical comparison of some semismooth algorithms for complementarity problems, Computatical Optimization and Applications,2000,16:173-205.
[47]A. Fischer, A special Newton-type optimization method, Optimization,1992,24:269-284.
[48]P. K. Subramanian, Gauss-Newton method for the complementarity problem, Journal of Optimization The-ory and Applications,1993,77:467-482.
[49]J. S. Pang, Newton's method for B-differentiable equation, Mathematics of Operations Research,1990,15: 311-341.
[50]陈国庆,变分不等式与互补问题,内蒙古大学内部讲义.
[51]L. Qi, J. Sun, A nonsmooth version of Newton's method, Mathematical Programming,1993,58:353-367.
[52]席少霖,顾明,奇异点处的拟Newton方法,计算数学,24(3),1988.
[53]任玉芳,非线性互补问题的光滑方程组解法,硕士学位论文,内蒙古,内蒙古大学,2009.
[54]B. Chenand X. Chen, A global and local superlinear continuzation-smoothing method for Po and R0NCP or monotone NCP, SIAM Journal Optimization,1999,9:624-645.
[55]乌彩英,互补问题与半定规划算法研究,博士学位论文,内蒙古,内蒙古大学,2009.
[2]J. M. Peng, Unconstrained optimization methods for nonlinear complementarity problem, Journal of Com-putational Mathematics,1995,13(3):259-266.
[3]修乃华,高自友,互补问题算法的新进展,数学进展,1999,28(3)：193-208.
[4]X. Naihua, Tangent projection equation and general variational inequalities, Journal of Mathematical Anal-ysis and Applications,2001,258:755-762.
[5]A. Fischer, A special Newton-Type optimization method, Optimization,1992,24:269-284.
[6]O. L. Mangasarian, Equivalence of the complementarity problems to a system of nonlinear equations, SIAM Journal on Applied Mathematics,1976,31:89-92.
[7]L. T. Watson, Solving the nonlinear complementarity problem by a homotopy method, SIAM Journal of Control and Optimization,1979,17:36-46.
[8]P. K. Subramanian, Gauss-Newton methods for the complementarity problem, Journal of Optimization The-ory and Applications,1993,77:467-482.
[9]C. Kanzow, Global convergence of some iterative methods for linear complementarity problems, SIAM Journal on Optimization,1996,6:326-341.
[10]S. M. Robinson, Strongly regular generalized equations, Mathematics of Operations Research,1980,5: 43-62.
[11]T. Luca, F. Facchinei, C. Kanzow, Theoretical and numerical comparison of some semismooth algorithms for complementarity problems, Computational Optimization and Applications,2000,16(2):173-205.
[12]J. Houyuan, Smoothed Fischer-Burmeister equation method for the complementarity problem, Technical Report, Department of Mathematics, The University of Melbourne, Parkvile, Victoria, Australia, June,1997.
[13]J. S. Pang, A B-differentiable equation based globally and locally quadratically convergent algorithm for nonlinear programs, complementarity and variational inequality problems. Mathematical Programming, 1991,51:101-131.
[14]J. S.Pang, S. A. Gabriel, A robust algorithm for the nonlinear complementarity proble, Mathematical Pro-gramming,1993,60:295-337.
[15]H. Jiang and L. Qi, A new nonsmooth equations approach to nonlinear complementarity problems, SIAM Journal on Control and Optimization,1997,35:178-193.
[16]T. D. Luca, F. Facchinei, and C. kanzow, A semismooth equation aproach to the solution of nonlinear complementarity problems, Mathematical Programming,1996,75:407-439.
[17]N. Yamashita and M. Fukushima, Modified Newton methods for solving a semismooth reformulation of monotone complementarity problems, Mathematical Programming,1997,76:469-491.
[18]B. Chen, X. Chen, C. Kanzow, A penalized Fischer-Burmeister NCP-function:Theoretical investigation and numerical results, Mathematical Programming,2000,88:211-216.
[19]T. Kouichi, M. Miyamoto, A globally convergent smoothing Newton method for nonlinear equations and its application to complementarity problems, Computational Optimization and Applications,2002,22(1): 81-101.
[20]J. Houyuan, Global convergence analysis of the generalized Newton and Gauss-Newton methods of the Fischer-Burmeister equation for the complementarity problem, Mathematics of Operations Research,1999, 24(3):529-543.
[21]Q. Houduo, L. LiZhi, A Smoothing Newton method for general nonlinear complementarity problems, Com-putational Optimization and Applications,2000,17(2-3):231-253.
[22]D. L. Mangasarian, V. Solodov, Nonlinear complementarity as unconstrained and constrainde minimization, Mathematical Programming,1993,62:277-297.
[23]N. Yamashita and M. Fukushima, On stationary points of the implicit Lagrangian for nonlinear complemen-tarity problem, Journal of Optimization Theory and Applications,1995,84:653-663.
[24]J. J. More, Global methods for nonlinear complementarity problems, MCS-P429-0494, Mathematics and Computer Division, Argonne National Laboratory, Argonne, Illinois, April 1994.
[25]A. Friedlander, J. M. Martinez and S A. Santos, Solution of the linear complementarity problems using minimization with simple bounds, Journal of Global Optimization,1995,6:1-15.
[26]C. Kanzow, Q. Houduo. A QP-free constrained Newton-type method for variational inequality problems, Mathematical Programming,1999,85:81-106.
[27]D. Sun, A new step-size skill for solving a class of nonlinear projection equations, Journal of Computational Mathematics,1995,13(4):357-368.
[28]D. Sun, Algorithms and convergence analysis for nonsmooth optimization and nonsmooth equations, Insti-tute of Applied Mathematics, Beijing, hina,1995.
[29]M. V. Solodov, P. Tseng, Modified projection-type methods for monotone variational inequalities, SIAM Journal on Control and Optimization,1996,34:1814-1830.
[30]M. Kojima, S. Mizuno, A. Yoshise, An iteration potential Reduction Algorithm for Linear Complementarity Problems, Mathematical Programming,1991,50:331-342.
[31]B. Chen, P. Harker, A non-interior-point continuation method for linear complementarity problems, SIAM Journal on Matrix Analysis and Applications,1993,14(4):1168-1190.
[32]K. Hotta, A. Yoshise, Global convergence of a class of non-interior-point algorithms using Chen-Harker-Kanzow functions for nonlinear complementarity problems, Mathematical Programming,1999,86:105-133.
[33]J. Burke, S. Xu, The global linear convergence of a noninterior path-following algorithm for linear comple-mentarity problems, Mathematics of Operations Research,1998,23(3):719-734.
[34]L. Qi, D. Sun, Improving the convergence of non-interior point algorithms for nonlinear complementarity problems, Mathematics of Computation,2000,69(229):283-304.
[35]S. Xu, V. J. Burke, A polynomial time interior-point path-following algorithm for LCP based on Chen-Harker-Kanzow smoothing techniques, Mathematical Programming,1999,86(1):91-103.
[36]G. W. Reddien, On Newton's method for singular problems, SIAM Journal Numerische Analysis,1978, 15(5):993-996.
[37]G. H. Golub, C. F. Van Loan, Matrix Computations, third edn. The Johns Hopkins University Press, Balti-more,1996.
[38]A. Griewank, Starlike domains of convergence for Newton's method at singularities, Numerische Mathe-matic,1980,35(1):95-111.
[39]J. M. Ortega, W. C. Reinboldt, Iterative solution of nonlinear equations in several variables, Academic Press, New York(1970).
[40]C. Oberlin, S. J. Wright, An accelerated Newton method for equations with semismooth Jacobians and nonlinear complementarity problems:Extended version, Optimization technical report, Computer Sciences Department, University of Wisconsin-Madison (2006, Revised January 2007).
[41]陈公宁,矩阵理论与应用,高等教育出版社,北京,1990.
[42]N. H. Xiu, J. Z. Zhang, Some recent advances in projection-type methods for variational inequalities, Journal of Computational and Applied Mathematics,2003,152:559-585.
[43]乌力吉,博士学位论文,内蒙古,内蒙古大学,2004.
[44]R. Mifflin, Semismooth and semiconvex functions in constrained optimization,SIAM Journal on Control and Optimization,1977,15:959-972[English Translation:Matecon,1977,1335-49].
[45]L. QI, J. SUN, A nonsmooth version of Newton's method, Mathematical Programming,1993,58:353-368.
[46]T. Deluca, F. Facchinei, C. Kanzow, A theoretical and numerical comparison of some semismooth algorithms for complementarity problems, Computatical Optimization and Applications,2000,16:173-205.
[47]A. Fischer, A special Newton-type optimization method, Optimization,1992,24:269-284.
[48]P. K. Subramanian, Gauss-Newton method for the complementarity problem, Journal of Optimization The-ory and Applications,1993,77:467-482.
[49]J. S. Pang, Newton's method for B-differentiable equation, Mathematics of Operations Research,1990,15: 311-341.
[50]陈国庆,变分不等式与互补问题,内蒙古大学内部讲义.
[51]L. Qi, J. Sun, A nonsmooth version of Newton's method, Mathematical Programming,1993,58:353-367.
[52]席少霖,顾明,奇异点处的拟Newton方法,计算数学,24(3),1988.
[53]任玉芳,非线性互补问题的光滑方程组解法,硕士学位论文,内蒙古,内蒙古大学,2009.
[54]B. Chenand X. Chen, A global and local superlinear continuzation-smoothing method for Po and R0NCP or monotone NCP, SIAM Journal Optimization,1999,9:624-645.
[55]乌彩英,互补问题与半定规划算法研究,博士学位论文,内蒙古,内蒙古大学,2009.