互补问题与非线性系统的算法研究
|
摘要
设计有效的算法是数值优化中的重要研究课题.本论文研究了非线性互补问题和非线性不等式系统这两类有着广泛应用背景的问题,主要从算法的设计,收敛性分析,数值效果等方面进行研究.
主要内容概括总结如下：
1.光滑互补函数在互补问题的光滑算法重构理论中起着重要作用.本章首先提出了一族新的光滑互补函数,该光滑函数包含了众多流行的光滑函数作为特例.这族光滑函数具有一些良好的性质,即：保证了与之相关的光滑路径的存在性和连续性,光滑算法所产生的迭代序列的有界性以及Jacobian相容性.利用这族光滑函数,讨论了一个光滑算法,实验结果表明新提出的光滑函数是有价值的.
2.基于Fischer-Burmeister光滑函数,提出了求解P0非线性互补问题的一种正则化非精确非单调光滑牛顿算法.在较弱的条件下,我们证明了水平集是有界的以及算法具有全局收敛性和局部二次收敛性.数值实验结果也表明了算法的有效性,尤其在求解大规模的非线性互补问题时优势更明显.
3.通过将信赖域技巧与线性搜索技巧相结合,提出了求解一般的(即：不要求是P0函数)非线性互补问题的一种新的半光滑Levenberg-Marquardt算法.这使得该算法可以去掉F至少是一个P0函数的假设.在适当的条件下,得到了算法的全局收敛性和局部超线性收敛性.数值实验结果表明该算法比一些现存方法更有效.
4.对于互补问题的一些无导数下降算法,现存的通常都是基于单调线搜索进行分析的,而实际计算中都用了非单调线搜索,缺乏相应的理论分析.本章基于p范数,引入了一种广义的惩罚Fischer-Burmeister价值函数并证明了其具有很多好的性质.利用这个新价值函数,提出了具有非单调线搜索的无导数算法并证明了其全局收敛性与局部收敛性.使用测试题库MCPLIB进行了数值实验,实验结果表明：提出的算法是有效的以及新提出的价值函数是有意义的.
5.利用加函数将非线性不等式系统转化为一非光滑的非线性方程组,再通过加函数的CHKS光滑函数,建立起非光滑方程组的近似光滑方程组.而后,提出了一个正则光滑牛顿算法来求解近似光滑方程组,从而得到原非线性不等式系统的解.数值实验结果表明了提出的算法是有效的.
The design of an efficient algorithm is one of the most important research areas in numerical optimization community. This dissertation considers two class of wide appli-cation background problems, such as nonlinear complementarity problems and system of nonlinear inequalities, and mainly concentrates on the design of the algorithm, con-vergence analysis, numerical implementation. The main contributions are listed as follows:
1. Smoothing functions play a key role in reformulation for the smoothing method. Firstly, a new smoothing function is proposed, which include many smoothing functions as special cases. The new smoothing functions possess a system of favorite properties, such as, the existence and continuity of a smooth path, boundedness of the iteration sequence and Jacobian consistency. Based on the new smoothing functions, we inves-tigate a smoothing Newton algorithm for the NCP, numerical results demonstrate that the new smoothing function introduced in this chapter is worth investigating.
2. Based on the Fischer-Burmeister smoothing function, we propose a nonmonotone inexact regularized smoothing Newton method for nonlinear complementarity problems with a P0-function. Under the weaker condition, the boundedness of level set, global convergence and locally super linear convergence of the algorithm are established. Nu-merical results indicate that the newly proposed algorithm is effective, especially for the large scale nonlinear complementarity problems.
3. By combining the trust region techniques and line searches, we propose a new semismooth Levenberg-Marquardt method for solving general (not necessarily P0) non-linear complementarity problems. Under suitable assumptions, global convergence and locally super linear convergence of the algorithm are established. Numerical results demonstrate that the proposed method is more efficient than some existing algorithms.
4. Since the existing derivative-free descent algorithms for complementarity prob-lems are based on monotone line search, while their numerical implementations are based on nonmonotone line search, there lack theoretical analysis. Based on p-norm, we introduce a new generalized penalized Fischer-Burmeister merit function, and show that the function possesses a system of favorite properties. We propose a derivative-free algorithm for nonlinear comple-mentarity problems with a nonmonotone line search. The global convergence and locally convergence of the algorithm are established. Nu-merical results indicate that the newly proposed algorithm is effective and the new merit function is meaningful.
5. The system of nonlinear inequalities is reformulated as a nonsmooth equation by using a plus function. By using the Chen-Harker-Kanzow-Smale smoothing function of plus function, the nonsmooth equation is approximated by a family of parameterized smooth equations. A regularized smoothing Newton algorithm is proposed to solve the smooth equations and the solution of the system of nonlinear inequalities is founded. Numerical results indicate that the proposed algorithm is efficient.
主要内容概括总结如下：
1.光滑互补函数在互补问题的光滑算法重构理论中起着重要作用.本章首先提出了一族新的光滑互补函数,该光滑函数包含了众多流行的光滑函数作为特例.这族光滑函数具有一些良好的性质,即：保证了与之相关的光滑路径的存在性和连续性,光滑算法所产生的迭代序列的有界性以及Jacobian相容性.利用这族光滑函数,讨论了一个光滑算法,实验结果表明新提出的光滑函数是有价值的.
2.基于Fischer-Burmeister光滑函数,提出了求解P0非线性互补问题的一种正则化非精确非单调光滑牛顿算法.在较弱的条件下,我们证明了水平集是有界的以及算法具有全局收敛性和局部二次收敛性.数值实验结果也表明了算法的有效性,尤其在求解大规模的非线性互补问题时优势更明显.
3.通过将信赖域技巧与线性搜索技巧相结合,提出了求解一般的(即：不要求是P0函数)非线性互补问题的一种新的半光滑Levenberg-Marquardt算法.这使得该算法可以去掉F至少是一个P0函数的假设.在适当的条件下,得到了算法的全局收敛性和局部超线性收敛性.数值实验结果表明该算法比一些现存方法更有效.
4.对于互补问题的一些无导数下降算法,现存的通常都是基于单调线搜索进行分析的,而实际计算中都用了非单调线搜索,缺乏相应的理论分析.本章基于p范数,引入了一种广义的惩罚Fischer-Burmeister价值函数并证明了其具有很多好的性质.利用这个新价值函数,提出了具有非单调线搜索的无导数算法并证明了其全局收敛性与局部收敛性.使用测试题库MCPLIB进行了数值实验,实验结果表明：提出的算法是有效的以及新提出的价值函数是有意义的.
5.利用加函数将非线性不等式系统转化为一非光滑的非线性方程组,再通过加函数的CHKS光滑函数,建立起非光滑方程组的近似光滑方程组.而后,提出了一个正则光滑牛顿算法来求解近似光滑方程组,从而得到原非线性不等式系统的解.数值实验结果表明了提出的算法是有效的.
The design of an efficient algorithm is one of the most important research areas in numerical optimization community. This dissertation considers two class of wide appli-cation background problems, such as nonlinear complementarity problems and system of nonlinear inequalities, and mainly concentrates on the design of the algorithm, con-vergence analysis, numerical implementation. The main contributions are listed as follows:
1. Smoothing functions play a key role in reformulation for the smoothing method. Firstly, a new smoothing function is proposed, which include many smoothing functions as special cases. The new smoothing functions possess a system of favorite properties, such as, the existence and continuity of a smooth path, boundedness of the iteration sequence and Jacobian consistency. Based on the new smoothing functions, we inves-tigate a smoothing Newton algorithm for the NCP, numerical results demonstrate that the new smoothing function introduced in this chapter is worth investigating.
2. Based on the Fischer-Burmeister smoothing function, we propose a nonmonotone inexact regularized smoothing Newton method for nonlinear complementarity problems with a P0-function. Under the weaker condition, the boundedness of level set, global convergence and locally super linear convergence of the algorithm are established. Nu-merical results indicate that the newly proposed algorithm is effective, especially for the large scale nonlinear complementarity problems.
3. By combining the trust region techniques and line searches, we propose a new semismooth Levenberg-Marquardt method for solving general (not necessarily P0) non-linear complementarity problems. Under suitable assumptions, global convergence and locally super linear convergence of the algorithm are established. Numerical results demonstrate that the proposed method is more efficient than some existing algorithms.
4. Since the existing derivative-free descent algorithms for complementarity prob-lems are based on monotone line search, while their numerical implementations are based on nonmonotone line search, there lack theoretical analysis. Based on p-norm, we introduce a new generalized penalized Fischer-Burmeister merit function, and show that the function possesses a system of favorite properties. We propose a derivative-free algorithm for nonlinear comple-mentarity problems with a nonmonotone line search. The global convergence and locally convergence of the algorithm are established. Nu-merical results indicate that the newly proposed algorithm is effective and the new merit function is meaningful.
5. The system of nonlinear inequalities is reformulated as a nonsmooth equation by using a plus function. By using the Chen-Harker-Kanzow-Smale smoothing function of plus function, the nonsmooth equation is approximated by a family of parameterized smooth equations. A regularized smoothing Newton algorithm is proposed to solve the smooth equations and the solution of the system of nonlinear inequalities is founded. Numerical results indicate that the proposed algorithm is efficient.
引文
[1]M.C.Ferris, J.S.Pang, Engineering and economic applications of complementarity problems, SIAM Review 1997,39,669-713.
[2]P.T.Harker, J.S.Pang, Finite dimensional variational inequality and nonlinear complemen-tarity problem:A survey of theory, algorithms and applications, Math. Program.1990,48, 161-220.
[3]R.W.Cottle, J.S.Pang, R.E.Stone, The linear complementarity problem, Academic Press, New York,1992.
[4]F.Facchinei, J.S.Pang, Finite-dimensional variational inequalities and complementarity prob-lems, Springer-Verlag, New York, Berlin, Heidelberg,2003.
[5]韩继业,修乃华,戚厚铎,非线性互补理论与算法,上海技术科学出版社,上海,2003.
[6]B.Chen, X.Chen, A global and local superlinear continuation-smoothing method for Po and R0 NCP or monotone NCP, SIAM J. Optim.1999,9,624-645.
[7]C.Geiger, C.Kanzow, Theorie und Numerik restringierter Optimierungsaufgaben, Springer-Verlag,2002.
[8]J.J.More, W.C.Rheinboldt, On P-and S-functions and related classes of n-dimensional non-linear mappings, Lin. Algebra Appl.1973,6,45-68.
[9]F.H.Clark, Optimization and Nonsmooth Analysis, New York:John Wiley Sons,1983,224-256.
[10]L. Qi, C-differentiability, C-differential opeators and generalized Newton methods. Technical Report, The University of New South Wales, Sydney, Australia,1996.
[11]R. Mifflin, Semismooth and semiconvex functions in constrained optimization, SIAM J. Con-trol Optim.1977,15,957-972.
[12]L.Qi, J.Sun, A nonsmooth version of Newton's method, Math. Program.1993,58,353-367.
[13]A.Fisher, Solution of monotone complementarity problems with locally Lipschitzian function, Math. Program.1997,76,513-532.
[14]A.Fisher, A special Newton-type optimization method, Optimization 1992,24,269-284.
[15]J.S.Pang, L.Qi, Nonsmooth equation:Motavation and algorithms, SIAM J. Optim.1993,3, 443-465.
[16]L.Qi, H.Jiang, Semismooth KKT equations and convergence analysis of Newton and quasi-Newton methods for solving these equations, Math. Op. Res.1997,22,301-325.
[17]F.Facchinei, J.Soares, A new merit function for nonlinear complementarity problems and a related algorithm, SIAM J. Optimiz.1997,225-247.
[18]L.Qi, Convergence analysis of some algorithm for nonsmooth equations, Math. Oper. Res. 1993,18,227-244.
[19]J. Nocedal, S. J. Wright, Numerical Optimization, Springer-Verlag, New York,1999.
[20]M.Kajima, S.Mizuno, A.Yoshise, A polynomial-time algorithm for a class of linear comple-mentarity problems, Math. Program.1989,44,1-26.
[21]J.Ji, F.Potra, S.Huang, A predictor-corrector method for linear complementarity problems with polynomial complexity and superlinear convergence, Technical Report 18, Department of Mathematics, University of Iowa, Iowa City, IC,1991.
[22]J.Miao, A quadratically convergent O((k+1)(?)L)-iteration algorithm for the P*(k)-matrix linear complementarity problem, Math. Program.1995,69,355-368.
[23]S.Xu, J.V.Burke, A polynomial time interior-point path-following algorithm for LCP based on Chen-Harke-Kanzow smoothing techniques, Math. Program.1999,86,91-103.
[24]Y.B.Zhao, D.Li, A new path-following algorithm for nonlinear P* complementarity problems, Comput. Optim. Appl. 2005,34,183-214.
[25]A.Fischer, A special Newton-type optimization method, Optimization,1992,24,269-284.
[26]D. Sun, L. Qi, On NCP-functions, Comput. Optim. Appl.1999,13,201-220.
[27]A.Fischer, H.Jang, Merit functions for complementarity and related problems:A survey, Comput. Optim. Appl.2000,17,159-182.
[28]J.S.Chen, S.H.Pan, A family of NCP functions and a descent method for the nonlinear complementarity problem, Comput. Optim. Appl.2008,40,389-404.
[29]J.S.Pang, S.A.Gabriel, NE/SQP:A robust algorithm for the nonlinear complementarity prob-lem, Math. Program.1993,60 295-337.
[30]P.T.Harker, B.Xiao, Newton's method for the nonlinear complementarity problem:A B-differentiable equation approach, Math. Program.1990,48 339-357.
[31]A.Fischer, On the local superlinear convergence of a Newton-type method for LCP under weak conditions, Optimization Method and Software 1995,6,83-107.
[32]H.Jiang, L.Qi, A New Nonsmooth Eqations Approach to Nonlinear Complementarity Prob-lems, SIAM J. Control Optim.1997,35,178-193.
[33]T.D. Luca, F. Facchinei, C. Kanzow, A semismooth equation approach to the solution of nonlinear complementarity problems, Math. Program.1996,75,407-439.
[34]N.Yamashita, M.Fukushima, Modified Newton methods for solving a semismooth reformula-tion of monotone complementarity problems, Math. Program.1997,76,469-491.
[35]T.D. Luca, F. Facchinei, C. Kanzow, A theoretical and numerical comparison of some semis-mooth algorithm for complementarity problems, Comput. Optim. Appl.2000,16,173-205.
[36]D.F.Sun, R.S.Womersley, H.D.Qi, A feasible semismooth asymptotically Newton method for mixed complementarity problems, Math. Program.2002,94.167-187.
[37]J.S.Chen, S.H.Pan, A regularization semismooth Newton method based on the generalized Fischer-Burmeister function for P0-NCPs, J. Comput. Appl. Math.2008,220,464-479.
[38]X.Chen, L.Qi, D.Sun, Global and superlinear convergence of the smoothing Newton method and its application to general box constriained variational inequalities, Math. Comput.1999, 222,519-540.
[39]C.Kanzow, H.Pieper, Jacobian smoothing methods for nonlinear complementarity problems, SIAM J. Optim.1999,9,342-373.
[40]H.D. Qi, L.Z. Liao A smoothing Newton method for general nonlinear complementarity problems Comput. Optim. Appl.2000,17,231-253.
[41]C.F.Ma, A new smoothing quasi-Newton method for nonlinear complementarity problems, Appl. Math. Comput.2005,171,807-823.
[42]C.F.Ma, A smoothing Broyden-like method for the mixed complementarity problems, Math. Comput. Model.2005,41,523-538.
[43]L.Qi, D.Sun, G.Zhou, A new look at smoothing Newton methods for nonlinear complemen-tarity problems and box constrained variational inequalities, Math. Program.2000,87,1-35.
[44]L. Zhang, J. Han, Z.H. Huang, Superlinear/quadratic one-step smoothing Newton method for P0-NCP, Acta Math Sinica 2005,26,117-128.
[45]Z.H. Huang, Locating a maximally complementarity solution of the monotone NCP by using non-interior-point smoothing algorithms, Math. Meth. Oper. Res.2005,61,41-55.
[46]B.Chen, P.T.Harker, A non-interior continuation algorithm for linear complementarity prob-lems, SIAM J. Matrix Anal. Appl.1993,14,1168-1190.
[47]J.Burke, S.Xu, The global linear convergence of a non-interior path-following algorithm for linear complementarity problems, Math. Oper. Res.1998,23,719-734.
[48]B.Chen, N.Xiu, A global linear and local quadratic non-interior continuation method for nonlinear complementarity problems based on Chen-Mangasarian smoothing function, SIAM J. Optim.1999,9,605-623.
[49]Z.H.Huang, J.Han, Z.Chen, Predictor-corrector smoothing newton method, based on a new smoothing function, for solving the nonlinear complementarity problem with a P0 function, J. Optim. Theory Appl.2003,117,39-68.
[50]Z.H.Huang, J.Sun, A non-interior continuation algorithm for the P0 or P* LCP with strong global and local convergence properties, Appl. Math. Optim.2005.52,237-262.
[51]X.Z.Zhang, H.F.Jiang. Y.J.Wang, A smoothing Newton-type method for generalized nonlin-ear complementarity problem, J. Com.put. Appl. Math.2008,212,75-85.
[52]H.Jiang, Unconstrained minimization approaches to nonlinear complementarity problems, J. Global Optim.1996,9,169-181.
[53]C.Geiger, C.Kanzow, On the resolution of monotone complementarity problems, Comput. Optim. Appli.1996,5,155-173.
[54]S.L.Hu, Z.H.Hang, J.S.Chen, Properties of a family of generalized NCP-functions and a derivative free algorithm for complementarity problems, J. Comput. Appl. Math.2009.230, 69-82.
[55]J.S.Chen, H.T.Gao, S.H.Pan, An R-linearly convergent derivative-free algorithm for nonlinear complementarity problems based on the generalized Fischer-Burmeister merit function, J. Comput. Appl. Math.2009,232,455-471.
[56]K.Yamada, N.Yamashita, M.Fukushima, A new derivative-free descent method for the non-linear complementarity problems, G.D. Pillo, F. Giannessi (Eds.), Nonlinear Optimization and Related Topics, Kluwer Academic Publishers, Netherlands,2000,463-487.
[57]J.W. Daniel, Newton's method for nonlinear inequalities, Numer. Math.1973,21,381-387.
[58]D.Q. Mayne, E. Polak, A.J. Heunis, Solving nonlinear inequalities in a finite number of iterations, J. Optim. Theory Appl.1981,33,207-221.
[59]M. Sahba, On the solution of nonlinear inequalities in a finite number of iterations, Numer. Math.1985,46,229-236.
[60]黄正海,变分不等式与互补问题的理论与算法以及可能不相容非线性不等式系统的求解,博士后论文,中国科学院应用数学研究所,2004.
[61]C.F.Ma, A globally convergent Levenberg-Marquardt method for the least l2-norm solution of nonlinear inequalities, Applied Mathematics and Computation 2008,206,133-140.
[62]何郁波,马昌凤,非线性不等式组的信赖域算法,工程数学学报2008,,25,224-230.
[63]Z.H. Huang, Y. Zhang, W. Wu, A smoothing-type algorithm for solving system of inequalities, J. Comput. Appl. Math.2008,220,355-363.
[64]J.E.Dennis, R.B.Schnabel, Numerical methods for unconstrained optimization and nonlinear equations, Prentice-Hall, Englewood Cliffs, NJ.1983.
[65]B.N.Pshenichnyi, Newton's method for the systems of equalities and inequalities, Math. Acad. Sci. USSR.,1970,8.827-830.
[66]J.Burke, S.P.Han, A Guass-Newton approach to solving generalized inequalities, Math. Oper. Res.1986,11,632-643.
[67]J.E.Dennis, M.M.El-Alem, K.Williamson, A trust region approach to nonlinear systems of equalities and inequalities, SIAM J. Optim.1999,9.291-315.
[68]童晓娇,周叔子.非线性等式与不等式问题的信赖域算法,数值计算与计算机应用2001,1,53-62.
[69]王长钰,宇振盛,求解非线性系统的有效集信赖域方法,数学物理学报2006,26,223-232.
[70]P.M.Pardalos, Y.Y.Ye, C.G.Han, J.A.Kaliski, Solutiong of P0 matrix linear complementarity problems using reduction algorithm, SI AM J. Matrix Anal. Appl.1993,14 1048-1060.
[71]C.F.Ma, X.H.Chen, The convergence of a one-step smoothing Newton method for P0-NCP based on a new smoothing NCP-function, J. Comput. Appl. Math.2008,216,1-13.
[72]Z.H.Huang, J. Han, D. Xu, L. Zhang, The non-linear continuation methods for solving the Po-functions nonlinear complementarity problem, Sci. China ser. A 2001,44,1107-1114.
[73]H.D.Yu, D.G.Pu, Smoothing Newton method for NCP with the identification of degenerate indices, J. Comput. Appl. Math.2010,234,3424-3435.
[74]J.S.Chen, Z.H. Huang, C.Y.She, A new class of penalized NCP-functions and its properties, Comput. Optim. Appl. DOI 10.1007/s10589-009-9315-9.
[75]S.L.Hu, Z.H.Huang, J.S.Chen, Properties of a family of generalized NCP-functions and a derivative free algorithm for complementarity problems, J. Comput. Appl. Math.2009,230, 69-82.
[76]M.Kojima, N.Megiddo, T.Noma, Homotopy Continuation Methods for Nonlinear Comple-mentarity Problems, Math. Oper. Res.1991,16,754-774.
[77]L.P.Zhang, S.Y.Wu, T.R.Gao, Improved smoothing Newton methods for P0 nonlinear com-plementarity problems, Appl. Math. Comput.2009,215,324-332.
[78]C.Kanzow, Some equation-based methods for the nonlinear complementarity problem, Op-tim. Meth. Soft.1994,3,327-340.
[79]X.Liu, W.Wu, Coerciveness of some merit functions over symmetric cones, J. Ind. Manag. Optim.2009,5,603-613.
[80]M.S.,Gowa, M.A.,Tawhid, Existence and Limiting Behavior of Trajectories Associated with P0-Equations, Comput. Optim. Appl.1999,12,229-251.
[81]M.Kojima, N.Megiddo, T.Noma, A.Yoshise, A Unified Approach to Interior-Point Algorithms for Linear Complementarity Problems, Lecture Notes in Computer Science, Springer Verlag, Berlin, Germany,538 (1991).
[82]L. Fang, A new one-step smoothing Newton method for nonlinear complementarity prob-lem with P0-function, Appl. Math. Comput. 2010.216,1087-1095.
[83]F.Facchinei, C.Kanzow, Beyond monotonicity in regularization methods for non-linear com-plementarity problems. SIAM J. Control Optim.1999,37,1150-1161.
[84]O.L.Mangasarian, M.V.Solodov, Nonlinear complementarity as unconstrained and con-strained minimization, Math. Program.1993,62,277-297.
[85]S.P.Dirkse, M.C.Ferris, MCPLIB:A collection of nonlinear mixed complementarity prob-lems, Optim. Meth. Soft.1995.5,319-345.
[86]C.Oberlin, S.J.Wright, An accelerated Newton method for equations with semismooth Jaco-bians and nonlinear complementarity problems, Math. Program.2009.117,355-386.
[87]F.A.Potra, Y.Ye, Interior-point methods for nonlinear complementarity problems, J. Optim. Theory Appl.1996,88,617-642.
[88]S.J.Wright, D.Ralph, A superlinear infeasible-interior-point algorithm for monotone comple-mentarity problems, Math. Oper. Res.1996,21,815-838.
[89]H.D. Qi, A regularized smoothing Newton method for box constrained varia.tional inequality problems with PO-functions, SIAM J. Optim.2000,10,315-330.
[90]D. Sun, A regularization Newton method for solving nonlinear complementarity problems, Appl. Math. Optim.1999,40,315-339.
[91]S.P.Rui, C.X.Xu, A smoothing inexact Newton method for nonlinear complementarity prob-lems, J. Comput. Appl. Math.2010,233,2332-2338.
[92]J.G.Zhu, H.W.Liu, X.L.Li, A regularized smoothing-type algorithm for solving a system of inequalities with a PO-function, J. Comput. Appl. Math.2010,233,2611-2619.
[93]H.C.Zhang, W.W.Hager, A nonmonotone line search technique and its application to uncon-strained optimization, SIAM J. Optim.2004,14,1043-1056.
[94]C.Kanzow, Global convergence properties of some iterative methods for linear complemen-tarity, SIAM J. Optim.1996,6,326-341.
[95]M.S. Gowda, J.J. Sznajder, Weak univalence and connectedness of inverse images of contin-uous functions, Math. Oper. Res.1999,24,255-261.
[96]G. Ravindran, M.S. Gowda, Regularization of PO-functions in box variational inequality problems, SIAM J. Optim.2001,11,748-760.
[97]Y.Fathi, Computational complexity of LCPs associated with positive definite matrices, Math. Program.1979,17,335-344.
[98]M.A.,Gomes-Ruggiero, J.M.,Martinez, S.A.,Santos, Solving nonsmooth equations by means of quasi-Newton methods with globalization, In:Recent Advances in Nonsmooth Optimiza-tion, World Scientific, Singapore.1995,121-140.
[99]C. Kanzow, H. Kleinmichel, A new class of semismooth Newton method for nonlinear com-plementarity problems, Comput. Optim. Appl.1998,11,227-251.
[100]B. Chen, X. Chen, C. Kanzow, A penalized Fischer-Burmeister NCP-function:Theoreti-cal investigation and numerical results, Institute of Applied Mathemat-ics, University of Hamburg, Hamburg, Germany, Preprint 126,1997.
[101]N. Yamashita, M. Fukushima, On the rate of convergence of the Levenberg-Marquardt method, Computing 2001,15,239-249.
[102]C. Kanzow, M. Zupke, Inexact trust region methods for nonlinear complementarity prob-lems. Reformulation:Nonsmooth, Piecewise Smooth, Semismooth and Smoothing Methods, M. Fukushima, L. Qi Eds. Kulwer Academic Press. Norwell, MA,1998,211-233.
[103]J.Y. Fan, Jianyu Pan, Convergence properties of a self-adaptive Levenberg-Marquardt algo-rithm under local error bound condition, Comput. Optim. Appl.2005,74,23-39.
[104]M.J.D. Powell, Convergence properties of a class of minimization algorithms, Nonlinear Programming 2, O.L. Mangasarian, R.R. Meyer, and S.M. Robinson Eds. Academic Press: New York,1975,1-27.
[105]D.P.Bertsekas, Constrained optimization and lagrange multiplier methods, Academic Press, New York,1982.
[106]C.Kanzow, On a semismooth least squares formulation of complementarity problem with gap reduction, Optim. Meth. Software 2004,19,507-525.
[107]L.T. Watson, Solving the nonlinear complementarity problem by a homotopy method, SIAM J. Control Optim.1979,17,36-46.
[108]W.Hock, K.Schittkowski, Test examples for nonlinear programming codes, Lecture Notes in Economics and Mathematical Systems 187, Springer-Verlag:Berlin, Germany,1981.
[109]O.L.Mangasarian, Equivalence of the complementarity problems to a system of nonlinear equations, SIAM J. Appl. Math.1976,31,89-92.
[110]X.Chen, Smoothing methods for complementarity problems and their applications:a sur-vey, J. Oper. Res. Soc. Jpn.2000,43,32-47.
[111]O.L.Mangasarian,M.V.Solodov, A linearly convergent descent method for strongly mono-tone complementarity problems, Comput. Optim. Appl.1999,14,5-16.
[112]H.Jiang, Unconstrained minimization approaches to nonlinear complementarity problems, J. Global Optim.1996,9,169-181.
[113]J.S.Chen,H.T.Gao, S.H.Pan, An R-linearly convergent derivative-free algorithm for non-linear complementarity problems based on the generalized Fischer-Burmeister merit function, J. Comput. Appl. Math.2009,232,455-471.
[114]J.S.Chen, S.H.Pan, A family of NCP-functions and a descent method for the nonlinear complementarity problem, Comput. Optim. Appl.2008,40,389-404.
[115]J.S.Chen, On some NCP-functions based on the generalized Fischer-Burmeister function, Asia-Pac. J. Oper. Res.2007,24,401-420.
[116]B.Chen, Error bounds for R0-type and monotone nonlinear complementarity problems, J. Optim. Theory Appl.2001,108,297-316.
[117]L.Grippo, F.Lampariello, S.Lucidi, A nonmonotone line search technique for Newton's method, SIAM J. Numer. Anal.1986,23.707-716.
[118]S.C.Billups, S.P.Dirkse, M.C.Soares. A comparison of algorithms for large scale mixed com-plementarity problems, Comput. Optim. Appl.1977,7,3-25.
[119]H.X. Yin, Z.H. Huang, L. Qi, The convergence of a Levenberg-Marquardt method for non-linear inequalities, Numer. Func. Anal. Optim.2008,29 687-716.
[2]P.T.Harker, J.S.Pang, Finite dimensional variational inequality and nonlinear complemen-tarity problem:A survey of theory, algorithms and applications, Math. Program.1990,48, 161-220.
[3]R.W.Cottle, J.S.Pang, R.E.Stone, The linear complementarity problem, Academic Press, New York,1992.
[4]F.Facchinei, J.S.Pang, Finite-dimensional variational inequalities and complementarity prob-lems, Springer-Verlag, New York, Berlin, Heidelberg,2003.
[5]韩继业,修乃华,戚厚铎,非线性互补理论与算法,上海技术科学出版社,上海,2003.
[6]B.Chen, X.Chen, A global and local superlinear continuation-smoothing method for Po and R0 NCP or monotone NCP, SIAM J. Optim.1999,9,624-645.
[7]C.Geiger, C.Kanzow, Theorie und Numerik restringierter Optimierungsaufgaben, Springer-Verlag,2002.
[8]J.J.More, W.C.Rheinboldt, On P-and S-functions and related classes of n-dimensional non-linear mappings, Lin. Algebra Appl.1973,6,45-68.
[9]F.H.Clark, Optimization and Nonsmooth Analysis, New York:John Wiley Sons,1983,224-256.
[10]L. Qi, C-differentiability, C-differential opeators and generalized Newton methods. Technical Report, The University of New South Wales, Sydney, Australia,1996.
[11]R. Mifflin, Semismooth and semiconvex functions in constrained optimization, SIAM J. Con-trol Optim.1977,15,957-972.
[12]L.Qi, J.Sun, A nonsmooth version of Newton's method, Math. Program.1993,58,353-367.
[13]A.Fisher, Solution of monotone complementarity problems with locally Lipschitzian function, Math. Program.1997,76,513-532.
[14]A.Fisher, A special Newton-type optimization method, Optimization 1992,24,269-284.
[15]J.S.Pang, L.Qi, Nonsmooth equation:Motavation and algorithms, SIAM J. Optim.1993,3, 443-465.
[16]L.Qi, H.Jiang, Semismooth KKT equations and convergence analysis of Newton and quasi-Newton methods for solving these equations, Math. Op. Res.1997,22,301-325.
[17]F.Facchinei, J.Soares, A new merit function for nonlinear complementarity problems and a related algorithm, SIAM J. Optimiz.1997,225-247.
[18]L.Qi, Convergence analysis of some algorithm for nonsmooth equations, Math. Oper. Res. 1993,18,227-244.
[19]J. Nocedal, S. J. Wright, Numerical Optimization, Springer-Verlag, New York,1999.
[20]M.Kajima, S.Mizuno, A.Yoshise, A polynomial-time algorithm for a class of linear comple-mentarity problems, Math. Program.1989,44,1-26.
[21]J.Ji, F.Potra, S.Huang, A predictor-corrector method for linear complementarity problems with polynomial complexity and superlinear convergence, Technical Report 18, Department of Mathematics, University of Iowa, Iowa City, IC,1991.
[22]J.Miao, A quadratically convergent O((k+1)(?)L)-iteration algorithm for the P*(k)-matrix linear complementarity problem, Math. Program.1995,69,355-368.
[23]S.Xu, J.V.Burke, A polynomial time interior-point path-following algorithm for LCP based on Chen-Harke-Kanzow smoothing techniques, Math. Program.1999,86,91-103.
[24]Y.B.Zhao, D.Li, A new path-following algorithm for nonlinear P* complementarity problems, Comput. Optim. Appl. 2005,34,183-214.
[25]A.Fischer, A special Newton-type optimization method, Optimization,1992,24,269-284.
[26]D. Sun, L. Qi, On NCP-functions, Comput. Optim. Appl.1999,13,201-220.
[27]A.Fischer, H.Jang, Merit functions for complementarity and related problems:A survey, Comput. Optim. Appl.2000,17,159-182.
[28]J.S.Chen, S.H.Pan, A family of NCP functions and a descent method for the nonlinear complementarity problem, Comput. Optim. Appl.2008,40,389-404.
[29]J.S.Pang, S.A.Gabriel, NE/SQP:A robust algorithm for the nonlinear complementarity prob-lem, Math. Program.1993,60 295-337.
[30]P.T.Harker, B.Xiao, Newton's method for the nonlinear complementarity problem:A B-differentiable equation approach, Math. Program.1990,48 339-357.
[31]A.Fischer, On the local superlinear convergence of a Newton-type method for LCP under weak conditions, Optimization Method and Software 1995,6,83-107.
[32]H.Jiang, L.Qi, A New Nonsmooth Eqations Approach to Nonlinear Complementarity Prob-lems, SIAM J. Control Optim.1997,35,178-193.
[33]T.D. Luca, F. Facchinei, C. Kanzow, A semismooth equation approach to the solution of nonlinear complementarity problems, Math. Program.1996,75,407-439.
[34]N.Yamashita, M.Fukushima, Modified Newton methods for solving a semismooth reformula-tion of monotone complementarity problems, Math. Program.1997,76,469-491.
[35]T.D. Luca, F. Facchinei, C. Kanzow, A theoretical and numerical comparison of some semis-mooth algorithm for complementarity problems, Comput. Optim. Appl.2000,16,173-205.
[36]D.F.Sun, R.S.Womersley, H.D.Qi, A feasible semismooth asymptotically Newton method for mixed complementarity problems, Math. Program.2002,94.167-187.
[37]J.S.Chen, S.H.Pan, A regularization semismooth Newton method based on the generalized Fischer-Burmeister function for P0-NCPs, J. Comput. Appl. Math.2008,220,464-479.
[38]X.Chen, L.Qi, D.Sun, Global and superlinear convergence of the smoothing Newton method and its application to general box constriained variational inequalities, Math. Comput.1999, 222,519-540.
[39]C.Kanzow, H.Pieper, Jacobian smoothing methods for nonlinear complementarity problems, SIAM J. Optim.1999,9,342-373.
[40]H.D. Qi, L.Z. Liao A smoothing Newton method for general nonlinear complementarity problems Comput. Optim. Appl.2000,17,231-253.
[41]C.F.Ma, A new smoothing quasi-Newton method for nonlinear complementarity problems, Appl. Math. Comput.2005,171,807-823.
[42]C.F.Ma, A smoothing Broyden-like method for the mixed complementarity problems, Math. Comput. Model.2005,41,523-538.
[43]L.Qi, D.Sun, G.Zhou, A new look at smoothing Newton methods for nonlinear complemen-tarity problems and box constrained variational inequalities, Math. Program.2000,87,1-35.
[44]L. Zhang, J. Han, Z.H. Huang, Superlinear/quadratic one-step smoothing Newton method for P0-NCP, Acta Math Sinica 2005,26,117-128.
[45]Z.H. Huang, Locating a maximally complementarity solution of the monotone NCP by using non-interior-point smoothing algorithms, Math. Meth. Oper. Res.2005,61,41-55.
[46]B.Chen, P.T.Harker, A non-interior continuation algorithm for linear complementarity prob-lems, SIAM J. Matrix Anal. Appl.1993,14,1168-1190.
[47]J.Burke, S.Xu, The global linear convergence of a non-interior path-following algorithm for linear complementarity problems, Math. Oper. Res.1998,23,719-734.
[48]B.Chen, N.Xiu, A global linear and local quadratic non-interior continuation method for nonlinear complementarity problems based on Chen-Mangasarian smoothing function, SIAM J. Optim.1999,9,605-623.
[49]Z.H.Huang, J.Han, Z.Chen, Predictor-corrector smoothing newton method, based on a new smoothing function, for solving the nonlinear complementarity problem with a P0 function, J. Optim. Theory Appl.2003,117,39-68.
[50]Z.H.Huang, J.Sun, A non-interior continuation algorithm for the P0 or P* LCP with strong global and local convergence properties, Appl. Math. Optim.2005.52,237-262.
[51]X.Z.Zhang, H.F.Jiang. Y.J.Wang, A smoothing Newton-type method for generalized nonlin-ear complementarity problem, J. Com.put. Appl. Math.2008,212,75-85.
[52]H.Jiang, Unconstrained minimization approaches to nonlinear complementarity problems, J. Global Optim.1996,9,169-181.
[53]C.Geiger, C.Kanzow, On the resolution of monotone complementarity problems, Comput. Optim. Appli.1996,5,155-173.
[54]S.L.Hu, Z.H.Hang, J.S.Chen, Properties of a family of generalized NCP-functions and a derivative free algorithm for complementarity problems, J. Comput. Appl. Math.2009.230, 69-82.
[55]J.S.Chen, H.T.Gao, S.H.Pan, An R-linearly convergent derivative-free algorithm for nonlinear complementarity problems based on the generalized Fischer-Burmeister merit function, J. Comput. Appl. Math.2009,232,455-471.
[56]K.Yamada, N.Yamashita, M.Fukushima, A new derivative-free descent method for the non-linear complementarity problems, G.D. Pillo, F. Giannessi (Eds.), Nonlinear Optimization and Related Topics, Kluwer Academic Publishers, Netherlands,2000,463-487.
[57]J.W. Daniel, Newton's method for nonlinear inequalities, Numer. Math.1973,21,381-387.
[58]D.Q. Mayne, E. Polak, A.J. Heunis, Solving nonlinear inequalities in a finite number of iterations, J. Optim. Theory Appl.1981,33,207-221.
[59]M. Sahba, On the solution of nonlinear inequalities in a finite number of iterations, Numer. Math.1985,46,229-236.
[60]黄正海,变分不等式与互补问题的理论与算法以及可能不相容非线性不等式系统的求解,博士后论文,中国科学院应用数学研究所,2004.
[61]C.F.Ma, A globally convergent Levenberg-Marquardt method for the least l2-norm solution of nonlinear inequalities, Applied Mathematics and Computation 2008,206,133-140.
[62]何郁波,马昌凤,非线性不等式组的信赖域算法,工程数学学报2008,,25,224-230.
[63]Z.H. Huang, Y. Zhang, W. Wu, A smoothing-type algorithm for solving system of inequalities, J. Comput. Appl. Math.2008,220,355-363.
[64]J.E.Dennis, R.B.Schnabel, Numerical methods for unconstrained optimization and nonlinear equations, Prentice-Hall, Englewood Cliffs, NJ.1983.
[65]B.N.Pshenichnyi, Newton's method for the systems of equalities and inequalities, Math. Acad. Sci. USSR.,1970,8.827-830.
[66]J.Burke, S.P.Han, A Guass-Newton approach to solving generalized inequalities, Math. Oper. Res.1986,11,632-643.
[67]J.E.Dennis, M.M.El-Alem, K.Williamson, A trust region approach to nonlinear systems of equalities and inequalities, SIAM J. Optim.1999,9.291-315.
[68]童晓娇,周叔子.非线性等式与不等式问题的信赖域算法,数值计算与计算机应用2001,1,53-62.
[69]王长钰,宇振盛,求解非线性系统的有效集信赖域方法,数学物理学报2006,26,223-232.
[70]P.M.Pardalos, Y.Y.Ye, C.G.Han, J.A.Kaliski, Solutiong of P0 matrix linear complementarity problems using reduction algorithm, SI AM J. Matrix Anal. Appl.1993,14 1048-1060.
[71]C.F.Ma, X.H.Chen, The convergence of a one-step smoothing Newton method for P0-NCP based on a new smoothing NCP-function, J. Comput. Appl. Math.2008,216,1-13.
[72]Z.H.Huang, J. Han, D. Xu, L. Zhang, The non-linear continuation methods for solving the Po-functions nonlinear complementarity problem, Sci. China ser. A 2001,44,1107-1114.
[73]H.D.Yu, D.G.Pu, Smoothing Newton method for NCP with the identification of degenerate indices, J. Comput. Appl. Math.2010,234,3424-3435.
[74]J.S.Chen, Z.H. Huang, C.Y.She, A new class of penalized NCP-functions and its properties, Comput. Optim. Appl. DOI 10.1007/s10589-009-9315-9.
[75]S.L.Hu, Z.H.Huang, J.S.Chen, Properties of a family of generalized NCP-functions and a derivative free algorithm for complementarity problems, J. Comput. Appl. Math.2009,230, 69-82.
[76]M.Kojima, N.Megiddo, T.Noma, Homotopy Continuation Methods for Nonlinear Comple-mentarity Problems, Math. Oper. Res.1991,16,754-774.
[77]L.P.Zhang, S.Y.Wu, T.R.Gao, Improved smoothing Newton methods for P0 nonlinear com-plementarity problems, Appl. Math. Comput.2009,215,324-332.
[78]C.Kanzow, Some equation-based methods for the nonlinear complementarity problem, Op-tim. Meth. Soft.1994,3,327-340.
[79]X.Liu, W.Wu, Coerciveness of some merit functions over symmetric cones, J. Ind. Manag. Optim.2009,5,603-613.
[80]M.S.,Gowa, M.A.,Tawhid, Existence and Limiting Behavior of Trajectories Associated with P0-Equations, Comput. Optim. Appl.1999,12,229-251.
[81]M.Kojima, N.Megiddo, T.Noma, A.Yoshise, A Unified Approach to Interior-Point Algorithms for Linear Complementarity Problems, Lecture Notes in Computer Science, Springer Verlag, Berlin, Germany,538 (1991).
[82]L. Fang, A new one-step smoothing Newton method for nonlinear complementarity prob-lem with P0-function, Appl. Math. Comput. 2010.216,1087-1095.
[83]F.Facchinei, C.Kanzow, Beyond monotonicity in regularization methods for non-linear com-plementarity problems. SIAM J. Control Optim.1999,37,1150-1161.
[84]O.L.Mangasarian, M.V.Solodov, Nonlinear complementarity as unconstrained and con-strained minimization, Math. Program.1993,62,277-297.
[85]S.P.Dirkse, M.C.Ferris, MCPLIB:A collection of nonlinear mixed complementarity prob-lems, Optim. Meth. Soft.1995.5,319-345.
[86]C.Oberlin, S.J.Wright, An accelerated Newton method for equations with semismooth Jaco-bians and nonlinear complementarity problems, Math. Program.2009.117,355-386.
[87]F.A.Potra, Y.Ye, Interior-point methods for nonlinear complementarity problems, J. Optim. Theory Appl.1996,88,617-642.
[88]S.J.Wright, D.Ralph, A superlinear infeasible-interior-point algorithm for monotone comple-mentarity problems, Math. Oper. Res.1996,21,815-838.
[89]H.D. Qi, A regularized smoothing Newton method for box constrained varia.tional inequality problems with PO-functions, SIAM J. Optim.2000,10,315-330.
[90]D. Sun, A regularization Newton method for solving nonlinear complementarity problems, Appl. Math. Optim.1999,40,315-339.
[91]S.P.Rui, C.X.Xu, A smoothing inexact Newton method for nonlinear complementarity prob-lems, J. Comput. Appl. Math.2010,233,2332-2338.
[92]J.G.Zhu, H.W.Liu, X.L.Li, A regularized smoothing-type algorithm for solving a system of inequalities with a PO-function, J. Comput. Appl. Math.2010,233,2611-2619.
[93]H.C.Zhang, W.W.Hager, A nonmonotone line search technique and its application to uncon-strained optimization, SIAM J. Optim.2004,14,1043-1056.
[94]C.Kanzow, Global convergence properties of some iterative methods for linear complemen-tarity, SIAM J. Optim.1996,6,326-341.
[95]M.S. Gowda, J.J. Sznajder, Weak univalence and connectedness of inverse images of contin-uous functions, Math. Oper. Res.1999,24,255-261.
[96]G. Ravindran, M.S. Gowda, Regularization of PO-functions in box variational inequality problems, SIAM J. Optim.2001,11,748-760.
[97]Y.Fathi, Computational complexity of LCPs associated with positive definite matrices, Math. Program.1979,17,335-344.
[98]M.A.,Gomes-Ruggiero, J.M.,Martinez, S.A.,Santos, Solving nonsmooth equations by means of quasi-Newton methods with globalization, In:Recent Advances in Nonsmooth Optimiza-tion, World Scientific, Singapore.1995,121-140.
[99]C. Kanzow, H. Kleinmichel, A new class of semismooth Newton method for nonlinear com-plementarity problems, Comput. Optim. Appl.1998,11,227-251.
[100]B. Chen, X. Chen, C. Kanzow, A penalized Fischer-Burmeister NCP-function:Theoreti-cal investigation and numerical results, Institute of Applied Mathemat-ics, University of Hamburg, Hamburg, Germany, Preprint 126,1997.
[101]N. Yamashita, M. Fukushima, On the rate of convergence of the Levenberg-Marquardt method, Computing 2001,15,239-249.
[102]C. Kanzow, M. Zupke, Inexact trust region methods for nonlinear complementarity prob-lems. Reformulation:Nonsmooth, Piecewise Smooth, Semismooth and Smoothing Methods, M. Fukushima, L. Qi Eds. Kulwer Academic Press. Norwell, MA,1998,211-233.
[103]J.Y. Fan, Jianyu Pan, Convergence properties of a self-adaptive Levenberg-Marquardt algo-rithm under local error bound condition, Comput. Optim. Appl.2005,74,23-39.
[104]M.J.D. Powell, Convergence properties of a class of minimization algorithms, Nonlinear Programming 2, O.L. Mangasarian, R.R. Meyer, and S.M. Robinson Eds. Academic Press: New York,1975,1-27.
[105]D.P.Bertsekas, Constrained optimization and lagrange multiplier methods, Academic Press, New York,1982.
[106]C.Kanzow, On a semismooth least squares formulation of complementarity problem with gap reduction, Optim. Meth. Software 2004,19,507-525.
[107]L.T. Watson, Solving the nonlinear complementarity problem by a homotopy method, SIAM J. Control Optim.1979,17,36-46.
[108]W.Hock, K.Schittkowski, Test examples for nonlinear programming codes, Lecture Notes in Economics and Mathematical Systems 187, Springer-Verlag:Berlin, Germany,1981.
[109]O.L.Mangasarian, Equivalence of the complementarity problems to a system of nonlinear equations, SIAM J. Appl. Math.1976,31,89-92.
[110]X.Chen, Smoothing methods for complementarity problems and their applications:a sur-vey, J. Oper. Res. Soc. Jpn.2000,43,32-47.
[111]O.L.Mangasarian,M.V.Solodov, A linearly convergent descent method for strongly mono-tone complementarity problems, Comput. Optim. Appl.1999,14,5-16.
[112]H.Jiang, Unconstrained minimization approaches to nonlinear complementarity problems, J. Global Optim.1996,9,169-181.
[113]J.S.Chen,H.T.Gao, S.H.Pan, An R-linearly convergent derivative-free algorithm for non-linear complementarity problems based on the generalized Fischer-Burmeister merit function, J. Comput. Appl. Math.2009,232,455-471.
[114]J.S.Chen, S.H.Pan, A family of NCP-functions and a descent method for the nonlinear complementarity problem, Comput. Optim. Appl.2008,40,389-404.
[115]J.S.Chen, On some NCP-functions based on the generalized Fischer-Burmeister function, Asia-Pac. J. Oper. Res.2007,24,401-420.
[116]B.Chen, Error bounds for R0-type and monotone nonlinear complementarity problems, J. Optim. Theory Appl.2001,108,297-316.
[117]L.Grippo, F.Lampariello, S.Lucidi, A nonmonotone line search technique for Newton's method, SIAM J. Numer. Anal.1986,23.707-716.
[118]S.C.Billups, S.P.Dirkse, M.C.Soares. A comparison of algorithms for large scale mixed com-plementarity problems, Comput. Optim. Appl.1977,7,3-25.
[119]H.X. Yin, Z.H. Huang, L. Qi, The convergence of a Levenberg-Marquardt method for non-linear inequalities, Numer. Func. Anal. Optim.2008,29 687-716.