Skip to main content
SpringerLink
Log in

Complexity analysis of a full-Newton step interior-point method for linear optimization

  • Published:
Periodica Mathematica Hungarica Aims and scope Submit manuscript

Abstract

This paper concerns a short-update primal-dual interior-point method for linear optimization based on a new search direction. We apply a vector-valued function generated by a univariate function on the nonlinear equation of the system which defines the central path. The common way to obtain the equivalent form of the central path is using the square root function. In this paper we consider a new function formed by the difference of the identity map and the square root function. We apply Newton’s method in order to get the new directions. In spite of the fact that the analysis is more difficult in this case, we prove that the complexity of the algorithm is identical with the one of the best known methods for linear optimization.

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

Fig. 1

Similar content being viewed by others

References

  1. M. Achache, A weighted-path-following method for the linear complementarity problem. Studia Univ. Babeş-Bolyai. Ser. Informatica 49(1), 61–73 (2004)

    MathSciNet  MATH  Google Scholar 

  2. M. Achache, A new primal-dual path-following method for convex quadratic programming. Comput. Appl. Math. 25(1), 97–110 (2006)

    MathSciNet  MATH  Google Scholar 

  3. M. Achache, Complexity analysis and numerical implementation of a short-step primal-dual algorithm for linear complementarity problems. Appl. Math. Comput. 216(7), 1889–1895 (2010)

    MathSciNet  MATH  Google Scholar 

  4. K. Ahmadi, F. Hasani, B. Kheirfam, A full-Newton step infeasible interior-point algorithm based on Darvay directions for linear optimization. J. Math. Model. Algorithms Oper. Res. 13(2), 191–208 (2014)

    Article  MathSciNet  MATH  Google Scholar 

  5. W. Ai, S. Zhang, 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)

    Article  MathSciNet  MATH  Google Scholar 

  6. F. Alizadeh, D. Goldfarb, Second-order cone programming. Math. Program. 95(1), 3–51 (2003)

    Article  MathSciNet  MATH  Google Scholar 

  7. E. Andersen, J. Gondzio, Cs Mészáros, X. Xu, Implementation of interior point methods for large scale linear programs, in Inter. Point Methods Math. Program., ed. by T. Terlaky (Kluwer Academic Publishers, Dordrecht, 1996), pp. 189–252

    Chapter  Google Scholar 

  8. S. Asadi, H. Mansouri, Polynomial interior-point algorithm for \({P}_*(\kappa )\) horizontal linear complementarity problems. Numer. Algorithms 63(2), 385–398 (2013)

    Article  MathSciNet  MATH  Google Scholar 

  9. S. Asadi, H. Mansouri, A new full-Newton step \({O}(n)\) infeasible interior-point algorithm for \({P}_*(\kappa )\)-horizontal linear complementarity problems. Comput. Sci. J. Moldova 22(1), 37–61 (2014)

    MathSciNet  MATH  Google Scholar 

  10. Y.Q. Bai, L.M. Sun, Y. Chen, A new path-following interior-point algorithm for monotone semidefinite linear complementarity problems. Dyn. Contin. Discrete Impuls. Syst., Ser. B: Appl. Algorithms 17, 769–783 (2010)

    Article  MathSciNet  MATH  Google Scholar 

  11. Y.Q. Bai, F.Y. Wang, X.W. Luo, A polynomial-time interior-point algorithm for convex quadratic semidefinite optimization. RAIRO-Oper. Res. 44(3), 251–265 (2010)

    Article  MathSciNet  MATH  Google Scholar 

  12. R.W. Cottle, J.S. Pang, R.E. Stone, The Linear Complementarity Problem. Computer Science and Scientific Computing (Academic Press, Boston, 1992)

    Google Scholar 

  13. Zs. Darvay, A new algorithm for solving self-dual linear optimization problems. Studia Univ. Babeş-Bolyai, Ser. Informatica 47(1), 15–26 (2002)

  14. Zs. Darvay, A weighted-path-following method for linear optimization. Studia Univ. Babeş-Bolyai, Ser. Informatica 47(2), 3–12 (2002)

  15. Zs. Darvay, New interior point algorithms in linear programming. Adv. Model. Optim. 5(1), 51–92 (2003)

  16. Zs. Darvay, Á. Felméri, N. Forró, I.-M. Papp, P.-R. Takács, A new interior-point algorithm for solving linear optimization problems, in XVII. FMTU, ed. by E. Bitay (Transylvanian Museum Society, Cluj-Napoca, 2012), pp. 87–90. In Hungarian

  17. Zs. Darvay, I.-M. Papp, P.-R. Takács, An infeasible full-Newton step algorithm for linear optimization with one centering step in major iteration. Studia Univ. Babeş-Bolyai, Ser. Informatica 59(1), 28–45 (2014)

  18. J. Gondzio, T. Terlaky, A computational view of interior point methods for linear programming, in Advances in Linear and Integer Programming, ed. by J. Beasley (Oxford University Press, Oxford, GB, 1995)

    Google Scholar 

  19. M. Halická, Analytical properties of the central path at boundary point in linear programming. Math. Program. 84(2), 335–355 (1999)

    Article  MathSciNet  MATH  Google Scholar 

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

    Article  MathSciNet  MATH  Google Scholar 

  21. T. Illés, Lineáris optimalizálás elmélete és belsőpontos algoritmusai. Operations Research Reports 2014-04, Eötvös Loránd University, Budapest, pp. 1–95 (2014)

  22. T. Illés, M. Nagy, A Mizuno-Todd-Ye type predictor-corrector algorithm for sufficient linear complementarity problems. Eur. J. Oper. Res. 181(3), 1097–1111 (2007)

    Article  MathSciNet  MATH  Google Scholar 

  23. T. Illés, M. Nagy, T. Terlaky, EP theorem for dual linear complementarity problems. J. Optim. Theory Appl. 140(2), 233–238 (2009)

    Article  MathSciNet  MATH  Google Scholar 

  24. T. Illés, M. Nagy, T. Terlaky, Polynomial interior point algorithms for general linear complementarity problems. Alg. Oper. Res. 5(1), 1–12 (2010)

    MathSciNet  MATH  Google Scholar 

  25. T. Illés, M. Nagy, T. Terlaky, A polynomial path-following interior point algorithm for general linear complementarity problems. J. Global. Optim. 47(3), 329–342 (2010)

    Article  MathSciNet  MATH  Google Scholar 

  26. T. Illés, T. Terlaky, Pivot versus interior point methods: Pros and Cons. Eur. J. Oper. Res. 140, 6–26 (2002)

    Article  MathSciNet  MATH  Google Scholar 

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

    Article  MathSciNet  MATH  Google Scholar 

  28. B. Kheirfam, A new infeasible interior-point method based on Darvay’s technique for symmetric optimization. Ann. Oper. Res. 211(1), 209–224 (2013)

    Article  MathSciNet  MATH  Google Scholar 

  29. B. Kheirfam, A predictor-corrector interior-point algorithm for \({P}_*(\kappa )\)-horizontal linear complementarity problem. Numer. Algorithms 66(2), 349–361 (2014)

    Article  MathSciNet  MATH  Google Scholar 

  30. E.D. Klerk, Aspects of Semidefinite Programming: Interior Point Algorithms and Selected Applications (Kluwer Academic Pubishers, Norwell, MA, 2002)

    Book  MATH  Google Scholar 

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

    MATH  Google Scholar 

  32. M. Kojima, N. Megiddo, Y. Ye, An interior point potential reduction algorithm for the linear complementarity problem. Math. Program. 54(1–3), 267–279 (1992)

    Article  MathSciNet  MATH  Google Scholar 

  33. M. Kojima, S. Mizuno, A. Yoshise, A polynomial-time algorithm for a class of linear complementarity problems. Math. Program. 44(1–3), 1–26 (1989)

    Article  MathSciNet  MATH  Google Scholar 

  34. I. Lustig, R. Marsten, D. Shanno, On implementing Mehrotra’s predictor-corrector interior-point method for linear programming. SIAM J. Optim. 2(3), 435–449 (1992)

    Article  MathSciNet  MATH  Google Scholar 

  35. I. Lustig, R. Marsten, D. Shanno, Computational experience with a globally convergent primal-dual predictor-corrector algorithm for linear programming. Math. Program. 66, 123–135 (1994)

    Article  MathSciNet  MATH  Google Scholar 

  36. H. Mansouri, M. Pirhaji, A polynomial interior-point algorithm for monotone linear complementarity problems. J. Optim. Theory Appl. 157(2), 451–461 (2013)

    Article  MathSciNet  MATH  Google Scholar 

  37. H. Mansouri, T. Siyavash, M. Zangiabadi, A path-following infeasible interior-point algorithm for semidefinite programming. Iran. J. Oper. Res. 3(1), 11–30 (2012)

    Google Scholar 

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

    Article  MathSciNet  MATH  Google Scholar 

  39. C. Mészáros, The efficient implementation of interior point methods for linear programming and their applications. Ph.D. thesis, Eötvös Loránd University of Sciences, Ph.D. School of Operations Research, Applied Mathematics and Statistics, Budapest (1996)

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

    Article  MathSciNet  MATH  Google Scholar 

  41. Y. Nesterov, A. Nemirovskii, Interior Point Polynomial Methods in Convex Programming: Theory and Algorithms, SIAM Studies in Applied Mathematics, vol. 13 (SIAM Publications, Philadelphia, 1994)

    Book  MATH  Google Scholar 

  42. J. Peng, C. Roos, T. Terlaky, Self-Regular Functions: A New Paradigm for Primal-Dual Interior-Point Methods (Princeton University Press, Princeton, 2002)

    MATH  Google Scholar 

  43. F.A. Potra, The Mizuno-Todd-Ye algorithm in a larger neighborhood of the central path. Eur. J. Oper. Res. 143(2), 257–267 (2002)

    Article  MathSciNet  MATH  Google Scholar 

  44. F.A. Potra, R. Sheng, Predictor-corrector algorithm for solving \({P}_*(\kappa )\)-matrix LCP from arbitrary positive starting points. Math. Program. 76(1), 223–244 (1996)

    Article  MathSciNet  MATH  Google Scholar 

  45. F.A. Potra, R. Sheng, A large-step infeasible-interior-point method for the \({P}^*\)-Matrix LCP. SIAM J. Optim. 7(2), 318–335 (1997)

    Article  MathSciNet  MATH  Google Scholar 

  46. C. Roos, T. Terlaky, J-Ph Vial, Theory and Algorithms for Linear Optimization (Springer, New York, 2005)

    MATH  Google Scholar 

  47. S. Schmieta, F. Alizadeh, Extension of primal-dual interior point algorithms to symmetric cones. Math. Program., Ser. A 96(3), 409–438 (2003)

    Article  MathSciNet  MATH  Google Scholar 

  48. G. Sonnevend, An ”analytic center” for polyhedrons and new classes of global algorithms for linear (smooth, convex) programming. in System Modelling and Optimization: Proceedings of the 12th IFIP-Conference held in Budapest, Hungary, September 1985, Lecture Notes in Control and Information Sciences. ed. by A Prékopa, J Szelezsán, B Strazicky, vol. 84 (Springer, Berlin, 1986) pp. 866–876

  49. T. Terlaky, An easy way to teach interior-point methods. Eur. J. Oper. Res. 130(1), 1–19 (2001)

    Article  MathSciNet  MATH  Google Scholar 

  50. M.V.C Vieira, Jordan algebraic approach to symmetric optimization. Ph.D. thesis, Electrical Engineering, Mathematics and Computer Science, Delft University of Technology (2007)

  51. G.Q. Wang, A new polynomial interior-point algorithm for the monotone linear complementarity problem over symmetric cones with full NT-steps. Asia-Pac. J. Oper. Res. 29(2), 1250,015 (2012)

    Article  MathSciNet  Google Scholar 

  52. G.Q. Wang, Y.Q. Bai, A new primal-dual path-following interior-point algorithm for semidefinite optimization. J. Math. Anal. Appl. 353(1), 339–349 (2009)

    Article  MathSciNet  MATH  Google Scholar 

  53. G.Q. Wang, Y.Q. Bai, A primal-dual interior-point algorithm for second-order cone optimization with full Nesterov-Todd step. Appl. Math. Comput. 215(3), 1047–1061 (2009)

    MathSciNet  MATH  Google Scholar 

  54. G.Q. Wang, Y.Q. Bai, A new full Nesterov-Todd step primal-dual path-following interior-point algorithm for symmetric optimization. J. Optim. Theory Appl. 154(3), 966–985 (2012)

    Article  MathSciNet  MATH  Google Scholar 

  55. G.Q. Wang, Y.J. Yue, X.Z. Cai, Weighted-path-following interior-point algorithm to monotone mixed linear complementarity problem. Fuzzy Inf. Eng. 1(4), 435–445 (2009)

    Article  MATH  Google Scholar 

  56. G.Q. Wang, Y.J. Yue, X.Z. Cai, A weighted-path-following method for monotone horizontal linear complementarity problem. in Fuzzy Information and Engineering, Advances in Soft Computing. ed. by B.y. Cao, C.y. Zhang, T.f. Li, vol. 54, (Springer, Berlin, 2009) pp. 479–487

  57. S. Wright, Primal-Dual Interior-Point Methods (SIAM, Philadelphia, 1997)

    Book  MATH  Google Scholar 

  58. Y. Ye, Interior Point Algorithms. Theory and Analysis (Wiley, Chichester, 1997)

    Book  MATH  Google Scholar 

  59. Y. Ye, A path to the Arrow-Debreu competitive market equilibrium. Math. Program. 111(1–2), 315–348 (2008)

    MathSciNet  MATH  Google Scholar 

  60. Y. Ye, M. Todd, S. Mizuno, An \(O(\sqrt{n}L)\)-iteration homogeneous and self-dual linear programming algorithm. Math. Oper. Res. 19, 53–67 (1994)

    Article  MathSciNet  MATH  Google Scholar 

