摘要
本文研究解变分不等式问题的同伦方法.我们对箱式约束、球约束、一般抽象约束集上的变分不等式问题从其等价的非光滑方程出发,利用它们的光滑逼近构造同伦,并在与已有的从K-K-T系统出发的组合同伦方法相同的条件下证明光滑同伦路径的存在性和收敛性.该方法与组合同伦方法一样,具有可以在较弱的解存在性条件下得到收敛性的优点,并且由于不需引进乘子变量,因而对投影算子容易计算的问题计算效率更高.此外,对组合同伦方法,我们给出一个新的更有效的路径跟踪算法,并在一定条件下证明了它的全局收敛性及多项式复杂性.
第一章概要地介绍同伦方法与变分不等式问题的发展历史、定义、记号以及本文中必需的基础知识.
第二章作者给出一种求解有界箱式约束变分不等式问题的光滑化同伦方法.首先将有界的箱式约束变分不等式问题等价变形为一个非光滑方程,然后将其中的非光滑部分一中值函数用Gabriel-Moré光滑函数逼近,并用它构造出一个光滑的同伦方程.则在所定义的映射F不需要做任何单调性假定的条件下,对几乎所有的初始点,可以证明同伦路径的存在性和收敛性.此外,作者还证明,如果初始点选在约束区域的内部时,所给出的方法也适用于内点法.数值实验结果表明这是一种有效的方法,且计算效率更高.
第三章作者给出求解球约束变分不等式问题的同伦方法.首先将球约束变分不等式问题等价变形为一个非光滑方程,然后将其中的非光滑部分——投影函数用一个类似于Chen-Harker-Kanzow-Smale函数的函数光滑化,并用其构造出一个光滑的同伦方程.则在映射F不需要做任何单调性假设的条件下,对几乎所有的初始点,可以证明同伦路径的存在性和收敛性.数值结果表明这是一种行之有效的方法.
第四章作者利用投影算子的任意光滑逼近构造了解一般的抽象无界闭凸集上的变分不等式问题的同伦方法.在较弱的解存在性条件下,对于几乎所有的初始点,作者证明一条光滑的同伦路径可以收敛到变分不等式问题的解.几个典型的数值实验结果表明这个方法是有效的,且计算效率更高.
在第五章中,给出了一个用来跟踪变分不等式问题的组合同伦路径的新算法,并在一定条件下证明了它的全局收敛性及多项式复杂性.该算法通过保证β-锥邻域在所论区域内部的条件来给出使迭代点列在区域内部的残量控制准则。克服了同伦方法的通用程序中每次预估步、校正步都要判断迭代点列是否在约束区域内部的缺点,从而减少了计算量、提高了计算效率.数值实验结果表明这个算法是有效的.
In this dissertation, homotopy methods for solving variational inequality problems are studied. For box constrained VIPs, ball constrained VIPs and as well as VIPs at general abstract convex sets, by using smooth approximations of their equivalent nonsmooth equations, smooth homotopy are constructed, and existence and convergence of smooth paths are proven under similar conditions with existing combined homotopy methods. The proposed homotopy methods have the same advantage with combined homotopy methods that convergence can be obtained under weak conditions and, nevertheless, it does not introduce in multiplier variables and hence is more efficient in cases that the projection function is easy to compute. Additionally, a new efficient algorithm for numerically tracing the combined homotopy path of the variational inequality problems is given, and its global convergence and polynomial complexity are proven under some conditions.
Chapter 1 devotes to reviewing the history and development of the variational inequality problem and the homotopy method.
In Chapter 2, by using the Gabriel-More smoothing function of the mid function, a smooth homotopy method for solving nonsmooth equation reformulation of bounded box constrained variational inequality problem VIP(l,u, F) is given. Without any monotonic-ity condition on the defining map F, for starting point chosen almost everywhere in R~n, existence and convergence of the homotopy pathway are proven. Nevertheless, it is also proven that, if the starting point is chosen to be an interior point of the box, the proposed homotopy method can also serve as an interior point method. The numerical results show the method is promising.
Utilizing a similar Chen-Harker-Kanzow-Smale function to smooth Robinson's normal equation in Chapter 3, the author presents a smoothing homotopy method for solving ball constrained variational inequalities. Without any monotonicity condition on the defining map F, for the starting point chosen almost everywhere in R~n, existence and convergence of the homotopy pathway are proven. Numerical experiments illustrate the method is feasible and efficient.
In Chapter 4, a smoothing homotopy method for solving the variational inequality problem on a general nonempty closed convex subset of R~n is proposed. The homotopy equation is constructed based on the smooth approximation to Robinson's normal equa- tion of variational inequality problem, where the smooth approximation function of the projection function belongs to the interior of the feasible set. Under a weak condition, which is needed for the existence of a solution to variational inequality problem, for the starting point chosen almost everywhere in R~n, existence and convergence of a smooth homotopy pathway are proved. Several numerical experiments indicate that the method is efficient.
In Chapter 5, a new algorithm for tracing the combined homotopy path of the variational inequality problems is proposed, and its global convergence and polynomial complexity are established under some conditions. The residual control criteria, which ensures that the obtained iterative points are interior points, is given by the condition that ensures theβ-cone neighborhood to be included in the interior part of the feasible region. Hence, the algorithm avoids judging whether the iterative points are the interior points or not in every predictor step and corrector step so that the computation is reduced greatly. The preliminary numerical experiments demonstrate that the algorithm is efficient and promising.
引文
[1]E.L.Allgower and K.Georg,Numerical Continuation Methods:An Introduction,Springer-Vergal,Berlin,New York,1990.
[2]R.Andreani,A.Friedlander and J.M.Martinez,On the solution of finite-dimensional variational inequalities using smooth optimization with simple bounds,Journal of Optimization Theory and Applications,94(1997)635-657.
[3]R.Andreani,A.Friedlander and J.M.Martinez,On the solution of bounded and unbounded mixed complementarity problems,Optimization,50(2001)265-278.
[4]A.Auslender,Optimization méthodes numériques,Masson,Paris,1976.
[5]A.B.Bakusinskii and B.T.Polyak,On the solution of variational inequalities,Sov.Math.Dokl.,15(1974)1705-1710.
[6]S.C.Billups,S.P.Dirkse and M.C.Ferris,A comparison of algorithms for large-scale mixed complementarity problems,Computational Optimization and Applications,7(1997)3-25.
[7]S.C.Billups,A.L.Speight and L.T.Watson,Nonmonotone path following methods for nonsmooth equations and complementarity problems.Complementarity:applications,algorithms and extensions(Madison,WI,1999),19-41,Appl.Optim.,50,Kluwer Acad.Publ.,Dordrecht,2001.
[8]S.C.Billups and L.T.Watson.A probability-one homotopy algorithm for nonsmooth equations and mixed complementarity problems,SIAM Journal on Optimization.12(2002)606-626.
[9]R.E.Bruck,An iterative solution of a variational inequality for certain monotone operators in Hilbert space,Bull.Amer.Math.Soc.,81(1975)890-892.
[10]J.Burke and S.Xu,A non-interior predictor-corrector path-following algorithm for LCP,in Reformulation:Nonsmooth,Piecewise Smooth and Smoothing Methods,Edited by Fukushima,M.and Qi,L.,Kluwer Academic Publishers,Boston,1999,pp.45-64.
[11]J.Burke and S.Xu,A non-interior predictor-corrector path following algorithm for the monotone linear complementarity problems,Mathematical Programming,87(2000)113-130.
[12]J.Burke and S.Xu,Complexity of a noninterior path-following method for the linear complementarity problem,Journal of Optimization Theory and Applications,112(2002)53-76.
[13]B.Chen and X.Chen,A global and local superlinear continuation-smoothing method for P_0 + R_0 NCP,SIAM Journal on Optimization,9(1999)624-645.
[14] B. Chen and P. T. Harker, A noninterior continuation method for quadratic and linear programming, SIAM J. Optim., 3 (1993) 503-515.
[15] B. Chen and P. T. Harker, Smooth approximations to nonlinear complementarity problems. SIAM Journal on Optimization, 7(2) (1997) 403-420.
[16] B. Chen and N. Xiu, A global linear and local quadratic non-interior continuation method for nonlinear complementarity problems based on Chen-Mangasarian smoothing functions, SIAM J. Optim., 9 (1999) 605-623.
[17] C. Chen and O. L. Mangasarian, Smoothing methods for convex inequalities and linear complementarity problems, Math. Programming, 71 (1995) 51-96.
[18] C. Chen and O. L. Mangasarian, A class of smoothing functions for nonlinear and mixed complementarity problems, Comput. Optim. Appl., 5 (1996) 97-138.
[19] X. Chen and L. Qi, A parameterized Newton method and a Broyden-like method for solving nonsmooth equations, Comput. Optim. Appl., 3 (1994) 157-179.
[20] 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, 67 (1998) 519-540.
[21] X. Chen and Y. Ye, On homotopy-smoothing methods for box-constrained variational inequalities, SIAM Journal on Control and Optimization, 37 (1999) 589-616.
[22] S. N. Chow, J. Mallet-Paret and J. A. Yorke, Finding Zeros of Maps: Homotopy methods that are constructive with probability one, Math. Comput, 32 (1978) 887-899.
[23] CNRS, Mathematics and Mathematical models, Gazette des Mathematiciens, 20, oct. 1982.
[24] O. Davidenko, On a new method of numerical solution of system of nonlinear equations. Doklady Akad. Nauk USSR, 28 (1953) 601-604.
[25] F. Facchinei, A. Fischer and C. Kanzow, A semismooth Newton method for variational inequalities: Theoretical results and preliminary numerical experience, Preprint 102, Institute of Applied Mathematics, University of Hamburg, Hamburg, Decemeber 1995.
[26] F. Facchinei, A. Fischer and C. Kanzow, A semismooth Newton method for variational inequalities: The case of box constraints. In: M.C. Ferris and J.-S. Pang (eds.): "Complementarity and Variational Problems: State of the Art", SIAM, Philadelphia, 1997, pp. 76-90.
[27] F. Facchinei and J.-S. Pang, Finite-dimensional variational inequalities and complementarity problems, Vol. I, II, Springer Series in Operations Research, Springer-Verlag, New York, 2003.
[28] G. Feng, Z. Lin and B. Yu, Existence of an interior pathway to a Karush-Kuhn-Tucker point of a nonconvex programming problem, Nonlinear Analysis TMA, 32 (1998) 761-768.
[29] G. Feng and B. Yu, Combined homotopy interior point method for nonlinear programming problems, in: H. Fujita, M. Yamaguti (Eds.), Advances in Numerial Mathematics; Proceedings of the second Japan-China Seminar on Numerical Mathematics, Lecture Notes in Numerical and Applied Analysis, Kinokuniya, Tokyo, 14 (1995) 9-16.
[30]M.C.Ferris and J.-S.Pang,Engineering and economic applications of complementarity problems,SIAM Review,39(1997)669-713.
[31]A.V.Fiacco and G.P.McCormick,Nonlinear Programming:Sequential Unconstrained Minimization Techniques,John Wiley & Sons,New York,1968,reprinted by SIAM Publications,1990.
[32]A.Fischer,A special Newton-type optimization method,Optimization,24(1992)269-284.
[33]A.Friedlander,J.M.Martinez and S.A.Santos,A new strategy for solving variational inequalities on bounded polytopes,Numerical Functional Analysis and Optimization,16(1995)653-668.
[34]K.R.Frisch,The logarithmic potential method of convex programming,Memorandum,Institute of Economics,Oslo,Norway,1955.
[35]M.Fukushima,A relaxed projection method for variational inequalities,Mathematical Programming,35(1986)58-70.
[36]M.Fukushima,Merit functions for variational inequality and complementarity problems.In:Nonlinear Optimization and Applications,G.Di Pillo,F.Giannessi,eds.,Plenum Publishing Corporation,New York,1996,pp.155-170.
[37]S.A.Gabriel and J.J.Moré,"Smoothing of mixed complementarity problems" in Complementarity and Variational Problems:State of the Art,M.C.Ferris and J.S.Pang(Eds.).SIAM:Philadelphia,Pennsylvania,1997,pp.105-116.
[38]C.B.Garcia and W.I.Zangwill,Pathways to Solutions,Fixed Points and Equilibria,Prentice-Hall,Englewood cliffs,N.J.,1981.
[39]M.K.Gavurin,Nonlinear functional equations and continuous analogues of iteration methods,Izv.Vyssh.Uchevn.Zaved.Mat.,5(6)(1958)18-31(In Russian).
[40]A.A.Goldstein,Convex programming in Hilbert space,Bull.Amer.Math.Soc.,70(1964)709-710.
[41]W.Gómez Bofill,Properties of an interior embedding for solving nonlinear optimization problems,Math.Program.(Series A),86(3)(1999)649-659.
[42]J.Hadamard,Etude sur les propriétés des fon éntiéres et en particulier d'une function.Math Naturwiss Anz Ungar Akad Wiss,21(1906)369-390.
[43]P.T.Harker and J.-S.Pang,Finite-dimensional variational inequality and nonlinear complementarity problem:a survey of theory,algorithm and applications,Math.Program.,48(1990)161-220.
[44]P.T.Harker and B.Xiao,Newton method for the nonlinear complementarity problem:A B-differentiable equation approach,Math.Program.(Series B),48(1990)339-357.
[45]B.He,A class of projection and contraction methods for monotone variational inequalities,Appl.Math.Optimization,35(1997)69-76.
[46]B.He and L.Liao,Improvements of some projection methods for monotone nonlinear variational inequalities,Journal of Optimization Theory and Applications,112(2002)111-128.
[47]B.He,Z.Yang and X.Yuan,An approximate proximal-extragradient type method for monotone variational inequalities,J.Math.Anal.Appl.,300(2004)362-374.
[48]D.den Hertog,Interior Point Approach to Linear,Quadratic and Convex Programming,Algorithms and Complexity,Kluwer Academic Publishers,Dordrecht,The Netherlands,1994.
[49]W.Hock and K.Schittkowski,Test examples for nonlinear programming codes,Springer,Berlin,1981.
[50]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 Applications,17(2000)183-201.
[51]Z.Huang,Sufficient conditions on nonemptiness and boundedness of the solution set of the P_0 function nonlinear complementarity problem,Operation Research Letters,30(2002)202-210.
[52]Z.Huang,D.Sun and G.Zhao,A smoothing Newton-type algorithm of stronger convergence for the quadratically constrained convex quadratic programming,Comput.Optim.Appl.,35(2006),199-237.
[53]A.N.Iusem,An iterative algorithm for the variational inequality problem,Comput.Appl.Math.,13(1994)103-114.
[54]A.N.Iusem and B.F.Svaiter,A variant of Korpelevich's method for variational inequalities with a new search strategy,Optimization,42(1997),pp.309-321.
[55]F.Jarre,On the method of analytic centers for solving smooth convex programs,Lecture Notes in Mathematical,Optimization,Springer,1405(1989)69-85.
[56]F.Jarre,Interior-point methods for convex programming,Applied Mathematics and Optimization,26(1992)287-311.
[57]H.Jiang and L.Qi,A new nonsmooth equations approach to nonlinear complementarity problems,SIAM J.Control Optim.,35(1997)178-193.
[58]N.H.Josephy,Newton's method for generalized equations,Technical summary report 1965,Mathematics Research Center,University of Wisconsin,Madison,WI,1979.
[59]C.Kanzow,Some equation-based methods for the nonlinear complementarity problem,Optimization Methods and Software,3(1994)327-340.
[60]C.Kanzow,Nonlinear complementarity as unconstrained optimization,Journal of Optimization Theory and Applications,88(1996)139-155.
[61]C.Kanzow,Some noninterior continuation methods for linear complementarity problems,SIAM Journal on Matrix Analysis and Applications,17(1996)851-868.
[62]C.Kanzow,Inexact semismooth Newton methods for large-scale complementarity problems.Optimization Methods and Software,19(2004)309-325.
[63]C.Kanzow and H.Pieper,Jacobian smoothing methods for nonlinear complementarity problems,SIAM J.Optim.,9(1999)342-373.
[64]N.Karmarkar,A new polynomial-time algorithm for linear programming,Combinatorica,4(1984)373-395.
[65]R.B.Kellogg,T.-Y.Li and J.A.Yorke,A constructive proof of the Brouwer fixed-point theorem and computational results,SIAM J.Numerical Analysis,13(1976)473-483.
[66]E.N.Khobotov,A modification of the extragradient method for the solution of variational inequalities and some optimization problems,USSR Comput.Math.Math.Phys.,27(1987)1462-1473.
[67]M.Kojima,N.Megiddo and T.Noma,Homotopy continuation methods for nonlinear complementarity problems,Mathematics of Operations Research,16(1991)754-774.
[68]M.Kojima,S.Mizuno and A.Yoshise,A primal-dual interior point algorithm for linear programming,in:N.Megiddo,ed.,Progress in Mathematical Programming,Interior Point and Related Methods,Springer-Verlag,New York,1988,pp.29-47.
[69]M.Kojima,S.Mizuno and A.Yoshise,A polynomial-time algorithm for a class of linear complementarity problems,Mathematical Programming,44(1989)1-26.
[70]M.Kojima and S.Shindo,Extensions of Newton and quasi-Newton methods to systems of PC~1 equations,Journal of Operation Research Society of Japan,29(1986)352-374.
[71]G.M.Korpelevich,The extragradient method for finding saddle points and other problems,Matecon,12(1976)747-756
[72]E.S.Levitin and B.T.Polyak,Constrained minimization problems,USSR Comput.Math.Math.Phys.,6(1966)1-50.
[73]D.Li and M.Fukushima,Smoothing Newton and Quasi-Newton methods for mixed complementarity problems,Computational Optimization and Applications,17(2000)203 - 230.
[74]J.Li and Q.Liu,A combined homotopy method for solving a class of bilevel programming problems,J.Jilin Univ.Sci.(Chinese)45(2007)213-215.
[75]J.Li,Q.Liu,W.Xang and G.Feng,A homotopy method for solving MPEC problem.Dyn.Contin.Discrete Impuls.Syst.Set.A Math.Anal.,14(2007),Part 2,suppl..708-712.
[76]Y.Li and Z.Lin,A constructive proof of the Poincare-Birkhoff theorem,Trans.Amer.Math.Soc.,37(1995)2111-2126.
[77]Z.Lin and Y.Li,Homotopy method for solving variational inequalities,Journal of Optimization Theory and Applications,100(1)(1999)207-218.
[78]Z.Lin,Y.Li and B.Yu,A combined homotopy interior point method for general nonlinear programming problems,Appl.Math.Comput.,80(1996)209-224.
[79]Z.Lin,B.Yu and G.Feng,A combined homotopy interior point method for convex nonlinear programming,Applied Mathematics and Computation,84(1997)193-211.
[80]Z.Lin,B.Yu and D.Zhu,A continuation method for solving fixed points of self-mappings in general nonconvex sets,Nonlinear Analysis TMA,52(2003)905-915.
[81]Z.Lin,D.Zhu and Z.Sheng,Finding a minimal efficient solution of a convex multiobjective program,Journal of Optimization Theory and Applications,118(3)(2003)587-600.
[82]Q.Liu and Z.Lin,A homotopy interior point method for computing weakly efficient solutions of multiobjective programming problems,Acta Math.Appl.Sinica(Chinese),23(2000)188-195.
[83]Q.Liu,B.Yu and G.Feng,An interior point path-following method for nonconvex program ming with quasi normal cone condition,数学进展,29(2000)281-282.
[84]刘国新,求解序列极大极小问题、互补问题和变分不等式的凝聚同伦方法,吉林大学博士学位论文,2003.
[85]O.L.Mangasarian,Equivalence of the complementarity problem to a system of nonlinear equations,SIAM J.Appl.Math.,31(1976)89-92.
[86]P.Marcotte,Application of Khobotov's algorithm to variational inequalities and network equilibrium problems,Inform.Systems Oper.Res.,29(1991)258-270.
[87]R.Mifflin,Semismooth and semiconvex functions in constrained optimization,SIAM Journal on Control and Optimization,15(1977)957-972.
[88]R.D.C.Monteiro and I.Adler,Interior path following primal-dual algorithms,part Ⅰ:Linear programming,Mathematical Programming,44(1989)27-41.
[89]R.D.C.Monteiro and I.Adler,Interior path following primal-dual algorithms,part Ⅱ:Convex quadratic programming,Mathematical Programming,44(1989)43-66.
[90]R.D.C.Monteiro and I.Adler,An extension of Karmarkar type algorithm to a class of convex separable programming problems with global linear rate of convergence,Mathematics of Operations Research,15(1990)408-422.
[91]G.L.Naber,Topological Method in Euclidean space,Cambridge Univ.Press,London,1980.
[92]Y.E.Nesterov and A.S.Nemirovsky,Interior Point Polynomial Methods in Convex Programming,SIAM Publications,1994.
[93]J.Nocedal and S.J.Wright,Numerical Optimization,Springer-Verlag,New York,1999.
[94]J.-S.Pang,A B-differentiable equation based,globally and locally quadratically convergent.algorithm for nonlinear programs,complementarity and variational inequality problems,Math.Programming,51(1991)101-131.
[95]J.-S.Pang,Complementarity problems,In R.Horst and P.Pardalos,Eds.,Handbook of Global Optimization.Kluwer Academic Publishers:Boston,1994,pp.271-338.
[96]J.-S.Pang and S.A.Gabriel,A robust algorithm for the nonlinear complementarity problem,Math.Programming,60(1993)295-337.
[97]J.Peng and M.Fukushima,A hybrid Newton method for solving the variational inequality problem via the D-gap function,Math.Programming,86(2)(1999)367-386.
[98]H.Qi,A regularized smoothing Newton method for box constrained variational inequality problems with P_0 functions,SIAM Journal on Optimization,10(2000)315-330.
[99]H.Qi and L.Liao,A smoothing Newton method for extended vertical linear complementarity problems,SIAM Journal on Matrix Analysis and Applications,21(1999)45-66.
[100]H.Qi and L.Liao,A smoothing New,on method for general nonlinear complementarity problems,Computational Optimization and Applications,17(2000)231-253.
[101]L.Qi,Convergence analysis of some algorithms for solving nonsmooth equations,Mathe matics of Operations Research,18(1993)227-244.
[102]L.Qi,Regular pseudo-smooth NCP and BVIP functions and globally and quadratically con vergent generalized Newton methods for complementarity and variational inequality problems,Mathematies of Operations Research,24(1999)440-471.
[103]L.Qi and J.Sun,A nonsmooth version of Newton's method,Mathematical Programming,58(1993)353-367.
[104]L.Qi and D.Sun,A survey of some nonsmooth equations and smoothing Newton methods,in:A.Eberhard,B.Glover,R.Hill,D.Ralph(Eds.),Progress in Optimization:Contributions from Australisia,Kluwer Academic,Dordrecht,1999.
[105]L.Qi and D.Sun,Improving the convergence of non-interior point algorithm for nonlinear complementarity problems,Math.Comput.,69(2000),283-304.
[106]L.Qi and D.Sun,Smoothing functions and smoothing Newton method for complementarity and variational inequality problems,Journal of Optimization Theory and Applications,113(1)(2002)121-147.
[107]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,87(2000)1-35.
[108]L.Qi,S.Wu and G.Zhou,Semismooth Newton methods for solving semi-infinite programming problems,Journal of Global Optimization,27(2003)215-232.
[109]L.Qi and G.Zhou,A smoothing Newton method for ball constrained variational inequalities with applications,Computing[Suppl],15(2001)211-225.
[110]S.M.Robinson,Normal maps induced by linear transformation,Math.Oper.Res.,17(1992)691-714.
[111]商玉凤,求解非线性规划、均衡规划和变分不等式问题的动边界组合同伦方法,吉林大学博士学位论文,2006.
[112]A.Shapiro,Sensitivity analysis of parameterized variational inequalities,Mathematics of Operations Research,30(2005)109-126.
[113]M.Sibony,Méthodes itératives pour les équations et inéquations aux dérivées partielles nonlinéares de type monotone,Calcolo 7(1970)65-183.
[114]S.Smale,A convergent process of price adjustment and global Newton method,J.Math.Econ.,3(1976)107-120.
[115]S.Smale,The problem of the average speed of the simplex method,Mathematical programming:the state of the art.Proceedings of the 11th International Symposium on Mathematical Programming held at the University of Bonn,Bonn,August 23-27,1982.
[116]S.Smale,Algorithms for solving equations,Proceeding of International Congress of Mathematicians,Edited by Gleason,A.M.,American Mathematics Society,Providence,Rhode Island,1986,pp.172-195.
[117]M.V.Solodov and B.F.Svaiter,A new projection method for variational inequality prob lems,SIAM Journal on Control and Optimization,37(1999)765 - 776.
[118]M.V.Solodov and B.F.Svaiter,a truly globally convergent Newton-type method for the monotone nonlinear comptementarity problem,SIAM Journal on Control and Optimization,10(2000)605-625.
[119]M.V.Solodov and P.Tseng,Modified projection-type methods for monotone variational inequalities,SIAM J.Control Optim.,34(1996)1814-1830.
[120]G.Sonnevend,An analytical centre for polyhedrons and new classes of global algorithms for linear(smooth,convex)programming.In:A.Prékopa(Ed.).Lecture Notes in Control and Information Sciences.vol.84,Springer-Verlag,New York,1985,pp.866-876.
[121]G.Stampacchia,Formes bilineaires coercitives sur les ensembles convexes,C.R.A.S.,Paris 1964,258:4413-4416.
[122]D.Sun,A new step-size skill for solving a class of nonlinear projection equations,J.Comput.Math.,13(1995),pp.357-368.
[123]D.Sun,M.Fukushima and L.Qi,"A computable generalized Hessian of the D-gap function and Newton-type methods for variational inequality problem",in:M.C.Ferris and J.-S.Pang,eds.,Complementarity and Variational Problems - State of the Art,SIAM Publications,Philadelphia,1997,pp.452-473.
[124]D.Sun and J.Han,Newton and quasi-Newton methods for a class of nonsmooth equations and related problems.SIAM J.Optim.,7(1997)463-480.
[125]D.Sun and L.Qi,Solving variational inequality problems via smoothing-nonsmooth reformulations,Journal of Computational and Applied Mathematics,129(2001)37-62.
[126]D.Sun and R.S.Womersley,A new unconstrained differentiable merit function for box constrained variational inequality problems and a damped Gauss-Newton method,SIAM J.OPTIM.,9(2)(1999)388-413.
[127]D.Sun,R.S.Womersley and H.Qi,A feasible semismooth asymptotically Newton method for mixed complementarity problems,Mathematical Programming,94(1)(2002)167-187.
[128]K.Taji,M.Fukushima and T.Ibaraki,A globally convergent Newton method for solving strongly monotone variational inequalities,Mathematical Programming,58(1993)369-383.
[129]T.Terlaky(Ed.),Interior Point Methods of Mathematical Programming Problems,Kluwer Academic Publishers,Dordrecht,1996.
[130]Ulji and G.Chen,New simple smooth merit function for box constrained variational inequalities and damped Newton type method,Applied Mathematics and Mechanics,26(8)(2005)1083-1092.
[131]C.Wang,Z.Li and Q.Liu,A new method for linear multiobjective programming,J.Jilin Univ.Sci.(Chinese),43(2005)282 - 286.
[132]L.T.Watson,Solving the nonlinear complementarity problem by a homotopy method,SIAM Journal on Control and Optimization,17(1979)36-46.
[133]L.T.Watson,Theory of globally convergent probability-one homotopies for nonlinear programming,SIAM J.Optim.,11(2000)761-780.
[134]L.T.Watson,S.C.Billups and A.P.Morgan,ALGORITHM 652:HOMPACK:a suite of codes for globally convergent homotopy algorithms,ACM Trans.Math.Software,13(1987) 281-310.
[135]H.Wolkowicz,R.Saigal and L.Vandenberghe,Handbook of Semidefinite Programming,Kluwer,Academic Publishers,2000.
[136]So J.Wright,Primal-Dual Interior-Point Methods,SIAM Publications,Philadelphia,1997.
[137]Q.Xu,Homotopy method for solving Nash equilibria,to appear.
[138]徐庆、林正华,组合同伦方法在无界域上的收敛性,应用数学学报.27(2004)624-631.
[139]Q.Xu,B.Yu and G.Feng,Homotopy Method for Variational Inequalities,Advances in Mathematics(Chinese),30(2001)476-479.
[140]Q.Xu,B.Yu and G.Feng,Homotopy method for solving variational inequalities in unbounded sets,Journal of Global Optimization,31(2005)121-131.
[141]Q.Xu,B.Yu,G.Feng and C.Dang,A condition for global convergence of a homotopy method for variational inequality problems on unbounded sets,Optimization Methods and Software,22(2007)587-599.
[142]S.Xu,The global linear convergence of an infeasible noninterior path-following algorithm for complementarity problems with uniform P-functions,Mathematical Programming(Series A),87(2000)501-517.
[143]N.Yamashita and M.Fukushima,Modified New,on methods for solving a semismooth reformulation of monotone complementarity problems,Mathematical Programming,76(1997)469 - 491.
[144]Y.Yang,X.Lv and Q.Liu,A combined homotopy infeasible interior-point method for convex nonlinear programming,Northeast.Math.J.,22(2006)188 - 192.
[145]Y.Yang,X.Lv,Q.Liu and Z.Zheng,Homotopy interior point algorithm for the set of effective solutions of double-objective convex programming,J.Jilin Univ.Sci.(Chinese).44(2006)39- 43.
[146]Y.Yang,L.Zhao,X.Lv and Q.Liu,The aggregate homotopy interior-point method for multi-objective convex programming,J.Jilin Univ.Sci.(Chinese),44(2006)883 - 887.
[147]Y.Yang,L.Zhao,X.Lv and Q.Liu,Homotopy interior-point method for minimal weak effect solutions of multi-object programming under quasi-normal cone condition,J.Jilin Univ.Sci.(Chinese),45(2007)35 - 38.
[148]B.Yu,G.Feng and S.Zhang,The aggregate constraint homotopy method for nonconvex nonlinear programming,Nonlinear Analysis TMA,45(2001)839-847.
[149]B.Yu and Z.Lin,Homotopy method for a class of nonconvex Brouwer fixed point problems.Appl.Math.Comput.,74(1996)65-77.
[150]B.Yu,Q.Liu and G.Feng,A combined homotopy interior point method for nonconvex programming with pseudo cone condition,Northeast.Math.J.,16(2000)383-386.
[151]于波、商玉凤,解非凸规划问题的动边界组合同伦方法,数学研究与评论,26(4)(2006)831-834.
[152]B.Yu,Q.Xu and G.Feng,On the complexity of a combined homotopy interior point method for convex programming,J.Comput.Appl.Math.,200(2007)32-46.
[153]I.Zang,A smoothing-out technique for min-max optimization,Math.Program.,19(1980)61-77.
[154]Y.Zhao,J.Han and H.Qi,Exceptional families and existence theorems for variational inequality problems,Journal of Optimization Theory and Applications,101(1999)475-495.
[155]D.Zhu,Q.Xu and Z.Lin,A homotopy method for solving bilevel programming problem,Nonlinear Analysis TMA,57(2004)917-928.