Nothing Special   »   [go: up one dir, main page]
Skip to main content
Springer Nature Link
Log in

An Adaptive Infeasible-Interior-Point Method with the One-Norm Wide Neighborhood for Semi-definite Programming

  • Published:
Journal of Scientific Computing Aims and scope Submit manuscript

    We’re sorry, something doesn't seem to be working properly.

    Please try refreshing the page. If that doesn't work, please contact support so we can address the problem.

Abstract

In this paper, we present a Mehrotra-type predictor–corrector infeasible-interior-point method, based on the one-norm wide neighborhood, for semi-definite programming. The proposed algorithm uses Mehrotra’s adaptive updating scheme for the centering parameter, which incorporates a safeguard strategy that keeps the iterates in a prescribed neighborhood and allows to get a reasonably large step size. Moreover, by using an important inequality that is the relationship between the one-norm and the Frobenius-norm, the convergence is shown for a commutative class of search directions. In particular, the complexity bound is \(\mathcal {O}(n\log \varepsilon ^{-1})\) for Nesterov–Todd direction, and \(\mathcal {O}(n^{3/2}\log \varepsilon ^{-1})\) for Helmberg–Kojima–Monteiro directions, where \(\varepsilon \) is the required precision. The derived complexity bounds coincide with the currently best known theoretical complexity bounds obtained so far for the infeasible semi-definite programming. Some preliminary numerical results are provided as well.

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
$34.99 /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 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. Alizadeh, F.: Combinatorial optimization with interior-point methods and semi-definite matrices Ph.D. thesis, Computer Sience Department, University of Minnesota, Minneapolis, USA (1991)

  2. Alizadeh, F.: Interior point methods in semidefinite programming with applications to combinatorial optimization. SIAM J. Optim. 5, 13–51 (1995)

    Article  MathSciNet  MATH  Google Scholar 

  3. Borchers, B.: Sdplib 1.2, a library of semidefinite programming test problems. Optim. Methods Softw. 11, 683–690 (1999)

    Article  MathSciNet  MATH  Google Scholar 

  4. Boyd, S., Ghaoui, L.E., Feron, E., Balakrishnan, V.: Linear Matrix Inequalities in System and Control Theory. SIAM, Philadelphia (1994)

    Book  MATH  Google Scholar 

  5. De Klerk, E.: Aspects of Semidefinite Programming: Interior Point Algorithms and Selected Applications. Kluwer Academic Publishers, Dordrecht (2002)

    Book  MATH  Google Scholar 

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

    Article  MathSciNet  MATH  Google Scholar 

  7. Horn, R.A., Johnson, C.R.: Topics in Matrix Analysis. Cambridge University Press, New York (1991)

    Book  MATH  Google Scholar 

  8. Ji, J., Potra, F.A., Sheng, R.: On the local convergence of a predictor–corrector method for semi-definite programming. SIAM J. Optim. 10, 195–210 (1999)

    Article  MathSciNet  MATH  Google Scholar 

  9. Kojima, M., Shindoh, S., Hara, S.: Interior-point methods for the monotone semidefinite linear complementarity problem in symmetric matrices. SIAM J. Optim. 7, 86–125 (1997)

    Article  MathSciNet  MATH  Google Scholar 

  10. Kojima, M., Shida, M.A., Shindoh, S.: Local convergence of predictor–corrector infeasible-interior-point algorithm for SDPs and SDLCPs. Math. Program. 80, 129–160 (1998)

    MathSciNet  MATH  Google Scholar 

  11. Koulaei, M.H., Terlaky, T.: On the complexity analysis of a Mehrotra-type primal--dual feasible algorithm for semidefinite optimization. Optim. Methods Softw. 25, 467–485 (2010)

    Article  MathSciNet  MATH  Google Scholar 

  12. Li, Y., Terlaky, T.: A new class of large neighborhood path-following interior point algorithms for semidefinite optimization with \(O(\sqrt{n}\log {(\text{ Tr }(X^0S^0)/{\varepsilon })})\) iteration complexity. SIAM J. Optim. 20, 2853–2875 (2010)

    Article  MathSciNet  MATH  Google Scholar 

  13. Liu, H., Liu, C., Yang, X.: New complexity analysis of a Mehrotra-type predictor-corrector algorithm for semidefinite programming. Optim. Methods Softw. 28, 1179–1194 (2013)

    Article  MathSciNet  MATH  Google Scholar 

  14. Luo, Z.Q., Sturm, J.F., Zhang, S.: Conic convex programming and self-dual embedding. Optim. Methods Softw. 14, 169–218 (2000)

    Article  MathSciNet  MATH  Google Scholar 

  15. Mehrotra, S.: On the implementation of a primal–dual interior point method. SIAM J. Optim. 2, 575–601 (1992)

    Article  MathSciNet  MATH  Google Scholar 

  16. Monteiro, R.D.C.: Primal–dual path-following algorithms for semidefenite programming. SIAM J. Optim. 7, 663–678 (1997)

    Article  MathSciNet  MATH  Google Scholar 

  17. Monteiro, R.D.C.: Polynomial convergence of primal--dual algorithms for semidefinite programming based on Monteiro and Zhang family of directions. SIAM J. Optim. 8, 797–812 (1998)

    Article  MathSciNet  MATH  Google Scholar 

  18. Monteiro, R.D.C., Zhang, Y.: A unified analysis for a class of long-step primal--dual path-following interior-point algorithms for semidefinite programming. Math. Program. 81, 281–299 (1998)

    MathSciNet  MATH  Google Scholar 

  19. Nesterov, Y.E., Nemirovsky, A.S.: Interior-Point Methods in Convex Programming: Theory and Applications. SIAM, Philsdephia (1994)

    Google Scholar 

  20. Nesterov, Y., Todd, M.: Self-scaled barriers and interior-point methods for convex programming. Math. Oper. Res. 22, 1–42 (1997)

    Article  MathSciNet  MATH  Google Scholar 

  21. Nesterov, Y., Todd, M.: Primal-dual interior-point methods for self-scaled cones. SIAM J. Optim. 8, 324–364 (1998)

    Article  MathSciNet  MATH  Google Scholar 

  22. Peng, J., Roos, C., Terlaky, T.: Self-Regularity: An New Paradigm for Primal–Dual Interior-Point Algorithms. Princeton University Press, Princeton (2002)

    MATH  Google Scholar 

  23. Peng, J., Roos, C., Terlaky, T.: Self-regular functions and new search directions for linear and semidefinite optimization. Math. Program. Ser. A 93, 129–171 (2002)

    Article  MathSciNet  MATH  Google Scholar 

  24. Potra, F.A., Sheng, R.: A superlinearly convergent primal–dual infeasible-interior-point algorithm for semidefinite programming. SIAM J. Optim. 8, 1007–1028 (1998)

    Article  MathSciNet  MATH  Google Scholar 

  25. Potra, F.A., Sheng, R.: On homogeneous interior-point algorithms for semi-definite programming. Optim. Methods Softw. 9, 161–184 (1998)

    Article  MathSciNet  MATH  Google Scholar 

  26. Potra, F.A., Sheng, R.: Superlinear convergence of interior-point algorithms for semidefinite programming. J. Optim. Theory Appl. 99, 103–119 (1998)

    Article  MathSciNet  MATH  Google Scholar 

  27. Rangarajan, B.K.: Polynomial convergence of infeasible-interior-point methods over symmetric cones. SIAM J. Optim. 16, 1211–1229 (2006)

    Article  MathSciNet  MATH  Google Scholar 

  28. Salahi, M., Mahdavi-Amiri, N.: Polynomial time second order Mehrotra-type predictor–corrector algorithms. Appl. Math. Comput. 183, 646–658 (2006)

    MathSciNet  MATH  Google Scholar 

  29. Salahi, M., Peng, J., Terlaky, T.: On Mehrotra-type predictor–corrector algorithms. SIAM J. Optim. 18, 1377–1397 (2007)

    Article  MathSciNet  MATH  Google Scholar 

  30. Sturm, J.F.: Using SeDuMi 1.02, a MATLAB toolbox for optimization over symmetric cones. Optim. Method Soft. 11, 625–653 (1999)

    Article  MathSciNet  MATH  Google Scholar 

  31. Todd, M.J., Toh, K.C., Tütüncü, R.H.: On the Nesterov–Todd direction in semidefinite programming. SIAM J. Optim. 8, 769–796 (1998)

    Article  MathSciNet  MATH  Google Scholar 

  32. Yang, X., Liu, H., Zhang, Y.: A second-order Mehrotra-type predictor–corrector algorithm with a new wide neighbourhood for semi-definite programming. Inter. J. Comput. Math. 91, 1082–1096 (2014)

    Article  MathSciNet  MATH  Google Scholar 

  33. Ye, Y.: A class of projective transformations for linear programming. SIAM J. Comput. 19, 457–466 (1990)

    Article  MathSciNet  Google Scholar 

  34. Zhang, Y.: On the convergence of a class of infeasible interior-point methods for the horizontal linear complementarity problem. SIAM J. Optim. 4, 208–227 (1994)

    Article  MathSciNet  MATH  Google Scholar 

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

    Article  MathSciNet  MATH  Google Scholar 

  36. Zhang, Y., Zhang, D.: On polynomial of the Mehrotra-type predictor–corrector interior-point algorithms. Math. Program. 68, 303–318 (1995)

    Article  MATH  Google Scholar 

Download references

Acknowledgements

We would like to thank the support of National Natural Science Foundation of China (NNSFC) under Grant Nos. 11501180, 11601134 and 11671122, Chinese Postdoctoral Science Foundation No. 2016M590346, Henan Normal University Doctoral Startup Issues No. qd14150 and Young Scientists Foundation No. 2014QK03, and Innovative Research Team (in Science and Technology) in University of Henan Province No. 14IRTSTHN023.

Author information

Authors and Affiliations

  1. College of Mathematics and Information Science, Henan Normal University, Xinxiang, 453007, People’s Republic of China

    Ximei Yang

  2. Department of Mathematics, Shanghai University, Shanghai, 200444, People’s Republic of China

    Ximei Yang & Yanqin Bai

Authors
  1. Ximei Yang
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Yanqin Bai
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Ximei Yang.

Rights and permissions

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Yang, X., Bai, Y. An Adaptive Infeasible-Interior-Point Method with the One-Norm Wide Neighborhood for Semi-definite Programming. J Sci Comput 78, 1790–1810 (2019). https://doi.org/10.1007/s10915-018-0827-2

Download citation

  • Received:

  • Revised:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s10915-018-0827-2

Keywords

Mathematics Subject Classification

Search

Navigation