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

A Second-Order Corrector Infeasible Interior-Point Method for Semidefinite Optimization Based on a Wide Neighborhood

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

Abstract

This paper proposes a second-order corrector infeasible interior-point method for semidefinite optimization in a large neighborhood of the central path. Our algorithm uses the Nesterov–Todd search directions as a Newton direction. We make use of the scaled Newton directions for symmetric search directions. Based on Ai and Zhang idea, we decompose the Newton directions into two orthogonal directions corresponding to positive and negative parts of the right-hand side of the Newton equation. In such a way, we use different step lengths for each of them and the corrector step is multiplied by the square of the step length of the infeasible directions in the expression of the new iterate. Starting with a point \((X^0, y^0, S^0)\) in the neighborhood in terms of Frobenius norm, we show that the algorithm terminates after at most \(\mathcal {O}(n^{\frac{5}{4}}\log \varepsilon ^{-1})\) iterations, improving by a factor \(n^{\frac{1}{4}}\) results on these kinds of algorithms. We believe that this is the first infeasible interior-point algorithm in a large neighborhood, which uses a Newton direction decomposition and a second-order corrector step to improve the iteration complexity. The main difference of the proposed method comparing with the existing methods in literature is the strategy for generating corrector directions. Some preliminary numerical results are given to verify the efficiency of the algorithm.

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. Ai, W.: Neighborhood-following algorithms for linear programming. Sci. China Ser. A 47, 812–820 (2004)

    Article  MathSciNet  MATH  Google Scholar 

  2. Ai, W., Zhang, S.: An \(O(\sqrt{n}L)\) iteration primal–dual path-following method, based on wide neighborhoods and large updates, for monotone LCP. SIAM J. Optim. 16(2), 400–417 (2005)

    MathSciNet  MATH  Google Scholar 

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

    Article  MathSciNet  MATH  Google Scholar 

  4. Asadi, S., Mansouri, H., Darvay, Zs, Zangiabadi, M., Mahdavi-Amiri, N.: Large-neighborhood infeasible predictor–corrector algorithm for horizontal linear complementarity problems over Cartesian product of symmetric cones. J. Optim. Theory Appl. 180, 811–829 (2019)

    Article  MathSciNet  MATH  Google Scholar 

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

    Book  MATH  Google Scholar 

  6. de Klerk, E.: Aspects of Semidefinite Programming. Applied Optimization. Kluwer, Dordrecht (2002)

    Book  MATH  Google Scholar 

  7. Faraut, J., korányi, A.: Analysis on Symmetric Cones. Oxford Mathematical Monographs. The Clarendon Press Oxford University Press, New York, Oxford Science Publications (1994)

  8. Feng, Z., Fang, L.: A wide neighborhood interior-point method with \(O(\sqrt{n}L)\) iteration-complexity bound for semidefinite programming. Optimization 59, 1235–1246 (2010)

    MathSciNet  MATH  Google Scholar 

  9. Feng, Z., Fang, L.: A new \(O(\sqrt{n}L)\)-iteration predictor–corrector algorithm with wide neighborhood for semidefinite programming. J. Comput. Appl. Math. 256, 65–76 (2014)

    MathSciNet  MATH  Google Scholar 

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

    Book  MATH  Google Scholar 

  11. Karmarkar, N.K.: A new polynomial-time algorithm for linear programming. Combinatorica 4(4), 373–395 (1984)

    Article  MathSciNet  MATH  Google Scholar 

  12. Kheirfam, B.: A predictor–corrector infeasible-interior-point algorithm for semidefinite optimization in a wide neighborhood. Fund. Inform. 152, 33–50 (2017)

    MathSciNet  MATH  Google Scholar 

  13. Kheirfam, B., Chitsaz, M.: Polynomial convergence of two higher order interior-point methods for \(P_*(\kappa )\)-LCP in a wide neighborhood of the central path. Period. Math. Hung. 76(2), 243–264 (2018)

    MATH  Google Scholar 

  14. Kheirfam, B., Haghighi, M.: A wide neighborhood interior-point algorithm for linear optimization based on a specific kernel function. Period. Math. Hung. 79, 94–105 (2019)

    Article  MathSciNet  MATH  Google Scholar 

  15. Kheirfam, B., Mohamadi-sangachin, M.: A wide neighborhood second-order predictor–corrector interior-point algorithm for semidefinite optimization with modified corrector directions. Fund. Inform. 153, 327–346 (2017)

    MathSciNet  MATH  Google Scholar 

  16. Kojima, M., Megiddo, N., Noma, T., Yoshise, A.: A Unified Approach to Interior Point Algorithms for Linear Complementarity Problems. Lecture Notes in Computer Science, Vol. 538. Springer, Berlin (1991)

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

    MATH  Google Scholar 

  18. Liu, H., Yang, X., Liu, C.: A new wide neighborhood primal–dual infeasible-interior-point method for symmetric cone programming. J. Optim. Theory Appl. 158(3), 796–815 (2013)

    Article  MathSciNet  MATH  Google Scholar 

  19. Liu, C., Liu, H.: A new second-order corrector interior-point algorithm for semidefinit programming. Math. Meth. Oper. Res. 75, 165–183 (2012)

    Article  MATH  Google Scholar 

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

    Article  MathSciNet  MATH  Google Scholar 

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

    Article  MathSciNet  MATH  Google Scholar 

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

    Article  MathSciNet  MATH  Google Scholar 

  23. Monteiro, R.D.C.: First- and second-order methods for semidefnite programming. Math. Program. 97, 209–244 (2003)

    Article  MathSciNet  MATH  Google Scholar 

  24. 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 

  25. Nesterov, Y.E., Nemirovski, A.S.: Interior Point Methods in Convex Programming: Theory and Applications. SIAM, Philadelphia (1994)

    Google Scholar 

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

    Article  MathSciNet  MATH  Google Scholar 

  27. Potra, F.A.: Interior point methods for sufficient horizontal LCP in a wide neighborhood of the central path with best known iteration complexity. SIAM J. Optim. 24(1), 1–28 (2014)

    Article  MathSciNet  MATH  Google Scholar 

  28. 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 

  29. 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 

  30. 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 

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

    Article  MathSciNet  MATH  Google Scholar 

  32. Zhang, M.W.: A second order Mehrotra-type predictor–corrector algorithm for semidefinite optimization. J. Syst. Sci. Complex. 25, 1108–1121 (2012)

    Article  MathSciNet  MATH  Google Scholar 

Download references

Acknowledgements

We are grateful to the anonymous referees and editor for their useful comments that help us improve the presentation of this paper.

Author information

Authors and Affiliations

  1. Department of Applied Mathematics, Azarbaijan Shahid Madani University, Tabriz, Iran

    B. Kheirfam, A. Nasrollahi & M. Mohammadi

Authors
  1. B. Kheirfam
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. A. Nasrollahi
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. M. Mohammadi
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to B. Kheirfam.

Additional information

Publisher's Note

Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.

Rights and permissions

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Kheirfam, B., Nasrollahi, A. & Mohammadi, M. A Second-Order Corrector Infeasible Interior-Point Method for Semidefinite Optimization Based on a Wide Neighborhood. J Sci Comput 86, 13 (2021). https://doi.org/10.1007/s10915-020-01384-w

Download citation

  • Received:

  • Revised:

  • Accepted:

  • Published:

  • DOI: https://doi.org/10.1007/s10915-020-01384-w

Keywords

Mathematics Subject Classification

Search

Navigation