互补问题的有效算法研究
|
摘要
本文主要研究求解互补问题的有效算法。从20世纪60年代互补问题的提出到现在，尤其是最近20多年来，互补问题发展非常迅速。并且出现了各种形式的互补问题。互补问题被广泛地应用于工程、经济和运筹学中。对互补问题的研究可以分为理论和算法。前者主要研究问题解的存在性、唯一性、稳定性以及灵敏度分析等性质。后者集中研究如何构造有效算法及其理论分析。本文旨在有效算法方面的研究。
第一章概述了互补问题的各种形式及其在工程、经济和运筹学中的应用，同时分类介绍了求解互补问题的几种主要算法，并将作者的工作穿插在相关算法里做了简要介绍。
第二章首先介绍了信息论中的熵、最大熵原理、最小叉熵原理。然后针对带不等式约束的非线性规划问题，给出一个Lagrange正则化(摄动)方法，该方法有效地克服了线性Lagrange函数难于在对偶变量空间直接求解的困难。文中分别以Shannon熵函数和Kullback叉熵函数作为摄动函数，导出其对偶函数分别是原问题的指数罚函数和指数乘子罚函数。这样就在Lagrange摄动和指数罚函数之间搭起了一座桥梁。然后文中把这种方法应用到有限维极大极小问题的一个等价非线性规划问题，得到了相应的光滑函数，且与用最大熵原则和最小叉熵原则得到的凝聚函数相同。
由于求解线性互补问题的内点法可以看作是线性规划原-对偶内点法的一个自然推广，在第三章开头首先介绍了内点法。然后，基于极大极小问题的均衡作用，构造了一个新的效益函数(势函数)，并以其梯度为零代替一般内点法中的互补条件方程。鉴于该效益函数是非光滑的，不便于操作，使用前一章给出光滑函数做了光滑处理，而得到的光滑效益函数是一个凸函数。与一般内点法中的摄动互补条件相比，其最优性条件含有一组中心化参数。这组参数利用上一个迭代点的信息对当前步向中心路径进行调整，文中称之为自调整作用。基于这组方程，文中建立了一个求解线性互补的不可行内点算法，并分析了它的多项式复杂度。数值结果表明参数起到了自调整作用。
第四章细化了Chen-Xiu求解线性互补问题的一步非内点延拓算法，并且推广到非线性互补问题。得到了与Chen-Xiu同样的全局线性收敛，推广了Chen-Xiu的局部超线性收敛到局部二次收敛。在一定意义下，光滑化函数是延拓算法的核心。本章尝试用叉熵函数来光滑化极小化NCP函数。建立了一个求解单调线性互补问题的非内点延拓算法。其数值结果非常好，部分的好于文中提到的不可行路径跟踪算法。在这一章的最后，把mid(.)函数重新表述，并用Shannon熵函数光滑化。文中讨论了得到的光滑函数的性质，给出一个求解一类混合互补问题的非内点预估-校正延拓算法，并分析了其全局收敛性。
基于非线性互补问题的一个等价不动点格式，第五章分别用Shannon熵函数和Kullback熵函数光滑化max函数。文中分别给出了两个迭代算法，并与Paul Tseng的外梯度投影法进行了数值比较。
在内点法中，采用不同的代数等价路径形成了通向最优解的不同轨迹。虽然Fang-Puthenpure、Tuncel-Todd、Wright等都认识到这个问题的重要性，但目前这方面的工
大连理工大学博士论文
作还很少。讨论了基于对数变换的代数等价路径，并构造了一个不可行的大步长路B
踪算法，并分析了它的复杂度，而且数值结果也是令人满意的。与此同时，分析了该方
法与Peng等人近期工作的联系，发现互补抓的右端可表示成嫡函数的负梯度。并且
证明，由Peng等人提出的自正则邻近度量函数方法（缩减了大步长 民踪算法的复
杂度），也可以通过等价代数变换得到。
第七章通过计算验证了文中提出的几个算法。首先，对文中提出的不可行路经跟
踪算法3．3、算法6．1与Zhans Yin的不可行路经R瞬算法进行了数值比较。其次，给
出了第四章中用Kullback叉嫡光滑化NCP函数的一个非内点延拓算法4．2的数值结果。
最后，对基于 Shannon嫡光滑化和 Kullback叉嫡光滑化的迭代算法与 Paul Tseng的外
梯度法进行了数值比较。
最后，作者总结了全文，并对下一步的研究工作做了展望。
－’·—，’一———－————””’””—”””－—”——”’——－唇
The paper deals with the study of efficient algorithms for complementarity problems (CPs). CPs have been developed very quickly since they appeared in the 60s last century, especially the recent two decades. Many formulations of them were proposed and widely used in engineering, economics and operations research. Roughly speaking, the study of CPs 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 intended to solve the problems efficiently, together with the theoretical analysis of the algorithms.
Different formulations of CPs are introduced in Chapter one, along with various applications in engineering, economics and operations research. Some algorithms for CPs are described. Meanwhile, the thesis work is outlined briefly.
Chapter two introduces the concept of entropy in information theory, maximum entropy principle, and minimum cross-entropy principle. It is difficult to analytically solve the inequality constrained NLPs in the dual space, due to the linear Lagrangian. A perturbed (regularized) Lagrangjan approach is proposed, which provides an analytic solution of the dual variables in terms of primal variables. The applications of Shannon entropy and Kullback's cross-entropy as perturbations are discussed. By maximizing the perturbed Lagrangians in dual space, we obtain the exponential penalty function and exponential multiplier penalty function, respectively, for inequality constrained NLPs. Thus, a bridge is built between the Lagrange perbuation methods and the exponential penalty methods. Then the perturbation methods are used to an equivalent NLP problem of minmax problems and the resulted smooth functions are just aggregate functions obtained by maximum entropy principle and minimum cross-entropy principle, respectively.
Chapter three introduces the development of interior-point methods for linear programs first since the interior-point methods for LCPs can be looked as a natural extension of primal-dual interior-point methods for LPs. A new merit function (potential function) is constructed in Chapter three, based on the balanced effect of the min-max problem. Because of the non-smoothness, Shannon entropy is used to smooth the merit function. The resulted smooth merit function is convex and its optimal conditions contain a set of extra parameters, compared with the usual perturbed complementarity conditions. The set of parameters is updated by using the information of the last iteration and brings about the centering effect towards the central path, which was called the self-adjusting effect. An infeasible path-following algorithm is constructed, and its polynomial complexity is analyzed. Numerical tests show the self-adjusting effect of the parameters.
The one-step non-interior continuation method of Chen and Xiu for LCPs is refined in Chapter four. It is extended to NLPs. The control parameter is replaced by the smoothing parameter in the perturbation term of Newton Step. The convergence of the refined non-interior
continuation method for NCPs is analyzed, the same global linear convergence as Chen-Xiu's is obtained. Locally quadratic convergence is also obtained, compared with the locally superlinear convengence of Chen-Xiu's. Smoothing functions, in some sense, are the center in continuation methods. Kullback's cross-entropy function is tried to smooth the minimal NCP-function and a non-interior continuation method is constructed for LCPs. Its numerical performance is very good, even better partly than the infeasible path-following methods in chapter three and chapter six. At last of the Chapter, the mid(.) function is reformulated. Shannon entropy function is used to smoothing it. A non-interior predictor-corrector continuation method is built for a class of mixed complementarity problems. Its global convergence is analyzed.
Shannon entropy and Kullback's cross-entropy are used to smooth the max function respectively in a fixed-point formulation of NC
第一章概述了互补问题的各种形式及其在工程、经济和运筹学中的应用，同时分类介绍了求解互补问题的几种主要算法，并将作者的工作穿插在相关算法里做了简要介绍。
第二章首先介绍了信息论中的熵、最大熵原理、最小叉熵原理。然后针对带不等式约束的非线性规划问题，给出一个Lagrange正则化(摄动)方法，该方法有效地克服了线性Lagrange函数难于在对偶变量空间直接求解的困难。文中分别以Shannon熵函数和Kullback叉熵函数作为摄动函数，导出其对偶函数分别是原问题的指数罚函数和指数乘子罚函数。这样就在Lagrange摄动和指数罚函数之间搭起了一座桥梁。然后文中把这种方法应用到有限维极大极小问题的一个等价非线性规划问题，得到了相应的光滑函数，且与用最大熵原则和最小叉熵原则得到的凝聚函数相同。
由于求解线性互补问题的内点法可以看作是线性规划原-对偶内点法的一个自然推广，在第三章开头首先介绍了内点法。然后，基于极大极小问题的均衡作用，构造了一个新的效益函数(势函数)，并以其梯度为零代替一般内点法中的互补条件方程。鉴于该效益函数是非光滑的，不便于操作，使用前一章给出光滑函数做了光滑处理，而得到的光滑效益函数是一个凸函数。与一般内点法中的摄动互补条件相比，其最优性条件含有一组中心化参数。这组参数利用上一个迭代点的信息对当前步向中心路径进行调整，文中称之为自调整作用。基于这组方程，文中建立了一个求解线性互补的不可行内点算法，并分析了它的多项式复杂度。数值结果表明参数起到了自调整作用。
第四章细化了Chen-Xiu求解线性互补问题的一步非内点延拓算法，并且推广到非线性互补问题。得到了与Chen-Xiu同样的全局线性收敛，推广了Chen-Xiu的局部超线性收敛到局部二次收敛。在一定意义下，光滑化函数是延拓算法的核心。本章尝试用叉熵函数来光滑化极小化NCP函数。建立了一个求解单调线性互补问题的非内点延拓算法。其数值结果非常好，部分的好于文中提到的不可行路径跟踪算法。在这一章的最后，把mid(.)函数重新表述，并用Shannon熵函数光滑化。文中讨论了得到的光滑函数的性质，给出一个求解一类混合互补问题的非内点预估-校正延拓算法，并分析了其全局收敛性。
基于非线性互补问题的一个等价不动点格式，第五章分别用Shannon熵函数和Kullback熵函数光滑化max函数。文中分别给出了两个迭代算法，并与Paul Tseng的外梯度投影法进行了数值比较。
在内点法中，采用不同的代数等价路径形成了通向最优解的不同轨迹。虽然Fang-Puthenpure、Tuncel-Todd、Wright等都认识到这个问题的重要性，但目前这方面的工
大连理工大学博士论文
作还很少。讨论了基于对数变换的代数等价路径，并构造了一个不可行的大步长路B
踪算法，并分析了它的复杂度，而且数值结果也是令人满意的。与此同时，分析了该方
法与Peng等人近期工作的联系，发现互补抓的右端可表示成嫡函数的负梯度。并且
证明，由Peng等人提出的自正则邻近度量函数方法（缩减了大步长 民踪算法的复
杂度），也可以通过等价代数变换得到。
第七章通过计算验证了文中提出的几个算法。首先，对文中提出的不可行路经跟
踪算法3．3、算法6．1与Zhans Yin的不可行路经R瞬算法进行了数值比较。其次，给
出了第四章中用Kullback叉嫡光滑化NCP函数的一个非内点延拓算法4．2的数值结果。
最后，对基于 Shannon嫡光滑化和 Kullback叉嫡光滑化的迭代算法与 Paul Tseng的外
梯度法进行了数值比较。
最后，作者总结了全文，并对下一步的研究工作做了展望。
－’·—，’一———－————””’””—”””－—”——”’——－唇
The paper deals with the study of efficient algorithms for complementarity problems (CPs). CPs have been developed very quickly since they appeared in the 60s last century, especially the recent two decades. Many formulations of them were proposed and widely used in engineering, economics and operations research. Roughly speaking, the study of CPs 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 intended to solve the problems efficiently, together with the theoretical analysis of the algorithms.
Different formulations of CPs are introduced in Chapter one, along with various applications in engineering, economics and operations research. Some algorithms for CPs are described. Meanwhile, the thesis work is outlined briefly.
Chapter two introduces the concept of entropy in information theory, maximum entropy principle, and minimum cross-entropy principle. It is difficult to analytically solve the inequality constrained NLPs in the dual space, due to the linear Lagrangian. A perturbed (regularized) Lagrangjan approach is proposed, which provides an analytic solution of the dual variables in terms of primal variables. The applications of Shannon entropy and Kullback's cross-entropy as perturbations are discussed. By maximizing the perturbed Lagrangians in dual space, we obtain the exponential penalty function and exponential multiplier penalty function, respectively, for inequality constrained NLPs. Thus, a bridge is built between the Lagrange perbuation methods and the exponential penalty methods. Then the perturbation methods are used to an equivalent NLP problem of minmax problems and the resulted smooth functions are just aggregate functions obtained by maximum entropy principle and minimum cross-entropy principle, respectively.
Chapter three introduces the development of interior-point methods for linear programs first since the interior-point methods for LCPs can be looked as a natural extension of primal-dual interior-point methods for LPs. A new merit function (potential function) is constructed in Chapter three, based on the balanced effect of the min-max problem. Because of the non-smoothness, Shannon entropy is used to smooth the merit function. The resulted smooth merit function is convex and its optimal conditions contain a set of extra parameters, compared with the usual perturbed complementarity conditions. The set of parameters is updated by using the information of the last iteration and brings about the centering effect towards the central path, which was called the self-adjusting effect. An infeasible path-following algorithm is constructed, and its polynomial complexity is analyzed. Numerical tests show the self-adjusting effect of the parameters.
The one-step non-interior continuation method of Chen and Xiu for LCPs is refined in Chapter four. It is extended to NLPs. The control parameter is replaced by the smoothing parameter in the perturbation term of Newton Step. The convergence of the refined non-interior
continuation method for NCPs is analyzed, the same global linear convergence as Chen-Xiu's is obtained. Locally quadratic convergence is also obtained, compared with the locally superlinear convengence of Chen-Xiu's. Smoothing functions, in some sense, are the center in continuation methods. Kullback's cross-entropy function is tried to smooth the minimal NCP-function and a non-interior continuation method is constructed for LCPs. Its numerical performance is very good, even better partly than the infeasible path-following methods in chapter three and chapter six. At last of the Chapter, the mid(.) function is reformulated. Shannon entropy function is used to smoothing it. A non-interior predictor-corrector continuation method is built for a class of mixed complementarity problems. Its global convergence is analyzed.
Shannon entropy and Kullback's cross-entropy are used to smooth the max function respectively in a fixed-point formulation of NC
引文
[1] S. Billups and K. G. Murty. Complementarity Problems. J. Comp. Appl. Math.,2000, 124:303-318.
[2] M. Fen-is and J. Pang. Engineering and economic applications of complementarity problems. SIAM Review. 1997, 39: 669-713.
[3] X. Chen. Smoothing methods for complementarity problems and their applications: a survey. Journal of the Operations Research Society of Japan. 2000, 43 (1): 32-47.
[4] M.C. Ferris and C. Kanzow. Complementarity and related problems: a surey. Technical Report 98-17, University of Wisconsin, USA,, 1998.
[5] 高自友，修乃华。互补问题算法的新进展。数学进展。1999，28(3)：193-210．
[6] 修乃华，变分与互补问题的非内点算法研究。北方交通大学学报．1999，23(2)：95-100．
[7] P. Harker and J. Pang, Finite-dimensional variational inequality and nonlinear complementarity problem: A survey of theory, algorithms and applications. Mathematical Programming, 1990, 48: 339-353.
[8] F. Tin-Loi and M. C. Ferris. Complementarity problems in engineering mechanics: models and solution. Technical Report, University of New south Wales. USA, 1998.
[9] C. Kanzow and H. Pieper. Jacobian smoothing methods for general nonlinear complementarity problems. SIAM Journal on Optimization. 1999, 9:342-372.
[10] H. Qi and L. Liao. A smoothing Newton method for general nonlinear complemenatrity problems. Computational Optimization and Applications. 2001, 17:231-253.
[11] S.J. Wright, Primal-dual interior-point methods. SIAM Philadephia Hall, USA 1997.
[12] M. Anitescu, G. Lesaja and F. A. Potra. Equivalence between different formulations of the linear complementarity problem. Technical Report. Department of Mathematics, University of Iowa, USA, 1995.
[13] Y.B. Zhao and J. Y. Han. Two interior-point methods for nonlinear P_* (τ)-complementarity problems. Journal on Optimization Theory and Applications. 1999, 103 (3): 659-679.
[14] J. Peng, C. Roos and T. Terlaky, New complexity analysis of primal-dual Newton method for P_* (k) linear complementarity problems. High Performence Optimization Techniques Kluwer Academic Publishers B.V. 249-269, 1999
[15] R.T. Rockafellar. Convex analysis. Princeton University Press. Princeton, 1970.
[16] G. Maier. A quadratic programming approach for certain class of nonlinear structural problems. Mechanica, 1968, 3:121-130.
[17] A. Klarbring. A mathematical programming approach to three-dimesional contact problems with friction, computational mehtods. Appl.Mech. Engrg. 1986, 58: 175-200.
[18] 钟万勰，张洪武，吴承伟。参变量变分原理及其在工程中的应用。科学出版社，北京，1997。
[19] 李录贤，叶天麟。有限变形粘弹性接触的数学规划方法。固体力学学报。1998，19(1)：9-14。
[20] 李学文，陈万吉。三位接触问题的非光滑算法。计算力学学报。2000，17(1)：43-52。
[21] 李录贤，沈亚鹏，叶天麟．摩擦解出问题的数学规划解法。应用力学学报。1998，第15卷第二期：49-56．
[22] M. Florian. Nonlinear cost network models in transportation analysis. Mathematical Programming. 1986, 26: 167-196.
[23] M. Smith. The existence, uniqueness and stability of traffic equilibria. Transportation Research. 1979, 13: 295-304.
[24] S. P. Dirke and M C. Ferris. MCPLIB: a collection of nonlinear complementarity problems. Optimization Methods and Software. 1995, 5:319-345.
[25] L. Mathiesen. An algorithm based on a sequence of linear complementarity problems applied to a Walrasian equilibrium model: an example. Mathematical Programming. 1987, 37:1-18.
[26] B. He. A projection and contraction method for a class linear complementarity problems and its application in convex quadratic programming. Appl. Math. Optim, 1992, 25:247-262.
[27] 何炳生。论求解单调变分不等式的一些投影收缩算法。计算数学。1996，18(1)：54-60．
[28] B. He. On some projection and contraction methods for solving monotone variable inequalities. Applied Mathematics and Optimization. 1997, 35: 69-76.
[29] B. He. A new method for a class of linear variational inequalities. Mathematical Programming. 1994, 66: 137-144.
[30] 何炳生．一类求解单调变分不等式的隐式方法．计算数学．1998，20(4)：337-344．
[31] 韩乔明，何炳生。解单调异变分不等式的预测-校正法。科学通报。1998，第43卷 第9期：921-924．
[32] 韩德仁，何炳生．Golden,Levitin-Polyak投影法中一个可行步长准则．科学通报．1998，43(9)：921-924．
[33] M. Solodov and P. Tseng. Modified projection-type methods for monotone variational inequalities. SIAM J. Cont Optim., 1996, 34:1814-1830.
[34] 孙德峰．广义非线性互补问题的投影梯度法．计算数学，1995，第19卷，183-194.
[35] 修乃华，王长钰。关于外梯度法的步长准则。计算数学．2000，22(2)：197-208．
[36] Y. Wang, N. Xiu and C. Wang. A new version of extragradient method for variational inequality problems. Computers and Mathematics with Applications. 2001,969-979.
[37] 张培爱，李兴斯。信息熵原理与互补问题的一种迭代算法。甘肃工业大学学报。2002，28(1)：103-107。
[38] M. Kojima, N. Megiddo and S. Mizuno. An O(n~(1/2)L)iteration potential reduction algorithm for linear complementarity problems. Mathematical Programming. 1991,50:331-342.
[39] D. Shannon and E. Simantiraki. An infeasible interior-point method for linear complementarity problems. Technical Report 95-7, 1995.
[40] Yu. E. Nesterov, M. J. Todd. Self-scaled barriers and interior-point methods for convex programming, Mathematics of Operations Research. 1997, 22: 1-42.
[41] F A. Potra and R. Sheng. Superlinear convergence of interior-point algorithms for semidefinite programming. J. Optim. Theory Appl. 1998, 99 (1) :103-119.
[42] M.J. Todd. A study of search directions in primal-dual interior-point methods for semidefinite
programming. Technical Report, School of Operations Research and Industrial Engineering, Comell University, Ithaca, NewYork, February, 1999.
[43] L. Vandenberghe and S. Boyd. Semidefinite programming, SIAM Rev. 1996, 38 (1): 49-95.
[44] J. Jarre and M. Saunders. A practical interior-point method for convex programming. SIAM Journal on Optimization. 1995, 5: 149-171.
[45] R. Monteito, I. Adler and M. Resende. A polynomial-time primal-dual affine scaling algorithm for linear and convex quadratic programming and its power series extension. Mathematics of Operations Research. 1990, 15: 191-214.
[46] C. Gonzaga. Path-following methods for linear programming. SIAM Review. 1992, 34:167-24.
[47] S. Mehrotra. On the implementation of a primal-dual interior-point method. SIAM Journal on Optimization. 1992, 2:575-601.
[48] Y. Ye and K. Anstreicher. On quadratic and O(n~(1/2)L) convergence of a predictor-corrector algorithm for LCP. Mathematical Programming. 1993, 62 (3): 537-551.
[49] C. Gonzaga and M. J. Todd. An O(N(1/2)L)-iteration large-step primal-dual affine algorithm for linear programming. SIAM Joumal on Optimization. 1992, 2: 349-359.
[50] M.J. Todd. The affine scaling direction for linear programming is a limit of projective scaling directions. Linear Algebra and its Applications 1991, 152: 93-105.
[51] F. Potra and S. J. Wright. Interior-point methods. Journal of Computational Mathematical. 2000, 124: 281-302.
[52] Y. Zhang and D. Zhang. On polynomiality of the Mehrotra-type predictor-corrector interior-point algorithms. Mathematical programming. 1995, 68:303-318.
[53] J. Gondzio. Multiple centrality corrections in a primal-dual method for linear programming. Journal on Computational Optimization and Applicaions. 1996, 6: 137-156.
[54] A.S. Barky, R. A. Tapia and Y Zhang. A study of indicators for identifying zeros variables in interior-point methods. SIAM Review. 1994, 36: 45-72.
[55] Y. Ye. On the finite convergence of interior-point algorithms for linear programming. Mathematical Programming. 1992, 57: 325-336.
[56] O. Guler and Y. Ye. Convergence behavior of interior-point algorithms. Mathematical Programming. 1993, 60:215-228.
[57] M.J. Todd. Combining phase Ⅰand phase Ⅱ in a potential reduction algorithm for linear programming. Mathematical Programming. 1993, 59:133-150
[58] P. J. Williams. Effective finite termination procedures in interior-point methods for linear programming. PhD Thesis, 1998. Rice University, USA.
[59] S. J. Wright. An infeasible-interior-point algorithm for linear complementarity problems. Mathematical Programming. 1994, 67(1)29-51.
[60] L. Tuncel and A. Seifi, A constant-potential infeasible-start interior-point algorithm with computational experiments and applications. Computational Optimization and Applications 1998, 9:107-152.
[61] B. Jansen, C. Roos, T. Terlaky and J.-Ph. Vial. Long-step primal-dual target-following algorithms for linear programming. Technical Report 94-46, Delft University of Technology. 1994, The Nertherlands.
[62] J. Peng and T. Terlaky. A dynamic large-update primal-dual interior-point mehtods for linear optimization. Technical Report. Advanced Optimization Laboratory, McMaster University, December 2001, Hamilton, Ontario, Canada..
[63] J. Peng, C. Roos and T. Terlaky. New complexity analysis of the primal-dual Newton method for linear program. Annals of Operations Research. 2000, 99: 23-39.
[64] J. Peng, C. Roos and T. Terlaky. Self-regular proximity and new search directions for linear and semidefinite optimization. Technical Report. Defty University of Technology. The Nertherlands. Septermer 5, 2000.
[65] E. de Klerk, C. Roos, and T. Terlaky. A nonconvex weighted potential function for polynomial target following methods. Annals of OR, 81:3-14, 1998.
[66] Y.Q. Bai, M, Eighami and C. Roos. A new efficient large-update promal-dual interior-point method based on a finite barrier.
[67] M. Kojima, N. Megiddo and S. Mizuno. A primal-dual infeasible-interior-point algorithm for linear programming. Mathematical Programming. 1993, 61: 261-280.
[68] M. Kojima, T. Moma, and A. Yoshise. Global convergence in infeasible-interior-point algorithms. Mathematicla programming. 1994, 65:43-72.
[69] S. Mizuno, M. Kojima and M. Todd. Infeasible-interior-point primal-dual potential-reduction algorithms for linear programmings. SIAM Journal on Optimization. 1995, 5: 52-67.
[70] F.A. Potra. A quadratically convergent predictor-corrector method for solving linear programs from infeasible starting points. Mathematical Programming. 1994, 67, 383-406.
[71] S. J. Wright and Y. Zhang. A superquadratically infeasible-interior-point method for linear complementarity problems. Mathematical Programming. 1996, 73: 269-289.
[72] 何尚录，徐成贤．求解互补问题的不可行内点法及其计算复杂性．中国科学．2002，第30卷第11期：983-989．
[73] 何尚录，徐成贤．求解一类非单调线性互补问题的路径跟踪算法。计算数学。2001，第23卷第3期：298-306．
[74] 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 (1): 208-227.
[75] F.A. Potra and and R. Sheng. Predictor-corrector algorithm for solving p_* (k)-matrix LCP from arbitrary positive starting points. Mathematical Programming, 1996, 76: 223-244.
[76] S. Mehrotra. On the implementation of a primal-dual interior point method. SIAM J. Optim. 1992, 2: 575-601.
[77] Entropy and Optimization. Phd Dissertation of Liverpool University, Liverpool, UK,1987.
[78] Li and Shuchueng Fang. On the entropic regularization method for min max problems with applications. Mathematical Method of Operation research. 1997, 46(1): 119-130.
[79] 李兴斯。解非线性规划的凝聚函数法。中国科学，A辑，1991，第34卷第12期：1476-1473．
[80] A. Templeman X. Li. A maximum entropy approach to constrained non-linear programming.
Engineering Optimization. 1987, 12:191-205.
[81] O. Guler. Limiting behavior of weighted central paths in linear programming. Mathematical Programming. 1994, 65: 347-363.
[82] S. Fang and S. Puthenpura. Linear optimization and extensions-theory and algorithm. 1993, Prentice Hall, USA.
[83] L. Tuncel M. J. Todd, On the interplay among entropy, variable metrics and potential functions in interior-point algorithms. Computational Optimization and Applications, 1997, 8 (1): 5-17.
[84] P. Harker and B. Xiao. Newton method for a class of linear complementarity problems: a B-differentiable equation approach. Mathematical Programming, 1990, 48: 339-357.
[85] A. Fischer. A special Newton-type optimization. Optimization 24, 1992, 269-284.
[86] S. Engelke and C. Kanzow. Predictor-corrector smoothing methods for the solution of linear programs. Preprint 153, Department of Mathematics, Center for Optimization and Approximation, University of Hamburg, Hamburg, March 2000.
[87] B. Chen, X. Chen and C. Kanzow, A penalized Fischer-Burmeister NCP-function: theoretical investigation and numerical results. Mathematical Programming. 2000, 88:211-216.
[88] C. Kanzow. Some noninterior continuation methods for linear complementarity problems. SIAM Journal on Matrix Analysis and Application. 1996, 17: 851-868.
[89] T. De Luca, F. Facchinei and C. Kanzow. A semismooth equation approach to the solution of nonlinear complementarity problems. Mathematical programming. 75, 1996, 407-439.
[90] L. Qi and D. Sun. On NCP-functions. Computational Optimization and Applications. 1999, 13: 201-220.
[91] C. Kanzow, N. Yamashita and M. Fukushima. New NCP-functions and their properties. Journal of Optimization Theory and Applications. 1994, 81: 569-590.
[92] O.L. Mangasarian. Equivalence of the Complemenatrity problem to a system of nonlinear equations. SIAM Applied Mathematics. 1976, 31 (1): 89-92.
[93] F.H. Clark. Optimization and nonsmooth analysis. Willey, New York, 1983.
[94] Robert Mifflin. Simismooth and semiconvex function in constrained optimization. SIAM Journal on Control and Optimization. 1977, 15: 959-972.
[95] L. Qi and J. Sun. A nonsmooth version of Newton method. Mathematical Programming. 1993, 58: 353-367.
[96] C. Kanzow and H. Kleinmichel. A new class of semismooth Newton4ype mehods for nonlinear complementarity problems. Computional Optimization and Applications. 1998, 11: 227-251.
[97] X. Chen, Zuhair Nashed and Liqun Qi. Smoothing methods and semismoth methods for nondifferentiable operator equations. Technical Report.
[98] L. Qi. Convergence of some algorithms for solving nonsmooth equations. Mathematical of Operations Research. 1993, 18: 227-244.
[99] S.M. Robinson. Local structure of feasible sets in nonlinear programming. Part Ⅲ, stability and sensitivity. Mathematical Programming Study, 1987, 30: 45-66.
[100] J. S. Pang. Newtons method for B-differentiable equations. Mathematics of Operations Research. 1990, 15:311-341.
[101] J. Pang. A B-differentiable Equation based globally and locally quadratically convergent algorithm for nonlinear program, complementarity and variational inequality problem. Mathematical Programming. 1991,51:101-131.
[102] D. Ralph. Global convergence of dampted Newtons method for nonsmooth equations via the path search. Mathematics of Operations Research. 1994, 19:352-389.
[103] J. Pang and L. Qi. Nonsmooth equations: Motivation and algorithms. SIAM Journal on Optimization, 1993, 3: 443.
[104] H. Jiang and L. Qi. A new nonsmooth equations approach to nonlinear complementarity problems. SIAM Journal on Control and Optimization. 1997, 35: 178-193.
[105] C. Chen and O. Mangasarian. Smoothing methods for convex inequalities and linear complementarity problems. Mathematical Programming. 1995, 71: 51-69.
[106] C. Chen. Smoothing methods in mathemtical programming. Ph.D Dissertation of University of Wisconsin, Madison, USA.
[107] B. Chen and P. T. Harker. A non-interior-point continuation method for linear complementarity problems, SIAM Journal on Matrix Analysis and Application. 1993, 4:1168-1190.
[108] I.Zang. A smoothing-out technique for rain max Optimization. Mathematical Programming. 1980, 19(1): 61-77.
[109] C. Chen and O. Mangasarian. A class of smoothing functions for nonlinear and mixed complementarity problems. Computation Optimization and Applications, 1996, 5: 97-138.
[110] S.A. Gabriel and J. J. More. Smoothing of mixed complementarity problems. In complementarity and variational problems: state of the art. M C Ferris and J S Pang(Eds). SIAM Philadelphia. 1997, 105-116.
[111] B. Chen and N. Xiu. Superlinear noninterior one-step continuation method for monotone LCP in the absence of strictly complementarity. Journal of Optimization Theory and Applications. 2001, 108 (2):317-332.
[112] L. Qi and X. Chen. A global convergent successive approximation method for severely non-smooth equations. SIAM Journal on Control and Optimization. 1995, 33: 402-418.
[113] L. Qi, D. Sun, and G. Zhou. A new look at smoothing Newton methods for nonlinear complementarity problems and box constrained variational inequalities. Mathematical Programming, 2000, 87: 1-35.
[114] J. Burke and S. Xu. The global linear convergence of a non-interior path-following algorithm for linear complementarity problem. Mathematics of Operation Research,. 1998, 23: 719-734.
[115] S. Xu. The global linear convergence of an infeasible non-interior path-following algorithm for complementarity problems with uniform P-functions. Mathematical Programming, 2000, 87: 501-517.
[116] J. Burke and S. Xu. A non-interior predictor-corrector path following algorithm for the monotone Iinear complementarity problems. Mathematical Programming. 2000, 87:113-130.
[117] B. Chen and N. Xiu. A global linear and local quadratic non-interior continuation method for nonlinear complementarity problems based on Chen-Mangasarian smoothing function. SIAM Journal on Optimization. 1999, 9: 605-623.
[118] J. Peng and Z. Lin. A non-interior-point continuation method for generalized linear complementarity problems. Mathematical Programming. 1999, 86: 533-563.
[119] B. Chen and X. Chen. A global and superlinear continution-smoothing methods for P_0 and R_0 NCP or monotone NCP. SIAM Journal on Optimization. 1999, 9: 624-645.
[120] N. Xiu. The quadratic convegence of a one-step non-interior continuation mehtod for complementarity problems. Seience in China. Series A. 1999, 44 (14): 1483-1488.
[121] D. Li and M. Fukushima. Smoothing Newton and quasi-Newton methods for mixed complementarity problems. Computational Optimization and Aplications. 2000, 17: 203-230.
[122] B. Chen and X. Chen. A global linear and local quadratic continuation smoothing method for variational inequalities with box constraints. Computational Optiomization and Applications. 2000, 17: 131-158.
[123] O. Mangasarian and M. Solodov. Nonlinear complememtarity as unconstrained and constratined minimization. Mathematical Programming. 1993, 62: 277-297.
[124] M. Fukushima. Equivalent differentiable optimization problems and descent methods for asymmetric variational inequality problems[J]. Mathematical Programming, 1992, 53:99-110
[125] N. Yamashita, K. Taji and M. Fukushima. Unconstrained optimization of reformations of variational inequality problems. Journal of Optimization Theory and Application. 1997, 9: 439-456.
[126] J. Peng. Unconstrained optimization methods for generalized nonlinear complementarity and variational inequality problems. Journal of Computational Mathematics, 1996, 14: 99-107.
[127] J. Peng. Equivalent of variational inequationlity problems to unconstrained optimization. Mathematical Programming. 1997, 78: 347-356.
[128] J. Peng. Global methods for variational inequality problems on polyhedral sets, Optimization methods and Software. 1997, 7:110-122.
[129] J. Peng. Global convergent method for variational inequality problems with nonlinear constraints, J. Optimization Theory and Applications, 1997, 95: 419-430.
[130] E.T. Jaynes. Information theory and statistical mechanics. The Physical Review, 1957, 106: 620-630.
[131] A. Ben-Tal and M.Teboulle. A smoothing technique for non-differentiable optimization problems. Lecture Notes in Mathematics, 1405, Springer Verlag. 1989, 1-11.
[132] D. Bertsekas. Approximation procedures based on the method of multipliers. JOTA. 1977, 23: 487-510.
[133] G. D. Pillo and L. Grippo. A smooth method .for the finite minimax problem. Mathematical Programming 1993, 60(6): 187-214.
[134] Y. Censor and S.A.Zenios. Proximal minimization algorithms with D-functions. JOTA. 1992, 73(6):451-464.
[135] M.Teboulle. Entropic proximal mappings with application to nonlinear programming. Mathematics of Operations Research. 1992, 17(6): 670-690.
[136] C. Charalambous and A.R. Conn. An efficient method to solve the minimax problem directly. SIAM J.Numer. Anal. 1978,15 (6): 162-187.
[137] V. Demyanov and V. Malozemov. On the theory of non-linear min-max problems. Russian Math.
Surveys. 1971,26 (6): 57-115.
[138] C. Gigola and S. Gomez. A regularization method for solving the finite convex min-max problem, SIAM J.Numer. Anal.. 1990, 27 (6): 1621-1634.
[139] X. Li. An entropy-based aggregate method for minimax optimization. Engineering Optimization. 1992, 18(6): 277-285.
[140] E R. Barnes. A variant of Karmarkar's algorithm for solving linear programming problems. Mathematical Programming. 1986, 36:174-182.
[141] R. Frend. Polynomial-time algorithms for linear programming based only on primal scaling and projected gradients of a potential function. Mathematical Programming. 1991,51:203-222.
[142] P. E. Gill, W. Murray, M. A. Saunders, J. A. Tomlin and M. H. Wright. On projected Newton barrier methods for linear programming and an equivalence to Karmarkar's projective method. Mathematical Progranuning. 1986, 36:183-209.
[143] L. Adler, N. Karmarkar,M. Resende and A. Veigs. An implementation of Karmarkar's algorithm for linear programming. Mathematical Programming. 1989, 44:297-335.
[144] P. Tseng and Z. Luo. On the convergence of the affine scaling algorithm for degenerate linear programming problems. Mathematical Programming. 1992, 56:301-319.
[145] Y. Ye. Interior-point algorithm: theory and analysis. John Wiley and Sons, New York, 1997.
[146] J. Renagar. A polynomial-time algorithm, based on Newton's method for linear programming. Mathematical programming. 1988, 59-93.
[147] R. Tapia, Y. Zhang and Y. Ye. On the convergence of the iteration sequence in primal-dual interior-point methods. Mathematical programming, 1995, 68:141-154.
[148] S. Mizuno, M.J. Todd, and Y. Ye. On adaptive-step primal-dual interior-point algorithms for linear programming. Mathematics of Operations Research 1993, 18:964-981.
[149] I. J. Lustig, R. E. Marsten and D.F. Shannon. Computational experience with a primal-dual interior-point method for linear complementarity problems. Linear Algebra and its Applications. 1991, 152:191-222.
[150] Y. Ye, M. J. Todd and S. Mizuno, An O(N~(1/2)L)-iteration homogeneous and self-dual linear programming algorithm. Mathematical Programming. 1993, 59: 53-67.
[151] X. Xu, P. F. flung, and Y. Ye. A simplified homogeneous and self-dual linear programming algorithm and its implementation. Annals of Operations Research, 1996, 62: 151-171.
[152] P. Harker and B. Xiao. Newton method for the complementarity problem: A B-differentiable equation approach. Mathematical Programming. 1990, 48:339-357.
[153] S. Robinson. Strongly regular generalized equation. Mathematics of Operatons Research. 1980, 5: 43-62.
[154] L. Qi and J. Sun. A nonsmooth version of Newtons method. Mathematical Programming. 1993, 58: 353-367.
[155] M. Kojima, N. Megiddo, and S. Mizuno. A general framework of continuation methods for complementarity problems. Mathematics of Operation Research, 1993, 18: 945-967.
[156] 李兴斯．一类不可微优化问题的有效解法．中国科学A辑，1994, 第24卷第4期，371-377．
[157] 李兴斯，求解极大极小问题的一个有效解法．科学通报．1991，第36卷：1448-1450．
[158] S. Gabriel. A hybrid smoothing method for mixed nonlinear complementarity problems. Computational Optimization and Application. 1998, 9: 153-173.
[159] H. Jiang. Global convergence analysis of the generalized Newton and Gauss-Newton methods of the Fischer-Burmeister equation for the complementarity problem. Mathematics of Operation Research. 1999, 24: 529-
[160] X. Chen, L. Qi and D. Sun. Global and superlinear convergence of the smoothing Newton method and its application to general box-constrained variational inequalities. Mathematics of Computation. 1998, 67: 519-540.
[161] S. Engelke and C. Kanzow. Improved Smoothing-type Methods for the Solution of Linear Programs. Technical report, University of Hamburg, German, Sep. 22, 2000.
[162] 马昌风。求解线性互补问题的一个新算法．经济数学．1999，16(1)：55-59．
[163] X. Chen and Y. Ye. On homotopy-smoothing methods for variational inequalities. SIAM J. Control and Optimization, 1999, 37: 589.
[164] 孙德峰，韩继业，赵云彬．线性互补问题的阻尼Newton法的有限终止性．应用数学学报．1998，21(1)：148-154．
[165] D. Li and M. Fukushima. Globally convergent Broyden-like methods for semismooth equations and applications to VIP,NCP and MCP. Technical Report of Kyoto. 1999.
[166] K. Hotta, M. Inaba and A. Yoshise. A complexity analysis of a smoothing method using CHKS-functions for monotone linear complementarity problems. Computational Optimization and Aplications. 2000, 17:183-201.
[167] 马昌风. A globally convergent inexact successie approximation method for nonlinear complementarity problems. 数学杂志. 2001,21 (3): 285-289.
[168] 黄正海，韩继业，徐大川，张立平。P_0函数非线性互补问题的非内部连续化算法。．中国科学，A辑．2001，31(6)：488-494．
[169] B. He. On some projection and contration methods for solving monotone variable inequalities. Applied Mathematics and Optimization. 1997, 35: 69-76.
[170] F. Facchinei, A.Fischer, C.Kanzow and J. Peng, A simply constrained optimization reformulation of KKT system arising from variational inequalities. Applied Mathematics and Optimization, 1999, 40: 19-37.
[171] C. Kanzow and H. Jiang. A continuation method for (strongly) monotone variational inequalities. Mathematical Programming, 1998, 81: 140-152.
[172] K. Hotta and A. Yoshise. Global convergence of a class of non-interior-point algorithms using Chen-Harker-Kanzow-Smale functions for nonlinear complementarity problems. Mathematical Programming, 1999, 86:105.
[173] S. Xu. The global linear convergence and complexity of a non-interior path-following algorithm for monotone LCP based on Chen-Harker-Kanzow-Smale smooth funtion, preprint, department if mathematics. University of Washington. 1997.
[174] F. Tin-Loi and M. C. Ferris. Complementarity Problems in Engineering and Mechanics: Models and
Solution. Mathematical Programming Technical Report 99-02, February 1999.
[175] M. C. Ferris and K. Sinapiromsaran. Formulating and Solving Nonlinear Programs as Mixed Complementarity Problems. Mathematical Programming Technical Report 98-21, December 1998.
[176] M. C. Ferris, C. Kanzow and Todd S. Munson. Feasible Descent Algorithms for Mixed Complementarity Problems. Mathematical Programming Technical Report 98-04, March 1998.
[177] S. Billups. Algorithms for Complementarity Problems and Generalized Equations. Mathematical Programming Ph.D. Dissertation of Univerdity of Wiconsin, Madison, USA, 1995.
[178] S. C. Billups and Michael C. Ferris. QPCOMP: A Quadratic Programming Based Solver for Mixed Complementarity Problems. Mathematical Programming 1997, 76:513-532.
[179] O. Barrientos. A global regularization method for solving the finite min-max problems. Computational Optimization and Applications. 1998, 11:277-295.
[180] 唐焕文，张立卫。求解凸规划的一个极大熵方法。科学通报．1994，39(8)：282-284．
[181] 王云诚，唐焕文。求解约束极大极小问题的极大熵方法。高等学校计算数学学报。1999，(2)：132-139。
[182] 唐焕文，张立卫，王雪华。求解一类不可微问题的极大熵方法。计算数学。1993，(3)：268-275。
[183] Marcottle. and H. J. Wu. On the convergence of projection methods: applications to decomposition of affine variational inequalities.
[184] D. Sun. A class of iterative method for solving nonlinear projection equations. J. Optimization Theory and Applications. 1996, 91: 123-140.
[185] J.S. Pang D. Chan. Iteration methods for solving variational and complementarity problems. mathematical programming, 1992, 24:284-313.
[186] 奥特加，莱因博尔特著．多元非线性方程组的迭代数法．朱季纳译．科学出版社，1983年，
[187] Kanzow. Global convergence problems of some iterative methods for linear complementarity problems. SIAM, Joumal on Optimization. 1996, Vol. 6, 326-341.
[188] 陈国庆，陈万吉，冯恩民。三维解出问题非线性互补原理及算法。中国科学A辑。1995，25(11)：1181-1190．
[2] M. Fen-is and J. Pang. Engineering and economic applications of complementarity problems. SIAM Review. 1997, 39: 669-713.
[3] X. Chen. Smoothing methods for complementarity problems and their applications: a survey. Journal of the Operations Research Society of Japan. 2000, 43 (1): 32-47.
[4] M.C. Ferris and C. Kanzow. Complementarity and related problems: a surey. Technical Report 98-17, University of Wisconsin, USA,, 1998.
[5] 高自友，修乃华。互补问题算法的新进展。数学进展。1999，28(3)：193-210．
[6] 修乃华，变分与互补问题的非内点算法研究。北方交通大学学报．1999，23(2)：95-100．
[7] P. Harker and J. Pang, Finite-dimensional variational inequality and nonlinear complementarity problem: A survey of theory, algorithms and applications. Mathematical Programming, 1990, 48: 339-353.
[8] F. Tin-Loi and M. C. Ferris. Complementarity problems in engineering mechanics: models and solution. Technical Report, University of New south Wales. USA, 1998.
[9] C. Kanzow and H. Pieper. Jacobian smoothing methods for general nonlinear complementarity problems. SIAM Journal on Optimization. 1999, 9:342-372.
[10] H. Qi and L. Liao. A smoothing Newton method for general nonlinear complemenatrity problems. Computational Optimization and Applications. 2001, 17:231-253.
[11] S.J. Wright, Primal-dual interior-point methods. SIAM Philadephia Hall, USA 1997.
[12] M. Anitescu, G. Lesaja and F. A. Potra. Equivalence between different formulations of the linear complementarity problem. Technical Report. Department of Mathematics, University of Iowa, USA, 1995.
[13] Y.B. Zhao and J. Y. Han. Two interior-point methods for nonlinear P_* (τ)-complementarity problems. Journal on Optimization Theory and Applications. 1999, 103 (3): 659-679.
[14] J. Peng, C. Roos and T. Terlaky, New complexity analysis of primal-dual Newton method for P_* (k) linear complementarity problems. High Performence Optimization Techniques Kluwer Academic Publishers B.V. 249-269, 1999
[15] R.T. Rockafellar. Convex analysis. Princeton University Press. Princeton, 1970.
[16] G. Maier. A quadratic programming approach for certain class of nonlinear structural problems. Mechanica, 1968, 3:121-130.
[17] A. Klarbring. A mathematical programming approach to three-dimesional contact problems with friction, computational mehtods. Appl.Mech. Engrg. 1986, 58: 175-200.
[18] 钟万勰，张洪武，吴承伟。参变量变分原理及其在工程中的应用。科学出版社，北京，1997。
[19] 李录贤，叶天麟。有限变形粘弹性接触的数学规划方法。固体力学学报。1998，19(1)：9-14。
[20] 李学文，陈万吉。三位接触问题的非光滑算法。计算力学学报。2000，17(1)：43-52。
[21] 李录贤，沈亚鹏，叶天麟．摩擦解出问题的数学规划解法。应用力学学报。1998，第15卷第二期：49-56．
[22] M. Florian. Nonlinear cost network models in transportation analysis. Mathematical Programming. 1986, 26: 167-196.
[23] M. Smith. The existence, uniqueness and stability of traffic equilibria. Transportation Research. 1979, 13: 295-304.
[24] S. P. Dirke and M C. Ferris. MCPLIB: a collection of nonlinear complementarity problems. Optimization Methods and Software. 1995, 5:319-345.
[25] L. Mathiesen. An algorithm based on a sequence of linear complementarity problems applied to a Walrasian equilibrium model: an example. Mathematical Programming. 1987, 37:1-18.
[26] B. He. A projection and contraction method for a class linear complementarity problems and its application in convex quadratic programming. Appl. Math. Optim, 1992, 25:247-262.
[27] 何炳生。论求解单调变分不等式的一些投影收缩算法。计算数学。1996，18(1)：54-60．
[28] B. He. On some projection and contraction methods for solving monotone variable inequalities. Applied Mathematics and Optimization. 1997, 35: 69-76.
[29] B. He. A new method for a class of linear variational inequalities. Mathematical Programming. 1994, 66: 137-144.
[30] 何炳生．一类求解单调变分不等式的隐式方法．计算数学．1998，20(4)：337-344．
[31] 韩乔明，何炳生。解单调异变分不等式的预测-校正法。科学通报。1998，第43卷 第9期：921-924．
[32] 韩德仁，何炳生．Golden,Levitin-Polyak投影法中一个可行步长准则．科学通报．1998，43(9)：921-924．
[33] M. Solodov and P. Tseng. Modified projection-type methods for monotone variational inequalities. SIAM J. Cont Optim., 1996, 34:1814-1830.
[34] 孙德峰．广义非线性互补问题的投影梯度法．计算数学，1995，第19卷，183-194.
[35] 修乃华，王长钰。关于外梯度法的步长准则。计算数学．2000，22(2)：197-208．
[36] Y. Wang, N. Xiu and C. Wang. A new version of extragradient method for variational inequality problems. Computers and Mathematics with Applications. 2001,969-979.
[37] 张培爱，李兴斯。信息熵原理与互补问题的一种迭代算法。甘肃工业大学学报。2002，28(1)：103-107。
[38] M. Kojima, N. Megiddo and S. Mizuno. An O(n~(1/2)L)iteration potential reduction algorithm for linear complementarity problems. Mathematical Programming. 1991,50:331-342.
[39] D. Shannon and E. Simantiraki. An infeasible interior-point method for linear complementarity problems. Technical Report 95-7, 1995.
[40] Yu. E. Nesterov, M. J. Todd. Self-scaled barriers and interior-point methods for convex programming, Mathematics of Operations Research. 1997, 22: 1-42.
[41] F A. Potra and R. Sheng. Superlinear convergence of interior-point algorithms for semidefinite programming. J. Optim. Theory Appl. 1998, 99 (1) :103-119.
[42] M.J. Todd. A study of search directions in primal-dual interior-point methods for semidefinite
programming. Technical Report, School of Operations Research and Industrial Engineering, Comell University, Ithaca, NewYork, February, 1999.
[43] L. Vandenberghe and S. Boyd. Semidefinite programming, SIAM Rev. 1996, 38 (1): 49-95.
[44] J. Jarre and M. Saunders. A practical interior-point method for convex programming. SIAM Journal on Optimization. 1995, 5: 149-171.
[45] R. Monteito, I. Adler and M. Resende. A polynomial-time primal-dual affine scaling algorithm for linear and convex quadratic programming and its power series extension. Mathematics of Operations Research. 1990, 15: 191-214.
[46] C. Gonzaga. Path-following methods for linear programming. SIAM Review. 1992, 34:167-24.
[47] S. Mehrotra. On the implementation of a primal-dual interior-point method. SIAM Journal on Optimization. 1992, 2:575-601.
[48] Y. Ye and K. Anstreicher. On quadratic and O(n~(1/2)L) convergence of a predictor-corrector algorithm for LCP. Mathematical Programming. 1993, 62 (3): 537-551.
[49] C. Gonzaga and M. J. Todd. An O(N(1/2)L)-iteration large-step primal-dual affine algorithm for linear programming. SIAM Joumal on Optimization. 1992, 2: 349-359.
[50] M.J. Todd. The affine scaling direction for linear programming is a limit of projective scaling directions. Linear Algebra and its Applications 1991, 152: 93-105.
[51] F. Potra and S. J. Wright. Interior-point methods. Journal of Computational Mathematical. 2000, 124: 281-302.
[52] Y. Zhang and D. Zhang. On polynomiality of the Mehrotra-type predictor-corrector interior-point algorithms. Mathematical programming. 1995, 68:303-318.
[53] J. Gondzio. Multiple centrality corrections in a primal-dual method for linear programming. Journal on Computational Optimization and Applicaions. 1996, 6: 137-156.
[54] A.S. Barky, R. A. Tapia and Y Zhang. A study of indicators for identifying zeros variables in interior-point methods. SIAM Review. 1994, 36: 45-72.
[55] Y. Ye. On the finite convergence of interior-point algorithms for linear programming. Mathematical Programming. 1992, 57: 325-336.
[56] O. Guler and Y. Ye. Convergence behavior of interior-point algorithms. Mathematical Programming. 1993, 60:215-228.
[57] M.J. Todd. Combining phase Ⅰand phase Ⅱ in a potential reduction algorithm for linear programming. Mathematical Programming. 1993, 59:133-150
[58] P. J. Williams. Effective finite termination procedures in interior-point methods for linear programming. PhD Thesis, 1998. Rice University, USA.
[59] S. J. Wright. An infeasible-interior-point algorithm for linear complementarity problems. Mathematical Programming. 1994, 67(1)29-51.
[60] L. Tuncel and A. Seifi, A constant-potential infeasible-start interior-point algorithm with computational experiments and applications. Computational Optimization and Applications 1998, 9:107-152.
[61] B. Jansen, C. Roos, T. Terlaky and J.-Ph. Vial. Long-step primal-dual target-following algorithms for linear programming. Technical Report 94-46, Delft University of Technology. 1994, The Nertherlands.
[62] J. Peng and T. Terlaky. A dynamic large-update primal-dual interior-point mehtods for linear optimization. Technical Report. Advanced Optimization Laboratory, McMaster University, December 2001, Hamilton, Ontario, Canada..
[63] J. Peng, C. Roos and T. Terlaky. New complexity analysis of the primal-dual Newton method for linear program. Annals of Operations Research. 2000, 99: 23-39.
[64] J. Peng, C. Roos and T. Terlaky. Self-regular proximity and new search directions for linear and semidefinite optimization. Technical Report. Defty University of Technology. The Nertherlands. Septermer 5, 2000.
[65] E. de Klerk, C. Roos, and T. Terlaky. A nonconvex weighted potential function for polynomial target following methods. Annals of OR, 81:3-14, 1998.
[66] Y.Q. Bai, M, Eighami and C. Roos. A new efficient large-update promal-dual interior-point method based on a finite barrier.
[67] M. Kojima, N. Megiddo and S. Mizuno. A primal-dual infeasible-interior-point algorithm for linear programming. Mathematical Programming. 1993, 61: 261-280.
[68] M. Kojima, T. Moma, and A. Yoshise. Global convergence in infeasible-interior-point algorithms. Mathematicla programming. 1994, 65:43-72.
[69] S. Mizuno, M. Kojima and M. Todd. Infeasible-interior-point primal-dual potential-reduction algorithms for linear programmings. SIAM Journal on Optimization. 1995, 5: 52-67.
[70] F.A. Potra. A quadratically convergent predictor-corrector method for solving linear programs from infeasible starting points. Mathematical Programming. 1994, 67, 383-406.
[71] S. J. Wright and Y. Zhang. A superquadratically infeasible-interior-point method for linear complementarity problems. Mathematical Programming. 1996, 73: 269-289.
[72] 何尚录，徐成贤．求解互补问题的不可行内点法及其计算复杂性．中国科学．2002，第30卷第11期：983-989．
[73] 何尚录，徐成贤．求解一类非单调线性互补问题的路径跟踪算法。计算数学。2001，第23卷第3期：298-306．
[74] 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 (1): 208-227.
[75] F.A. Potra and and R. Sheng. Predictor-corrector algorithm for solving p_* (k)-matrix LCP from arbitrary positive starting points. Mathematical Programming, 1996, 76: 223-244.
[76] S. Mehrotra. On the implementation of a primal-dual interior point method. SIAM J. Optim. 1992, 2: 575-601.
[77] Entropy and Optimization. Phd Dissertation of Liverpool University, Liverpool, UK,1987.
[78] Li and Shuchueng Fang. On the entropic regularization method for min max problems with applications. Mathematical Method of Operation research. 1997, 46(1): 119-130.
[79] 李兴斯。解非线性规划的凝聚函数法。中国科学，A辑，1991，第34卷第12期：1476-1473．
[80] A. Templeman X. Li. A maximum entropy approach to constrained non-linear programming.
Engineering Optimization. 1987, 12:191-205.
[81] O. Guler. Limiting behavior of weighted central paths in linear programming. Mathematical Programming. 1994, 65: 347-363.
[82] S. Fang and S. Puthenpura. Linear optimization and extensions-theory and algorithm. 1993, Prentice Hall, USA.
[83] L. Tuncel M. J. Todd, On the interplay among entropy, variable metrics and potential functions in interior-point algorithms. Computational Optimization and Applications, 1997, 8 (1): 5-17.
[84] P. Harker and B. Xiao. Newton method for a class of linear complementarity problems: a B-differentiable equation approach. Mathematical Programming, 1990, 48: 339-357.
[85] A. Fischer. A special Newton-type optimization. Optimization 24, 1992, 269-284.
[86] S. Engelke and C. Kanzow. Predictor-corrector smoothing methods for the solution of linear programs. Preprint 153, Department of Mathematics, Center for Optimization and Approximation, University of Hamburg, Hamburg, March 2000.
[87] B. Chen, X. Chen and C. Kanzow, A penalized Fischer-Burmeister NCP-function: theoretical investigation and numerical results. Mathematical Programming. 2000, 88:211-216.
[88] C. Kanzow. Some noninterior continuation methods for linear complementarity problems. SIAM Journal on Matrix Analysis and Application. 1996, 17: 851-868.
[89] T. De Luca, F. Facchinei and C. Kanzow. A semismooth equation approach to the solution of nonlinear complementarity problems. Mathematical programming. 75, 1996, 407-439.
[90] L. Qi and D. Sun. On NCP-functions. Computational Optimization and Applications. 1999, 13: 201-220.
[91] C. Kanzow, N. Yamashita and M. Fukushima. New NCP-functions and their properties. Journal of Optimization Theory and Applications. 1994, 81: 569-590.
[92] O.L. Mangasarian. Equivalence of the Complemenatrity problem to a system of nonlinear equations. SIAM Applied Mathematics. 1976, 31 (1): 89-92.
[93] F.H. Clark. Optimization and nonsmooth analysis. Willey, New York, 1983.
[94] Robert Mifflin. Simismooth and semiconvex function in constrained optimization. SIAM Journal on Control and Optimization. 1977, 15: 959-972.
[95] L. Qi and J. Sun. A nonsmooth version of Newton method. Mathematical Programming. 1993, 58: 353-367.
[96] C. Kanzow and H. Kleinmichel. A new class of semismooth Newton4ype mehods for nonlinear complementarity problems. Computional Optimization and Applications. 1998, 11: 227-251.
[97] X. Chen, Zuhair Nashed and Liqun Qi. Smoothing methods and semismoth methods for nondifferentiable operator equations. Technical Report.
[98] L. Qi. Convergence of some algorithms for solving nonsmooth equations. Mathematical of Operations Research. 1993, 18: 227-244.
[99] S.M. Robinson. Local structure of feasible sets in nonlinear programming. Part Ⅲ, stability and sensitivity. Mathematical Programming Study, 1987, 30: 45-66.
[100] J. S. Pang. Newtons method for B-differentiable equations. Mathematics of Operations Research. 1990, 15:311-341.
[101] J. Pang. A B-differentiable Equation based globally and locally quadratically convergent algorithm for nonlinear program, complementarity and variational inequality problem. Mathematical Programming. 1991,51:101-131.
[102] D. Ralph. Global convergence of dampted Newtons method for nonsmooth equations via the path search. Mathematics of Operations Research. 1994, 19:352-389.
[103] J. Pang and L. Qi. Nonsmooth equations: Motivation and algorithms. SIAM Journal on Optimization, 1993, 3: 443.
[104] H. Jiang and L. Qi. A new nonsmooth equations approach to nonlinear complementarity problems. SIAM Journal on Control and Optimization. 1997, 35: 178-193.
[105] C. Chen and O. Mangasarian. Smoothing methods for convex inequalities and linear complementarity problems. Mathematical Programming. 1995, 71: 51-69.
[106] C. Chen. Smoothing methods in mathemtical programming. Ph.D Dissertation of University of Wisconsin, Madison, USA.
[107] B. Chen and P. T. Harker. A non-interior-point continuation method for linear complementarity problems, SIAM Journal on Matrix Analysis and Application. 1993, 4:1168-1190.
[108] I.Zang. A smoothing-out technique for rain max Optimization. Mathematical Programming. 1980, 19(1): 61-77.
[109] C. Chen and O. Mangasarian. A class of smoothing functions for nonlinear and mixed complementarity problems. Computation Optimization and Applications, 1996, 5: 97-138.
[110] S.A. Gabriel and J. J. More. Smoothing of mixed complementarity problems. In complementarity and variational problems: state of the art. M C Ferris and J S Pang(Eds). SIAM Philadelphia. 1997, 105-116.
[111] B. Chen and N. Xiu. Superlinear noninterior one-step continuation method for monotone LCP in the absence of strictly complementarity. Journal of Optimization Theory and Applications. 2001, 108 (2):317-332.
[112] L. Qi and X. Chen. A global convergent successive approximation method for severely non-smooth equations. SIAM Journal on Control and Optimization. 1995, 33: 402-418.
[113] L. Qi, D. Sun, and G. Zhou. A new look at smoothing Newton methods for nonlinear complementarity problems and box constrained variational inequalities. Mathematical Programming, 2000, 87: 1-35.
[114] J. Burke and S. Xu. The global linear convergence of a non-interior path-following algorithm for linear complementarity problem. Mathematics of Operation Research,. 1998, 23: 719-734.
[115] S. Xu. The global linear convergence of an infeasible non-interior path-following algorithm for complementarity problems with uniform P-functions. Mathematical Programming, 2000, 87: 501-517.
[116] J. Burke and S. Xu. A non-interior predictor-corrector path following algorithm for the monotone Iinear complementarity problems. Mathematical Programming. 2000, 87:113-130.
[117] B. Chen and N. Xiu. A global linear and local quadratic non-interior continuation method for nonlinear complementarity problems based on Chen-Mangasarian smoothing function. SIAM Journal on Optimization. 1999, 9: 605-623.
[118] J. Peng and Z. Lin. A non-interior-point continuation method for generalized linear complementarity problems. Mathematical Programming. 1999, 86: 533-563.
[119] B. Chen and X. Chen. A global and superlinear continution-smoothing methods for P_0 and R_0 NCP or monotone NCP. SIAM Journal on Optimization. 1999, 9: 624-645.
[120] N. Xiu. The quadratic convegence of a one-step non-interior continuation mehtod for complementarity problems. Seience in China. Series A. 1999, 44 (14): 1483-1488.
[121] D. Li and M. Fukushima. Smoothing Newton and quasi-Newton methods for mixed complementarity problems. Computational Optimization and Aplications. 2000, 17: 203-230.
[122] B. Chen and X. Chen. A global linear and local quadratic continuation smoothing method for variational inequalities with box constraints. Computational Optiomization and Applications. 2000, 17: 131-158.
[123] O. Mangasarian and M. Solodov. Nonlinear complememtarity as unconstrained and constratined minimization. Mathematical Programming. 1993, 62: 277-297.
[124] M. Fukushima. Equivalent differentiable optimization problems and descent methods for asymmetric variational inequality problems[J]. Mathematical Programming, 1992, 53:99-110
[125] N. Yamashita, K. Taji and M. Fukushima. Unconstrained optimization of reformations of variational inequality problems. Journal of Optimization Theory and Application. 1997, 9: 439-456.
[126] J. Peng. Unconstrained optimization methods for generalized nonlinear complementarity and variational inequality problems. Journal of Computational Mathematics, 1996, 14: 99-107.
[127] J. Peng. Equivalent of variational inequationlity problems to unconstrained optimization. Mathematical Programming. 1997, 78: 347-356.
[128] J. Peng. Global methods for variational inequality problems on polyhedral sets, Optimization methods and Software. 1997, 7:110-122.
[129] J. Peng. Global convergent method for variational inequality problems with nonlinear constraints, J. Optimization Theory and Applications, 1997, 95: 419-430.
[130] E.T. Jaynes. Information theory and statistical mechanics. The Physical Review, 1957, 106: 620-630.
[131] A. Ben-Tal and M.Teboulle. A smoothing technique for non-differentiable optimization problems. Lecture Notes in Mathematics, 1405, Springer Verlag. 1989, 1-11.
[132] D. Bertsekas. Approximation procedures based on the method of multipliers. JOTA. 1977, 23: 487-510.
[133] G. D. Pillo and L. Grippo. A smooth method .for the finite minimax problem. Mathematical Programming 1993, 60(6): 187-214.
[134] Y. Censor and S.A.Zenios. Proximal minimization algorithms with D-functions. JOTA. 1992, 73(6):451-464.
[135] M.Teboulle. Entropic proximal mappings with application to nonlinear programming. Mathematics of Operations Research. 1992, 17(6): 670-690.
[136] C. Charalambous and A.R. Conn. An efficient method to solve the minimax problem directly. SIAM J.Numer. Anal. 1978,15 (6): 162-187.
[137] V. Demyanov and V. Malozemov. On the theory of non-linear min-max problems. Russian Math.
Surveys. 1971,26 (6): 57-115.
[138] C. Gigola and S. Gomez. A regularization method for solving the finite convex min-max problem, SIAM J.Numer. Anal.. 1990, 27 (6): 1621-1634.
[139] X. Li. An entropy-based aggregate method for minimax optimization. Engineering Optimization. 1992, 18(6): 277-285.
[140] E R. Barnes. A variant of Karmarkar's algorithm for solving linear programming problems. Mathematical Programming. 1986, 36:174-182.
[141] R. Frend. Polynomial-time algorithms for linear programming based only on primal scaling and projected gradients of a potential function. Mathematical Programming. 1991,51:203-222.
[142] P. E. Gill, W. Murray, M. A. Saunders, J. A. Tomlin and M. H. Wright. On projected Newton barrier methods for linear programming and an equivalence to Karmarkar's projective method. Mathematical Progranuning. 1986, 36:183-209.
[143] L. Adler, N. Karmarkar,M. Resende and A. Veigs. An implementation of Karmarkar's algorithm for linear programming. Mathematical Programming. 1989, 44:297-335.
[144] P. Tseng and Z. Luo. On the convergence of the affine scaling algorithm for degenerate linear programming problems. Mathematical Programming. 1992, 56:301-319.
[145] Y. Ye. Interior-point algorithm: theory and analysis. John Wiley and Sons, New York, 1997.
[146] J. Renagar. A polynomial-time algorithm, based on Newton's method for linear programming. Mathematical programming. 1988, 59-93.
[147] R. Tapia, Y. Zhang and Y. Ye. On the convergence of the iteration sequence in primal-dual interior-point methods. Mathematical programming, 1995, 68:141-154.
[148] S. Mizuno, M.J. Todd, and Y. Ye. On adaptive-step primal-dual interior-point algorithms for linear programming. Mathematics of Operations Research 1993, 18:964-981.
[149] I. J. Lustig, R. E. Marsten and D.F. Shannon. Computational experience with a primal-dual interior-point method for linear complementarity problems. Linear Algebra and its Applications. 1991, 152:191-222.
[150] Y. Ye, M. J. Todd and S. Mizuno, An O(N~(1/2)L)-iteration homogeneous and self-dual linear programming algorithm. Mathematical Programming. 1993, 59: 53-67.
[151] X. Xu, P. F. flung, and Y. Ye. A simplified homogeneous and self-dual linear programming algorithm and its implementation. Annals of Operations Research, 1996, 62: 151-171.
[152] P. Harker and B. Xiao. Newton method for the complementarity problem: A B-differentiable equation approach. Mathematical Programming. 1990, 48:339-357.
[153] S. Robinson. Strongly regular generalized equation. Mathematics of Operatons Research. 1980, 5: 43-62.
[154] L. Qi and J. Sun. A nonsmooth version of Newtons method. Mathematical Programming. 1993, 58: 353-367.
[155] M. Kojima, N. Megiddo, and S. Mizuno. A general framework of continuation methods for complementarity problems. Mathematics of Operation Research, 1993, 18: 945-967.
[156] 李兴斯．一类不可微优化问题的有效解法．中国科学A辑，1994, 第24卷第4期，371-377．
[157] 李兴斯，求解极大极小问题的一个有效解法．科学通报．1991，第36卷：1448-1450．
[158] S. Gabriel. A hybrid smoothing method for mixed nonlinear complementarity problems. Computational Optimization and Application. 1998, 9: 153-173.
[159] H. Jiang. Global convergence analysis of the generalized Newton and Gauss-Newton methods of the Fischer-Burmeister equation for the complementarity problem. Mathematics of Operation Research. 1999, 24: 529-
[160] X. Chen, L. Qi and D. Sun. Global and superlinear convergence of the smoothing Newton method and its application to general box-constrained variational inequalities. Mathematics of Computation. 1998, 67: 519-540.
[161] S. Engelke and C. Kanzow. Improved Smoothing-type Methods for the Solution of Linear Programs. Technical report, University of Hamburg, German, Sep. 22, 2000.
[162] 马昌风。求解线性互补问题的一个新算法．经济数学．1999，16(1)：55-59．
[163] X. Chen and Y. Ye. On homotopy-smoothing methods for variational inequalities. SIAM J. Control and Optimization, 1999, 37: 589.
[164] 孙德峰，韩继业，赵云彬．线性互补问题的阻尼Newton法的有限终止性．应用数学学报．1998，21(1)：148-154．
[165] D. Li and M. Fukushima. Globally convergent Broyden-like methods for semismooth equations and applications to VIP,NCP and MCP. Technical Report of Kyoto. 1999.
[166] K. Hotta, M. Inaba and A. Yoshise. A complexity analysis of a smoothing method using CHKS-functions for monotone linear complementarity problems. Computational Optimization and Aplications. 2000, 17:183-201.
[167] 马昌风. A globally convergent inexact successie approximation method for nonlinear complementarity problems. 数学杂志. 2001,21 (3): 285-289.
[168] 黄正海，韩继业，徐大川，张立平。P_0函数非线性互补问题的非内部连续化算法。．中国科学，A辑．2001，31(6)：488-494．
[169] B. He. On some projection and contration methods for solving monotone variable inequalities. Applied Mathematics and Optimization. 1997, 35: 69-76.
[170] F. Facchinei, A.Fischer, C.Kanzow and J. Peng, A simply constrained optimization reformulation of KKT system arising from variational inequalities. Applied Mathematics and Optimization, 1999, 40: 19-37.
[171] C. Kanzow and H. Jiang. A continuation method for (strongly) monotone variational inequalities. Mathematical Programming, 1998, 81: 140-152.
[172] K. Hotta and A. Yoshise. Global convergence of a class of non-interior-point algorithms using Chen-Harker-Kanzow-Smale functions for nonlinear complementarity problems. Mathematical Programming, 1999, 86:105.
[173] S. Xu. The global linear convergence and complexity of a non-interior path-following algorithm for monotone LCP based on Chen-Harker-Kanzow-Smale smooth funtion, preprint, department if mathematics. University of Washington. 1997.
[174] F. Tin-Loi and M. C. Ferris. Complementarity Problems in Engineering and Mechanics: Models and
Solution. Mathematical Programming Technical Report 99-02, February 1999.
[175] M. C. Ferris and K. Sinapiromsaran. Formulating and Solving Nonlinear Programs as Mixed Complementarity Problems. Mathematical Programming Technical Report 98-21, December 1998.
[176] M. C. Ferris, C. Kanzow and Todd S. Munson. Feasible Descent Algorithms for Mixed Complementarity Problems. Mathematical Programming Technical Report 98-04, March 1998.
[177] S. Billups. Algorithms for Complementarity Problems and Generalized Equations. Mathematical Programming Ph.D. Dissertation of Univerdity of Wiconsin, Madison, USA, 1995.
[178] S. C. Billups and Michael C. Ferris. QPCOMP: A Quadratic Programming Based Solver for Mixed Complementarity Problems. Mathematical Programming 1997, 76:513-532.
[179] O. Barrientos. A global regularization method for solving the finite min-max problems. Computational Optimization and Applications. 1998, 11:277-295.
[180] 唐焕文，张立卫。求解凸规划的一个极大熵方法。科学通报．1994，39(8)：282-284．
[181] 王云诚，唐焕文。求解约束极大极小问题的极大熵方法。高等学校计算数学学报。1999，(2)：132-139。
[182] 唐焕文，张立卫，王雪华。求解一类不可微问题的极大熵方法。计算数学。1993，(3)：268-275。
[183] Marcottle. and H. J. Wu. On the convergence of projection methods: applications to decomposition of affine variational inequalities.
[184] D. Sun. A class of iterative method for solving nonlinear projection equations. J. Optimization Theory and Applications. 1996, 91: 123-140.
[185] J.S. Pang D. Chan. Iteration methods for solving variational and complementarity problems. mathematical programming, 1992, 24:284-313.
[186] 奥特加，莱因博尔特著．多元非线性方程组的迭代数法．朱季纳译．科学出版社，1983年，
[187] Kanzow. Global convergence problems of some iterative methods for linear complementarity problems. SIAM, Joumal on Optimization. 1996, Vol. 6, 326-341.
[188] 陈国庆，陈万吉，冯恩民。三维解出问题非线性互补原理及算法。中国科学A辑。1995，25(11)：1181-1190．
© 2004-2018 中国地质图书馆版权所有 京ICP备05064691号 京公网安备11010802017129号 地址：北京市海淀区学院路29号 邮编：100083 电话：办公室：(+86 10)66554848；文献借阅、咨询服务、科技查新：66554700 |