Search directions and convergence analysis of some infeasibnle path-following methods for the monoton semi-definite lcpFootnote^∗

^∗This research is supported by National Science Foundation Grant CCR-9311621

References

• Alizadeh , F. “ Optimization over the positive-definite cone:interior point methods and combinatorial applications ” . In Advances in Optimization and Parallel Computing Edited by: Pardalos , P. 1 – 25 .
   Google Scholar
• Alizadeh , F. 1995 . Interior point methods in semidefinite programming with application to combinatorial optimization . SIAM J. Optim , 5 : 13 – 51 .
   Web of Science ®Google Scholar
• Alizadeh , F. , Haeberly , J.P.A. and Overton , M.L. . Primal-dual interior point methods for semidefinite programming . Presented at the Math Programming Symposium . Ann Arbor . Manuscript
   Google Scholar
• Alizadeh , F. , Haeberly , J.P.A. and Overton , M.L. 1996 . “ Primal-dual interior point methods for semidefinite programming:convergence rates ” . In stability and numerical results, Working paper , New Brunswick : Rutgers University . RUTCOR
   Google Scholar
• Anstreicher , K.M. and Frampa , M. 1996 . A long-step path following algorithm for semidefinite programming problems , Working paper, Department of Management Sciences
   Google Scholar
• Faybusovich , L. 1995 . Semi-definite programming:a path-following algorithm for a linearquadratic functional , University of Notre Dame . Report, Department of Mathematics,Notre Dame, SIAM J. Optimization, to appear
   Google Scholar
• Freund , R.M. 1994 . Complexity of an algorithm for finding an approximate solution of a semidefinite program with no regularity assumption , Cambridge : Massachusetts Institute of Technology . Working paper OR 302-94, Operations Research Center
   Google Scholar
• Gonzaga , C.C. 1997 . The largest step path following algorithm forlinear complementarity problems . Math. Prog , 76 : 309 – 332 .
   Google Scholar
• Rendl , F. , Vanderbei , R.J. and Wolkowicz , H. 1996 . An interior-point method for semidefinite programming . SIAM J. Optim , 6 : 342 – 361 .
   Google Scholar
• Horn , R.A. and Johnson , C.R. 1985 . Matrix Analysis , Cambridge : Cambridge pess .
   Google Scholar
• Jarre , F. 1993 . An interior-point method for minimizing the maximum eigenvalue of a linear combination of matrices . SIAM J. Control Optim , 31 : 1360 – 1377 .
   Web of Science ®Google Scholar
• Kojima , M. , Megiddo , N. and Mizuno , S. 1993 . A primal-dual infeasible-interior-point algorithm for linear programming . Math. Programming , 61 : 263 – 280 .
   Web of Science ®Google Scholar
• Kojima , M. , Kojima , S. and Hara , S. 1997 . Linear algebra for semidefinite programming , Vol. 1004 , 1 – 23 . Kyoto : Kyoto University . RIMS Kokyuroku, Research Institute of Mathematical Sciences
   Google Scholar
• Kojima , M. , Shindoh , S. and Hara , S. 1997 . Interior-point methods forj the monotone semidefinite linear complementarity problems . SIAM J. Optim , 7 : 86 – 125 .
   Web of Science ®Google Scholar
• Kojima , M. , Shida , M. and Shindoh , S. 1995 . Local convergence of predictor-corrector infeasible interior-point algorithms for SDPs and SDLCPs , Tokyo : Tokyo Institute of Technology . Research Report 306, Department of Mathematical and Computing Sciences,Math. Programming, to appear
   Google Scholar
• Kojima , M. , Shida , M. and Shindoh , S. 1996 . A predictor-corrector inprior-point algorithms for the semidefinite linear complementarity problem using thtb Alizadeh-Haeberly-Overton search direction , Tokyo : Tokyo Institute of Technology . Research Report 311, Department of I Mathematical and Computing Sciences
   Google Scholar
• Kojima , M. , Shida , M. and Shindoh , S. 1996 . A note on the Nesterof-Todd and the Kojima-Shindo-Hara search directions in semidefinite programming , Tokyo : Tokyo Institute of Technology . Research Report 313, Department of Mathematical and Computing Sciences
   Google Scholar
• Lin , C.J. and Saigal , R. 1995 . A predictor-corrector method for semi-definite linear programming , Ann Arbor : The University of Michigan . Working paper, Department of Industrial and Operations Engineering
   Google Scholar
• Lin , C.J. and Saigal , R. 1995 . An infeasible start predictor-corrector method for semi-definite linear programming , Ann Arbor : The University of Michigan . Working paper, Department of Industrial and Operations Engineering
   Google Scholar
• Luo , Z. , Sturm , J.F. and Zhang , S. 1996 . Superlinear convergenab of a symmetric primal-dual path following algorithm for semidefinite programming , Rotterdam : Erasmus University . Report 9607/A, Econometric Institute,SIAM J\. Optim., to appear
   Google Scholar
