摘要
本文主要研究互补问题与半定规划问题的数值解法。所取得的主要结果有:
1.提出无约束最优化共轭梯度法参数β_κ修正的两种新形式。与经典共轭梯度法的区别是新方法中体现了函数值下降量信息。提出这两种方法的改进形式。证明了这四种方法的全局收敛性。数值实验表明了算法的有效性。
2.提出求解大规模非线性互补问题(NCP(F))的共轭梯度法。(ⅰ)利用Fischer-BurmeisterNCP-函数,将NCP(F)转化为非线性方程组,基此提出PRP-型共轭梯度法。算法的突出特点是在不需要额外假设及线搜索的辅助下满足充分下降条件,在F是连续可微P_0+R_0函数且F′(x)在水平集上全局Lipschitz连续条件下,算法全局收敛。(ⅱ)利用光滑Fischer-Burmeister函数,将NCP(F)转化为光滑非线性方程组,基此对大规模非线性互补问题提出光滑PRP-型共轭梯度法。算法执行一步需进行两个Armijo线性搜索既确保光滑参数μ的非负性又极小化由光滑Fischer-Burmeister函数所形成的光滑价值函数.在F为P_0+R_0连续可微函数时,算法全局收敛。数值实验表明了这两种算法的数值有效性。
3.提出半定规划的半定互补解法。首先考虑一类特殊的半定规划问题(即在对偶问题中加入约束条件y≥0),将其最优性条件等价转化为半定互补问题(SDCP),藉此提出预估-校正光滑牛顿法,证明了牛顿方向的存在性、迭代点列的有界性及算法的全局收敛性。在解点处广义导数可逆的假设下得到算法的超线性收敛率。然后推广这一思想,将标准半定规划的最优性条件转化为广义半定互补问题(GSDCP),提出预估-校正光滑牛顿法。该方法是非线性互补问题(NCP(F))算法的推广。同样证明了牛顿方向的存在性、迭代点列的有界性及算法的全局收敛性。在解点处广义导数可逆的假设下得到算法的二次收敛率。不需要任何对称化技巧,此二方法自动产生对称搜索方向。
4.提出半定规划的非内点连续化方法。该方法是求解半定互补问题(SDCP)算法的推广。证明了牛顿方向的存在性。在中心路径邻域有界的假设下得到迭代点列的有界性,进而证明了算法的全局收敛性。在解点处广义导数可逆的假设下算法局部二次收敛。给出了数值实验结果。
5.提出半定规划的PRP~+共轭梯度法。基于Fischer-Burmeister SDCP-函数,对SDP的最优性条件提出一梯度具有全局Lipschitz连续性的价值函数,从而将半定规划转化为无约束优化问题,进而用PRP~+共轭梯度法求解.为得到PRP~+共轭梯度法的收敛性同时使函数值在每次迭代中有所下降,提出一Armijo-型线搜索。无需水平集有界及迭代点列聚点的存在,算法全局收敛。
This thesis is devoted to study the algorithms for complementarity and semidefinite programming problems.The main results,obtained in this dissertation,are summarized as follows:
1.Two new formulas of the main parameterβ_k of conjugate gradient methods for unconstrained optimization problems are presented.In comparison with classic conjugate gradient methods,the new methods take both available gradient and function value information. Furthermore,their modifications are proposed.The global convergence of these methods are proved respectively.Numerical results indicate that these algorithms are efficient.
2.The conjugate gradient algorithms for large scale nonlinear complementarity problems (NCP(F)) are proposed.(ⅰ) We present a new PRP-type conjugate gradient method for solving large scale nonlinear complementarity problems based on a nonlinear system of equations reformulated by Fischer-Burmeister NCP-function,which satisfies the sufficient descent condition without requiring any assumption.Under the conditions that F:IR~n→IR~n is a continuously differentiable P_0+R_0 function and the Jacobian matrix F′(x) satisfies global Lipschitzian continuity on level set,global convergence result is established.Numerical experience is reported which demonstrates good computational performance on large scale NCP(F).(ⅱ) A PRP-type smoothing conjugate gradient method for solving large scale nonlinear complementarity problems is proposed based on a smoothing nonlinear system of equations reformulated by smoothing Fischer-Burmeister function.At each iteration,two Armijo line searches are performed,which guarantee the positive property of the smoothing parameterμand minimize the merit function formed by smoothing Fischer-Burmeister function,respectively.Global convergence is obtained when F:IR~n→IR~n is a continuously differentiable P_0+R_0 function. Finally,numerical examples are given to show the effectiveness of the method.
3.The semidefinite complementarity methods are presented to solve semidefinite programming (SDP).Firstly,a special type of semidefinite programming(namely,the dual problem contains the constraint y≥0) is considered.The optimality conditions of semidefinite programming is reformulated equivalently as a semidefinite complementarity problem (SDCP),and then a predictor-corrector smoothing Newton algorithm for SDCP is presented.The existence of Newton directions,boundedness of iterates and global convergence are proved.Local superlinear convergence is proved under the assumption that the generalized derivative at solution point are invertible.Secondly,the optimality conditions of the standard semidefinite programming is reformulated as a generalized semidefinite complementarity problem(GSDCP).Then,enlightened by some techniques in algorithms for NCP(F),we present a predictor-corrector smoothing Newton algorithm and prove the existence of Newton directions,boundedness of iterates and global convergence.Local quadratic convergence can be obtained under the condition that the generalized derivative at solution point are invertible.The presented methods generate symmetric directions without any further transformations.
4.The noninterior continuation method for semidefinite complementarity problem(SDCP) is extended to semidefinite programming(SDP).The existence of Newton directions is proved.The boundedness of iterates generated by the method is obtained under the condition that the neighborhood is bounded,and the global convergence is proved. Local quadratic convergence follows from the assumption that the generalized derivative at solution point are invertible.Some numerical results are also reported.
5.The PRP~+ conjugate gradient algorithm for solving semidefinite programming(SDP) is discussed.Based on the Fischer-Burmeister SDCP-function,a merit function with globally Lipschitzian continuously gradient for the optimality conditions of SDP is proposed, which reformulates the optimality conditions as an unconstrained optimization problem. The PRP~+ conjugate gradient algorithm is applied to solve this problem.In order to obtain the convergence of the PRP~+ method and decrease the function evaluation at each iteration,we provide a new Armijo-type line search rule.Global convergence of the algorithm is proved without requiring the boundedness of level set and existence of accumulation point of produced sequence by the method.
引文
[1]R.W.Cottle,Nonlinear programs with positively bounded Jacobians,Ph.D.dissertation,Department of Mathematics,University of California(Berkeley,CA),1964.
[2]R.W.Cottle,G.L.Habetler and C.E.Lemke,Quadratic forms semi-definite over convex cones,in:H.W.Kuhn,ed.,Proceedings of the Princeton Symposium on Mathematical Programming (Princeton University Press,Princeton,NJ),1970,551-565.
[3]S.Karamardian,Generalized complementarity problem,J.Optim.Theory Appl.,1971,8:161-167.
[4]R.W.Cottle,J.S.Pang and R.E.Stone,The linear complementarity problem,Academic Press,San Diego,1992.
[5]F.Facchinei and J.S.Pang,Finite-dimensional variational inequalities and complementarity problems,Springer-Verlag,New York,Berlin,Heidelberg,2003.
[6]M.C.Ferris and J.S.Pang,Engineering and economic applications of complementarity problems,SIAM J.Review,1997,39:669-713.
[7]韩继业,修乃华,戚厚铎,非线性互补理论与算法,上海科学技术出版社,上海,2006.
[8]P.Hartman and G.Stampacchia,On some nonlinear elliptic differential functional equations,Acta Mathematiea,1966,115:153-188.
[9]M.Kojima,S.Mizuno and A.Yoshise,A polynomial-time algorithm for a class of linear complementarity problems,Math.Programming,1989,44:1-26.
[10]M.Kojima,Y.Kurita and S.Mizuno,Large-step interior point algorithms for linear complementarity problems,SIAM J.Optmization,1993,3:398-412.
[11]J.S.Pang and S.A.Gabriel,NE/SQP:A robust algorithm for the nonlinear complementarity problem,Math.Programming,1993,60:295-337.
[12]A.Fischer,On the local superlinear convergence of a Newton-type method for LCP under weak conditions,Optimization Methods and Software,1995,6:83-107.
[13]H.Jiang and L.Qi,A new nonsmooth equations approach to nonlinear complementarity problems,SIAM Journal on Control and Optimization,1997,35:178-193.
[14]T.D.Luca,F.Facchinei,and C.Kanzow,A semismooth equation approach to the solution of nonlinear complementarity problems,Mathematical Programming,1996,75:407-439.
[15]N.Yamashita and M.Fukushima,Modified Newton methods for solving a semismooth reformulation of monotone complementarity problems,Mathematical Programming,1997,76:469-491.
[16]B.Chen and X.Chen,A global and local superlinear continuation-smoothing method for P_0and R_0 NCP or monotone NCP,SIAM J.Optim.,1999,9:624-645.
[17]J.J.More,Coercivity conditions in nonlinear complementarity problems,SIAM Review,1974,16:1-16.
[18]B.Chen and N.Xiu,A global and local quadratic noninterior continuation smoothing method for nonlinear complementarity problems based on Chen-Mangasarian smoothing functions,SIAM J.Optim.,1999,9:605-623.
[19]D.Sun and L.Qi,On NCP-functions,Computational Optimization and Applications,1999,13:201-220.
[20]陈公宁,矩阵理论与应用,高等教育出版社,北京,1990.
[21]B.Chen and P.T.Harker,A non-interior-point continuation method for linear complementarity problems,SIAM J.Matrix Anal.Appl.,1993,14:1168-1190.
[22]P.T.Harker and J.S.Pang,Finite-dimensional variational inequality and nonlinear compleraentarity problem:A survey of theory,algorithms and applications.Math.Programming,1990,48:161-220.
[23]S.J.Wright,Primal-dual interior-point methods,SIAM,Philadelphia,PA,1997.
[24]M.Kojima,S.Mizuno and S.Yoshise,A primal-dual interior point algorithm for linear programming,in:N.Megiddo,ed.,Progress in Mathematical Programming,Interior-point and related methods,New York:Springer-Verlag,1989,29-47.
[25]M.Achache,A weighted-path-following method for the linear complementarity problem,Stud.Univ.Babes-Bolyai Inform.,2004,49:61-73.
[26]A.Keraghel,Z.Kebbiche and M.Achache,An implementing weighted path-following algorithm for linear complementarity problems,An.Univ.Oradea Fasc.Mat.,2007,14:53-64.
[27]Y.B.Zhao and D.Li,A new path-following algorithm for nonlinear P_* complementarity problems,Computational Optimization and Applications,2005,34:183-214.
[28]M.Kojima,S.Mizuno and A.Yoshise,An O((?)L) iteration potential reduction algorithm for linear complementarity problems,Math.Programming,1991,50:331-342.
[29]M.Kojima,N.Megiddo,T.Noma and A.Yoshise,A unified approach to interior point algorithms for linear complementarity problems,Lecture Notes in Computer Science 538,Berlin:Springer-Verlag,1991.
[30]Y.Y.Ye,A further result on the potential reduction algorithm for the P-matrix linear complementarity problem,Advances in Optimization and Parallel Computing,P.M.Pardalos,ed.,North-Holland,Amsterdam,New York,1992,310-316.
[31]P.M.Pardalos,Y.Ye,C.G.Han,etc.,Solution of P_0-matrix linear complementarity problems using a potential reduction algorithm,SIAM J.Matrix Anal.Appl.,1993,14:1048-1060.
[32]J.Ji,F.Potra and S.Huang,A predictor-corrector method for linear complementarity problems with polynomial complexity and superlinear convergence,Technical Report 18,Department of Mathematics,University of Iowa,Iowa City,IC,1991.
[33]J.Miao,A quadratically convergent O((κ+1)(?)L)-iteration algorithm for the P)_*(κ) - matrix linear complementarity problem,Math.Programming,1995,69:355-368.
[34]Q.Yu,C.C.Huang and X.J.Wang,A combined homotopy interior point method for the linear complementarity problem,Applied Mathematics and Computation,2006,179:696-701.
[35]何尚录,徐成贤,求解互补问题的不可行内点法及其计算复杂性,中国科学,2000,30:983-989.
[36]A.Fischer,A special Newton-type optimization method,Optimization,1992,24:269-284.
[37]O.L.Mangasarian,Equivalence of the complementarity problem to a system of nonlinear equations,SIAM Journal on Applied Mathematics,1976,31:89-92.
[38]A.Fischer and H.Jiang,Merit functions for complementarity and related problems:A survey,Computational Optimization and Applications,2000,17:159-182.
[39]Ulji and G.Q.Chen,A new smooth merit function for nonlinear complementarity problems and a Newton-type method,Numer.Math.Appl.,2005,27:1-14.
[40]J.S.Chen and S.H.Pan,A family of NCP functions and a descent method for the nonlinear complementarity problem,Comput.Optim.Appl.,2008,40:389-404.
[41]P.T.Harker and B.Xiao,Newton's method for the nonlinear complementarity problem:A B-differentiable equation approach,Math.Programming,1990,48:339-357.
[42]T.D.Luca,F.Facchinei and C.Kanzow,A theoretical and numerical comparison of some semismooth algorithm for complementarity problems,Comput.Optim.Appl.,2000,16:173-205.
[43]D.F.Sun,R.S.Womersley and H.D.Qi,A feasible semismooth asymptotically Newton method for mixed complementarity problems,Math.Program.,Ser.A,2002,94:167-187.
[44]C.Kanzow,Inexact semismooth Newton methods for large-scale complementarity problems,Optimization Methods and Software,2004,19:309-325.
[45]J.S.Chen and S.H.Pan,A regularization semismooth Newton method based on the generalized Fischer-Burmeister function for P0-NCPs,Journal of Computational and Applied Mathematics,2008,220:464-479.
[46]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,Math.Comp.,1998,67:519-540.
[47]C.Kanzow and H.Pieper,Jacobian smoothing methods for nonlinear complementarity problems,SIAM J.Optim.,1999,9:342-373.
[48]C.F.Ma,A new smoothing quasi-Newton method for nonlinear complementarity problems,Applied Mathematics and Computation,2005,171:807-823.
[49]C.F.Ma,A smoothing Broyden-like method for the mixed complementarity problems,Mathematical and Computer Modelling,2005,41:523-538.
[50]L.P.Zhang and Z.Y.Gao,Superlinear/Quadratic one-step smoothing Newton method for P_0-NCP without strict complementarity,Math.Meth.Oper.Res.,2002,56:231-241.
[51]L.P.Zhang,J.Y.Han and Z.H.Huang,Superlinear/Quadratic one-step smoothing Newton method for P_0-NCP,Acta Mathematica Sinica,English Series,2005,21:117-128.
[52]L.Q.Qi,D.F.Sun and G.L.Zhou,A new look at smoothing Newton method for nonlinear complementarity problems and box constrained variational inequalities,Math.Programming,2000,87:1-35.
[53]Z.H.Huang,Locating a maximally complementary solution of the monotone NCP by using non-interior-point smoothing algorithms,Math.Meth.Oper.Res.,2005,61:41-55.
[54]Z.H.Huang and W.Z.Gu,A smoothing-type algorithm for solving linear complementarity problems with strong convergence properties,Appl.Math.Optim.,2008,57:17-29.
[55]J.V.Burke and S.Xu,The global linear convergence of a non-interior path following algorithm for linear complementarity problems,Mathematics of Operations Research,1998,23:719-734.
[56]Z.H.Huang and J.Sun,A Non-Interior continuation algorithm for the P_0 or P_* LCP with strong global and local convergence properties,Appl.Math.Optim.,2005,52:237-262.
[57]X.Z.Zhang,H.F.Jiang and Y.J.Wang,A smoothing Newton-type method for generalized nonlinear complementarity problem,Journal of Computational and Applied Mathematics,2008,212:75-85.
[58]G.M.Korpelevich,The extragradient method for finding saddle points and other problems,Matecon,1976,12:747-756.
[59]B.S.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.
[60]N.Xiu and J.Zhang,Some recent advances in projection-type methods for variational inequalities,J.Comput.Appl.Math.,2003,152:559-585.
[61]W.E.Donath and A.J.Hoffman,Lower bounds for the partitioning of graphs,IBM J.of Research and Development,1973,17:120-125.
[62]J.Cullum,W.E.Donath and P.Wolfe,The minimization of certain nondifferentiable sums of eigenvalues of symmetric matrices,Mathematical Programming Study,1975,3:35-55.
[63]L.Lovasz,On the Shannon capacity of a graph,IEEE Transactions on Information Theory,1979,25:1-7.
[64]M.L.Overton,On minimization the maximum eigenvalue of a symmetric matrix,SIAM J.Matrix Anal.Appl.,1988,9:256-268.
[65]M.Goemans and D.P.Williamson,Improved approximation algorithms for max cut and satisfiablity problems using semidefinite programming,J.A.C.M,1995,42:1115-1145.
[66]F.Alizadeh,Interior point methods in semidefinite programming with applications to combinatorial optimization,SIAM Journal on Optimization,1995,5:13-51.
[67]C.Helmberg,Semidefinite programming for combinatorial optimization,Konrad-Zuse-Zentrum fur Informationstechnik Berlin,Germany,October 2000.
[68]M.J.Todd,Semidefinite optimization,Acta.Numerica,2001,10:515-560.
[69]H.Wolkowicz,R.Saigal and L.Vandenberghe,Handbook of semidefinite programming,Kluwer Academic Publishers,Boston-Dordrecht-London,2000.
[70]L.Vandenberghe and S.Boyd,Semidefinite programming,SIAM Review,1996,38:49-95.
[71]C.Helmberg,Semidefinite programming home page(Download link http://www.zib.de.helmber9/ semidef.html).
[72]W.S.Lu,Design of FIR filters with discrete coefficient:a semidefinite programming relaxation approach,IEEE,2001(Download link:http://www.ieee.org).
[73]H.T.Peng and L.K.Rasmussen,The application of semidefinite programming for detection in CDMA,IEEE Selected Areas in Communication,2001,19:1442-1449.
[74]S.Homer and M.Peinado,Design and performance of parallel and distributed approximation algorithms for maxcut,Journal of Parallel and Distributed Computing,1997,46:48-61.
[75]Q.Z.Yang,A new proof of the strong duality theorem for semidefinite programming,J.Math.Anal.Appl.,2005,303:622-626.
[76]Y.Nesterov and A.Nemirovski,Interior point polynomial Algorithms in convex programming,SIAM Publications,SIAM,Philadelphia,USA,1994.
[77]C.Helmberg,F.Rendl,R.J.Vanderbei and H.Wolkowicz,An interior-point method for semidefinite programming,SIAM J.Optim.,1996,6:342-361.
[78]M.Kojima,S.Shindoh and S.Hara,Interior-point methods for the monotone semidefinite linear complementarity problem in symmetric matrices,SIAM J.Optim.,1997,7:86-125.
[79]Y.Nesterov and M.J.Todd,Self-scaled barriers and interior-point methods for convex programming,Math.Oper.Res.,1997,22:1-42.
[80]Y.Nesterov and M.J.Todd,Primal-dual interior-point methods for self-scaled cones,SIAM J.Optim.,1998,8:324-364.
[81]F.Alizadeh,J.P.A.Haeberly and M.L.Overton,A new primal-dual interior-point method for semidefinite programming,In J.G.Lewis,editor,Proceedings of the Fifth SIAM Conference on Applied Linear Algebra,pages 113-117,SIAM,1994.
[82]F.Alizadeh,J.P.A.Haeberly and M.L.Overton,Primal-dual interior-point methods for semidefinite programming:Convergence rates,stability and numerical results,SIAM J.Optim.,1998,8:746-768.
[83]Y.Zhang,On extending some primal-dual interior-point algorithms from linear programming to semidefinite programming,SIAM J.Optim.,1998,8:365-386.
[84]C.Helmberg and F.Rendl,A spectral bundle method for semidefinite programming,SIAM Journal on Optimization,2000,10:673-696.
[85]F.Oustry,The u-Lagrangian of the maximum eigenvalue function,SIAM Journal on Optimization,1999,9:526-549.
[86]F.Oustry,A second-order bundle method to minimize the maximum eigenvalue function,Mathematical Programming,2000,89:1-33.
[87]S.Buret and R.D.C.Monteiro,A projected gradient algorithm for solving the Maxcut SDP relaxation,Optimization Methods and Softwqre,2001,15:175-200.
[88]S.Burer and R.D.C.Monteiro,A nonlinear programming algorithm for solving semidefinite programs via low-rank factorizaiton,Mathematical Programming,Series B,2003,95:329-357.
[89]G.Pataki,On the rank of extreme matrices in semifefinite programs and the multiplicity of optimal eigenvalues,Mathematics of Operations Research,1998,23:339-358.
[90]S.Burer and R.D.C.Monteiro,Local minima and convergence in low-rank semidefinite programming,Mathematical Programming,Series A,2005,103:427-444.
[91]S.Burer and C.Choi,Computational enhancements in low-rank semidefinite programming,Optimization Methods and Software,2006,21:493-512.
[92]S.Burer,R.D.C.Monteiro and Y.Zhang,Interior-point algorithms for semidefinite programming based on a nonlinear programming formulation,Computational Optimization and Applications,2002,22:49-79.
[93]S.Burer,R.D.C.Monteiro and Y.Zhang,Solving a calss of semidefinite programs via nonlinear programming,Mathematical Programming,2002,93:97-123.
[94]Z.S.Lu,A.Nemirovski and R.D.C.Monteiro,Large-scale semidefinite programming via a saddle point Mirror-Prox algorithm,Math.Program.,Ser.B,2007,109:211-237.
[95]S.Burer,Semidefinite programmingin the space of partial positive semidefinite matrices,SIAM Journal on Optimization,2003,14:139-172.
[96]K.C.Toh and M.Kojima,Solving some large scale semidefinite programs via the conjugate residual method,SIAM Journal on Optimization,2002,12:669-691.
[97]K.C.Toh,Solving large scale semidefinite programs via an iterative solver on the augmented systems,SIAM Journal on Optimization,2003,14:670-698.
[98]戴彧虹,袁亚湘,非线性共轭梯度法,上海科学技术出版社,上海,1999.
[99]A.Perry,A modified conjugate gradient algorithm,Operations Research,1978,26:1073-1078.
[100]J.C.Gilbert and J.Nocedal,Global convergence properties of conjugate gradient methods for optimization,SIAM Journal on Optimization,1992,2:21-42.
[101]Y.H.Dai and L.Z.Liao,New conjugacy conditions and related nonlinear conjugate gradient methods,Applied Mathematics and Optimization,2001,43:87-101.
[102]H.Yabe and N.Sakaiwa,A new nonlinear conjugate gradient method for unconstrained optimization,Journal of the Operations Research,2005,48:284-296.
[103]X.Chen and J.Sun,Global convergence of a two-parameter family of conjugate gradient methods without line search,Journal of Computational and Applied Mathematics,2002,146:37-45.
[104]G.Zoutendijk,Nonlinear programming,computational methods,in:Integer and Nonlinear Programming(J.Abadie,ed.),Amsterdam:North-Holland,1970.
[105]Y.Yuan,Analysis on the conjugate gradient method,Optimization Methods and Software,1993,2:19-29.
[106]M.J.D.Powell,Restart procedures for the conjugate gradient method,Mathematical Programming,1977,2:241-254.
[107]M.J.D.Powell,Convergence properties of algorithms for nonlinear optimization,SIAM Review,1986,28:487-500.
[108]Y.H.Dai,J.Y.Han,G.H.Liu,D.F.Sun,H.X.Yin and Y.Yuan,Convergence properties of nonlinear conjugate gradient methods,SIAM Journal of Optimization,1999,10:345-358.
[109]J.J.More,B.S.Garbow and K.E.Hillstrom,Testing unconstrained optimization software,ACM Transactions on Mathematical Software,1981,7:17-41.
[110]T.Deluca,F.Facchinei and C.Kanzow,A semismooth equation approach to the solution of nonlinear complementarity problems,Mathmatical Programming,1996,75:407-439.
[111]C.Chen and O.L.Mangasarian,A class of smoothing functions for nonlinear and mixed complementarity problems,Computational Optimization and Applications,1996,5:97-138.
[112]C.Geiger and C.Kanzow,On the Resolution of Monotone Complementarity Problems,Computational Optimization and Applications,1996,5:155-173.
[113]X.Chen and Y.Ye,On Smoothing Methods for the P_0- Matrix Linear Complementarity Problem,SIAM Journal on Optimization,2000,11:341-363.
[114]P.M.Pardalos,Y.Ye,C.G.Han and J.A.Kaliski,Solution of P_0-Matrix Linear Complementarity Problems Using a Potential Reduction Algorithm,SIAM Journal on Matrix Analysis and Applications,1993,14:1048-1060.
[115]B.H.Ahn,Iterative methods for linear complementarity problem with upperbounds and lowerbounds,Mathematical Programming,1983,26:265-315.
[116]P.T.Harker and J.S.Pang,A damped-Newton method for the linear complementarity problem,Lectures in Applied Mathematics,1990,26:265-284.
[117]Ulji and G.Q.Chen,New simple smooth merit function for box constrained variational inequalities and damped Newton type method,Applied Mathematics and Mechanics,2005,26:1083-1092.
[118]C.Kanzow and C.Nagel,Semidefinite programs:new search directions,smoothing-type methods,and numerical rusults,SIAM Journal on Optimization,2002,13:1-23.
[119]D.Sun and J.Sun,Semismooth matrix valued functions,Mathematics of Operations Research,2002,27:150-169.
[120]P.Tseng,Merit functions for semidefinite complementarity problems,Mathematical Programming,1998,83:159-185.
[121]R.A.Horn and C.R.Johnson,Matrix analysis,Cambridge University Press,New York,1985.
[122]X.Chen and P.Tseng,Noninterior continuation methods for solving semidefinite complementarity problems,Mathematical Programming,Ser.A,2003,95:431-474.
[123]P.Tseng,Search directions and convergence analysis of some infeasible path-following methods for the monotone semi-definite LCP,Optim.Methods Software,1998,9:245-268.
[124]L.Q.Qi and J.Sun,A nonsmooth version of Newton's method,Mathematical Programming,1993,58:353-368.
[125]Z.H.Huang,J.Han and Z.Chen,Predictor-corrector smoothing Newton method,based on a new smoothing function,for solving the nonlinear complemeatarity problem with a P_0function,Journal of Optimization Theory and Applications,2003,117:39-68.
[126]D.Sun and J.Sun,Nonsmooth matrix valued functions defined by singular values,Manuscript,Mathematical Programming,forthcoming,2002.
[127]L.P.Zhang,A global linear and local quadratic single-step noninterior continuation method for monotone semidefinite complementarity problems,Acta Mathematica Scientia,2007,27B:243-253.
[128]Z.J.Shi and J.Shen,Convergence of the Polak-Ribi(?)re-Polyak conjugate gradient method,Nonlinear Analysis,2007,66:1428-1441.
[129]C.K.Sim,J.Sun and D.Ralph,A note on the Lipschitz continuity of the gradient of the squared norm of the matrix-valued Fischer-Burmeister function,Mathematical Programming,2006,107:547-553.
[130]Z.J.Shi and J.Shen,Convergence of descent method without line search,Applied Mathematics and Computation,2005,167:94-107.
[131]E.S.Levitin and B.T.Polyak,Constrained minimization problems,USSR,Comput.Math.Math.Phys.,1966,6:1-50.
[132]C.Helmberg,F.Rendl and R.Weismantel,A semidefinite programming approach to the Quadratic Knapsack problem,Journal of Combinatorial Optimization,2000,4:197-215.
[133]H.D.Qi and Y.Z.Zhang,A smoothing Newton method for complementarity problems(in Chinese),Math.Numer.Sin.,2001,23:257-264.