Skip to main content
SpringerLink
Log in

On the convergence of a predictor-corrector variant algorithm

  • Original Paper
  • Published:
TOP Aims and scope Submit manuscript

Abstract

A feasible predictor-corrector Linear Programming variant of Mehrotra’s algorithm, that was shown to have good performance on transportation and assignment problems, was developed by Bastos and Paixão. We prove the theoretical efficiency of this algorithm by showing its polynomial complexity and its superlinear convergence.

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

Similar content being viewed by others

References

  • Almeida R, Bastos F, Teixeira A (2010) On polynomiality of a predictor-corrector variant algorithm. In: International conference on numerical analysis and applied mathematica 2010—ICNAAM 2010, American Institute of Physics (AIP). AIP Conference Proceedings, vol 2. Springer-Verlag, New York, pp 959–963

  • Bastos F (1994) Problemas de transporte e métodos de ponto interior. Dissertação de Doutoramento. Universidade Nova de Lisboa, Lisboa

    Google Scholar 

  • Bastos F, Paixão J (1993) Interior-point approaches to the transportation and assignment problems on microcomputers. Investigação Operacional 13(1):3–15

    Google Scholar 

  • Freund RW, Jarre F (1994) A QMR-based interior-point algorithm for solving linear programs. Numerical Analysis Manuscript. AT&T Bell Laboratories, Murray Hill, 94–19

  • Güler O, Ye Y (1993) Convergence behavior of interior-point algorithms. Math Program 60:215–228

    Article  Google Scholar 

  • Karmarkar NK (1984) A new polynomial-time algorithm for linear programming. Combinatorica 4:373–395

    Article  Google Scholar 

  • Kojima M, Megiddo N, Mizuno S (1993) Theoretical convergence of large-step primal-dual interior point algorithms for linear programming. Math Program 59(1–3):1–21

    Article  Google Scholar 

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

    Article  Google Scholar 

  • Kovacevic-Vujcic VV (1991) Improving the rate of convergence of interior point methods for linear programming. Math Program 52:467–479

    Article  Google Scholar 

  • Lustig IJ, Marsten RE, Shanno DF (1991) Computational experience with a primal-dual interior point method for linear programming. Linear Algebra Appl 152:191–222

    Article  Google Scholar 

  • Lustig IJ, Marsten RE, Shanno DF (1992) On implementing Mehrotra’s predictor-corrector interior-point method for linear programming. SIAM J Optim 2(3):435–449

    Article  Google Scholar 

  • Lustig IJ, Marsten RE, Shanno DF (1994) Interior point method for linear programming: computational state of the art. ORSA J Comput 6:1–14

    Article  Google Scholar 

  • McShane KA, Monma CL, Shanno DF (1989) An implementation of a primal-dual interior point method for linear programming. ORSA J Comput 1:70–83

    Article  Google Scholar 

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

    Article  Google Scholar 

  • Obuchowska WT, Caron RJ (1993) Improving the rate of convergence of interior point methods for smooth convex programmes. Windsor Mathematics Statistics Report, 93–03

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

    Google Scholar 

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

    Article  Google Scholar 

  • Teixeira A, Almeida R (2012) On the complexity of a mehrotra-type predictor-corrector algorithm. Lectures Notes in Computer Science 7335, Part III, pp 17–29

  • Wright SJ (1997) Primal-dual interior-point methods. SIAM, Philadelphia

    Book  Google Scholar 

  • Ye Y (1995) On the finite convergence of interior-point algorithms for linear programming. Math Program 68:303–318

    Google Scholar 

  • Ye Y (1997) Interior-point algorithms, theory and analysis. Wiley, Chichester

    Book  Google Scholar 

  • Zhang Y, Tapia RA (1992) Superlinear and quadratic convergence of primal-dual interior-point methods for linear programming revisited. J Optim Theory Appl 73(2):229–242

    Article  Google Scholar 

  • Zhang Y, Tapia RA, Dennis JE (1992) On the superlinear and quadratic convergence of primal-dual interior point linear programming algorithms. SIAM J Optim 2:304–324

    Article  Google Scholar 

  • Zhang Y, Zhang D (1994) Superlinear convergence of infeasible-interior-point methods for linear programming. Math Program 66(1–3):361–377

    Article  Google Scholar 

Download references

Acknowledgments

A. Teixeira was financially supported by the Unit Centro de Investigação Operacional (MATH-LVT-Lisboa-152), based at the Faculty of Sciences, University of Lisbon, financed by the Portuguese Foundation for Science and Technology (FCT).

Author information

Authors and Affiliations

  1. Department of Mathematics, University of Trás-os-Montes e Alto Douro, 5000-911, Vila Real, Portugal

    R. Almeida & A. Teixeira

  2. CM-UTAD, University of Trás-os-Montes e Alto Douro, Vila Real, Portugal

    R. Almeida

  3. CIO, Faculty of Sciences, University of Lisbon, Lisbon, Portugal

    A. Teixeira

Authors
  1. R. Almeida
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. A. Teixeira
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to A. Teixeira.

Rights and permissions

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Almeida, R., Teixeira, A. On the convergence of a predictor-corrector variant algorithm. TOP 23, 401–418 (2015). https://doi.org/10.1007/s11750-014-0346-8

Download citation

  • Received:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s11750-014-0346-8

Keywords

Mathematics Subject Classification

Search

Navigation