半定规划的非内点算法
|
摘要
半定规划是数学规划方面一个相对较新的领域,是线性规划的推广,它是在满足约束“对称矩阵的仿射组合半正定”的条件下使线性函数极大(极小)化问题,这个约束是非线性的、非光滑的、凸的,因而半定规划是一个非光滑凸优化问题。
本文首先介绍了半定规划的基本理论、主要算法和研究现状,在此基础上对半定规划问题算法研究做了如下工作:
1.给出了解决半定规划问题的筛选算法。文中首先采用低秩分解技术将半定规划问题转化为与其等价的非线性规划问题,进而利用非线性规划问题的筛选算法来求解。文中给出了两种筛选算法,一种是基于方向分解的筛选法,分析了它的主要思想,并给出了具体的算法,最后给出了它的收敛性结论。另一种是与SQP结合的筛选法,对其进行了详细的分析,并得到了较好的全局收敛性结论.
2.文中又给出了一种光滑化牛顿方法。首先利用推广的Fischer-Burmeister函数将半定规划问题的KKT条件转化为一个等价的非光滑方程组,进而利用光滑化方法将该非光滑方程组光滑化,构造了半定规划问题的光滑化方法。最后,在超线性收敛的基础上,又对算法作了改进,得到了二次收敛性结论。
Semidefinite programming is an extension of linear programming. In semidefinite programming, one maximizes (minimizes) a linear function subject to the constraint that an affine combination of symmetric matrices is positive semidefinite. Such a constraint is nonlinear and nonsmooth, but convex, so semidefinite programming is a nonsmooth and convex optimization problem.
In the paper, the theory, algorithm,and recent reseach of semidefinite programming are summarized, some works in algorihm are introduced. In detail, we conclude them as follows:
1. A filter method for semidefinite programming is proposed in this paper. Firstly, a low-rank decomposition technique is adopted to transform the standard semidefinite programming into an equivalent nonlinear programming problem. Then two kinds of filter algorithms are introduced to solve the problem. The first algorithm is based on a decomposition of direction. We give the main idea of it and the convergence conclusions. The second is a combination of filter and the SQP. A detailed analysis is carried out and better global convergence conclusions are obtained.
2. An extensive Fischer-Burmeister function method are used to convert the optimality conditions of SDP into an equivalent nonsmooth system of equations, then by smoothing the nonsmooth equations, a smoothing-type method for semidefinite programming is constructed. At last, on the basis of the superlinear convergence, an improved algorithm is presented and a rapid quadratic convergence conclusion is obtained.
本文首先介绍了半定规划的基本理论、主要算法和研究现状,在此基础上对半定规划问题算法研究做了如下工作:
1.给出了解决半定规划问题的筛选算法。文中首先采用低秩分解技术将半定规划问题转化为与其等价的非线性规划问题,进而利用非线性规划问题的筛选算法来求解。文中给出了两种筛选算法,一种是基于方向分解的筛选法,分析了它的主要思想,并给出了具体的算法,最后给出了它的收敛性结论。另一种是与SQP结合的筛选法,对其进行了详细的分析,并得到了较好的全局收敛性结论.
2.文中又给出了一种光滑化牛顿方法。首先利用推广的Fischer-Burmeister函数将半定规划问题的KKT条件转化为一个等价的非光滑方程组,进而利用光滑化方法将该非光滑方程组光滑化,构造了半定规划问题的光滑化方法。最后,在超线性收敛的基础上,又对算法作了改进,得到了二次收敛性结论。
Semidefinite programming is an extension of linear programming. In semidefinite programming, one maximizes (minimizes) a linear function subject to the constraint that an affine combination of symmetric matrices is positive semidefinite. Such a constraint is nonlinear and nonsmooth, but convex, so semidefinite programming is a nonsmooth and convex optimization problem.
In the paper, the theory, algorithm,and recent reseach of semidefinite programming are summarized, some works in algorihm are introduced. In detail, we conclude them as follows:
1. A filter method for semidefinite programming is proposed in this paper. Firstly, a low-rank decomposition technique is adopted to transform the standard semidefinite programming into an equivalent nonlinear programming problem. Then two kinds of filter algorithms are introduced to solve the problem. The first algorithm is based on a decomposition of direction. We give the main idea of it and the convergence conclusions. The second is a combination of filter and the SQP. A detailed analysis is carried out and better global convergence conclusions are obtained.
2. An extensive Fischer-Burmeister function method are used to convert the optimality conditions of SDP into an equivalent nonsmooth system of equations, then by smoothing the nonsmooth equations, a smoothing-type method for semidefinite programming is constructed. At last, on the basis of the superlinear convergence, an improved algorithm is presented and a rapid quadratic convergence conclusion is obtained.
引文
[1] Y.Nesterov and A.Nemirovsky.,Interior-point polynomial methods in convex progra-mming,volume 13 of Studies in Applied Mathematics, SIAM, Philadelphia, PA, 1994 .
[2] Helmberg C . Rendl F . Vanderbei R.J.and WolkowiczH .,An interior-point method for semidefinite programming,Manuscipt,Program in Statistics and Operations Research,Princeton University.
[3] Nesterov Y.E. and Todd M.J. Primal-dual interior-point methods for selfed-scaled cones , SIAM, Journal on Optimization,8( 1998),32 4-364.
[4] A lizadehF., Haeberly J .P.A. and Overton M .L. Primal-dual interior-point methods for semidefinite programming,Manuscipt,19 94.
[5] Zhang Y. On extending some primal-dual interior-point algorithms form linear programming to semidefinite programming,SIAM,Journal on Optimization8 (1998),365-386.
[6] FaybusovichL., Jordan algebras, symmetric cones and interior-point methods,Te chnical. Report, Department of Mathematics,Norte Dame University,1 995.
[7] Sturm J .F.,Similarity and the spectral relations for symmetric cones,Linear Algebra and its applications,3 12(2000),13 5154.
[8] Muramatsu M. On a commutative class of search directions for linear programming over symmetric cones.Journalof Optimization Theory and applications,11 2(2)(2 002),59 5- 625
[9] F.Alizadeh.Interior-point methods in semidefinite programming with a pplications to combinatorial optimization.SI AM1 .Optimization.19 95,5(1):13-51
[10] M .J. To dd.Semidefinite optimization.Acta.Numerica,20 01,10 :515-560.
[11] C. Helmberg. Semidefinite Programming for Combinatorial Optimization Konrad- Zuse -Zentrum fur informations technik Berlin, Germany, October 2000.
[12] S.P.Wu, S.Boyd, and L.Vandenberghe. FIR filter design via semidefinite Programming and spectral factorization.Proc.35th Conf.Decision and Control. pp.271-276 ,Kobe.Japan,Dec.1996
[13] Wing-Kin Ma, and T. N. Davidson. Quasi-maximum-likelihood multiuser detection using semidefinite relaxation.(Download link:http//www.ieee.org)
[14] Etienne de Klerk.Aspects of Semidefinite Programming Interio Point Algorithmsand Selected Applications.KLUWER ACADEMIC PUBLISHERS.
[15] 房亮.半定规划.泰山学院学报[J].2004年5月.
[16] F.A lizadeh. Interior-point methods in semidefinite programming with applications to combinatorial optimization.SIAM .Optimization.19 95,5(1):13-51
[17] 应玖茜,魏权龄.非线性规划及其应用。人民大学出版社,北京,1994。
[18] YE.Nesterov,A .S .Nemirovski. Interior point polynomial algorithmsin convex programming.SIAM publications.SIAM,Philadelphia,USA,1994.
[19] C.Helmberg.Semidefinite Programming for Combinatorial Optimization Konrad-Zu se-Zen trumfur informations techikB erlin,Germany,October2 000.
[20] K.Fujisawa,M.Kojima,and K.Nakata.Exploiting sparsity in primal-dual interior-point methods for semidefinite Programming. Math. program, 79: 235– 253,1997.
[21] C.Helmberg and F.Oustry.Bundle methods and eigenvalue function.In H.Wolkkowi -cz,R.Saigal,and L.Vandenberghe,editors,Handbook of semidefinite programming. pages 307-337.Kluwer Academic Publishers,Norwell,MA,2000.
[22] S. Burer and R. D.C.Monteiro. A projected gradient algorithm for solving the MAX CUT SDP relaxation. Optimization Methods and Software. 2001,15 :175-200 .
[23] S. Burer, R. D. C. Monteiro and Y. Zhang. Interior-point algorithms for semid efi -nitep rogramsv ial ow-rankf actorization.M ath.P rog. 2003, Ser.B, 95 (2): 59-380.
[24] Samuel Burer ,Renato D.C.Monteiro.A Nonlinear Programming for Solving Semidefinite Programming via Low-rank Factorization[J]. Math.Program.Ser.B 95:329-357(2003).
[25] Samuel Burer ,Renato D.C.Monteiro. Local Minima and Convergence in Low-rank Semidefinite Programming[J]. Math. Program., Ser. A (2004)
[26] M.X.Goemans and D.P.Williamso. Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming.Journal of the ACM,42(6):1115-1145,1995
[27] A.Frieze and M.Jerrum. Improved approximation algorithms for MAX k-cut and MAX BISECTION. In Proc.4th IPCO conference,pages 1-13,1995.
[28] Y.Ye, An approximating quadratic programming with bound and quadratic constraints.Mathematical Programming,84:219-226,1999.
[29] H.Karloff and U.Zwick.A 7/8-approximation algorithm for MAX 3SAT?In Proc.38th FOCS,pages 406-415,1997.
[30] E.de Klerk, H.van Maaren.,and J.P. Warners. Relaxations of the satisfiability problem using semidefinite programming.Journal of automated reasoning,24:37-65,2000.
[31] H.D.shenali and W.P.Adams.A hierarchy of relaxations between the continuous and convex hull representations for 0-1 programming problems. SIAM Journal on Discrete Mathematics,3(3):411-430,1990.
[32] M.S.Bazarraa, H.D.Sherali,and C.M.Shetty.Nonliear Programming:Theory and Algorithms.John Wiley and Sons,New York,1993.
[33] B.Lasserre.Global optimization with polynomisls and the problem of moments.SIAM J.Optimization,11:796-817,2001
[34] J.B.Lasserre An explicit exact SDP relaxation for nonlinear 0-1 programs.In Proc.IPCO VIII,pages 293-303,2001.
[35] S.E>Boyd, L.El Ghaoui,E.Feron,and V.Balakrishnan.Linear matrix inequalities in system and control theory.SIAM Studies in Applied Mathematics,Vol.15.SIAM,Philadelphia,USA,1994.
[36] A.Ben-TalLEl Ghaaoui, and A.S. Nemirovski.Robustness.In H.Wolkowicz, R.Saigal,and L.Vandenberghe,editors,Handbook of semidefinite programming, pages421-442.Kluwer Academic Publishers,Norwell,MA,2000.
[37] L.Vandenberghe and S.Boyd.Semidefinite programming.SIAM Review, 38:49-95,1996.
[38] A.Ben-TalLEl Ghaaoui, and A.S. Nemirovski.Robustness.In H.Wolkowicz, R.Saigal,and L.Vandenberghe,editors,Handbook of semidefinite programming, pages139-162.Kluwer Academic Publishers,Norwell,MA,2000.
[39] Y. Nesterov and A. Nemirovskii: Interior-Point Polynomial Algorithms in Convex Programming. SIAM, Philadelphia, PA, 1994.
[40] R.A. Horn and C.R. Johnson: Topics in Matrix Analysis. Cambridge University Press, 1991.
[41] 刘三阳,王新辉,刘红卫.多用户检测问题的半定规划方法.工程数学学报. 2002, 19(2):39-46.
[42] 刘红卫,刘三阳,王新辉.基于半定规划的多用户检测问题的二次规划方法.系统工程与电子技术,2003,25(3):355-358.
[43] R.Bellman and K.Fan. On Systems of linear Inequalities in Hermitian Matrix Variable s. I n :Convexity,Proceedings of Symposia in Pure Mathematics American Mathematical Society, Providence,R I.19 63,7:1-11
[44] Yu. E. Nesterov and A. S. Nemirovski. Conic formulation of convex programming problem and duality. Optimization Methods Software 199 2, 1:9 5- 11 5.
[45] YingYuYe.A class of projective transformations for linear programming.SIAMJ.Comput . 1990,19:457-466
[46] K. Fujisawa, M. Kojima, and K. Nakata. Exploiting sparsity in primal-dual interior-point methods for semidefinite programming.Math.Programming. 1997,79:2 35-253
[47] S. Benson, Y. Ye and X. Zhang. Solving large-scale sparse semidefinite program -ming for combinatorial optimization.SIAM J.Optimization,2 000:4 43-4 61 .
[48] K. Najata, K. Fujisawa and M. Fukuda etc. Exploiting sparsity in semidefinite pro gramming via matrix complition:implementation and numerical results. Technical Report B-368,Dept.of Information Science,Tokyo Institute of Technology, Tokyo, Japan, 2001.
[49] S. Burer. Semidefinite programming in the space of partial positive semidefinite matrices .SIAM .J.Optim.2003,14(1):139-172.
[50] C. helmberg and F. Rendl. A spectral bundle method for semidefinite programming. SIAM. J. Optimization, 2000,10:673-696.
[51] C .Helmberg,F .R endlan dW eismantel.A semidefinite programming Approach to the Quadratic Knapsack problem, J. of Combinatorial Optimization,20 00 ,4: 19 7- 215.
[52] D.karger R.Motwani and M.Sudan. Approximate graph coloring by semidefinite programming.J. ACM.1998,45:246-265.
[53] A. Forsgren. Optimality conictions for nonconvex semidefinite programming Math. Prog,2000,88(A):105-128.
[54] L .M.G ranaDrummond,Alfredo Noellusem and B .F. Sv aiter.On the central path for nonlinear semidefinite programming.Rairo Oper.Research,2000.34:331-345.
[55] Fletcer R,Leyffer S,toint,Ph.L.(1998): On the Global Convergence of Filter-SQP Algorithm[J].Numerical Analysis Report NA/97,University of Dundee, UK, Nove--mber 2000.Submitted to SIOPT.
[56] Fletcher R, Leyffer S. Nonlinear Programming without a penalty Function[J]. Mathematical Programming,2002,91:239-269
[57] Fletcer R, Leyffer S.A Bundle Filter Method for Nonsmooth Nonlinear Optimizati -on[J]. Tech.Report. NA/195, Department of Mathematics, Univercity of Dundee,1999.
[58] Conn,A.R, Gould, N.I.M,Toint, P.L.Trust-region methods. MPS/SIAM Series on Optimization, Society for Industrial and Applied Mathematics (SIAM), Philadelphia, PA, 2000
[59] Conn, A.R, Gould, N.I.M,Toint, P.L.:Trust-region methods. MPS/SIAM Series on Optimization, Society for Industrial and Applied Mathematics (SIAM), Philadelphia, PA, 2000
[60] Facchinei, F.Lucidi, S.Quadratically and superlinearly convergent algorithms for the solution of inequality constrained minimization problems. J. Optim. Theory Appl. 85, 265–289 (1995)
[61] Fletcher, R.Gould, N.I.M.Leyffer, S.Toint, P.L.Wachter, A: Global convergence of a trust-region SQP-filter algorithm for general nonlinear programming. SIAM J. Optim. 13, 635–659 (2002)
[62] Ulbrich M,Ulbrich S,Vicente LN. A Globally Convergent Primal-dual Interior-point Filter Method for Nonconvex Nonlinear Programming [J] .Mathematical Programming, 2004,100:379-410
[63] 聂普炎.筛选法解非线性方程组[J].应用数学学报 2004.3
[64] W¨achter,A.,Biegler, L.T.:Global and local convergence of line search filter methods for nonlinear programming.CAPD Technical Report B-01-09, Department of Chemical Engineering, Carnegie Mellon University, Pittsburgh, Pennsylvania, 2001 (Revised 2002)
[65] Gonzaga, C.C.Karas, E.Vanti, M.A globally convergent filter method for nonlinear programming. Technical Report, Department of Mathematics, Federal University of Santa Catarina, Brazil, 2001 (Revised 2002)
[66] F.N.K.Karmarkar. A new polynomial-time algorithm for linear Programming. Combinatorica, 1984, 4:373-395.
[67] J.Peng, C.Roos, and T.Terlaky. Self-regular proximities and new search directions for linear and semi-definite optimization [J]. Math Programming, 2002, 93: 129-171.
[68] X.Chen and P.Tseng: Non-interior continuation methods for solving semidefinite complementarity problems. Technical Report, Department of Mathematics, University of Washington, Seattle, WA, 1999.
[69] D.Sun and J.Sun, Semismooth matrix valued functions.Mathematics of Operations Research , 27( 2002)pp:150-169.
[70] 李兴斯 潘少华,求解线性规划问题的一个非内点算法.大连理工大学学报2004,3
[71] X.Chen and P.Tseng: Non-interior continuation methods for solving semidefinite complementarity problems. Technical Report, Department of Mathematics, Univ -ersity of Washington, Seattle, WA, 1999.
[72] A. Fischer: A special Newton-type optimization method.Optimization 24, 1992, pp.269–284.
[73] P. Tseng: Merit functions for semi-definite complementarity problems. Mathemati -cal Programming 83, 1998, pp. 159–185.
[74] C. Kanzow: Some noninterior continuation methods for linear complementarity problems.SIAM Journal on Matrix Analysis and Applications 17, 1996, pp. 851–868.
[75] D. Sun and J. Sun: Semismooth matrix valued functions. Technical Report, School of Mathematics, University of New South Wales, Sydney, Australia, November 1999.
[76] H. Jiang: Smoothed Fischer-Burmeister equation methods for the complementarity problem. Technical Report, Department of Mathematics, University of Melbourne, Melbourne,Australia, June 1997.
[77] X.CHEN AND P.TSENG:Non-interior continuation methods for solving semidefin ite complementarity problems. Math. Program., Ser. A 95: 431–474 (2003)
[78] C. Kanzow and C. Nagel: Semidefinite programs:New search directions, smoothing type methods and numerical results. SIAM Journal on Optimization13, 2003, 1-23.
[79] Alizadeh F. Interior point method in semidefinite programming with applications to combinatorial optimization[J],SIAM Joumal on Optimization,1995,5:13-51.
[80] KojimaM,ShidaM,ShindohS.Local convergence of predictor-corrector infeasible interior-point algorithms for SDPS and SDLCPS Mathematical Programming,1998
[2] Helmberg C . Rendl F . Vanderbei R.J.and WolkowiczH .,An interior-point method for semidefinite programming,Manuscipt,Program in Statistics and Operations Research,Princeton University.
[3] Nesterov Y.E. and Todd M.J. Primal-dual interior-point methods for selfed-scaled cones , SIAM, Journal on Optimization,8( 1998),32 4-364.
[4] A lizadehF., Haeberly J .P.A. and Overton M .L. Primal-dual interior-point methods for semidefinite programming,Manuscipt,19 94.
[5] Zhang Y. On extending some primal-dual interior-point algorithms form linear programming to semidefinite programming,SIAM,Journal on Optimization8 (1998),365-386.
[6] FaybusovichL., Jordan algebras, symmetric cones and interior-point methods,Te chnical. Report, Department of Mathematics,Norte Dame University,1 995.
[7] Sturm J .F.,Similarity and the spectral relations for symmetric cones,Linear Algebra and its applications,3 12(2000),13 5154.
[8] Muramatsu M. On a commutative class of search directions for linear programming over symmetric cones.Journalof Optimization Theory and applications,11 2(2)(2 002),59 5- 625
[9] F.Alizadeh.Interior-point methods in semidefinite programming with a pplications to combinatorial optimization.SI AM1 .Optimization.19 95,5(1):13-51
[10] M .J. To dd.Semidefinite optimization.Acta.Numerica,20 01,10 :515-560.
[11] C. Helmberg. Semidefinite Programming for Combinatorial Optimization Konrad- Zuse -Zentrum fur informations technik Berlin, Germany, October 2000.
[12] S.P.Wu, S.Boyd, and L.Vandenberghe. FIR filter design via semidefinite Programming and spectral factorization.Proc.35th Conf.Decision and Control. pp.271-276 ,Kobe.Japan,Dec.1996
[13] Wing-Kin Ma, and T. N. Davidson. Quasi-maximum-likelihood multiuser detection using semidefinite relaxation.(Download link:http//www.ieee.org)
[14] Etienne de Klerk.Aspects of Semidefinite Programming Interio Point Algorithmsand Selected Applications.KLUWER ACADEMIC PUBLISHERS.
[15] 房亮.半定规划.泰山学院学报[J].2004年5月.
[16] F.A lizadeh. Interior-point methods in semidefinite programming with applications to combinatorial optimization.SIAM .Optimization.19 95,5(1):13-51
[17] 应玖茜,魏权龄.非线性规划及其应用。人民大学出版社,北京,1994。
[18] YE.Nesterov,A .S .Nemirovski. Interior point polynomial algorithmsin convex programming.SIAM publications.SIAM,Philadelphia,USA,1994.
[19] C.Helmberg.Semidefinite Programming for Combinatorial Optimization Konrad-Zu se-Zen trumfur informations techikB erlin,Germany,October2 000.
[20] K.Fujisawa,M.Kojima,and K.Nakata.Exploiting sparsity in primal-dual interior-point methods for semidefinite Programming. Math. program, 79: 235– 253,1997.
[21] C.Helmberg and F.Oustry.Bundle methods and eigenvalue function.In H.Wolkkowi -cz,R.Saigal,and L.Vandenberghe,editors,Handbook of semidefinite programming. pages 307-337.Kluwer Academic Publishers,Norwell,MA,2000.
[22] S. Burer and R. D.C.Monteiro. A projected gradient algorithm for solving the MAX CUT SDP relaxation. Optimization Methods and Software. 2001,15 :175-200 .
[23] S. Burer, R. D. C. Monteiro and Y. Zhang. Interior-point algorithms for semid efi -nitep rogramsv ial ow-rankf actorization.M ath.P rog. 2003, Ser.B, 95 (2): 59-380.
[24] Samuel Burer ,Renato D.C.Monteiro.A Nonlinear Programming for Solving Semidefinite Programming via Low-rank Factorization[J]. Math.Program.Ser.B 95:329-357(2003).
[25] Samuel Burer ,Renato D.C.Monteiro. Local Minima and Convergence in Low-rank Semidefinite Programming[J]. Math. Program., Ser. A (2004)
[26] M.X.Goemans and D.P.Williamso. Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming.Journal of the ACM,42(6):1115-1145,1995
[27] A.Frieze and M.Jerrum. Improved approximation algorithms for MAX k-cut and MAX BISECTION. In Proc.4th IPCO conference,pages 1-13,1995.
[28] Y.Ye, An approximating quadratic programming with bound and quadratic constraints.Mathematical Programming,84:219-226,1999.
[29] H.Karloff and U.Zwick.A 7/8-approximation algorithm for MAX 3SAT?In Proc.38th FOCS,pages 406-415,1997.
[30] E.de Klerk, H.van Maaren.,and J.P. Warners. Relaxations of the satisfiability problem using semidefinite programming.Journal of automated reasoning,24:37-65,2000.
[31] H.D.shenali and W.P.Adams.A hierarchy of relaxations between the continuous and convex hull representations for 0-1 programming problems. SIAM Journal on Discrete Mathematics,3(3):411-430,1990.
[32] M.S.Bazarraa, H.D.Sherali,and C.M.Shetty.Nonliear Programming:Theory and Algorithms.John Wiley and Sons,New York,1993.
[33] B.Lasserre.Global optimization with polynomisls and the problem of moments.SIAM J.Optimization,11:796-817,2001
[34] J.B.Lasserre An explicit exact SDP relaxation for nonlinear 0-1 programs.In Proc.IPCO VIII,pages 293-303,2001.
[35] S.E>Boyd, L.El Ghaoui,E.Feron,and V.Balakrishnan.Linear matrix inequalities in system and control theory.SIAM Studies in Applied Mathematics,Vol.15.SIAM,Philadelphia,USA,1994.
[36] A.Ben-TalLEl Ghaaoui, and A.S. Nemirovski.Robustness.In H.Wolkowicz, R.Saigal,and L.Vandenberghe,editors,Handbook of semidefinite programming, pages421-442.Kluwer Academic Publishers,Norwell,MA,2000.
[37] L.Vandenberghe and S.Boyd.Semidefinite programming.SIAM Review, 38:49-95,1996.
[38] A.Ben-TalLEl Ghaaoui, and A.S. Nemirovski.Robustness.In H.Wolkowicz, R.Saigal,and L.Vandenberghe,editors,Handbook of semidefinite programming, pages139-162.Kluwer Academic Publishers,Norwell,MA,2000.
[39] Y. Nesterov and A. Nemirovskii: Interior-Point Polynomial Algorithms in Convex Programming. SIAM, Philadelphia, PA, 1994.
[40] R.A. Horn and C.R. Johnson: Topics in Matrix Analysis. Cambridge University Press, 1991.
[41] 刘三阳,王新辉,刘红卫.多用户检测问题的半定规划方法.工程数学学报. 2002, 19(2):39-46.
[42] 刘红卫,刘三阳,王新辉.基于半定规划的多用户检测问题的二次规划方法.系统工程与电子技术,2003,25(3):355-358.
[43] R.Bellman and K.Fan. On Systems of linear Inequalities in Hermitian Matrix Variable s. I n :Convexity,Proceedings of Symposia in Pure Mathematics American Mathematical Society, Providence,R I.19 63,7:1-11
[44] Yu. E. Nesterov and A. S. Nemirovski. Conic formulation of convex programming problem and duality. Optimization Methods Software 199 2, 1:9 5- 11 5.
[45] YingYuYe.A class of projective transformations for linear programming.SIAMJ.Comput . 1990,19:457-466
[46] K. Fujisawa, M. Kojima, and K. Nakata. Exploiting sparsity in primal-dual interior-point methods for semidefinite programming.Math.Programming. 1997,79:2 35-253
[47] S. Benson, Y. Ye and X. Zhang. Solving large-scale sparse semidefinite program -ming for combinatorial optimization.SIAM J.Optimization,2 000:4 43-4 61 .
[48] K. Najata, K. Fujisawa and M. Fukuda etc. Exploiting sparsity in semidefinite pro gramming via matrix complition:implementation and numerical results. Technical Report B-368,Dept.of Information Science,Tokyo Institute of Technology, Tokyo, Japan, 2001.
[49] S. Burer. Semidefinite programming in the space of partial positive semidefinite matrices .SIAM .J.Optim.2003,14(1):139-172.
[50] C. helmberg and F. Rendl. A spectral bundle method for semidefinite programming. SIAM. J. Optimization, 2000,10:673-696.
[51] C .Helmberg,F .R endlan dW eismantel.A semidefinite programming Approach to the Quadratic Knapsack problem, J. of Combinatorial Optimization,20 00 ,4: 19 7- 215.
[52] D.karger R.Motwani and M.Sudan. Approximate graph coloring by semidefinite programming.J. ACM.1998,45:246-265.
[53] A. Forsgren. Optimality conictions for nonconvex semidefinite programming Math. Prog,2000,88(A):105-128.
[54] L .M.G ranaDrummond,Alfredo Noellusem and B .F. Sv aiter.On the central path for nonlinear semidefinite programming.Rairo Oper.Research,2000.34:331-345.
[55] Fletcer R,Leyffer S,toint,Ph.L.(1998): On the Global Convergence of Filter-SQP Algorithm[J].Numerical Analysis Report NA/97,University of Dundee, UK, Nove--mber 2000.Submitted to SIOPT.
[56] Fletcher R, Leyffer S. Nonlinear Programming without a penalty Function[J]. Mathematical Programming,2002,91:239-269
[57] Fletcer R, Leyffer S.A Bundle Filter Method for Nonsmooth Nonlinear Optimizati -on[J]. Tech.Report. NA/195, Department of Mathematics, Univercity of Dundee,1999.
[58] Conn,A.R, Gould, N.I.M,Toint, P.L.Trust-region methods. MPS/SIAM Series on Optimization, Society for Industrial and Applied Mathematics (SIAM), Philadelphia, PA, 2000
[59] Conn, A.R, Gould, N.I.M,Toint, P.L.:Trust-region methods. MPS/SIAM Series on Optimization, Society for Industrial and Applied Mathematics (SIAM), Philadelphia, PA, 2000
[60] Facchinei, F.Lucidi, S.Quadratically and superlinearly convergent algorithms for the solution of inequality constrained minimization problems. J. Optim. Theory Appl. 85, 265–289 (1995)
[61] Fletcher, R.Gould, N.I.M.Leyffer, S.Toint, P.L.Wachter, A: Global convergence of a trust-region SQP-filter algorithm for general nonlinear programming. SIAM J. Optim. 13, 635–659 (2002)
[62] Ulbrich M,Ulbrich S,Vicente LN. A Globally Convergent Primal-dual Interior-point Filter Method for Nonconvex Nonlinear Programming [J] .Mathematical Programming, 2004,100:379-410
[63] 聂普炎.筛选法解非线性方程组[J].应用数学学报 2004.3
[64] W¨achter,A.,Biegler, L.T.:Global and local convergence of line search filter methods for nonlinear programming.CAPD Technical Report B-01-09, Department of Chemical Engineering, Carnegie Mellon University, Pittsburgh, Pennsylvania, 2001 (Revised 2002)
[65] Gonzaga, C.C.Karas, E.Vanti, M.A globally convergent filter method for nonlinear programming. Technical Report, Department of Mathematics, Federal University of Santa Catarina, Brazil, 2001 (Revised 2002)
[66] F.N.K.Karmarkar. A new polynomial-time algorithm for linear Programming. Combinatorica, 1984, 4:373-395.
[67] J.Peng, C.Roos, and T.Terlaky. Self-regular proximities and new search directions for linear and semi-definite optimization [J]. Math Programming, 2002, 93: 129-171.
[68] X.Chen and P.Tseng: Non-interior continuation methods for solving semidefinite complementarity problems. Technical Report, Department of Mathematics, University of Washington, Seattle, WA, 1999.
[69] D.Sun and J.Sun, Semismooth matrix valued functions.Mathematics of Operations Research , 27( 2002)pp:150-169.
[70] 李兴斯 潘少华,求解线性规划问题的一个非内点算法.大连理工大学学报2004,3
[71] X.Chen and P.Tseng: Non-interior continuation methods for solving semidefinite complementarity problems. Technical Report, Department of Mathematics, Univ -ersity of Washington, Seattle, WA, 1999.
[72] A. Fischer: A special Newton-type optimization method.Optimization 24, 1992, pp.269–284.
[73] P. Tseng: Merit functions for semi-definite complementarity problems. Mathemati -cal Programming 83, 1998, pp. 159–185.
[74] C. Kanzow: Some noninterior continuation methods for linear complementarity problems.SIAM Journal on Matrix Analysis and Applications 17, 1996, pp. 851–868.
[75] D. Sun and J. Sun: Semismooth matrix valued functions. Technical Report, School of Mathematics, University of New South Wales, Sydney, Australia, November 1999.
[76] H. Jiang: Smoothed Fischer-Burmeister equation methods for the complementarity problem. Technical Report, Department of Mathematics, University of Melbourne, Melbourne,Australia, June 1997.
[77] X.CHEN AND P.TSENG:Non-interior continuation methods for solving semidefin ite complementarity problems. Math. Program., Ser. A 95: 431–474 (2003)
[78] C. Kanzow and C. Nagel: Semidefinite programs:New search directions, smoothing type methods and numerical results. SIAM Journal on Optimization13, 2003, 1-23.
[79] Alizadeh F. Interior point method in semidefinite programming with applications to combinatorial optimization[J],SIAM Joumal on Optimization,1995,5:13-51.
[80] KojimaM,ShidaM,ShindohS.Local convergence of predictor-corrector infeasible interior-point algorithms for SDPS and SDLCPS Mathematical Programming,1998