• McShane , K.A. 1994 . Superlinearly convergent -iteration interior point algorithms for linear programming and the monotone linear complementarity problem . SIAM J. Optim , 4 : 247 – 261 .
   Google Scholar
• Mizuno , S. , Yoshise , A. and Kikuchi , T. 1989 . Practical polynomial time algorithms for linear complementarity problems . J. Oper. Res. Soc. Japan , 32 : 75 – 92 .
   Google Scholar
• Mizuno , S. , Todd , M.J. and Ye , Y. 1993 . On adaptive step primal-dual interior-point algorithms for linear programming . Math. Oper. Res , 18 : 964 – 981 .
   Web of Science ®Google Scholar
• Mizuno , S. 1994 . Polynomiality of infeasible interior point algorithms for linear programming . Math. Programming , 67 : 109 – 119 .
   Web of Science ®Google Scholar
• Monteiro , R.D.C. 1995 . “ Primal-dual path following algorithms for semidefinite programming ” . In SIAM J. Optim , Atlanta : Georgia Institute of Technology . Working paper School of Inustrial and Systems Engineering
   Google Scholar
• Monteiro , R.D.C. and Zhang , Y. 1996 . “ A unified analysis for a class of path-following primaldual interior-point algorithms for semidefinite programming ” . In Math. Programming , Atlanta : Georgia Institute of Technology . Working paper, School of Industrial and Systems Engineering,to appear
   Google Scholar
• Nesterov , Y.E. and Nemirovskii , A.S. 1993 . “ Interior Point Polynomial Methods in Convex Programming:Theory and Applications ” . In SIAM Philadelphia
   Google Scholar
• Nesterov , Y.E. and Todd , M.J. 1997 . Self-scaled Barrier and interior-point metod for convex programming . Math. Oper. Res , 22 : 1 – 42 .
   Web of Science ®Google Scholar
• Nesterov Y.E. Todd M.J. Primal-dual interior-point methods for self-scaled cones Technical report 1125 School of Operations Reseach and Industrial Engineering, Cornell University Ithaca 1995 revised 1996
   Google Scholar
• Porta F. Sheng R. A Superlinearly convergent primal-dual infeasible-interior-point alogorithm for semidefinite programming Reports on Computational Mathematics 78 Department of Mathematics, University of Iowa Iowa City 1995
   Google Scholar
• Porta , F. and Sheng , R. 1995 . “ Homogeneous interior-point algorithms for semidefinite programming ” . In Department of Mathematics , Vol. 82 , lowa City : University of lowa . Reports on Computational Mathematics
   Google Scholar
• Porta , F. and Sheng , R. 1996 . “ Superlinear convergence of interior-point algorithms for semidefinite programming ” . In Department of Mathematics , Vol. 86 , lowa City : University of lowa . Report on Computational Mathimatics
   Google Scholar
• Shida , M. , Shindoh , S. and Kojima , M. 1996 . “ Existence of search directions in interior-point-algorithms for the SDP and the monotone SDLCP ” . In Department of Mathematical and Computing Science , Vol. 310 , Tokyo : Tokyo Institute of Technology . Research Report
   Google Scholar
• Shida , M. and Shindoh , S. 1996 . “ Monotone semidefinite complementarity problems ” . In Department of Mathematical and Computing Science , Vol. 312 , Tokyo : Tokyo Institute of Technology . Research Report
   Google Scholar
• Sturm J.F. Zhang S. Symmetric primal-dual path following algorthims for semidefinite programming Report 9554/A Econometric Institute, Erasmus University Rotterdam 1995 revised 1996
   Google Scholar
• Todd , M.J. 1996 . Private communication , 312
   Google Scholar
• Todd , M.J. , Toh , K.C. and Tütüncü , R.H. 1996 . “ On the Nesterov-Todd direction in semidefinite programming ” . In School of Operations Research and Industrial Engineering , Ithaca : Cornell University . Technical report
   Google Scholar
• Tseng , P. 1992 . Complexity analysis of a linear complementarity algorithm based on a Lyapunov function . Math. Programming , 53 : 297 – 306 .
   Google Scholar
• Tseng , P. 1995 . “ Simplified analysis of a linear O(nL)-iteration infeasible predictor-corrector path following method for monotone LCP ” . In Recent Trends in Optimization Theory and Application , Edited by: Agarwal , R.P. 423 – 434 . Singapore : World Scientific .
   Google Scholar
• Vandenberghe , L. and Boyd , S. 1995 . A primal-dual potential reduction method for problem involving matrix inequalities . Math. Programming , 69 : 205 – 236 .
   Web of Science ®Google Scholar
• Zhang , Y. 1995 . “ On extending primal-dual interior-point algorthims from linear programming to semidefinite programming ” . In Department of Mathematics and Statistics , Baltimore : University of Maryland Baltimore County . SIAM J. Optim., to appear
   Google Scholar