nach oben

Erschienen in:

2014 | OriginalPaper | Buchkapitel

22. The Homogeneous Self-Dual Method

verfasst von : Robert J. Vanderbei

Erschienen in: Linear Programming

Verlag: Springer US

Einloggen

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config

KI-gestützte Suche

Aus

Abstract

In Chapter 18, we described and analyzed an interior-point method called the path-following algorithm. This algorithm is essentially what one implements in practice but as we saw in the section on convergence analysis, it is not easy (and perhaps not possible) to give a complete proof that the method converges to an optimal solution. If convergence were completely established, the question would still remain as to how fast is the convergence. In this chapter, we shall present a similar algorithm for which a complete convergence analysis can be given.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Vorheriges Kapitel The Affine-Scaling Method

Nächstes Kapitel Integer Programming

The astute reader might notice that setting all variables to 0 produces an optimal solution.

Adler, I., Karmarkar, N., Resende, M., and Veiga, G. (1989). An implementation of Karmarkar’s algorithm for linear programming. Mathematical Programming, 44, 297–335.CrossRef

Mehrotra, S. (1989). Higher order methods and their performance (Techincal Report TR 90-16R1) Department of Industrial Engineering and Management Sciences, Northwestern University, Evanston. Revised July 1991.

Mehrotra, S. (1992). On the implementation of a (primal-dual) interior point method. SIAM Journal on Optimization, 2, 575–601.CrossRef

Mizuno, S., Todd, M., and Ye, Y. (1993). On adaptive-step primal-dual interior-point algorithms for linear programming. Mathematics of Operations Research, 18, 964–981.CrossRef

Tucker, A. (1956). Dual systems of homogeneous linear equations. Annals of Mathematics Studies, 38, 3–18.

Xu, X., Hung, P., and Ye, Y. (1993). A simplified homogeneous and self-dual linear programming algorithm and its implementation (Techincal Report). College of Business Administration, University of Iowa. To appear in Annals of Operations Research.

Ye, Y., Todd, M., and Mizuno, S. (1994). An \(o(\sqrt{n}l)\)-iteration homogeneous and self-dual linear programming algorithm. Mathematics of Operations Research, 19, 53–67.CrossRef

Titel: The Homogeneous Self-Dual Method
verfasst von: Robert J. Vanderbei
Verlag: Springer US
Buch: Linear Programming
Print ISBN: 978-1-4614-7629-0

Electronic ISBN: 978-1-4614-7630-6

Copyright-Jahr: 2014
DOI: https://doi.org/10.1007/978-1-4614-7630-6_22