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.
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
Bastos F, Paixão J (1993) Interior-point approaches to the transportation and assignment problems on microcomputers. Investigação Operacional 13(1):3–15
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
Karmarkar NK (1984) A new polynomial-time algorithm for linear programming. Combinatorica 4:373–395
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
Kojima M, Megiddo N, Mizuno S (1993) A primal-dual infeasible-interior point algorithm for linear programming. Math Program Ser A 61:261–280
Kovacevic-Vujcic VV (1991) Improving the rate of convergence of interior point methods for linear programming. Math Program 52:467–479
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
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
Lustig IJ, Marsten RE, Shanno DF (1994) Interior point method for linear programming: computational state of the art. ORSA J Comput 6:1–14
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
Mehrotra S (1992) On the implementation of a primal-dual interior point method. SIAM J Optim 2:575–601
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
Salahi M, Peng J, Terlaky T (2007) On mehrotra-type predictor-corrector algorithms. SIAM J Optim 18(4):1377–1397
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
Ye Y (1995) On the finite convergence of interior-point algorithms for linear programming. Math Program 68:303–318
Ye Y (1997) Interior-point algorithms, theory and analysis. Wiley, Chichester
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
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
Zhang Y, Zhang D (1994) Superlinear convergence of infeasible-interior-point methods for linear programming. Math Program 66(1–3):361–377
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
Corresponding author
Rights and permissions
About this article
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
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s11750-014-0346-8
Keywords
- Linear Programming
- Predictor-corrector algorithm
- Interior-point methods
- Mehrotra-type algorithm
- Polynomial complexity
- Superlinear convergence