Skip to main content
SpringerLink
Log in

An arc-search \({\mathcal {O}}(nL)\) infeasible-interior-point algorithm for linear programming

  • Original Paper
  • Published:
Optimization Letters Aims and scope Submit manuscript

Abstract

Arc-search interior-point methods have been proposed to capture the curvature of the central path using an approximation based on ellipse. Yang et al. (J Appl Math Comput 51(1–2):209–225, 2016) proved that an arc-search algorithm has the computational order of \({\mathcal {O}}(n^{5/4}L)\). In this paper, we propose an arc-search infeasible-interior-point algorithms and discuss its convergence analysis. We improve the polynomial bound from \({\mathcal {O}}(n^{5/4}L)\) to \({\mathcal {O}}(nL)\), which is at least as good as the best existing bound for infeasible-interior-point algorithms for linear programming. Numerical results indicate that the proposed method solved LP instances faster than the existing \({\mathcal {O}}(n^{5/4}L)\) method.

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. Bland, R.G., Goldfarb, D., Todd, M.J.: The ellipsoid method: a survey. Oper. Res. 29(6), 1039–1091 (1981)

    Article  MathSciNet  MATH  Google Scholar 

  2. Browne, S., Dongarra, J., Grosse, E., Rowan, T.: The Netlib mathematical software repository. D-Lib magazine. http://www.dlib.org/dlib/september95/netlib/09browne.html (1995). Accessed 21 Mar 2017

  3. Do Carmo, M.P.: Differential Geometry of Curves and Surfaces, vol. 2. Prentice-hall, Englewood Cliffs (1976)

    MATH  Google Scholar 

  4. Dolan, E.D., Moré, J.J.: Benchmarking optimization software with performance profiles. Math. Program. 91(2), 201–213 (2002)

    Article  MathSciNet  MATH  Google Scholar 

  5. Gonzaga, C.C.: Polynomial affine algorithms for linear programming. Math. Program. 49(1–3), 7–21 (1990)

    Article  MathSciNet  MATH  Google Scholar 

  6. Karmarkar, N.: A new polynomial-time algorithm for linear programming. In Proceedings of the Sixteenth Annual ACM Symposium on Theory of Computing, pp. 302–311. ACM, (1984)

  7. Khachiyan, L.G.: Polynomial algorithms in linear programming. USSR Comput. Math. Math. Phys. 20(1), 53–72 (1980)

    Article  MathSciNet  MATH  Google Scholar 

  8. Klee, V., Minty, G.: How good is the simplex algorithm? In: Shisha, O. (ed.) Inequalities III, pp. 159–175. Academic, Cambridge (1972)

    Google Scholar 

  9. Kojima, M.: Basic lemmas in polynomial-time infeasible-interior-point methods for linear programs. Ann. Oper. Res. 62(1), 1–28 (1996)

    Article  MathSciNet  MATH  Google Scholar 

  10. Kojima, M., Megiddo, N., Mizuno, S.: A primal-dual infeasible-interior-point algorithm for linear programming. Math. Program. 61(1–3), 263–280 (1993)

    Article  MathSciNet  MATH  Google Scholar 

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

    Article  MathSciNet  MATH  Google Scholar 

  12. Lustig, I.J., Marsten, R.E., Shanno, D.F.: 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 

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

    Article  MathSciNet  MATH  Google Scholar 

  14. Miao, J.: Two infeasible interior-point predictor–corrector algorithms for linear programming. SIAM J. Optim. 6(3), 587–599 (1996)

    Article  MathSciNet  MATH  Google Scholar 

  15. Mizuno, S.: Polynomiality of infeasible-interior-point algorithms for linear programming. Math. Program. 67(1), 109–119 (1994)

    Article  MathSciNet  MATH  Google Scholar 

  16. Mizuno, S., Todd, M.J., Ye, Y.: On adaptive-step primal–dual interior-point algorithms for linear programming. Math. Oper. Res. 18(4), 964–981 (1993)

    Article  MathSciNet  MATH  Google Scholar 

  17. Monteiro, R.D., Adler, I., Resende, M.G.: A polynomial-time primal–dual affine scaling algorithm for linear and convex quadratic programming and its power series extension. Math. Oper. Res. 15(2), 191–214 (1990)

    Article  MathSciNet  MATH  Google Scholar 

  18. Renegar, J.: A polynomial-time algorithm, based on Newton’s method, for linear programming. Math. Program. 40(1–3), 59–93 (1988)

    Article  MathSciNet  MATH  Google Scholar 

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

    Article  MathSciNet  MATH  Google Scholar 

  20. Salahi, M., Terlaky, T.: Mehrotra-type predictor–corrector algorithm revisited. Optim. Methods Softw. 23(2), 259–273 (2008)

    Article  MathSciNet  MATH  Google Scholar 

  21. Shmakov, S.L.: A universal method of solving quartic equations. Int. J. Pure Appl. Math. 71(2), 251–259 (2011)

    MathSciNet  MATH  Google Scholar 

  22. Wright, S.J.: Primal–Dual Interior-Point Methods. SIAM, Philadelphia (1997)

    Book  MATH  Google Scholar 

  23. Yang, X., Zhang, Y., Liu, H.: A wide neighborhood infeasible-interior-point method with arc-search for linear programming. J. Appl. Math. Comput. 51(1–2), 209–225 (2016)

    Article  MathSciNet  MATH  Google Scholar 

  24. Yang, Y.: A polynomial arc-search interior-point algorithm for convex quadratic programming. Eur. J. Oper. Res. 215(1), 25–38 (2011)

    Article  MathSciNet  MATH  Google Scholar 

  25. Yang, Y.: A polynomial arc-search interior-point algorithm for linear programming. J. Optim. Theory Appl. 158(3), 859–873 (2013)

    Article  MathSciNet  MATH  Google Scholar 

  26. Yang, Y.: CurveLP-a MATLAB implementation of an infeasible interior-point algorithm for linear programming. Numer. Algorithms 74(4), 967–996 (2017)

    Article  MathSciNet  MATH  Google Scholar 

  27. Yang, Y., Zhou, Z.: An analytic solution to Wahba’s problem. Aerosp. Sci. Technol. 30, 46–49 (2013)

    Article  Google Scholar 

  28. Ye, Y.: An \({\cal{O}}(n^3 {L})\) potential reduction algorithm for linear programming. Math. Program. 50(1–3), 239–258 (1991)

    Article  MathSciNet  Google Scholar 

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

    Article  MathSciNet  MATH  Google Scholar 

Download references

Acknowledgements

Makoto Yamashita’s research was partially supported by JSPS KAKENHI (Grant Number: 15K00032).

Author information

Authors and Affiliations

  1. US NRC, Office of Research, 21 Church Street, Rockville, MD, 20850, USA

    Yaguang Yang

  2. Department of Mathematical and Computing Science, Tokyo Institute of Technology, Tokyo, Japan

    Makoto Yamashita

Authors
  1. Yaguang Yang
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Makoto Yamashita
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Makoto Yamashita.

Rights and permissions

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Yang, Y., Yamashita, M. An arc-search \({\mathcal {O}}(nL)\) infeasible-interior-point algorithm for linear programming. Optim Lett 12, 781–798 (2018). https://doi.org/10.1007/s11590-017-1142-9

Download citation

  • Received:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s11590-017-1142-9

Keywords

Search

Navigation