摘要
本论文主要对拉格朗日正则化方法和线性规划原-对偶算法进行了研究，其中，前者是一种特殊的光滑化方法，为本文线性规划原-对偶内点和非内点算法的建立提供了基础。
极大熵方法是解有限极大极小问题的一种有效光滑化法，它通过在极大极小问题的拉格朗日函数上引进Shannon信息熵作正则项，给出一致逼近极大值函数的光滑函数。因该函数所具有的优良性质，使其在求解各类优化问题中得到了广泛的应用。
本文从两个方面发展了这种熵正则化方法，即将其从极大极小问题推广到一般不等式约束优化问题上和用一般函数代替熵函数作正则项，建立新的正则化方法。为了克服不可微正齐次函数δ(·|R_-~m)给约束优化问题的等价无约束形式求解带来的困难，我们将其目标函数M(x)重新用一个以经典拉格朗日函数为目标的锥优化问题来表示。当将熵函数作为正则项加到拉格朗日函数上，我们得到了逐点逼近于M(x)的光滑函数。经证明，该函数即为指数罚函数。在此基础上，通过用一般可分离乘子函数代替熵函数作正则项，建立了一种新型正则化方法，即拉格朗日正则化法。该方法不仅提供了统一光滑不可微函数M(x)和δ(·|R_-~m)的办法，而且还给出了一种构造罚函数的统一框架，由此将罚函数与经典拉格朗日函数从对偶空间的角度联系在一起。
本文上篇共含四章，主要进行拉格朗日正则化法的研究。第一章为绪论，简单描述了熵正则化方法与罚函数法的研究现状；第二章，针对有限极大极小问题，通过研究熵正则化方法与指数(乘子)罚函数方法之间的关系，揭示熵正则方法的数学本质；第三章将极大熵方法推广到一般不等式约束优化问题上，建立了拉格朗日正则化方法；第四章利用第三章建立的拉格朗日正则化方法，给出一种构造罚函数的统一框架，并通过具体的罚和障碍函数例子加以说明。
本文下篇集中建立求解线性规划的有效原-对偶算法。在各种内点法里，最
成功的也是最为有效的当属原一对偶路径跟踪算法.但现有的算法几乎都是基于
标准摄动方程组，即标准线性规划对数障碍问题的卜K-T系统，建立起来的。
本文从三个不同的角度来改造此摄动方程组，并建立相应的原一对偶路径跟踪内
点和非内点算法。
经过对标准中心化方程Xs二户。实施代数等价变换，我们得到了一个新的扰
动K一K一T方程组，并针对具体的幕变换，由此摄动方程组给出了彭积明等人在缩
减大步算法的复杂性界限时所使用的牛顿方程。在这一事实和彭等人的出色结果
激发下，我们利用一个特殊的代数变换一对数变换，建立一个不可行大步原一对偶
路径跟踪内点算法。该算法在遵循中心路径的同时，沿着原一对偶嫡函数的最速
下降方向达到线性规划的原一对偶解集。另外，基于min一Inax本身所具有的“均
化”作用，我们定义了一个新的邻近度量函数，并以其最优性条件作为中心化方
程。其目的是在摄动方程本身建立一种自调节机制，以使牛顿方向能够根据上一
次迭代点的信息在各个互补对之间作出自适应的调整。前述的两种方法是针对扰
动K一K一T系统进行的，而本文的另一种方法是采用NCP函数，直接将标准线性规
划K一K一T条件化为一个不含内点约束的等价方程组，以此改造标准摄动方程组。
下篇由后四章组成。第五章简单回顾了线性规划及内点法，并重点介绍了原
一对偶路径跟踪内点算法。第六章研究了对标准中心化方程实施代数等价变换的
作用，并特别就对数变换情形，建立一个不可行大步原一对偶路径跟踪内点算法，
同时给出其收敛性及复杂性界限分析。第七章，通过构造一个新的邻近度量函数，
提出一个具有自调节功能的原一对偶路径跟踪内点算法，并将其与线性规划软件
LIPSOL和彭等人的M。IPM进行数值比较，证实了该算法的有效性;第八章，基
于NCP函数及其光滑函数，建立求解线性规划的非内点原一对偶路径跟踪算法，
并给出相应的全局及局部收敛性分析。
This dissertation is devoted to studying Lagrangian regularization approach and primal-dual algorithms for linear programming, of which the former is a kind of special smoothing methods that provide a basis for developing the primal-dual interior point and non-interior point algorithms for linear programming.
Maximum Entropy Method is an effective smoothing one for the finite min-max problem, which, by adding Shannon's informational entropy as a regularizing term to the Lagrangian function of min-max problem, yields a smooth function that uniformly approaches the non-smooth max-valued function. Due to the excellent properties of this smooth function, this method is extensively applied to many kinds of optimization problems.
In this thesis, we extend the entropy regularization method in two ways: from the min-max problem to general inequality constrained optimization problems and from the entropy function to more general functions. To circumvent the non-differentiable
difficulty caused by the positive homogeneously function that is involved in an equivalent unconstrained formulation
for general inequality constrained optimization problems, we turn to the classical Lagrangian function and redefine M (x) by a conic optimization problem with the
Lagrangian as the objective function. When adding an entropy function as regularizing term to the Lagrangian function, we obtain a smooth approximate function for M(x) , which turns out to be the exponential penalty function.
Furthermore, when replacing the entropy function by a general separate multiplier function, we develop a new regularization approach, referred to as Lagrangian regularization approach. This approach does not only provide a unified smoothing
technique for the non-differentiable M(x) and but also offers a unified
framework for constructing penalty functions, whereby building a bridge between the penalty functions and the classical Lagrangian.
The first part of this dissertation is composed of four chapters, concentrating on the study for Lagrangian regularization approach. The first chapter is the introduction for the entropy regularization method and penalty function method. The second chapter reveals the mathematical essence of entropy regularization method for the finite min-max problem, through exploring the relationship between entropy regularization method and exponential penalty function method. The third chapter extends Maximum Entropy Method to a general inequality constrained optimization problem and establishes the Lagrangian regularization approach. The fourth chapter presents a unified framework for constructing penalty functions by virtue of the Lagrangian regularization approach, and illustrates it by some specific penalty and barrier function examples.
The second part of this dissertation is committed to developing the effective primal-dual path following algorithms for linear programming. Among various types of interior point methods, the so-called primal-dual path following algorithm is the most successful and effective one. However, the existing algorithms are almost based on the standard perturbed system, namely the K-K-T system of logarithmic barrier problem for standard linear programming. In this thesis, we modify the perturbed system from three different angles and develop the corresponding primal-dual path following interior point and non-interior point algorithms.
By making algebraically equivalent transformation for the standard centering equation Xs=μe, we obtain a new system of perturbed K-K-T equations and, for
specific power transformation, recover the Newton equations that are recently used by J. M. Peng et al to show a lower polynomial complexity bound for large-update algorithm. Motivated by this fact and Peng's promising result, we utilize a special algebraic transformation, namely logarithmic transformation, to establish a non-infeasible long-step primal-dual path following algorithm. This algorithm arrives at the primal-dual solution set along the steepest descent direction of primal-dual
引文
[1] 李兴斯，非线性极大极小问题的一个有效解法，科学通报，1991，36：1448-1450．
[2] X. S. Li and S. C. Fang, On the entropic regularization method for solving min-max problems, Mathematical Methods of Operations Research, 1997, 46: 119-130.
[3] E. T. Jaynes, Information theory and statistical mechanics, Physics Review, 1957, 106: 620-630.
[4] S. Kullback and R. A. Leibler, On information and sufficiency, Annals of Mathematical Statistics, 1951, 22: 79-86.
[5] J. M. Peng, A smoothing function and its applications, Reformulation-Nonsmooth, Piecewise Smooth, Semismooth and Smoothing Methods, Edited by M. Fukushima and L. Qi, Kluwer Academic Publisher, 1998, 293-316.
[6] J. M. Peng and Z. H. Lin, A non-interior-point continuation method for generalized linear complementarity problems, Mathematical Programming, 1999, 86: 533-563.
[7] L. Qi and D. F. Sun, Smoothing function and a smoothing Newton method for complementarity and variational inequalities problem, School of Mathematics, University of New South Wales, Sydney, October 1998.
[8] 彭红波，刘三阳，求解非线性规划问题的极大熵外点法，现代电子技术，1998，8-12．
[9] 王雪华，秦学志，多目标规划的极大熵方法，计算数学，1996，3：305-308．
[10] 吴至友，于辉，彭建文，关于下层规划带线性约束的二层规划问题，重庆师范学院学报(自然科学版)，2000，3：24-27．
[11] 吴至友，单阶段随机规划的一种近似计算方法，重庆师范学院学报(自然科学版)，2000．1：23-28．
[12] X. L. Sun and D. Li, Asymptotic strong duality for bounded integer programming: A logarithmic-exponential dual formulation, Mathematics of Operations Research, 2000, 4: 625-644.
[13] A. Ben-Tal and M. Teboulle, A smoothing technique for non-differentiable
optimization problems, Lecture notes in mathematics 1405, Springer-Verlag, 1989, 1-11．
[14] D. P. Bertsekas, Approximation procedures based on the method of multipliers, Journal of Optimization Theory and Applications, 1977, 23: 487-510．
[15] A. V. Fiacco and G. P. McCormic, Nonlinear Programming: Sequential Unconstrained Minimization Techniques, SIAM, Philadephia, 1990．
[16] N. K. Karmarkar, A new polynomial-time algorithm for linear programming, Combinatorica, 1984, 4: 373-395．
[17] P. E. Gill, W. Murray and M. A. Saunders et al, On projected Newton barrier methods for linear programming and an equivalence to Karmarkar' s projective method, Mathematical Programming, 1986, 36: 183-209．
[18] S. J. Wright, Primal-Dual Interior-Point Methods, SIAM, Philadelphia, USA, 1997．
[19] Y. Ye, Interior-Point Algorithms, Theory and Analysis, John Wiley & Sons, Chichester, UK, 1997．
[20] C. Roos, T. Terlaky, and J.-Ph. Vial, Theory and Algorithms for Linear Optimization. An Interior-Point Approach, John Wiley & Sons, Chichester, UK, 1997．
[21] R. J. Vanderbei and D. F. Shanno, An interior-point algorithm for nonconvex nonlinear programming, Statistics and Operations Research, Princeton University, SOR-97-21．
[22] F. Alizadeh, Interior point methods in semidefinite programming with applications to combinatorial optimization, SIAM Journal on Optimization, 1995, 5: 13-51．
[23] J. E. Mitchell and P. M. Pardalos, Interior point method for combinatorial optimization, Manuscript.
[24] R. Cominetti and J. San Martin, Asymptotic analysis of the exponential penalty trajectory in linear programming, Mathematical Programming, 1994, 67: 169-187．
[25] R. Cominetti and J. P. Dussault, Stable exponential-penalty algorithm with
superlinear convergence, Journal of Optimization Theory and Application, 1994, 83: 285-309．
[26] A. Auslender, Penalty and barrier methods: a unified framework, SIAM Journal on Optimization, 1999, 10: 211-230．
[27] A. Auslender, Asymptotic analysis for penalty and barrier methods in convex and linear programming, Mathematics of Operations Research, 1997, 22: 43-62．
[28] R. T. Rockafellar, Convex Analysis, Princeton University Press, Princeton, New Jersey, 1970．
[29] J. B. Hiriart-Urruty and C. Lemarechal, Convex Analysis and Minimization Algorithm, Springer-Verlag, Berlin, 1993．
[30] D. P. Bertsekas, Convexity, Duality and Lagrange Multipliers, Lecture Notes in Massachusetts Institute of Technology, Spring 2001．
[31] E. Ploak, On the mathematical foundations of non-differentiable optimization, SIAM Review, 1987, 29:21-89．
[32] E. Ploak, J. E. Higgins and D. Q. Maynes, A barrier function method for minimax problems, Mathematical Programming, 1992, 54: 155-176．
[33] R. T. Rockafellar, Computational schemes for large-scale problems in extended linear-quadratic programming, Mathematical Programming, 1990, 48: 447-474．
[34] Charalambous and A. R. Conn, An efficient method to solve the minimax problem directly, SIAM Journal on Numerical Analysis, 1978, 15: 162-187．
[35] E. Ploak, J. E. Higgins and D. Q. Maynes, Superlinear convergent algorithm for minimax problem, Journal of Optimization Theory and Application, 1991, 69: 406-439．
[36] S. P. Han, Variable metric methods for minimizing a class of non-differentiable functions, Mathematical Programming, 1981, 20: 1-13．
[37] R. Fletcher, A model algorithm for composite nondifferentiable optimization problem, Mathematical Programming Study, 1982, 17: 67-76．
[38] W. Murry and M. L. Overton, A projected Lagrangian algorithm for nonlinear minimax optimization, SIAM Journal on Scientific and Statistical Computing, 1980, 1: 345-370．
[39] M. C. Gígola, Techniques de regularization pour un problem d optimisation non-differentiable, Thèse, Université de Provence, Provence, France, February, 1975.
[40] C. Gígola and S. Gomez, A regularization method for solving finite convex min-max problem, SIAM Journal on Numerical Analysis, 1990, 27: 1621-1634.
[41] O. Barrientos, A global regularization method for solving the finite min-max problem, Computational Optimization and Applications, 1998, 11: 277-295.
[42] 杨庆之，熵函数法中的计算技巧，数值计算与计算机应用，2000，4：314-320．
[43] 李兴斯，解非线性规划的一个可微‘准’精确惩罚函数方法，科学通报，1991，19：1451-1453．
[44] M. Q. Pinar and S. A. Zenios, On smoothing exact penalty functions for convex constrained optimization, SIAM Journal on Optimization, 1994, 4: 456-511.
[45] 李兴斯，解非线性规划的凝聚函数法，中国科学(A)，1991，12：1283-1288．
[46] 陈国庆，赵素芬，熵函数法的数学理论，计算数学，1999，4：398-405．
[47] P. Tseng and D. P. Bertsekas, On the convergence of the exponential multiplier method for convex programming, Mathematical Programming, 1993, 60: 1-19.
[48] S. C. Fang and H. 5. J. Tsao, On the entropic perturbation and exponential penalty methods for linear programming, Journal of Optimization Theory and Applications, 1996, 89: 461-466.
[49] O. L. Mangasarian, A Newton method for linear programming, Technical Report, Computer Science Department, University of Wisconsion, Madison.
[50] C. Kanzow, H. D. Qi and L. Q. Qi, On the minimum norm solution of linear programs, Preprint, University of Hamburg, Hamburg, 2001. Journal of Optimization Theory and Applications, to appear.
[51] R. R. Polyak, Modified barrier functions (theory and methods), Mathematical Programming, 1992, 54: 177-222.
[52] M. Halická and M. Hamala, Duality of transformation functions in the interior point methods, Acta Math. Univ. Comenianae, LXV (1996), 229-245.
[53] Y. E. Nesterov and A. S. Nemirovskii, Interior point polynomial algorithms in convex programming, SIAM Studies in Applied Mathematics, SIAM, Philadelphia,
USA, 1994．
[54] D. P. Bertsekas, Constrained Optimization and Lagrange Multiplier Methods, Academic Press, New York, 1982．
[55] A. N. Isuem, B. Svaiter and M. Tebollue, Entropy-like proximal methods in convex programming, Mathematics of Operations Research, 1994, 19: 790-814．
[56] A. Ben-Tal and L. Yuzefovich and M. Zibulevsky, Penalty/barrier multiplier methods for minmax and constrained smooth convex programs, Research report 9, Optimization Laboratory, Faculty of Industrial Engineering and Management, Israel Institute of Technology, Haifa, Israel.
[57] A. Ben-Tal and M. Zibulevsky, Penalty/barrier multiplier methods for convex programming problems, SIAM Journal on Optimization, 1997, 7: 347-366．
[58] M. Teboulle, Entropic proximal mappings with application to nonlinear programming, Mathematics of Operations Research, 1992, 17: 670-690．
[59] R. A. Polyak and M. Teboulle, Nonlinear rescaling and proximal-like methods in convex optimization, Mathematical Programming, 1997, 76: 265-284．
[60] L. Bregman, The relaxation method for finding the common point of convex sets and its application to the solution of problems in convex programming, USSR Computational Mathematics and Mathematical Physics, 1967, 7: 201-217．
[61] I. Csiszar, Information-type measure of difference of probability distributions and indirect observations, Studia Sci. Math. Hungar., 1967, 2: 299-318．
[62] R. T. Rockafellar, A dual approach to solving nonlinear programming problems by unconstrained minimization, Mathematical Programming, 1973, 5: 354-373．
[63] G. B. Dantzig, Linear Programming and Extensions, Princeton University Press, Princeton, N. J., 1963．
[64] K.-H. Borgwardt, The Simplex Method. A Probability Analysis, Springer Verlag, Berlin, 1987．
[65] V. Klee and G. Minty, How good is the simplex method?, In Inequalities III, O. Sisha, ed., Academic Press, New York, NY, 1972．
[66] L. G. Khachiyan, A polynomial algorithm for linear programming, Soviet Math.
Dokl., 1979, 20: 191-194．
[67] L. G. Khachiyan, Polynomial algorithms in linear programming, USSR Computational Mathematics and Math. Phys., 1980, 20: 53-72．
[68] N. Shor, Utilization of the operation of space dilatation in the minimization of convex functions, Kibernetika, 1970, 1: 6-12; English translation: Cybernetics, 6: 7-15．
[69] D. B. Yudin and A. S. Nemirovskii, Informational complexity and effective methods of solution for convex extremal problems, Ekonomika i Matematicheski Metody, 1976, 12: 357-369．
[70] M. Todd and B. Burrell, An extension of Karmarkar' s algorithm for linear programming using dual variables, Algorithmica, 1986, 1: 409-424．
[71] K. R. Frisch, Principles of linear programming-with particular reference to the double gradient form of the logarithmic potential method, Memorandum of October 18, 1954, University Institute of Economics, Oslo.
[72] K. R. Frisch, The logarithmic potential method of convex programming, Memorandum of May 13, 1955, University Institute of Economics, Oslo.
[73] P. Huard, Resolution of mathematical programming with nonlinear constraints by the method of centers, in Nonlinear Programming, J. Abadie, ed., North Holland, Amsterdam, 1967, 207-219．
[74] I. I. Dikin, Iterative solution of problems of linear and quadratic programming, Soviet Math. Dokl., 1967, 8: 674-675．
[75] I. I. Dikin, On the speed of an iterative process, Upravlyaemye Sistemy, 1974, 12: 54-60．
[76] J. Renegar, A polynomial time algorithm based on Newton' s method for linear programming, Mathematical Programming, 1988, 40: 59-94．
[77] G. Sonnevend, An analytical center for polyhedrons and new classes of global algorithms for linear (smooth, convex) programming, in Lecture Notes Control Inform. Sci. 84, Springer-Verlag, New York, NY, 1985, 866-876．
[78] N. Megiddo, Pathways to the optimal set in linear programming, in Progress in Mathematical Programming Interior Point and Related Methods, N. Megiddo,
ed., Springer-Verlag, Berlinm 1989．
[79] C. C. Gonzaga, Path-following methods for linear programming, SIAM Review, 1992, 2: 167-224．
[80] R. D. C. Monteiro and I. Adler, Interior point path-following primal-dual algorithms. Part I: Linear programming, Mathematical Programming, 1989, 44: 27-41．
[81] K. Tanabe, Centered Newton method for mathematical programming, in System Modeling and Optimization: Proceedings of the 13th IFIP conference, Lecture Notes in Control and Information systems 113, Berlin, August/September 1987, Springer-Verlag, New York, 1988, 197-206．
[82] M. J. Todd and Y. Ye, A centered projective algorithm for linear programming, Mathematics of Operations Research, 1990, 15: 508-529．
[83] M. Kojima, S. Mizuno and A. Yoshise, A primal-dual interior point algorithm for linear programming, in Progress in Mathematical Programming: Interior Point and Related Methods, N. Megiddo, ed., Springer-Verlag, New York, 1989, 29-47．
[84] M. Kojima, S. Mizuno and A. Yoshise, An O(nL) iteration potential reduction algorithm for linear complementarity problems, Mathematical Programming, 1991, 50: 331-342．
[85] S. Mehrotra, On the implementation of primal-dual interior point method, SIAM Journal on Optimization, 1992, 2: 575-601．
[86] A. J. Goldman and A. W. Tucker, Theory of linear programming, in Linear Equalities and Related Systems, H. W. Kuhn and A. W. Tucker, eds., Princeton University Press, Princeton, N. J., 1956, 53-97．
[87] S. Mehrotra and Y. Ye, Finding an interior point in the optimal face of linear programs, Mathematical Programming, 1993, 62: 497-515．
[88] Y. Ye, On the finite convergence of interior-point algorithms for linear programming, Mathematical Programming, 1992, 57: 325-335．
[89] M. Kojima, N. Megiddo and S. Mizuno, A general framework of continuation
methods for complementarity problems, Mathematics of Operation Research, 1993, 18: 945-963．
[90] Y. Zhang, On the convergence of a class of infeasible-interior-point methods for the horizontal linear complementarity problem, SIAM Journal on Optimization, 1994, 4: 208-227．
[91] Y. Ye, M. J. Todd and S. Mizuno, An O(nL)-iteration homogeneous and self-dual linear programming algorithm, Mathematics of Operations Research, 1994, 19: 208-227．
[92] J. Peng, C. Roos and T. Terlaky, New and efficient large-update interior-point method for linear optimization, Journal of Computational Technologies, 2001, 4: 61-80．
[93] J. Peng, C. Roos, and T. Terlaky, A new class of polynomial primal-dual methods for linear and semidefinite optimization, Manuscript.
[94] J. Peng, C. Roos and T. Terlaky, Self-regular functions and new search directions for linear and semi-definite optimization, Mathematical Programming, 2002, 93: 129-171．
[95] J. Peng, C. Roos and T. Terlaky, Self-Regularity: A New Paradigm for Primal-Dual Interior-Point Algorithms, Princeton University Press.
[96] K. A. McShane, C. L. Monma and D. F. Shanno, An implementation of a primal-dual interior point method for linear programming, ORSA Journal on Computing, 1989, 1: 70-83．
[97] S. Mizuno, An O(n3L)algorithm using a sequence for linear complementarity problems, Journal of the Operations Research Society of Japan, 1990, 33: 66-75．
[98] Y. Zhang and R. A. Tapia, Superlinear and quadratic convergence of primal-dual interior point methods for linear programming revisited, Journal of Optimization Theory and Applications, 1992, 73: 229-242．
[99] B. Jansen, C. Roos, T. Terlaky and J.-Ph. Vial, Primal-dual algorithms for linear programming based on the logarithmic barrier method, Journal of Optimization Theory and Applications 1994, 83: 1-26．
[100] G. Zhao, Large-step path-following primal-dual algorithms for linear programming, Research Report 613, National University of Singapore, Department of Mathematics, 10 Kent Ridge Crescent, Singapore 0511, March 1994．
[101] L. Tuncel and M. J. Todd, On the interplay among entropy, variable metrics and potential functions in interior-point algorithms, Computational Optimization and Applications, 1997, 8: 5-19．
[102] Xiaohang Zhu, Implementing the New Self-Regular Proximity Based IPMs, Master Thesis, June, 2002, McMaster University.
[103] Qirong Miao, Implementation of the New Interior-Point Methods, Master Thesis,September, 2002, McMaster University.
[104] Jiu Ding and Tien-Yien Li, An algorithm based on weighted logarithmic barrier functions for linear complementarity problems, The Arabian Journal for Science and Engineering, 1990, 15: 679-685．
[105] Y. Zhang, User's guide to Lipsol: linear-programming interior point solvers V 0． 4． Interior point methods, Optimization Methods and Software, 1991, 12: 385-396．
[106] R. J. Vanderbei and D. F. Shanno, An interior-point algorithm for nonconvex nonlinear programming, Computational Optimization and Applications, 1999, 13: 231-252．
[107] J. E. Mitchell, P. M. Pardalos and M. G. C. Resender, Interior point method for combinatorial optimization, Handbook in Combinatorial Optimization, Kluwer Academic Publishers, 1998．
[108] L. Vandenberghe and S. Boyd, Semidef inite Programming, SIAM Review, 1996, 38: 49-95．
[109] S. Engelke and C. Kanzow, Predictor-corrector smoothing methods for the solution of linear programs, Hamburger Beitrage zur Angewandten Mathematik, March 2000, Preprint 153．
[110] S. Engelke and C. Kanzow, Improved smoothing-type methods for the solution of linear programs, Numerische Mathematik, to appear.
[111] S. Billups and K. G. Murty, Complementarity problems, Journal of Computational
and Applied Mathematics, 2000, 124: 303-318．
[112] M. C. Ferris and C. Kanzow, Complementarity and related problems: a survey, Technical Report 98-17, University of Wisconsin, USA., 1998．
[113] P. Harker and J. Pang, Finite-dimensional variational inequality and nonlinear complementarity problem: A survey of theory, algorithm and applications, Mathematical Programming, 1990, 48: 339-353．
[114] O. L. Mangasarian, Equivalence of the complementarity problem to a system of nonlinear equations, SIM Applied Mathematicas, 1976, 31: 89-92．
[115] A. Fischer, A special Newton-type optimization, Optimization, 1992, 24: 269-284．
[116] S. Engelke and C. Kanzow, On the solution of linear programs by Jacobian smoothing methods, Annals of Operations Research, Optimization and Numerical Algebra, to appear.
[117] B. Chen, X. Chen and C. Kanzow, A penalized Fischer-Burmeister NCP-function: theoretical investigation and numerical results, Mathematical Programming, 2000, 88: 211-216．
[118] B. Chen and P. T. Marker, A non-interior-point continuation method for linear complementarity problems, SIAM Journal on Matrix Analysis and Applications, 1993, 14: 1168-1190．
[119] C. Kanzow, Some non-interior continuation methods for linear complementarity problems, SIAM Journal on Matrix Analysis and Applications, 1996, 17:851-868．
[120] D. F. Sun and L. Q. Qi, On NCP-functions, Computational Optimization and Applications, 1999, 13: 201-220．
[121] Xingsi Li, An entropy-based aggregate method for min-max optimization, Engineering Optimization, 1992: 18, 277-285．
[122] C. Chen and O. L. Mangasarian, A class of smoothing functions for nonlinear and mixed complementarity problems, Computational Optimization and Applications, 1996, 5: 97-138．
[123] H. Jiang, Smoothed Fisher-Burmeister equation methods for the complementarity problem, Technical Report. Department of Mathematics, University of Melbourne,
Melbourne, Australia, June 1997．
[124] C. Kanzow and H. Pieper, Jacobian smoothing methods for non-linear complementarity problems,SIAM Journal on Optimization, 1999, 9: 342-373．
[125] B. Chen and N. Xiu, A global linear and local quadratic non-interior point continuation method for nonlinear complementarity problems based on Chen-Mangasarian smoothing functions, SIAM Journal on Optimization, 1999, 9: 605-623．
[126] J. V. Burke and S. Xu, A non-interior predictor-corrector path-following algorithm for the monotone linear complementarity problem, Mathematical Programming, 2000, 87: 113-130．
[127] J. E. Dennis and R. B. Schnabel, Numerical Methods for Unconstrained Optimization and Nonlinear Equations. Prentice-Hall, Englewood Cliffs, NJ, 1983．