互补问题的算法研究
|
摘要
互补问题是数学规划研究中较为活跃的分支.由于其应用背景的广泛性和与其他分支的交叉性,近年来受到越来越多的研究者的关注并取得了丰硕的成果.对互补问题的研究可以分为理论和算法两方面.前者主要研究问题的解的存在性、唯一性、稳定性以及灵敏度分析等性质,后者着重研究如何构造有效的算法.
本文主要研究互补问题的数值算法.主要内容概括总结如下：
1.基于Chen-Harler-Kanzow-Smale (CHKS)光滑函数,提出求解P0-函数混合互补问题的一种正则化的光滑方法.即：通过求得适定问题的一组解序列来代替求解原来不适定的问题,并且使得这组解序列收敛于原来问题的解.该算法中的正则参数和光滑参数都是彼此独立的变量,并且可以通过线性方程组的迭代很快得到.
2.鉴于光滑函数在解决互补问题的光滑类算法中的重要性,根据混合互补问题的定义域本身的结构,构造了两种新的混合互补函数函数.它们具有一些很好的性质,即：保证了与之相关的光滑路径的存在性和连续性以及光滑类算法所产生的迭代序列的有界性.在此基础上,给出了求解P0-函数混合互补问题的三种光滑算法：预测校正光滑牛顿算法、一步光滑牛顿算法和Broyden-like拟牛顿算法.
3.针对一般的(即：不要求是P0函数)混合互补问题提出了一种修正的光滑牛顿算法.该算法结合了梯度步.这使得该算法可以去掉F至少是一个P0-函数的假设.在适当条件下,该算法全局收敛性和局部超线性收敛性也得到了证明.
4.构造了一种新的对称锥上的互补函数,并研究了这个函数的强制性和强半光滑性以及其雅可比矩阵的强半光滑性.这些良好的性质为利用该SCCP互补函数设计相关算法求解对称锥互补问题SCCP打下了一定的基础.
Complementarity problem is a heated topic in the research of mathematical program-ming. Because of its wide application background and overlapping with other branch, Complementarity problem attracts more and more attentions from various fields of sci-ence and engineering in recent years. Also many achievements have been proposed in the field. Generally speaking, its research can be classified into two classes:theory and algorithms. The former is devoted to the existence, uniqueness, stability and sensitivity analysis of the solutions, while the latter is confined to solve the problems efficiently.
This paper is primarily designed to solve the problems efficiently. The main contri-butions are listed as follows:
1. Based on Chen-Harler-Kanzow-Smale (CHKS) smoothing function, we propose a regularized smoothing Newton method for mixed complementarity problems with a P0-function. This method is designed to handle ill-posed problems which substitutes the solution of original problem with the solution of a sequence of well-defined problems whose solutions converging to the solution of the original problem. And the regularization parameter and the smoothing parameter in our algorithm are independent variables and can be immediately obtained through iteration of linear system.
2. In view of the significance of smooth functions in smoothing type algorithms for solving complementarity problems, we construct two new MCP functions by smoothing a perturbed mid function such that one can study the existence and continuity of the smooth path and boundedness of the iteration sequence. Then, three smoothing algorithms for solving the MCP with a P0-function, that is, predictor-corrector smoothing Newton algo-rithm and one-step smoothing Newton method and broyden-like quasi-Newton algorithm are proposed respectively.
3. To solve general (not necessarily P0) mixed complementarity problems, a modified one-step smoothing Newton method is given. The algorithm incorporates a gradient step. Such procedure make the algorithm remove the condition that function F is required to be at least a P0-function. Under suitable assumptions, global convergence and locally superlinear convergence of the algorithm are established.
4. A new C-function for symmetric cone complementarity problems is constructed. It is showed that the new C-function is coercive, strongly semismooth and its Jacobian is also strongly semismooth, which are important for the construction of the corresponding algorithm for solving symmetric cone complementarity problems with this C-function.
本文主要研究互补问题的数值算法.主要内容概括总结如下：
1.基于Chen-Harler-Kanzow-Smale (CHKS)光滑函数,提出求解P0-函数混合互补问题的一种正则化的光滑方法.即：通过求得适定问题的一组解序列来代替求解原来不适定的问题,并且使得这组解序列收敛于原来问题的解.该算法中的正则参数和光滑参数都是彼此独立的变量,并且可以通过线性方程组的迭代很快得到.
2.鉴于光滑函数在解决互补问题的光滑类算法中的重要性,根据混合互补问题的定义域本身的结构,构造了两种新的混合互补函数函数.它们具有一些很好的性质,即：保证了与之相关的光滑路径的存在性和连续性以及光滑类算法所产生的迭代序列的有界性.在此基础上,给出了求解P0-函数混合互补问题的三种光滑算法：预测校正光滑牛顿算法、一步光滑牛顿算法和Broyden-like拟牛顿算法.
3.针对一般的(即：不要求是P0函数)混合互补问题提出了一种修正的光滑牛顿算法.该算法结合了梯度步.这使得该算法可以去掉F至少是一个P0-函数的假设.在适当条件下,该算法全局收敛性和局部超线性收敛性也得到了证明.
4.构造了一种新的对称锥上的互补函数,并研究了这个函数的强制性和强半光滑性以及其雅可比矩阵的强半光滑性.这些良好的性质为利用该SCCP互补函数设计相关算法求解对称锥互补问题SCCP打下了一定的基础.
Complementarity problem is a heated topic in the research of mathematical program-ming. Because of its wide application background and overlapping with other branch, Complementarity problem attracts more and more attentions from various fields of sci-ence and engineering in recent years. Also many achievements have been proposed in the field. Generally speaking, its research can be classified into two classes:theory and algorithms. The former is devoted to the existence, uniqueness, stability and sensitivity analysis of the solutions, while the latter is confined to solve the problems efficiently.
This paper is primarily designed to solve the problems efficiently. The main contri-butions are listed as follows:
1. Based on Chen-Harler-Kanzow-Smale (CHKS) smoothing function, we propose a regularized smoothing Newton method for mixed complementarity problems with a P0-function. This method is designed to handle ill-posed problems which substitutes the solution of original problem with the solution of a sequence of well-defined problems whose solutions converging to the solution of the original problem. And the regularization parameter and the smoothing parameter in our algorithm are independent variables and can be immediately obtained through iteration of linear system.
2. In view of the significance of smooth functions in smoothing type algorithms for solving complementarity problems, we construct two new MCP functions by smoothing a perturbed mid function such that one can study the existence and continuity of the smooth path and boundedness of the iteration sequence. Then, three smoothing algorithms for solving the MCP with a P0-function, that is, predictor-corrector smoothing Newton algo-rithm and one-step smoothing Newton method and broyden-like quasi-Newton algorithm are proposed respectively.
3. To solve general (not necessarily P0) mixed complementarity problems, a modified one-step smoothing Newton method is given. The algorithm incorporates a gradient step. Such procedure make the algorithm remove the condition that function F is required to be at least a P0-function. Under suitable assumptions, global convergence and locally superlinear convergence of the algorithm are established.
4. A new C-function for symmetric cone complementarity problems is constructed. It is showed that the new C-function is coercive, strongly semismooth and its Jacobian is also strongly semismooth, which are important for the construction of the corresponding algorithm for solving symmetric cone complementarity problems with this C-function.
引文
[1]韩继业,修乃华,戚厚铎,非线性互补理论与算法[M],上海科学技术出版社,上海,2006.
[2]M.J.Todd, Potential-reduction methods in mathematical programming[J], Math.Prog.,1996,76:3-45.
[3]M.Kojima, S. Mizuho and A.Yoshise, A polynomial-time algorithm for a class of linear complementarity problems[J], Math. Prog.,1989,44:1-26.
[4]M.Kojima, S. Mizuho and A.Yoshise, An 0((?)nL) iteration potential reduction algorithm for linear complementarity problems[J], Math.Prog.,1991,50:331-342.
[5]Y.Y.Ye, A further result on the potential reduction algorithm for the P-matrix linear complementarity problem[J], Advances in Optimization and Parallel Com-puting,P.M.Pardalos, ed., North-Holland, Amsterdam, New York,1992:310-316.
[6]Y.Y.Ye and P.M.Pardalos, A class of linear complementarity problems in polynomial time[J], Linear Algebra Appl.,1991,152:3-17.
[7]P.M.Pardalos, Y.Y.Ye and C.G.Han etc., Solution of P0-matrix linear complemen-tarity problems using a potential reduction algorithm[J], SIAM J. Matrix Anal. Appl.,1993,14:1048-1060.
[8]M.Kojima, N.M. Giddo and T.Noma, etc.. A unified approach to interior point algorithm for linear complementarity problems[J], Research Report RJ 7493, IBM Almaden Research Center, San Jose, CA,1990.
[9]J.Ji, F.Potra and S.Huang, A predictor-corrector method for linear complementar-ity problems with polynomial complexity and superlinear convergence [J],Technical Report 18, Department of Mathematics, University of Iowa, Iowa City,IC,1991.
[10]J. Miao, A quadratically convergent O((κ+1)(?)nL)-iteration algorithm for the P*(κ)-matrix linear complementarily problem [J], Math. Prog.,1995,69:355-368.
[11]S.Xu and J.V.Burke, A polynomial time interior-point path-following algorithm for LCP based on Chen-Harker-Hanzow smoothing techniques [J], Math. Prog., .1999,86:91-103.
[12]何尚录,徐成贤,求解互补问题的不可行内点法及其计算复杂性[J], 中国科学,2000,30：983-989.
[13]B.Chen and P.T.Harker, A non-interior-point continuation method for linear com-plementarity problems [J], SIAM J, Matrix Anal. Appl.,1993,14:1168-1190.
[14]C. Kanzow, Some Noninterior Continuation Methods for Linear Complementarity Problems[J]. SIAM J. Matrix Anal. Appl.1996,17:851-868.
[15]C. Chen and O.L. Mangasarian, A class of smoothing functions for nonlinear and mixed complementarity problems [J], Comput.Optim. Appl.,1996,5:97-138.
[16]S.A. Gabriel and J.J. More, Smoothing of Mixed Complementarity Problems [J]. In M.C. Ferris and J.S. Pang (eds.), Complementarity and Variational Problems:State of the Art. Philadelphia, PA:SIAM,1997,105-116.
[17]X. Chen, L. Qi and D.Sun, Global and superlinear convergence of the smoothing Newton method and its application to general box constrained variational inequal-ities[J], Math-Comp.,1998,67:519-540.
[18]X. Chen and Y.Ye, On homotopy-smoothing methods for box-constrained varia-tional inequalities[J], SIAM.J. Control Optim.,1999,37:589-616.
[19]J. Burke and S. Xu, A non-interior predictor-corrector path following algorithm for the monotone linear complementarity problem[J], Math. Prog.,2000,87:113-130.
[20]S.Xu, The global linear convergence of an infeasible non-interior path-following al-gorithm for complementarity problems with uniform P-functions[J], Math. Prog., 2000,87:501-517.
[21]B. Chen and N.Xiu, A global and local quadratic noninterior continuation smooth-ing method for nonlinear complementarity problems based on Chen-Mangasarian smoothing functions[J], SIAM J. Optim.,1999,9:605-623.
[22]修乃华:互补问题非内点法的一步二次收敛性[J],科学通报,1999,44:1483-1488.
[23]B. Chen and X. Chen, A global and local superlinear continuation-smoothing method for P0 and R0 NCP or monotone NCP[J], SIAM J. Optim,1999,9:624-645.
[24]陈国庆：三维弹性接触问题极小化数值解法一非线性互补原理、模型和算法,学位论文,大连理工大学,1994.
[25]A.Y.T.Leung, G. Q. Chen and W. J. Cuen, Smoothing Newton method for two-and three-dimensional frictional contact problems[J], International Journal for Nu-merical Methods in Engineering,1998,41:1001-1027.
[26]陈国庆,陈万吉,互补问题的光滑逼近法[J],高校应用数学学报,1998,14:189-196
[27]陈国庆,赵素芬,熵函数法的数学理论[J],计算数学,1999,21:397-406.
[28]J.M.Peng and Z.Lin, A non-interior continuation method for generalized linear com-plementarity problems[J], Math. Prog.,1999,86:533-563.
[29]H.D.Qi and L.Z.Liao, A smoothing Newton method for extended vertical linear complementarity problems[J], SIAM J. Matrix Anal. Appl.,1999,21:45-66.
[30]宋岱才,刘国新,刘庆怀等,线性互补问题的一个高阶收敛性算法[J],吉林大学自然科学学报,1999,127:12-16.
[31]陈国庆,曹兵,箱式约束变分不等式的一种新NCP-函数及其广义牛顿法[J],计算数学,2002,24：91-104.
[32]S.M. Robinson, Local structure of feasible sets in nonlinear programming, part III: Stability and sensitivity[J], Math.Prog.Stud.,1987,30:45-66.
[33]J. S. Pang, Newton's method for B-differentiable equations [J]. Math Oper Res, 1990,15(2):311-341
[34]J.S.Pang and S.A.Gabrier, NE/SQP:A robust algorithm for the nonlinear comple-mentarity problem[J], Math.Prog.,1993,60:295-337.
[35]P.T.Harker and B. Xiao, Newton's method for the nonlinear complementarity prob-lem:A B-differentiable equation approach [J], Math. Prog.,1990.48:339-357.
[36]A. Fischer, A Special Newton-Type Optimization Method [J]. Optimization 1992,24:269-284.
[37]M.C. Ferris, C.Kanzow and T.S.Munson, Feasible descent algorithms for mixed complementarity problems[J], Math. prog.,1999,86:475-497.
[38]D.Sun and L.Qi, On NCP-functions[J], Computational Optimization and Applica-tions,1999,13:201-220.
[39]L.Qi and J.Sun, A nonsmooth version of Newton's method[J]. Math. Prog., 1993,58:353-368.
[40]J.S.Pang and L.Qi, Nonsmooth equations:motivation and algorithm [J], SIAM J. Optim.,1993,3:443-465.
[41]P.T.Harker and J.S.Pang, A damped-Newton method for the linear complementarity problem [J], Lectures in Applied Mathematics,1990,26:265-284.
[42]H.Jiang and L.Qi, A new nonsmooth equations approach to nonlinear complemen-tarity problems[J], SIAM J. Control Optim.,1997,35:178-193.
[43]C.Kanzow, Strictly feasible equation-based methods for mixed complementarity problems[J], Numer. Math.,2001,89:135-160.
[44]T.D. Luca, F.Facchinei and C.Kanzow, A theoretical and numerical com-parison of some semismooth algorithm for complementarity problems[J], Comput.Optim.Appl.,2000,16:173-205
[45]T.S.Munson, F.Facchinei and M.C.Ferris, etc., The semismooth algorithm for large scale complementarity problems[J], Tech.Report, Comput.Sci.Dept., University of Wisconsin, Madison, WI,1999.
[46]L.Qi, Convergence analysis of some algorithms for solving nonsmooth equations[J], Mathematics of Operations Research,1993,18:227-244.
[47]A.A.Goldstein, Convex programming in Hilbert space[J], Bull.Amer.Math.Soc., 1964,70:709-710.
[48]E.S.Levitin and B.T.Polyak, Constrained minimization problems [J], USSR Comput. Math. Math.Phys.,1966,6:1-50.
[49]G.M.Korpelevich, The extragradient method for finding saddle points and other problems[J], Matecon,1976,12:747-756.
[50]E.N.Khobotov, Modification of the extragradient method for solv-ing variational inequalities and certain optimization problem [J], USSR Comput.Math.Phys.,1987,27:120-127.
[51]P.Marcotte, Application of Khobotov's algorithm to variational inequalities and network equilibrium problems [J], Inform. Systems Oper. Res,1991,29:258-270.
[52]J.Zhang and N.Xiu, New projection-type methods for monotone LCP with finite termination[J], Numer. Math.2002,92:179-195.
[53]M.V.Solodov and B.F.Svaiter, A new projection method for variational inequality problems[J], SIAM J. Control Optim.1999,37:765-776.
[54]M.V. Solodov and B.F. Svaiter, A truly globally convergent Newton-type method for the monotone nonlinear complementarity proble[J], SIAM J. Optim.,2000,10:605-625.
[55]B.S.He, A projection and contraction method for a class of linear complementarity problems an its application in convex quadratic programming [J], Applied Mathe-matics and Optimization,1992,25:247-262.
[56]B.S. He, Inexact implicit methods for monotone general variational inequalities [J], Math, prog.,1999,86:199-217.
[57]Y.B. Zhao, Extended projection methods for monotone variational inequalities [J], J.Optim.Theory Appl.,1999,100:219-231.
[58]陈国庆,大型稀蔬线性互补问题的行作用法[J],高校计算数学学报,2000,22
[59]N. Xiu and J. Zhang, Some recent advances in projection-type methods for varia-tional inequalities [J], J.Comput. Appl. Math,,2003,152:559-585.
[60]M.C. Ferris and C. Kanzow, Complementarity and related problems:a survey [J], Tech.Report, Comput.Sci.Dept., University of Wisconsin, Madison, WI,1998.
[61]M.C. Ferris and J.S. Pang, Engineering and economic applications of complemen-tarity problems[J],SIAM J.Review,1997,39:669-713.
[62]修乃华,高自友：互补问题算法的新进展[J],数学进展,1999,28:193-210.
[63]Z.H. Huang, J. Han and Z. Chen, Predictor-Corrector Smoothing Newton Method, Based on a New Smoothing Function,for Solving the Nonlinear Complementarity Problem with a P0Function[J] journal of optimization theory and applications, Vol. 117, No.1, pp.39-68,2003.
[64]M. S. Gowda and M. A. Tawhid, Existence and Limiting Behauior of Trajectories Associated with P0-Equations[J], Computational Optimization and Applications, Vol.12, pp.229-251,1999.
[65]L. Qi, D. Sun and G. Zhou, A New Look at Smoothing Newton Methods for Non-linear Complementarity Problems and Box-Constrained VariationalInequalities[J], Mathematical Programming, Vol.87, pp.1-35,2000.
[66]G. Ravindran and M. S. Gowda, Regularization of P0-Functions in Box Variational Inequality Problems[J], SIAM Journal on Optimization, Vol.11, pp.748-760,2000.
[67]J. Burke and S. Xu, A Noninterior Predictor-Corrector Path-Following Algorithm for LCP, Reformulation:Nonsmooth, Piecewise-Smooth, Semismooth, and Smooth-ing Methods [J], Edited by M. Fukushima and L. Qi, Kluwer Academic Publishers, Boston, Massachusetts, pp.45-64,1998.
[68]J. Burke and S. Xu, A Noninterior Predictor-Corrector Path-Following Algorithm for the Monotone Linear Complementarily Problem[J], Mathematical Programming, Vol.87, pp.113-130,2000.
[69]S. Engelke and C. Kanzow, Predictor-Corrector Smoothing Methods for the Solu-tion of Linear Programming[J], Preprint, Department of Mathematics, University of Hamburg, Hamburg, Germany,2000.
[70]D. Sun, A Regularization Newton Method for Soluing Nonlinear Complementarity Problems[J]. Applied Mathematics and Optimization, Vol.36, pp.315-339,1999.
[71]R. MiffHin, Semismooth and Semiconvex Functions Constrained Optimization[J], SIAM Journal on Control and Optimization. Vol.15, pp.957-972,1977.
[72]L. Qi and J. Sun, A Nonsmooth Version of Newton's Method[J], Mathematical Programming, Vol.58, pp.353-367,1993.
[73]D. Sun and L. Qi, Soluing Variational Inequality Problems uia Smoothing- Nons-mooth Reformulations[J], Journal of Computational and Applied Mathematics, Vol. 129, pp.37-62,2001.
[74]H. D. Qi, A Regularization Smoothing Newton Method for Box-Constrained Vari-ational Inequality Problems with P -Functions[J], SIAM Journal on Optimization, Vol.10, pp.315-330,1999.
[75]D. Luca, T. Facchinei and C. Kanzow, A Semismooth Equation Approach to the Solution of Nonlinear Complementarity Problems[J], Mathematical Programming, Vol.75, pp.407-439,1996.
[76]A. Fiscjer, Solution of Monotone Complementarity Problems with Locally Lips-chitzian Functions [J], Mathematical Programming, Vol.76, pp.513-532,1997.
[77]H. Jiang and L. Qi, A New Nonsmooth Eqations Approach to Nonlinear Comple-mentarity Problems[J], SIAM Journal on Control and Optimization, Vol.35, pp. 178-193,1997.
[78]F. H. Clarke, Optimization and Nonsmooth Analysis, Wiley, New York, NY,1983.
[79]L. Qi, Convergence analysis of some algorithms for solving nonsmooth equations. Mathematics of Operations Research 18:227-244,1993.
[80]乌力吉：互补问题的乘子法,博士论文,内蒙古大学,2004.
[81]B. Chen and X. Chen, A Global and Local Superlinear Continuation-Smoothing Method for P0+R0 and Monotone NCP, SIAM Journal on Optimization, Vol.9, pp.624-645,1999.
[82]B. Chen and N.H. Xiu, A Global Linear and Local Quadratic Noninterior Continua-tion Method for Nonlinear Complementarity Problems Based on Chen- Mangasarian Smoothing Functions, SIAM Journal on Optimization, Vol.9, pp.605-623,1999
[83]B. Chen and X. Chen, A Global Linear and Local Quadratic Continuation Smooth-ing Method for Variational Inequalities with Box Constraints, Computational Op-timization and Applications, Vol.13, pp.131-158,2000.
[84]P. Tseng, Analysis of a Noninterior Continuation Method Based on Chen-Mangasarian Smoothing Functions for Complementarity Problems, Reformulation: Nonsmooth, Piecewise-Smooth, Semismooth, and Smoothing Methods, Edited by M. Fukushima and L. Qi, Kluwer Academic Publishers, Boston, Massachusetts, pp. 381-404,1998.
[85]L.p. Zhang and Z.Y. Gao, Superlinear/quadratic one-step smoothing Newton method for PO-NCP without strict complementarity, Math Meth Oper Res 2002, 56:231-241.
[86]H.D. Qi and L.Z. Liao, A Smoothing Newton Method for General Nonlinear Comple-mentarity Problems, Computational Optimization and Applications,2000,17:231-253.
[87]C. Kanzow and H. Pieper, Jacobian smoothing methods for general nonlinear com-plementarity problems, SIAM J. Optim.,1999,9:342-372.
[88]H. Jiang, Smoothed Fischer-Burmeister equation methods for the complementar-ity problem, Technic Report, Department of Mathematics, The University of Mel-bourne, Parkville, Victoria, Australia, June 1997.
[89]U. Faraut, A. Koranyi, Analysis on Symmetric Cones, New York:Oxford University Press,1994.
[90]L.C. Kong, N.H. Xiu, New smooth C-function for symmetric cone complementarity problems, Optimization Letters,1:391-400(2007).
[91]S.H.Kum, Y.D.Lim, Coercivity and Strong Semismoothness of the Penalized Fischer-Burmeister Function for the Symmetric Cone Complementarity Problem, J Optim Theory Appl.142:377-383(2009).
[92]D. Sun, J. Sun, Semismooth matrix valued functions. Math. Oper.27:150-169(2002).
[93]D. Sun, J. Sun, Lowner's operator and spectral functions on Euclidean Jordan algebras, Math. Oper.33(0),2008.
[94]L.C. Kong, L. Tuncel and N.H. Xiu, Vector-valued Implicit Lagrangian for Symmet-ric Cone Complementarity Problems, Asia-Pacific Journal of Operational Research (APJOR), vol.26,199-233(2009).
[95]C.F. Ma, X.H.Chen, J. Tang, On convergence of a smoothing Broyden-like method for P0-NCP, Nonlinear Analysis:Real World Applications,9(2008), pp.899-911.
[96]D.-H. Li, M. Fukushima, A derivative-free line search and global convergence of Broyden-like method for nonlinear equations, Optimization Methods and Software, 13 (2000), No.3, pp.181-201.
[2]M.J.Todd, Potential-reduction methods in mathematical programming[J], Math.Prog.,1996,76:3-45.
[3]M.Kojima, S. Mizuho and A.Yoshise, A polynomial-time algorithm for a class of linear complementarity problems[J], Math. Prog.,1989,44:1-26.
[4]M.Kojima, S. Mizuho and A.Yoshise, An 0((?)nL) iteration potential reduction algorithm for linear complementarity problems[J], Math.Prog.,1991,50:331-342.
[5]Y.Y.Ye, A further result on the potential reduction algorithm for the P-matrix linear complementarity problem[J], Advances in Optimization and Parallel Com-puting,P.M.Pardalos, ed., North-Holland, Amsterdam, New York,1992:310-316.
[6]Y.Y.Ye and P.M.Pardalos, A class of linear complementarity problems in polynomial time[J], Linear Algebra Appl.,1991,152:3-17.
[7]P.M.Pardalos, Y.Y.Ye and C.G.Han etc., Solution of P0-matrix linear complemen-tarity problems using a potential reduction algorithm[J], SIAM J. Matrix Anal. Appl.,1993,14:1048-1060.
[8]M.Kojima, N.M. Giddo and T.Noma, etc.. A unified approach to interior point algorithm for linear complementarity problems[J], Research Report RJ 7493, IBM Almaden Research Center, San Jose, CA,1990.
[9]J.Ji, F.Potra and S.Huang, A predictor-corrector method for linear complementar-ity problems with polynomial complexity and superlinear convergence [J],Technical Report 18, Department of Mathematics, University of Iowa, Iowa City,IC,1991.
[10]J. Miao, A quadratically convergent O((κ+1)(?)nL)-iteration algorithm for the P*(κ)-matrix linear complementarily problem [J], Math. Prog.,1995,69:355-368.
[11]S.Xu and J.V.Burke, A polynomial time interior-point path-following algorithm for LCP based on Chen-Harker-Hanzow smoothing techniques [J], Math. Prog., .1999,86:91-103.
[12]何尚录,徐成贤,求解互补问题的不可行内点法及其计算复杂性[J], 中国科学,2000,30：983-989.
[13]B.Chen and P.T.Harker, A non-interior-point continuation method for linear com-plementarity problems [J], SIAM J, Matrix Anal. Appl.,1993,14:1168-1190.
[14]C. Kanzow, Some Noninterior Continuation Methods for Linear Complementarity Problems[J]. SIAM J. Matrix Anal. Appl.1996,17:851-868.
[15]C. Chen and O.L. Mangasarian, A class of smoothing functions for nonlinear and mixed complementarity problems [J], Comput.Optim. Appl.,1996,5:97-138.
[16]S.A. Gabriel and J.J. More, Smoothing of Mixed Complementarity Problems [J]. In M.C. Ferris and J.S. Pang (eds.), Complementarity and Variational Problems:State of the Art. Philadelphia, PA:SIAM,1997,105-116.
[17]X. Chen, L. Qi and D.Sun, Global and superlinear convergence of the smoothing Newton method and its application to general box constrained variational inequal-ities[J], Math-Comp.,1998,67:519-540.
[18]X. Chen and Y.Ye, On homotopy-smoothing methods for box-constrained varia-tional inequalities[J], SIAM.J. Control Optim.,1999,37:589-616.
[19]J. Burke and S. Xu, A non-interior predictor-corrector path following algorithm for the monotone linear complementarity problem[J], Math. Prog.,2000,87:113-130.
[20]S.Xu, The global linear convergence of an infeasible non-interior path-following al-gorithm for complementarity problems with uniform P-functions[J], Math. Prog., 2000,87:501-517.
[21]B. Chen and N.Xiu, A global and local quadratic noninterior continuation smooth-ing method for nonlinear complementarity problems based on Chen-Mangasarian smoothing functions[J], SIAM J. Optim.,1999,9:605-623.
[22]修乃华:互补问题非内点法的一步二次收敛性[J],科学通报,1999,44:1483-1488.
[23]B. Chen and X. Chen, A global and local superlinear continuation-smoothing method for P0 and R0 NCP or monotone NCP[J], SIAM J. Optim,1999,9:624-645.
[24]陈国庆：三维弹性接触问题极小化数值解法一非线性互补原理、模型和算法,学位论文,大连理工大学,1994.
[25]A.Y.T.Leung, G. Q. Chen and W. J. Cuen, Smoothing Newton method for two-and three-dimensional frictional contact problems[J], International Journal for Nu-merical Methods in Engineering,1998,41:1001-1027.
[26]陈国庆,陈万吉,互补问题的光滑逼近法[J],高校应用数学学报,1998,14:189-196
[27]陈国庆,赵素芬,熵函数法的数学理论[J],计算数学,1999,21:397-406.
[28]J.M.Peng and Z.Lin, A non-interior continuation method for generalized linear com-plementarity problems[J], Math. Prog.,1999,86:533-563.
[29]H.D.Qi and L.Z.Liao, A smoothing Newton method for extended vertical linear complementarity problems[J], SIAM J. Matrix Anal. Appl.,1999,21:45-66.
[30]宋岱才,刘国新,刘庆怀等,线性互补问题的一个高阶收敛性算法[J],吉林大学自然科学学报,1999,127:12-16.
[31]陈国庆,曹兵,箱式约束变分不等式的一种新NCP-函数及其广义牛顿法[J],计算数学,2002,24：91-104.
[32]S.M. Robinson, Local structure of feasible sets in nonlinear programming, part III: Stability and sensitivity[J], Math.Prog.Stud.,1987,30:45-66.
[33]J. S. Pang, Newton's method for B-differentiable equations [J]. Math Oper Res, 1990,15(2):311-341
[34]J.S.Pang and S.A.Gabrier, NE/SQP:A robust algorithm for the nonlinear comple-mentarity problem[J], Math.Prog.,1993,60:295-337.
[35]P.T.Harker and B. Xiao, Newton's method for the nonlinear complementarity prob-lem:A B-differentiable equation approach [J], Math. Prog.,1990.48:339-357.
[36]A. Fischer, A Special Newton-Type Optimization Method [J]. Optimization 1992,24:269-284.
[37]M.C. Ferris, C.Kanzow and T.S.Munson, Feasible descent algorithms for mixed complementarity problems[J], Math. prog.,1999,86:475-497.
[38]D.Sun and L.Qi, On NCP-functions[J], Computational Optimization and Applica-tions,1999,13:201-220.
[39]L.Qi and J.Sun, A nonsmooth version of Newton's method[J]. Math. Prog., 1993,58:353-368.
[40]J.S.Pang and L.Qi, Nonsmooth equations:motivation and algorithm [J], SIAM J. Optim.,1993,3:443-465.
[41]P.T.Harker and J.S.Pang, A damped-Newton method for the linear complementarity problem [J], Lectures in Applied Mathematics,1990,26:265-284.
[42]H.Jiang and L.Qi, A new nonsmooth equations approach to nonlinear complemen-tarity problems[J], SIAM J. Control Optim.,1997,35:178-193.
[43]C.Kanzow, Strictly feasible equation-based methods for mixed complementarity problems[J], Numer. Math.,2001,89:135-160.
[44]T.D. Luca, F.Facchinei and C.Kanzow, A theoretical and numerical com-parison of some semismooth algorithm for complementarity problems[J], Comput.Optim.Appl.,2000,16:173-205
[45]T.S.Munson, F.Facchinei and M.C.Ferris, etc., The semismooth algorithm for large scale complementarity problems[J], Tech.Report, Comput.Sci.Dept., University of Wisconsin, Madison, WI,1999.
[46]L.Qi, Convergence analysis of some algorithms for solving nonsmooth equations[J], Mathematics of Operations Research,1993,18:227-244.
[47]A.A.Goldstein, Convex programming in Hilbert space[J], Bull.Amer.Math.Soc., 1964,70:709-710.
[48]E.S.Levitin and B.T.Polyak, Constrained minimization problems [J], USSR Comput. Math. Math.Phys.,1966,6:1-50.
[49]G.M.Korpelevich, The extragradient method for finding saddle points and other problems[J], Matecon,1976,12:747-756.
[50]E.N.Khobotov, Modification of the extragradient method for solv-ing variational inequalities and certain optimization problem [J], USSR Comput.Math.Phys.,1987,27:120-127.
[51]P.Marcotte, Application of Khobotov's algorithm to variational inequalities and network equilibrium problems [J], Inform. Systems Oper. Res,1991,29:258-270.
[52]J.Zhang and N.Xiu, New projection-type methods for monotone LCP with finite termination[J], Numer. Math.2002,92:179-195.
[53]M.V.Solodov and B.F.Svaiter, A new projection method for variational inequality problems[J], SIAM J. Control Optim.1999,37:765-776.
[54]M.V. Solodov and B.F. Svaiter, A truly globally convergent Newton-type method for the monotone nonlinear complementarity proble[J], SIAM J. Optim.,2000,10:605-625.
[55]B.S.He, A projection and contraction method for a class of linear complementarity problems an its application in convex quadratic programming [J], Applied Mathe-matics and Optimization,1992,25:247-262.
[56]B.S. He, Inexact implicit methods for monotone general variational inequalities [J], Math, prog.,1999,86:199-217.
[57]Y.B. Zhao, Extended projection methods for monotone variational inequalities [J], J.Optim.Theory Appl.,1999,100:219-231.
[58]陈国庆,大型稀蔬线性互补问题的行作用法[J],高校计算数学学报,2000,22
[59]N. Xiu and J. Zhang, Some recent advances in projection-type methods for varia-tional inequalities [J], J.Comput. Appl. Math,,2003,152:559-585.
[60]M.C. Ferris and C. Kanzow, Complementarity and related problems:a survey [J], Tech.Report, Comput.Sci.Dept., University of Wisconsin, Madison, WI,1998.
[61]M.C. Ferris and J.S. Pang, Engineering and economic applications of complemen-tarity problems[J],SIAM J.Review,1997,39:669-713.
[62]修乃华,高自友：互补问题算法的新进展[J],数学进展,1999,28:193-210.
[63]Z.H. Huang, J. Han and Z. Chen, Predictor-Corrector Smoothing Newton Method, Based on a New Smoothing Function,for Solving the Nonlinear Complementarity Problem with a P0Function[J] journal of optimization theory and applications, Vol. 117, No.1, pp.39-68,2003.
[64]M. S. Gowda and M. A. Tawhid, Existence and Limiting Behauior of Trajectories Associated with P0-Equations[J], Computational Optimization and Applications, Vol.12, pp.229-251,1999.
[65]L. Qi, D. Sun and G. Zhou, A New Look at Smoothing Newton Methods for Non-linear Complementarity Problems and Box-Constrained VariationalInequalities[J], Mathematical Programming, Vol.87, pp.1-35,2000.
[66]G. Ravindran and M. S. Gowda, Regularization of P0-Functions in Box Variational Inequality Problems[J], SIAM Journal on Optimization, Vol.11, pp.748-760,2000.
[67]J. Burke and S. Xu, A Noninterior Predictor-Corrector Path-Following Algorithm for LCP, Reformulation:Nonsmooth, Piecewise-Smooth, Semismooth, and Smooth-ing Methods [J], Edited by M. Fukushima and L. Qi, Kluwer Academic Publishers, Boston, Massachusetts, pp.45-64,1998.
[68]J. Burke and S. Xu, A Noninterior Predictor-Corrector Path-Following Algorithm for the Monotone Linear Complementarily Problem[J], Mathematical Programming, Vol.87, pp.113-130,2000.
[69]S. Engelke and C. Kanzow, Predictor-Corrector Smoothing Methods for the Solu-tion of Linear Programming[J], Preprint, Department of Mathematics, University of Hamburg, Hamburg, Germany,2000.
[70]D. Sun, A Regularization Newton Method for Soluing Nonlinear Complementarity Problems[J]. Applied Mathematics and Optimization, Vol.36, pp.315-339,1999.
[71]R. MiffHin, Semismooth and Semiconvex Functions Constrained Optimization[J], SIAM Journal on Control and Optimization. Vol.15, pp.957-972,1977.
[72]L. Qi and J. Sun, A Nonsmooth Version of Newton's Method[J], Mathematical Programming, Vol.58, pp.353-367,1993.
[73]D. Sun and L. Qi, Soluing Variational Inequality Problems uia Smoothing- Nons-mooth Reformulations[J], Journal of Computational and Applied Mathematics, Vol. 129, pp.37-62,2001.
[74]H. D. Qi, A Regularization Smoothing Newton Method for Box-Constrained Vari-ational Inequality Problems with P -Functions[J], SIAM Journal on Optimization, Vol.10, pp.315-330,1999.
[75]D. Luca, T. Facchinei and C. Kanzow, A Semismooth Equation Approach to the Solution of Nonlinear Complementarity Problems[J], Mathematical Programming, Vol.75, pp.407-439,1996.
[76]A. Fiscjer, Solution of Monotone Complementarity Problems with Locally Lips-chitzian Functions [J], Mathematical Programming, Vol.76, pp.513-532,1997.
[77]H. Jiang and L. Qi, A New Nonsmooth Eqations Approach to Nonlinear Comple-mentarity Problems[J], SIAM Journal on Control and Optimization, Vol.35, pp. 178-193,1997.
[78]F. H. Clarke, Optimization and Nonsmooth Analysis, Wiley, New York, NY,1983.
[79]L. Qi, Convergence analysis of some algorithms for solving nonsmooth equations. Mathematics of Operations Research 18:227-244,1993.
[80]乌力吉：互补问题的乘子法,博士论文,内蒙古大学,2004.
[81]B. Chen and X. Chen, A Global and Local Superlinear Continuation-Smoothing Method for P0+R0 and Monotone NCP, SIAM Journal on Optimization, Vol.9, pp.624-645,1999.
[82]B. Chen and N.H. Xiu, A Global Linear and Local Quadratic Noninterior Continua-tion Method for Nonlinear Complementarity Problems Based on Chen- Mangasarian Smoothing Functions, SIAM Journal on Optimization, Vol.9, pp.605-623,1999
[83]B. Chen and X. Chen, A Global Linear and Local Quadratic Continuation Smooth-ing Method for Variational Inequalities with Box Constraints, Computational Op-timization and Applications, Vol.13, pp.131-158,2000.
[84]P. Tseng, Analysis of a Noninterior Continuation Method Based on Chen-Mangasarian Smoothing Functions for Complementarity Problems, Reformulation: Nonsmooth, Piecewise-Smooth, Semismooth, and Smoothing Methods, Edited by M. Fukushima and L. Qi, Kluwer Academic Publishers, Boston, Massachusetts, pp. 381-404,1998.
[85]L.p. Zhang and Z.Y. Gao, Superlinear/quadratic one-step smoothing Newton method for PO-NCP without strict complementarity, Math Meth Oper Res 2002, 56:231-241.
[86]H.D. Qi and L.Z. Liao, A Smoothing Newton Method for General Nonlinear Comple-mentarity Problems, Computational Optimization and Applications,2000,17:231-253.
[87]C. Kanzow and H. Pieper, Jacobian smoothing methods for general nonlinear com-plementarity problems, SIAM J. Optim.,1999,9:342-372.
[88]H. Jiang, Smoothed Fischer-Burmeister equation methods for the complementar-ity problem, Technic Report, Department of Mathematics, The University of Mel-bourne, Parkville, Victoria, Australia, June 1997.
[89]U. Faraut, A. Koranyi, Analysis on Symmetric Cones, New York:Oxford University Press,1994.
[90]L.C. Kong, N.H. Xiu, New smooth C-function for symmetric cone complementarity problems, Optimization Letters,1:391-400(2007).
[91]S.H.Kum, Y.D.Lim, Coercivity and Strong Semismoothness of the Penalized Fischer-Burmeister Function for the Symmetric Cone Complementarity Problem, J Optim Theory Appl.142:377-383(2009).
[92]D. Sun, J. Sun, Semismooth matrix valued functions. Math. Oper.27:150-169(2002).
[93]D. Sun, J. Sun, Lowner's operator and spectral functions on Euclidean Jordan algebras, Math. Oper.33(0),2008.
[94]L.C. Kong, L. Tuncel and N.H. Xiu, Vector-valued Implicit Lagrangian for Symmet-ric Cone Complementarity Problems, Asia-Pacific Journal of Operational Research (APJOR), vol.26,199-233(2009).
[95]C.F. Ma, X.H.Chen, J. Tang, On convergence of a smoothing Broyden-like method for P0-NCP, Nonlinear Analysis:Real World Applications,9(2008), pp.899-911.
[96]D.-H. Li, M. Fukushima, A derivative-free line search and global convergence of Broyden-like method for nonlinear equations, Optimization Methods and Software, 13 (2000), No.3, pp.181-201.