Skip to main content
SpringerLink
Log in

Local convergence of predictor—corrector infeasible-interior-point algorithms for SDPs and SDLCPs

  • Published:
Mathematical Programming Submit manuscript

Abstract

An example of an SDP (semidefinite program) exhibits a substantial difficulty in proving the superlinear convergence of a direct extension of the Mizuno—Todd—Ye type predictor—corrector primal-dual interior-point method for LPs (linear programs) to SDPs, and suggests that we need to force the generated sequence to converge to a solution tangentially to the central path (or trajectory). A Mizuno—Todd—Ye type predictor—corrector infeasible-interior-point algorithm incorporating this additional restriction for monotone SDLCPs (semidefinite linear complementarity problems) enjoys superlinear convergence under strict complementarity and nondegeneracy conditions. © 1998 The Mathematical Programming Society, Inc. Published by Elsevier Science B.V.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

References

  1. C. Helmberg, F. Rendl, R.J. Vanderbei, H. Wolkowicz, An interior-point method for semidefinite programming, SIAM Journal on Optimization 6 (1996) 342–361.

    Google Scholar 

  2. M. Kojima, S. Shindoh, S. Hara, Interior-point methods for the monotone semidefinite linear complementarity problems, SIAM Journal on Optimization 7 (1997) 86–125.

    Google Scholar 

  3. F. Alizadeh, Interior point methods in semidefinite programming with application to combinatorial optimization, SIAM Journal on Optimization 5 (1995) 13–51.

    Google Scholar 

  4. F. Alizadeh, J.-P.A. Haeberly, M.L. Overton, Primal-dual interior-point methods for semidefinite programming, Working Paper, 1994.

  5. R.M. Freund, Complexity of an Algorithm for Finding an Approximate Solution of a Semidefinite Program with no Regularity Assumption, Technical report OR 302-94, Operations Research Center, MIT press, Cambridge, MA, 1994.

    Google Scholar 

  6. F. Jarre, An interior-point method for minimizing the maximum eigenvalue of a linear combination of matrices, SIAM Journal on Control and Optimization 31 (1993) 1360–1377.

    Google Scholar 

  7. Yu.E. Nesterov, A.S. Nemirovskii, Interior Point Polynomial Methods in Convex Programming: Theory and Applications, SIAM, Philadelphia, 1993.

    Google Scholar 

  8. L. Vandenberghe, S. Boyd, A primal-dual potential reduction method for problems involving matrix inequalities, Mathematical Programming 69 (1995) 205–236.

    Google Scholar 

  9. L. Vandenberghe, S. Boyd, Semidefinite Programming, SIAM Review 38 (1996) 49–95.

    Google Scholar 

  10. M. Kojima, S. Mizuno, A. Yoshise, A polynomial-time algorithm for a class of linear complementary problems, Mathematical Programming 44 (1989) 1–26.

    Google Scholar 

  11. R.D.C. Monteiro, I. Adler, Interior Path-Following Primal-Dual Algorithm, Part I: Linear Programming, Mathematical Programming 44 (1989) 27–41.

    Google Scholar 

  12. M. Kojima, S. Mizuno, A. Yoshise, An\(o(\sqrt n L)\) iteration potential reduction algorithm for linear complementarity problems, Mathematical Programming 50 (1991) 331–342.

    Google Scholar 

  13. S. Mizuno, M. Kojima, M.J. Todd, Infeasible-interior-point primal-dual potential-reduction algorithms for linear programming, SIAM Journal on Optimization 5 (1995) 52–67.

    Google Scholar 

  14. R.D.C. Monteiro, Primal-Dual Path Following Algorithms for Semidefinite Programming, SIAM Journal on Optimization (to appear).

  15. M. Kojima, S. Mizuno, 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, Berlin, 1989, pp. 29–47.

    Google Scholar 

  16. Y. Zhang, On Extending Primal-Dual Interior-Point Algorithms from Linear Programming to Semidefinite Programming, SIAM Journal on Optimization (to appear).

  17. Y. Zhang, On the convergence of a class of infeasible interior-point algorithms for the horizontal linear complementarity problem, SIAM Journal on Optimization 4 (1994) 208–227.

    Google Scholar 

  18. F.A. Potra, R. Sheng, A Superlinearly Convergent Primal-Dual Infeasible-Interior-Point Algorithm for Semidefinite Programming, Department of Mathematics, University of Iowa, Iowa City, IA 52242, October 1995.

    Google Scholar 

  19. S. Mizuno, M.J. Todd, Y. Ye, On adaptive-step primal-dual interior-point algorithms for linear programming, Mathematics of Operations Research 18 (1993) 964–981.

    Google Scholar 

  20. C.-J. Lin, R. Saigal, A predictor—corrector method for semi-definite linear programming, Working paper, Department of Industrial and Operations Engineering, The University of Michigan, Ann Arbor, Michigan 48109-2117, October 1995.

    Google Scholar 

  21. M. Kojima, M. Shida, S. Shindoh, Global and local convergence of predictor—corrector infeasibleinterior-point algorithms for semidefinite programs, Research Report #305, Department of Mathematical and Computing Sciences, Tokyo Institute of Technology, Oh-Okayama, Meguro, Tokyo 152, Japan, October 1995.

    Google Scholar 

  22. F. Alizadeh, J.-P.A. Haeberly, M.L. Overton, Complementarity and nondegeneracy in semidefinite programming, Working Paper, 1995.

  23. K. Fujisawa, M. Kojima, K. Nakata, SDPA (Semidefinite Programming Algorithm) — User's Manual — Technical Report B-308, Department of Mathematical and Computing Sciences, Tokyo Institute of Technology, Oh-Okayama, Meguro, Tokyo 152, Japan, December 1995, Revised August 1996.

    Google Scholar 

  24. M. Kojima, A primitive interior point algorithm for semidefinite programs in Mathematica, Technical Report B-293, Department of Mathematical and Computing Sciences, Tokyo Institute of Technology, Oh-Okayama, Meguro, Tokyo 152, Japan, December 1994.

    Google Scholar 

  25. J.-P.A. Haeberly, Private communication, February 1996.

  26. S. Mizuno, A superlinearly convergent infeasible-interior-point algorithm for geometrical LCPs without a strictly complementarity condition, Mathematics of Operations Research 21 (1996) 382–400.

    Google Scholar 

  27. Y. Ye, K. Anstreicher, On quadratic and\(o(\sqrt n L)\) convergence of a predictor—corrector algorithm for LCP, Mathematical Programming 62 (1993) 537–551.

    Google Scholar 

  28. R.D.C. Monteiro, S.J. Wright, Local convergence of interior-point algorithms for degenerate monotone LCP, Computational Optimization and Applications 3 (1994) 131–155.

    Google Scholar 

  29. Yu.E. Nesterov, M.J. Todd, Self-Scaled Cones and Interior-Point Methods in Nonlinear Programming, Working Paper, CORE, Catholic University of Louvain, Louvain-la-Neuve, Belgium, April 1994.

    Google Scholar 

  30. Yu.E. Nesterov, M.J. Todd, Primal-dual interior-point methods for self-scaled cones, SIAM Journal on Optimization (to appear).

  31. F.A. Potra, R. Sheng, Superlinear convergence of infeasible-interior-point algorithms for semidefinite programming, Department of Mathematics, University of Iowa, Iowa City, IA 52242, April 1996.

    Google Scholar 

  32. Z.-Q. Luo, J.S. Sturm, S. Zhang, Superlinear convergence of a symmetric primal-dual path following algorithm for semidefinite programming, SIAM Journal on Optimization (to appear).

  33. M. Kojima, M. Shida, S. Shindoh, A predictor—corrector interior-point algorithm for the semidefinite linear complementarity problem using the Alizadeh-Haeberly-Overton search direction, Research Report #311, Department of Mathematical and Computing Sciences, Tokyo Institute of Technology, Oh-Okayama, Meguro, Tokyo 152, Japan, December 1996.

    Google Scholar 

  34. F. Alizadeh, J.-P.A. Haeberly, M.L. Overton, Primal-dual interior-point methods for semidefinite programming: Convergence rates, stability and numerical results, SIAM Journal On Optimization (to appear).

Download references

Author information

Authors and Affiliations

  1. Department of Mathematical and Computing Sciences, Tokyo Institute of Technology, 2-12-1 Oh-Okayama, Meguro-ku, 152, Tokyo, Japan

    Masakazu Kojima

  2. Department of Mathematics, Kanagawa University, 3-27-1 Rokkakubashi, Kanagawa-ku, 221, Yokohama, Japan

    Masayuki Shida

  3. Department of Mathematics and Physics, The National Defense Academy, Hashirimizu 1-10-20, 239, Yokosuka, Japan

    Susumu Shindoh

Authors
  1. Masakazu Kojima
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Masayuki Shida
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Susumu Shindoh
    View author publications

    You can also search for this author in PubMed Google Scholar

Rights and permissions

Reprints and permissions

About this article

Cite this article

Kojima, M., Shida, M. & Shindoh, S. Local convergence of predictor—corrector infeasible-interior-point algorithms for SDPs and SDLCPs. Mathematical Programming 80, 129–160 (1998). https://doi.org/10.1007/BF01581723

Download citation

  • Received:

  • Revised:

  • Issue Date:

  • DOI: https://doi.org/10.1007/BF01581723

Keywords

Search

Navigation