非线性最优化问题中若干重要算法的理论研究
|
摘要
本文主要是对非线性最优化问题中的若干重要算法的理论分析作了探讨，包括约束最优化问题中的梯度投影方法以及求解变分不等式和互补问题的几类算法，主要是集中在这几种算法的收敛性分析上。
第一章是绪论部分，简单介绍了变分不等式与互补问题，本文所研究的内容，以及本文的主要工作。
第二章研究了通过广义D-间隙函数求解变分不等式问题的一种方法的收敛性和误差界估计。我们知道，通过广义D-间隙函数，可以将变分不等式问题转化为一个无约束极小化问题。近来，Peng和Fukushima提出了一种混合Newton类型的方法来极小化一个特殊的广义D-间隙函数，在本章中，我们将这种方法用来极小化一般形式的广义D-间隙函数g_(αβ)。我们证明了算法具有更强的收敛性质。在合适的条件下，证明了算法的全局收敛性和局部二次收敛性。更进一步，当广义D-间隙函数g_(αβ)中的参数β取值于某一区间时，证明了函数g_(αβ)对于强单调变分不等式而言，具有有界的水平集，同时，给出了算法的一个误差界估计，它部分回答了Yamashita等人提出的一个问题。
第三章对求解互补问题的阻尼Gauss-Newton方法作了研究，这种方法最早是由Subramanian提出的。本章主要研究了阻尼Gauss-Newton方法的全局收敛性，在较弱的条件下，获得了一个更强的全局收敛结果，该结果推广了相应文献中算法的全局收敛性结果。同时，我们给出了一种不需要线性搜索的新的步长选择方法，研究了在此步长规则下的阻尼Gauss-Newton方法，得到了一个更好的全局收敛结果。
第四章对求解互补问题的可微的无约束优化法作了研究。在将互补问题转化为一个无约束优化问题的基础上，给出了一种求解互补问题的混合方法，证明了该算法的全局收敛性。
第五章研究了求解约束最优化问题的梯度投影方法，在步长的选取时采用了一种新的策略，这种策略不需要进行传统的线搜索且包含步长取常数这种特例，在较弱的条件下，证明了梯度投影方法的全局收敛性。进一步给出了目标函数f(x)是凸函数和拟凸函数时的更强的收敛性结果。
第六章是结论部分，主要对本论文的内容作了简单的概括和分析。
Some important algorithms for nonlinear optimization problems are studied in this dissertation. The aim of this dissertation is to give some theoretical analysis.
Chapter 1 is the introduction of this dissertation, which introduces the variational inequality problem and the complementarity problem, the context of this dissertation and the main results obtained in this dissertation.
A hybrid Newton-type method for solving the variational inequality problem (VIP) is studied in Chapter 2. It is known that the VIP can be reformulated as an unconstrained minimization problem through the D-gap function. Recently, a hybrid Newton-type method was proposed by Peng and Fukushima (1999) for minimizing the D-gap function. In this chapter, the hybrid Newton-type method is extended to minimize a generalized D-gap
function gαβ in the general form. It is shown that the algorithm has nice convergence
properties. Under some reasonable conditions, it is proved that the algorithm is locally and globally convergent. Moreover, when the parameter β is chosen in a certain interval, it is
proved that the generalized D-gap function gαβ has bounded level sets for the strongly
monotone VIP. An error bound estimation of the algorithm is obtained, which partially gives an answer to the question raised by Yamashita (1997) et al.
The authors study the convergence properties of the damped Gauss-Newton algorithm which was originally proposed by Subramanian for the complementarity problem in Chapter 4. The aim of this chapter is to give a global convergence result under weaker conditions. The results here improve and generalize those in the literature. In addition, a new step-size rule, which need not a line search, is presented for the damped Gauss-Newton algorithm. A nice global convergence result is obtained.
In Chapter 4, a new algorithm for the solution of nonlinear complementarity problems is developed. The algorithm is based on a reformulation of the complementarity problem as an unconstrained optimization. It is proved that the algorithm is globally convergent.
In Chapter 5, the authors study the convergence properties of the gradient projection method for the constrained optimization problem. In this chapter, a new step-size rule, which avoids fulfiling the classical line search and includes choosing a constant as the step size as a special case, is presented and analyzed. Some convergence results of the gradient projection
in
method under milder conditions are obtained.
Finally we conclude the dissertation with some remarks in Chapter 6.
第一章是绪论部分，简单介绍了变分不等式与互补问题，本文所研究的内容，以及本文的主要工作。
第二章研究了通过广义D-间隙函数求解变分不等式问题的一种方法的收敛性和误差界估计。我们知道，通过广义D-间隙函数，可以将变分不等式问题转化为一个无约束极小化问题。近来，Peng和Fukushima提出了一种混合Newton类型的方法来极小化一个特殊的广义D-间隙函数，在本章中，我们将这种方法用来极小化一般形式的广义D-间隙函数g_(αβ)。我们证明了算法具有更强的收敛性质。在合适的条件下，证明了算法的全局收敛性和局部二次收敛性。更进一步，当广义D-间隙函数g_(αβ)中的参数β取值于某一区间时，证明了函数g_(αβ)对于强单调变分不等式而言，具有有界的水平集，同时，给出了算法的一个误差界估计，它部分回答了Yamashita等人提出的一个问题。
第三章对求解互补问题的阻尼Gauss-Newton方法作了研究，这种方法最早是由Subramanian提出的。本章主要研究了阻尼Gauss-Newton方法的全局收敛性，在较弱的条件下，获得了一个更强的全局收敛结果，该结果推广了相应文献中算法的全局收敛性结果。同时，我们给出了一种不需要线性搜索的新的步长选择方法，研究了在此步长规则下的阻尼Gauss-Newton方法，得到了一个更好的全局收敛结果。
第四章对求解互补问题的可微的无约束优化法作了研究。在将互补问题转化为一个无约束优化问题的基础上，给出了一种求解互补问题的混合方法，证明了该算法的全局收敛性。
第五章研究了求解约束最优化问题的梯度投影方法，在步长的选取时采用了一种新的策略，这种策略不需要进行传统的线搜索且包含步长取常数这种特例，在较弱的条件下，证明了梯度投影方法的全局收敛性。进一步给出了目标函数f(x)是凸函数和拟凸函数时的更强的收敛性结果。
第六章是结论部分，主要对本论文的内容作了简单的概括和分析。
Some important algorithms for nonlinear optimization problems are studied in this dissertation. The aim of this dissertation is to give some theoretical analysis.
Chapter 1 is the introduction of this dissertation, which introduces the variational inequality problem and the complementarity problem, the context of this dissertation and the main results obtained in this dissertation.
A hybrid Newton-type method for solving the variational inequality problem (VIP) is studied in Chapter 2. It is known that the VIP can be reformulated as an unconstrained minimization problem through the D-gap function. Recently, a hybrid Newton-type method was proposed by Peng and Fukushima (1999) for minimizing the D-gap function. In this chapter, the hybrid Newton-type method is extended to minimize a generalized D-gap
function gαβ in the general form. It is shown that the algorithm has nice convergence
properties. Under some reasonable conditions, it is proved that the algorithm is locally and globally convergent. Moreover, when the parameter β is chosen in a certain interval, it is
proved that the generalized D-gap function gαβ has bounded level sets for the strongly
monotone VIP. An error bound estimation of the algorithm is obtained, which partially gives an answer to the question raised by Yamashita (1997) et al.
The authors study the convergence properties of the damped Gauss-Newton algorithm which was originally proposed by Subramanian for the complementarity problem in Chapter 4. The aim of this chapter is to give a global convergence result under weaker conditions. The results here improve and generalize those in the literature. In addition, a new step-size rule, which need not a line search, is presented for the damped Gauss-Newton algorithm. A nice global convergence result is obtained.
In Chapter 4, a new algorithm for the solution of nonlinear complementarity problems is developed. The algorithm is based on a reformulation of the complementarity problem as an unconstrained optimization. It is proved that the algorithm is globally convergent.
In Chapter 5, the authors study the convergence properties of the gradient projection method for the constrained optimization problem. In this chapter, a new step-size rule, which avoids fulfiling the classical line search and includes choosing a constant as the step size as a special case, is presented and analyzed. Some convergence results of the gradient projection
in
method under milder conditions are obtained.
Finally we conclude the dissertation with some remarks in Chapter 6.
引文
[1] Giannessi, F., Theorems of the alternative, quadrative programs, and complementary problems, in: Cottle, R.W., Giannessi, F., Lions, J.L., eds., Variational inequality and complementarity problems, John Wiley and sons, New York, 1980,151-186,
[2] Harker, P.T., and Pang, J.S., Finite-dimensional variational inequality and nonlinear complementarity problems: a surrey of theory, algorithm and applications, Math. Programming, 1990, 48(2): 163-220.
[3] 张石生，变分不等式和相补问题理论及应用，上海科技文献出版社，上海，1991．
[4] Hartman, P., and Stampacchia, G., On some nonlinear elliptic differenttial functions, Acta. Math., 1996, 115:153-188.
[5] Mancino, O., and Stampacchia, G., Convex programming and variational inequalities, J.Opti.Th, Appl., 1972, 9.3-2.3.
[6] Stampacchia G., Variational inequalities, In theory and applications of monotone operators, Proceedings of the NATO advanced study institute, Venice, Italy (Edizioni Oderisi, Gubbio, Italy, 1968), 102-192.
[7] Chen, B. and Harker, P.T., A continuation method for monotone variational inequalities, Math. Programming, 1995, 69(2): 237-253.
[8] Kanzow. C., and Jiang, H., A continuation method for strongly monotone variational inequalities, Math. Programming, 1998, 81:103-126.
[9] 简金宝，单调变分不等式的可行与非可行点组合的连读算法，运筹学学报，1997，(1)：76-85．
[10] Sun, D., Fukushima, M., Qi, L., A computable generalized Hessian of D-gap function and Newton type methods for variational inequality problems, Applied Mathematics Report AMR95-35, School of Mathematics, the University of New South Wale Sydney, South Wales 2052, Australia, 1995.
[11]戚厚铎，变分不等式问题的拟牛顿算法，中国计算数学与科学工程和计算研究所研究报告，1997．
[12] Taji, K., Fukushima M., Ibaraki, T., A globally convergent Newton method for solving strongly monotone variational inequalities, Math. Programming, 1993, 58(3): 369-383.
[13] Bertsekas, D. P., Gafni, E.M., Projection methods for variational inequalities with application to the traffic assignment problem, Mathematical Programming Study, 1982, 17:139-159.
[14] Pang, J.S, Chen, D., Iterative methods for variational and complementarity problem, Math.Programming, 1982, 24(3): 284-313.
[15] Marcotte, P., Wu, J.H., on the convergence of projection methods: Application to the decomposition of affine variational inequalities, J.Optim.Theory Appl., 1995, 85(2): 347-362.
[16] Fukushima, M., A relaxed projection method for variational inequalities, Math. Programming, 1986, 35(1): 58-70.
[17]何炳生，论求解单调变分不等式的一些投影收缩算法，计算数学，1996，18(1)：54-60．
[18] He B.S. A modified projection and contraction method for a class of linear complementarity problems, J.Comput. Math., 1996, 14:54-63.
[19] He, B.S., A class of projection and contraction methods for monotone variational inequalities, Appl.Math, Optim., 1997, 35:69-76.
[20] 何炳生，一类广义性变分不等式的求解与应用，中国科学(A)，1995，25(9)：939-1008．
[21] Mangasarian, O. L., Equivalence of the complementarity problem to a system of nonlinear equations. SIAM J. Applied Mathematics. 1976, 31: 89-92.
[22] Subramanian, P. K., Gauss-Newton methods for the complementarity problem, J.O.T.A., 1993, 77: 467-482.
[23] Watson, L.T., Solving nonlinear complementarity problem by a homotopy method. SIAM J. Control and Optimization, 1979, 17: 36-46.
[24] Subramanian, P. K., Xiu, N. H., Convergence analysis of Gauss-Newton methods for the complementarity problem, J.O.T.A., 1997, 94(3): 727-738.
[25] Kanzow, C., Global convergence properties of some iterative methods for linear complementarity problems, SIAM J.Optimization, 1996, 6: 326-341.
[26] Tseng, P., Growth behavior of a class of merit functions for the nonlinear complementarity problem, J.O.T.A., 1996, 89: 17-37.
[27] Robinson, S.M., Strongly regular generalized equations. Math. Oper. Res., 1980, 5: 43-62.
[28] Pang, J.S., A B-differentiable equation based, globally and locally quadratically convergent algorithm for nonlinear programs, complementarily, and variational inequality problems. Math, Programming, 1991,51: 101-131.
[29] Luo, Z.Q., Tseng, P. A new class of merit functions for the nonlinear complementarity problem. In Ferris, M. C., and Pang, J.S., eds., Complementarty and Variational Problem: State of the Art. SIAM Publications, 1997, 241-255.
[30] Mangasarian, O.L., and Solodov, M.V., Nonlinear complementarity as uncon -strained and constrained minimization, Math. Programming, 1993, 62: 277-297.
[31] Yamashita, N., and Fukushima, M., on stationary points of the implicit lagrangian for nonlinear complementarity problems. J.O.T.A., 1995.84: 635-663.
[32] Kanzow, C., Nonlinear complementarity as unconstrained optimization, J.O.T.A., 1996, 88(1): 139-155.
[33] Fukushima, M., Equivalent differentiable optimization problems and descent methods for asymmetric variational inequality problems. Math, Programming, 1992, 53:99-110.
[34] Peng, J.M., Equivalence of variational inequality problems to unconstrained optimization, Math. Prog., 1997, 78: 347-355.
[35] Fukushima, M., Merit function for variational inequality and complementarity problem, In Di Pillo G and Giannessi F, eds. : Nonlinear Optimization and Applications, Plenum Press, New York, 1996, 155-170.
[36] Sun, D., A new step-size skill for solving a class of nonlinear projection equations. J. Comput. Math., 1995, 13(4): 357-368.
[37] Solodov, M.V., and Tseng, P., Modified projection-type methods for monotone variational inequalities, SIAM J. Control Optim., 1996, 34:1814-1830.
[38] Kojima, M., Mizuno, S., and Yoshise, A., An o(n~1/2L) iteration potential reduction algorithm for linear complementarity problems. Math. Programming, 1991, 50: 331-342.
[39] Billups, S.C., and Ferris, M.C., Convergence of an infeasible interior point algorithm from arbitrary positive starting points. SIAM J. Optimization, 1996, 6: 316-325.
[40] Wang, T., Monteiro, R.D.C., and Pang, J.S., An interior point potential reduction method for constrained equations. Math. Programming, 1996, 74:159-195.
[41] Bonnans, J. F., and Gonzaga, C. C., convergence of interior point algorithms for the monotone linear complementarity problem. Math. Oper. Res., 1996, 21: 1-25.
[42] Tseng, P., Analysis of an infeasible interior path-following method for complementarity problems. Technical Report, Department of Mathe -matics, University of Washington 98195, USA, 1997.
[43] Chen, B., and Harker, P. T., A non-interior-point continuation method for linear complementarity problems. SIAM J. Matrix Analysis and Applications, 1993. 14:1168-1190.
[44] Qi, L., and Sun, D., Nonsmooth equations and smoothing methods. Progress in Optimization: Contribution from Australian. Eberhard, A., Glover, B., Hill R and Ralph D, eds, kluwer Academic Publisher, Norwell, MA. USA, 1998.
[45] Chen, X., and Ye, Y., On homogeneous methods for the PO matrix linear complementarity problem. The University of New South Wales, Sydney, Australia, 1997.
[46] Marcotte, P., and Dussault, J.P., A note on a globally convergent Newton method for solving monotone variational inequalities, Oper. Res, Lett,, 1987, 6: 35-42.
[47] Larsson, T., and Patriksson, M., A class of gap functions for variational inequalities, Math. Programming, 1994, 64: 53-79.
[48] Auchmuty, G., Variational principles for variational inequalities, Numer. Funct. Anal. Opti., 1989, 10: 863-874.
[49] Zhu D.L., and Marcotte P., An extended descent framework for variational inequalities, J. Opti, Th. Appl., 1994, 80:349-366.
[50] Wu, J.H., Florian, M., and Marcotte, P., A general descent framework for the monotone variational inequality problem. Math. Programming, 1993, 66:281-300.
[51] Yamashita, N., Taji, K., and Fukushima, M., Unconstrained optimization reformulations of variational inequality problems, J.O.T.A., 1997, 92: 439-456.
[52] Ferris, M.C., and Lucidi, S., Globally convergent methods for nonlinear equations. J.O.T.A., 1994, 81: 53-71.
[53] 简金宝 赖炎连，变分不等式的几类求解方法，高校应用数学学报．1998，14A(2)：197-212．
[54] 修乃华，高自友，互补问题算法的新发展，数学进展，1999，28(3)：193-210．
[55] Calamai, P. H., and Moré, J. J., Projection gradient methods for linearly constrained problems, Math. Programming. 1987,39:93-116.
[56] Solodov, M.V., and Tseng. P., Modified projection-type methods for monotone variational inequalities. SIAM J.Control Optim., 1996, 34:1814-1830.
[57] Wang, C. Y., Xiu, N. H., Convergence of the gradient projection method for generalized convex minimization. Comp. Optim. Appl., 2000, 16:111-120.
[58] 陈开明，<<非线性规划>>(大学应用数学从书)，上海科学技术出版社，2000．
[59] 袁亚湘 孙文瑜，<<最优化理论与方法>>，科学出版社，1999．
[60] 赵瑞安 吴方，<<非线性最优化理论和方法>>(应用数学从书)，复旦大学出版社，1991．
[61] R.W. Cottle, Nolinear programs with positively bounded Jacobians, Ph. D. dissertation, Department of Mathematics, University of Calafornia (Berkeley, CA, 1964).
[62] R. W. Cottle, Nolinear programs with positively bounded Jacobians, SIAM Journal on Applied
Mathematics, 1996, 14: 147-158.
[63] R.W. Cottle, G.J. Habetler and C.E.Lemke, Quadratic forms Semi-definite over convex cones, in: H. W. Kuhn, ed., Proceedings of the Princeton Symposiuuuuum on Mathematical Programming (Princeton University Press, Princeton, NJ, 1970): 551-565.
[64] 修乃华，王长钰，关于外梯度法的步长规则，计算数学，2000(22)：197-208．
[65] Y. J. Wang, N. H. Xiu and C. Y. Wang, A new version of extragradient method for variational inequality problems, Comput. Math. Appl., 2001, 42: 969-979.
[66] 王宜举，变分不等式问题的一个外梯度投影算法，计算数学，2002(1)：105-112．
[67] 李飞，梁昔明，徐成贤，求解单调变分不等式问题的连续牛顿法，工程数学学报，2001，18(3)：1-5．
[68] 何尚录，徐成贤，求解一类非单调线性互补问题的路径跟踪法及其计算复杂性，计算数学，2001，23(2)：299-306．
[69] 徐成贤，线性互补问题的内点算法，数值计算与计算机应用，1995，16(2)：109-118．
[70] 孙德峰，韩继业，线性互补问题的阻尼牛顿法的有限终止性，应用数学学报，1998，21(1)：148-154．
[71] 形志栋，曾云辉，刘三阳，变分不等式问题的新发展，西安电子科技大学学报(自然科学版)，2000，27(5)：648-652．
[2] Harker, P.T., and Pang, J.S., Finite-dimensional variational inequality and nonlinear complementarity problems: a surrey of theory, algorithm and applications, Math. Programming, 1990, 48(2): 163-220.
[3] 张石生，变分不等式和相补问题理论及应用，上海科技文献出版社，上海，1991．
[4] Hartman, P., and Stampacchia, G., On some nonlinear elliptic differenttial functions, Acta. Math., 1996, 115:153-188.
[5] Mancino, O., and Stampacchia, G., Convex programming and variational inequalities, J.Opti.Th, Appl., 1972, 9.3-2.3.
[6] Stampacchia G., Variational inequalities, In theory and applications of monotone operators, Proceedings of the NATO advanced study institute, Venice, Italy (Edizioni Oderisi, Gubbio, Italy, 1968), 102-192.
[7] Chen, B. and Harker, P.T., A continuation method for monotone variational inequalities, Math. Programming, 1995, 69(2): 237-253.
[8] Kanzow. C., and Jiang, H., A continuation method for strongly monotone variational inequalities, Math. Programming, 1998, 81:103-126.
[9] 简金宝，单调变分不等式的可行与非可行点组合的连读算法，运筹学学报，1997，(1)：76-85．
[10] Sun, D., Fukushima, M., Qi, L., A computable generalized Hessian of D-gap function and Newton type methods for variational inequality problems, Applied Mathematics Report AMR95-35, School of Mathematics, the University of New South Wale Sydney, South Wales 2052, Australia, 1995.
[11]戚厚铎，变分不等式问题的拟牛顿算法，中国计算数学与科学工程和计算研究所研究报告，1997．
[12] Taji, K., Fukushima M., Ibaraki, T., A globally convergent Newton method for solving strongly monotone variational inequalities, Math. Programming, 1993, 58(3): 369-383.
[13] Bertsekas, D. P., Gafni, E.M., Projection methods for variational inequalities with application to the traffic assignment problem, Mathematical Programming Study, 1982, 17:139-159.
[14] Pang, J.S, Chen, D., Iterative methods for variational and complementarity problem, Math.Programming, 1982, 24(3): 284-313.
[15] Marcotte, P., Wu, J.H., on the convergence of projection methods: Application to the decomposition of affine variational inequalities, J.Optim.Theory Appl., 1995, 85(2): 347-362.
[16] Fukushima, M., A relaxed projection method for variational inequalities, Math. Programming, 1986, 35(1): 58-70.
[17]何炳生，论求解单调变分不等式的一些投影收缩算法，计算数学，1996，18(1)：54-60．
[18] He B.S. A modified projection and contraction method for a class of linear complementarity problems, J.Comput. Math., 1996, 14:54-63.
[19] He, B.S., A class of projection and contraction methods for monotone variational inequalities, Appl.Math, Optim., 1997, 35:69-76.
[20] 何炳生，一类广义性变分不等式的求解与应用，中国科学(A)，1995，25(9)：939-1008．
[21] Mangasarian, O. L., Equivalence of the complementarity problem to a system of nonlinear equations. SIAM J. Applied Mathematics. 1976, 31: 89-92.
[22] Subramanian, P. K., Gauss-Newton methods for the complementarity problem, J.O.T.A., 1993, 77: 467-482.
[23] Watson, L.T., Solving nonlinear complementarity problem by a homotopy method. SIAM J. Control and Optimization, 1979, 17: 36-46.
[24] Subramanian, P. K., Xiu, N. H., Convergence analysis of Gauss-Newton methods for the complementarity problem, J.O.T.A., 1997, 94(3): 727-738.
[25] Kanzow, C., Global convergence properties of some iterative methods for linear complementarity problems, SIAM J.Optimization, 1996, 6: 326-341.
[26] Tseng, P., Growth behavior of a class of merit functions for the nonlinear complementarity problem, J.O.T.A., 1996, 89: 17-37.
[27] Robinson, S.M., Strongly regular generalized equations. Math. Oper. Res., 1980, 5: 43-62.
[28] Pang, J.S., A B-differentiable equation based, globally and locally quadratically convergent algorithm for nonlinear programs, complementarily, and variational inequality problems. Math, Programming, 1991,51: 101-131.
[29] Luo, Z.Q., Tseng, P. A new class of merit functions for the nonlinear complementarity problem. In Ferris, M. C., and Pang, J.S., eds., Complementarty and Variational Problem: State of the Art. SIAM Publications, 1997, 241-255.
[30] Mangasarian, O.L., and Solodov, M.V., Nonlinear complementarity as uncon -strained and constrained minimization, Math. Programming, 1993, 62: 277-297.
[31] Yamashita, N., and Fukushima, M., on stationary points of the implicit lagrangian for nonlinear complementarity problems. J.O.T.A., 1995.84: 635-663.
[32] Kanzow, C., Nonlinear complementarity as unconstrained optimization, J.O.T.A., 1996, 88(1): 139-155.
[33] Fukushima, M., Equivalent differentiable optimization problems and descent methods for asymmetric variational inequality problems. Math, Programming, 1992, 53:99-110.
[34] Peng, J.M., Equivalence of variational inequality problems to unconstrained optimization, Math. Prog., 1997, 78: 347-355.
[35] Fukushima, M., Merit function for variational inequality and complementarity problem, In Di Pillo G and Giannessi F, eds. : Nonlinear Optimization and Applications, Plenum Press, New York, 1996, 155-170.
[36] Sun, D., A new step-size skill for solving a class of nonlinear projection equations. J. Comput. Math., 1995, 13(4): 357-368.
[37] Solodov, M.V., and Tseng, P., Modified projection-type methods for monotone variational inequalities, SIAM J. Control Optim., 1996, 34:1814-1830.
[38] Kojima, M., Mizuno, S., and Yoshise, A., An o(n~1/2L) iteration potential reduction algorithm for linear complementarity problems. Math. Programming, 1991, 50: 331-342.
[39] Billups, S.C., and Ferris, M.C., Convergence of an infeasible interior point algorithm from arbitrary positive starting points. SIAM J. Optimization, 1996, 6: 316-325.
[40] Wang, T., Monteiro, R.D.C., and Pang, J.S., An interior point potential reduction method for constrained equations. Math. Programming, 1996, 74:159-195.
[41] Bonnans, J. F., and Gonzaga, C. C., convergence of interior point algorithms for the monotone linear complementarity problem. Math. Oper. Res., 1996, 21: 1-25.
[42] Tseng, P., Analysis of an infeasible interior path-following method for complementarity problems. Technical Report, Department of Mathe -matics, University of Washington 98195, USA, 1997.
[43] Chen, B., and Harker, P. T., A non-interior-point continuation method for linear complementarity problems. SIAM J. Matrix Analysis and Applications, 1993. 14:1168-1190.
[44] Qi, L., and Sun, D., Nonsmooth equations and smoothing methods. Progress in Optimization: Contribution from Australian. Eberhard, A., Glover, B., Hill R and Ralph D, eds, kluwer Academic Publisher, Norwell, MA. USA, 1998.
[45] Chen, X., and Ye, Y., On homogeneous methods for the PO matrix linear complementarity problem. The University of New South Wales, Sydney, Australia, 1997.
[46] Marcotte, P., and Dussault, J.P., A note on a globally convergent Newton method for solving monotone variational inequalities, Oper. Res, Lett,, 1987, 6: 35-42.
[47] Larsson, T., and Patriksson, M., A class of gap functions for variational inequalities, Math. Programming, 1994, 64: 53-79.
[48] Auchmuty, G., Variational principles for variational inequalities, Numer. Funct. Anal. Opti., 1989, 10: 863-874.
[49] Zhu D.L., and Marcotte P., An extended descent framework for variational inequalities, J. Opti, Th. Appl., 1994, 80:349-366.
[50] Wu, J.H., Florian, M., and Marcotte, P., A general descent framework for the monotone variational inequality problem. Math. Programming, 1993, 66:281-300.
[51] Yamashita, N., Taji, K., and Fukushima, M., Unconstrained optimization reformulations of variational inequality problems, J.O.T.A., 1997, 92: 439-456.
[52] Ferris, M.C., and Lucidi, S., Globally convergent methods for nonlinear equations. J.O.T.A., 1994, 81: 53-71.
[53] 简金宝 赖炎连，变分不等式的几类求解方法，高校应用数学学报．1998，14A(2)：197-212．
[54] 修乃华，高自友，互补问题算法的新发展，数学进展，1999，28(3)：193-210．
[55] Calamai, P. H., and Moré, J. J., Projection gradient methods for linearly constrained problems, Math. Programming. 1987,39:93-116.
[56] Solodov, M.V., and Tseng. P., Modified projection-type methods for monotone variational inequalities. SIAM J.Control Optim., 1996, 34:1814-1830.
[57] Wang, C. Y., Xiu, N. H., Convergence of the gradient projection method for generalized convex minimization. Comp. Optim. Appl., 2000, 16:111-120.
[58] 陈开明，<<非线性规划>>(大学应用数学从书)，上海科学技术出版社，2000．
[59] 袁亚湘 孙文瑜，<<最优化理论与方法>>，科学出版社，1999．
[60] 赵瑞安 吴方，<<非线性最优化理论和方法>>(应用数学从书)，复旦大学出版社，1991．
[61] R.W. Cottle, Nolinear programs with positively bounded Jacobians, Ph. D. dissertation, Department of Mathematics, University of Calafornia (Berkeley, CA, 1964).
[62] R. W. Cottle, Nolinear programs with positively bounded Jacobians, SIAM Journal on Applied
Mathematics, 1996, 14: 147-158.
[63] R.W. Cottle, G.J. Habetler and C.E.Lemke, Quadratic forms Semi-definite over convex cones, in: H. W. Kuhn, ed., Proceedings of the Princeton Symposiuuuuum on Mathematical Programming (Princeton University Press, Princeton, NJ, 1970): 551-565.
[64] 修乃华，王长钰，关于外梯度法的步长规则，计算数学，2000(22)：197-208．
[65] Y. J. Wang, N. H. Xiu and C. Y. Wang, A new version of extragradient method for variational inequality problems, Comput. Math. Appl., 2001, 42: 969-979.
[66] 王宜举，变分不等式问题的一个外梯度投影算法，计算数学，2002(1)：105-112．
[67] 李飞，梁昔明，徐成贤，求解单调变分不等式问题的连续牛顿法，工程数学学报，2001，18(3)：1-5．
[68] 何尚录，徐成贤，求解一类非单调线性互补问题的路径跟踪法及其计算复杂性，计算数学，2001，23(2)：299-306．
[69] 徐成贤，线性互补问题的内点算法，数值计算与计算机应用，1995，16(2)：109-118．
[70] 孙德峰，韩继业，线性互补问题的阻尼牛顿法的有限终止性，应用数学学报，1998，21(1)：148-154．
[71] 形志栋，曾云辉，刘三阳，变分不等式问题的新发展，西安电子科技大学学报(自然科学版)，2000，27(5)：648-652．