On a special class of regularized central paths for semidefinite programs | Mathematical Programming
Skip to main content
Springer Nature Link
Log in

On a special class of regularized central paths for semidefinite programs

  • FULL LENGTH PAPER
  • Series A
  • Published:
Mathematical Programming Submit manuscript

Abstract

We present a special class of regularized central paths for standard primal-dual semidefinite program (SDP) that can be used to design path-following algorithms for finding the projection of any symmetric matrix/vector onto the solution set of the SDP. We will study the existence, convergence, and analytical properties of these paths.

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

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
¥17,985 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price includes VAT (Japan)

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

References

  1. Dieudonné J.: Foundations of Modern Analysis. Academic Press, New York/London (1960)

    MATH  Google Scholar 

  2. Halická M.: Analyticity of the central path at the boundary point in semidefinite programming. Eur. J. Oper. Res. 143(2), 311–324 (2002)

    Article  MATH  Google Scholar 

  3. Halická M.: Two simple proofs for analyticity of the central path in linear programming. Oper. Res. Lett. 28(1), 9–19 (2001)

    Article  MATH  MathSciNet  Google Scholar 

  4. Hoffman A.J.: On approximate solutions of systems of linear inequalities. J. Res. Natl Bureau Stand. 49, 263–265 (1952)

    Google Scholar 

  5. Horn, R.A., Johnson, C.R.: Topics in Matrix Analysis. Cambridge University Press, Cambridge (1994, corrected reprint of the 1991 original)

  6. Kojima M., Megiddo N., Noma T.: Homotopy continuation methods for nonlinear complementarity problems. Math. Oper. Res. 16, 754–774 (1991)

    Article  MATH  MathSciNet  Google Scholar 

  7. Lin A.: A high-order path-following method for locating the least-2-norm solution of monotone LCPs. SIAM J. Optim. 18(4), 1414–1435 (2008)

    Article  Google Scholar 

  8. Lin, A.: A high-order path-following method for projection onto the primal-dual optimal solution set of linear programs. Optimization (2008, in press)

  9. Mclinden L.: The complementarity problem for maximal monotone multifunction. In: Cottle, R.W., Giannessi, F., Lions, J.L.(eds) Variational Inequalities and Complementarity Problems, pp. 251–270. Wiley, New York (1980)

    Google Scholar 

  10. Megiddo N.: Pathways to the optimal set in linear programming. In: Meggido, N.(eds) Progress in Mathematical Programming: Interior-Point and Related Methods, pp. 131–158. Springer, New York (1989)

    Google Scholar 

  11. Monteiro R.D.C., Pang J.S.: On two interior-point mappings for nonlinear semidefinite complementarity problems. Math. Oper. Res. 23(1), 39–60 (1998)

    Article  MATH  MathSciNet  Google Scholar 

  12. Potra F.A.: Q-superlinear convergence of the iterates in primal-dual interior-point methods. Math. Program. Ser. A 91, 99–115 (2001)

    MATH  MathSciNet  Google Scholar 

  13. Stoer J., Wechs M., Mizuno S.: High order infeasible-interior-point methods for solving sufficient linear complementarity problems. Math. Oper. Res. 23, 832–862 (1998)

    Article  MATH  MathSciNet  Google Scholar 

  14. Stoer J., Wechs M.: On the analyticity properties of infeasible-interior-point paths for monotone linear complementarity problems. Numer. Math. 81, 631–645 (1999)

    Article  MATH  MathSciNet  Google Scholar 

  15. Stoer J.: High order long-step methods for solving linear complementarity problems. Ann. Oper. Res. 103, 149–159 (2001)

    Article  MATH  MathSciNet  Google Scholar 

  16. Preiß M., Stoer J.: Analysis of infeasible-interior-point paths arising with semidefinite linear complementarity problems. Math. Program. Ser. A 99(3), 499–520 (2004)

    Article  MATH  Google Scholar 

  17. Preiß, M., Stoer, J.: Analysis of infeasible-interior-point paths and high-order methods for solving SDLCP’s. In: Parametric Optimization and Related Topics. VII, pp. 235–251. Aportaciones Mat. Investig., vol. 18. Soc. Mat. Mexicana, Mexico (2004)

  18. Sturm J.F., Zhang S.: On the long step path-following method for semidefinite programming. Oper. Res. Lett. 22, 145–150 (1998)

    Article  MATH  MathSciNet  Google Scholar 

  19. Sturm J.F.: Superlinear convergence of an algorithm for monotone linear complementarity problems, when no strictly complementary solution exists. Math. Oper. Res. 24, 72–94 (1999)

    Article  MATH  MathSciNet  Google Scholar 

  20. Wright S.J.: Primal-dual Interior-point Methods. SIAM, Philadelphia (1997)

    MATH  Google Scholar 

  21. Wolkowicz, H., Saigal, R., Vandenberghe, L. (eds.): Handbook of semidefinite programming. In: International Series in Operations Research & Management Science, vol. 27. Kluwer, Boston (2000)

  22. Zhang S.: Global error bounds for convex conic problems. SIAM J. Optim. 10(3), 836–851 (2000)

    Article  MATH  MathSciNet  Google Scholar 

  23. Zhang Y.: On extending some primal-dual interior-point algorithms from linear programming to semidefinite programming. SIAM J. Optim. 8(2), 365–386 (1998)

    Article  MATH  MathSciNet  Google Scholar 

  24. Zhao Y.B., Li D.: On a new homotopy continuation trajectory for nonlinear complementarity problems. Math. Oper. Res. 26, 119–146 (2001)

    Article  MATH  MathSciNet  Google Scholar 

  25. Zhao Y.B., Li D.: Locating the least 2-norm solution of linear programs via a path-following method. SIAM J. Optim. 12, 893–912 (2002)

    Article  MATH  MathSciNet  Google Scholar 

  26. Zhao G.Y., Sun J.: On the rate of local convergence of high-order-infeasible-path-following algorithms for P *-linear complementarity problems. Comput. Optim. Appl. 14(3), 293–307 (1999)

    Article  MATH  MathSciNet  Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Department of Mathematical Sciences, Middle Tennessee State University, Murfreesboro, TN, 37132, USA

    Anhua Lin

Authors
  1. Anhua Lin
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Anhua Lin.

Additional information

A. Lin was partially supported by Middle Tennessee State University FRCAC Grant, Spring 2006–Fall 2006.

Rights and permissions

Reprints and permissions

About this article

Cite this article

Lin, A. On a special class of regularized central paths for semidefinite programs. Math. Program. 122, 65–85 (2010). https://doi.org/10.1007/s10107-008-0241-x

Download citation

  • Received:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s10107-008-0241-x

Keywords

Mathematics Subject Classification (2000)

Search

Navigation