Download references

Acknowledgments

The authors gratefully acknowledge the support of the Edutus College (Collegium Talentum) and the Transylvanian Museum Society. The authors are thankful to the editor and the reviewer for their helpful suggestions that improved the presentation of this paper. We also thank Ágnes Felméri and Nóra Forró for their useful comments on the paper. The work of the third author was supported by a grant of the Romanian National Authority for Scientific Research, CNCS-UEFISCDI, project number PN-II-ID-PCE-2011-3-0024.

Author information

Authors and Affiliations

  1. Faculty of Mathematics and Computer Science, Babeş-Bolyai University, No. 1 Mihail Kogălniceanu Street, 400084, Cluj-Napoca, Romania

    Zsolt Darvay, Ingrid-Magdolna Papp & Petra-Renáta Takács

Authors
  1. Zsolt Darvay
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Ingrid-Magdolna Papp
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Petra-Renáta Takács
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Zsolt Darvay.

Rights and permissions

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Darvay, Z., Papp, IM. & Takács, PR. Complexity analysis of a full-Newton step interior-point method for linear optimization. Period Math Hung 73, 27–42 (2016). https://doi.org/10.1007/s10998-016-0119-2

Download citation

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s10998-016-0119-2

Keywords

Mathematics Subject Classification

Search

Navigation