Skip to main content
Fachgebiete
Automobil + Motoren Bauwesen + Immobilien Business IT + Informatik Elektrotechnik + Elektronik Energie + Nachhaltigkeit Finance + Banking Management + Führung Marketing + Vertrieb Maschinenbau + Werkstoffe Versicherung + Risiko
DE
EN
Bücher
Zeitschriften
Themenseiten
Organisationspsychologie Projektmanagement Marketing Smart Manufacturing
Weitere Formate
Podcasts Webinare Technik Webinare Wirtschaft Kongresse Veranstaltungskalender Awards
Jetzt Einzelzugang starten
Zugang für Unternehmen
Referenzkunden
SLX-Digitalkonferenz: Zukunftswerkstatt 2024

Mehr Umsatz mit Top-Kontakten

Am 7. Mai erfahren Sie, wie Vertriebsteams Leadgenerierung, Leadnurturing und Leadstrategien effizient steuern können.
Erweiterte Suche
Anmelden
nach oben
Erschienen in:
Introduction Kapitel lesen Erstes Kapitel lesen

2021 | OriginalPaper | Buchkapitel

5. Basics in Linear and Convex Optimization

verfasst von : Roman A. Polyak

Erschienen in: Introduction to Continuous Optimization

Verlag: Springer International Publishing

Einloggen

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

search-config
loading …

Abstract

In the first part of this chapter we cover basic LP facts, including LP duality, special LP structure, as well as two main tools for solving LP: simplex and interior point methods (IPMs).

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 "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 390 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Maschinenbau + Werkstoffe




 

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 Optimization with Equality Constraints
Nächstes Kapitel Self-Concordant Functions and IPM Complexity
Literatur
Adler, I., Monteiro, R.: Limiting behavior of the affine scaling continuous trajectories for linear programming problems. Math. Program. 50, 29–51 (1991)MathSciNetMATHCrossRef
Adler, I., Karmarkar, N., Resende, M., Veiga, G.: An implementation of Karmarkar’s algorithm for linear programming. Math. Program. 44, 297–335 (1989). Errata in Math. Program. 50, 415 (1991)
Anstreicher, K.M.: Potential reduction algorithms, In: Terlaky, T. (ed.) Interior Point Methods of Mathematical Programming, pp. 125–158. Kluwer Academic Publishers, Dordrecht (1996)CrossRef
Barnes, E.R.: A variation on Karmarkar’s algorithm for solving linear programming problem. Math. Program. 36, 174–182 (1986)MathSciNetMATHCrossRef
Barnes, E.R.: Some results concerning convergence of the affine scaling algorithm. Contemp. Math. 114, 131–139 (1990)MathSciNetCrossRef
Beck, A., Teboulle, M.: Fast gradient based algorithm for constrained total variation image denoising and deblurring problems. Trans. Imag. Proc. 18, 2419–2434 (2009)MathSciNetMATHCrossRef
Beck, A., Teboulle, M.: A fast iterative shrinkage—thresholding algorithm for linear inverse problem. SIAM J. Imag. Sci. 2(1), 183–202 (2009a)MathSciNetMATHCrossRef
Bertsekas, D.P.: Constrained Optimization and Lagrange Multiplier Methods. Academic Press, New York (1982)MATH
Bertsekas, D.P.: Nonlinear Programming. Athena Scientific, Belmont (1999)
Bixby, R.E.: A brief history of linear and mixed—integer programming computation. In: Documenta Mathematica Optimization Stories, Berlin (2012)
Chen, C., Mangasarian, O.L.: Smoothing methods for convex inequalities and linear complementarity problems. Math. Program. 71, 51–69 (1995)MathSciNetMATHCrossRef
Cheney, W., Goldstein, A.: Note on paper by Zuhovickii concerning the Tchebycgeff problem for linear equations. J. Soc. Indust. Appl. Math. 6(3), 233–239 (1958)MathSciNetMATHCrossRef
Dantzig, G.: Linear Programming and Extensions. Princeton University, Princeton (1963)MATHCrossRef
Dantzig, G., Wolfe, P.: The decomposition principle for linear programs. Oper. Res. 8(1), 101–111 (1960)MATHCrossRef
Dantzig, G., Fulkerson, D., Johnson, S.: Solution of a large—scale traveling—salesman problem. J. Oper. Res. Soc. Am. 2(4), 393–410 (1954)MathSciNetMATH
Dantzig, G., Ford, L., Fulkerson, D.: In: Kuhn, H., Tucker, A. (eds.) Algorithm for Simultaneous Solution the Primal and Dual Linear Programming Problem in Linear Inequalities and Related System (1956)
Demyanov, V., Rubinov, A.: Approximate Methods in Optimization Problems. American Elsevier Publishing, New York (1970)
Den Hertog, D., Roos, C., Vial, J.: A complexity reduction for the long-step path-following algorithm for linear programming. SIAM J. Optim. 2, 71–87 (1992)MathSciNetMATHCrossRef
Dikin, I.: Iterative solution of problems of linear and quadratic programming. Doklady Akademii Nauk SSSR 174, 747–748 (1967). Translated in Soviet Mathematics Doklady 8, 674–675 (1967)
Dikin, I.: On the convergence of an iterative process. Upravlyaemye Sistemi 12, 54–60 (1974, in Russian)
Farkas, J.: Teorie der einfachen Ungleivhungen. J. Reine und Angewandte Mathematik 124, 1–27 (1902)
Fiacco, A.V., McCormick, G.P.: Nonlinear Programming: Sequential Unconstrained Minimization Techniques. SIAM, Philadelphia (1990)MATHCrossRef
Freund, R.: Theoretical efficiency of a shifted barrier function algorithm for linear programming. Linear Algebra Appl. 152, 19–41 (1991)MathSciNetMATHCrossRef
Garber, D., Hazan, E.: Faster Rates for the Frank–Wolfe Method over Strongly Convex Sets (2014, 2015). arxiv: 1406.1305v2[mathOC]
Gill, P., Murray, W., Saunders, J., Tomlin, J., Wright, M.: On projected Newton Barrier methods for linear programming and an equivalence to Karmarkar’s projective method. Math. Program. 36, 183–209 (1986)MathSciNetMATHCrossRef
Goldshtein, E., Tretiakov, N.: Modified Lagrangian Functions. Nauka, Moscow (1989)
Goldstein, A.: Convex programming in gilbert space. Bull. Am. Math Soc. 70, 709–710 (1964)MATHCrossRef
Gonzaga, C.: An algorithm for solving linear programming problems in O(n 3 L) operations. In: Megiddo, N. (ed.) Progress in Mathematical Programming: Interior Point and Related Methods, pp. 1–28. Springer, New York (1989)
Griva, I., Shanno, D., Vanderbei, R., Benson, H.: Global convergence of a primal-dual interior-point method for nonlinear programming. Algorithmic Oper. Res. 3(1), 12–29 (2008)MathSciNetMATH
Grossman, K., Kaplan, A.A.: Nonlinear programming based on unconstrained minimization. Novosibirsk, Nauka (1981), in Russian
Guler, O., den Hertog, D., Roos, C., Terlaky, T., Tsuvhiya, T.: Degeneracy in interior point methods for linear programming: a survey. Ann. Oper. Res. 46, 107–138 (1993)MathSciNetMATHCrossRef
Hoffman, A.: On approximate solution of system of linear inequalities. J. Res. Nat. Bureau Stand. 49, 263–265 (1952)MathSciNetCrossRef
Ioffe, A., Tichomirov, V.: Duality of convex functions and extremum problems. Uspexi Mat. Nauk 23(6)(144), 51–116 (1968)
Ioffe, A.D., Tihomirov, V.M.: Theory of Extremal Problems. North-Holland, Amsterdam (2009)MATH
Jensen, B., Roos, C., Terlaky, T., Vial, J.: Primal-dual algorithms for linear programming based on th logarithmic barrier method. J. Optim. Theory Appl. 83, 1–26 (1994)MathSciNetMATHCrossRef
Jensen, B., Roos, C., Terlaky, T.: A polynomial dikin-type primal-dual algorithm for linear programming. Math. Oper. Res. 21, 341–353 (1996)MathSciNetMATHCrossRef
Kantorovich, L.: Mathematical methods of organizing and planning production. Manage. Sci. 6(4), 366–422 (1939). JSTOR 2627082
Kantorovich, L.:The Best Use of Economic Resources. Pergamon Press, New York (1959)
Khachiyan, L.: A polynomial algorithm in linear programming. Doklady Akademiia Nauk SSSR 244, 1093–1096 (1979). (Translated into English in Soviet Mathematics Doklady 20, 191–194)
Kojima, M., Mizuno, S., Yoshise, A.: A polynomial-time algorithm for a class of linear complementarity problems. Math. Program. 44, 1–26 (1989)MathSciNetMATHCrossRef
Kojima, M., Mizuno, S., Yoshise, A.: A primal-dual interior point algorithm for linear programming, In: Megiddo, N. (ed.) Progress in mathematical programming: interior point and related methods, pp 29–47. Springer, New York (1989a)CrossRef
Kojima, M., Megiddo, N., Noma, T., Yoshise, A.: A unified approach to interior point algorithms for linear complementarity problems. Lecture Notes in Computer Science, vol. 538. Springer, Berlin (1991)
Koopmans, T.C.: Optimum utilization of the transportation system. Econometrica 17, 136–146 (1949)CrossRef
Kuhn, H., Tucker, A.: Nonlinear programming. In: Neyman, J. (ed.) Proceedings of the Second Berkeley Symposium on Mathematical Statistics and Probability. University of California Press, Berkeley, pp. 481–492 (1951)
Levitin, E., Polyak, B.: Minimization methods in the presence of constraints. Z. Vycisl. Mat. i Mat Fizz 6, 787–823 (1966)MathSciNetMATH
Lustig, I., Marsten, R., Shanno, D.: Computational experience with a primal-dual interior point method for linear programming. Linear Algebra Appl. 152, 191–222 (1991)MathSciNetMATHCrossRef
Lustig, I., Marsten, R., Shanno, D.: On implementing Mehrotra’s predictor-corrector interior point method for linear programming. SIAM J. Optim. 2, 435–449 (1992)MathSciNetMATHCrossRef
Lustig, I., Marsten, R., Shanno, D.: Interior point methods for linear programming: computational state of the art. ORSA J. Comput. 6(1), 1–14 (1994)MathSciNetMATHCrossRef
Megiddo, N.: Pathways to the optimal set in linear programming. In: Progress in Mathematical Programming—Interior Point and Related Methods. Springer, Berlin, pp. 131–158 (1989)
Megiddo, N., Shub, M.: Boundary behavior of interior point methods in linear programming. Math. Oper. Res. 14(1), 97–146 (1989)MathSciNetMATHCrossRef
Mehrotra, S.: Higher order methods and their performance. Technical Report 90-16R1, Department of Industrial Engineering and Management Science, Northwestern University, Evanston, IL 60208, USA (1990). Revised July 1991
Mizuno, S., Todd, M.: An O(n 3 L) adaptive path following algorithm for a linear complementarity problem. Math. Program. 52, 587–595 (1991)MathSciNetMATHCrossRef
Monteiro, R., Adler, I., Resende, M.: A polynomial - time primal-dual affine scaling algorithm for linear and convex quadratic programming and its power series extension. Math. Oper. Res. 15, 191–214 (1990)MathSciNetMATHCrossRef
Nemirovski, A., Yudin, D.: Informational Complexity and Efficient Methods for Solution of Convex Extremal Problems. Wiley, New York (1983)
Nesterov, Y.: A method for solving convex programming problems with convergence rate O(k −2). Dokl. Akad. Navk. SSSR 269(3), 543–547 (1983, in Russian)
Nesterov, Y.: Introductory Lectures on Convex Optimization. Kluwer Academic Publishers, Norwell, (2004)MATHCrossRef
Pardalos, P., Resende, M.: Interior point methods for global optimization. In: Terlaky, T. (ed.) IPM of Mathematical Programming Applied Optimization, vol. 5. Kluwer, Dordrecht, pp. 467–500 (1996)
Pardalos, P., Wolkowicz, H.: Topics in Semidefinite and Interior - Point Methods. Fields Institute Communications Series 18, American Mathematical Society, New York (1998)
Pardalos, P., Ye, Y., Han, G.: Computational Aspects of an Interior Point Algorithm for Quadratic Problems with box Constraints. In: Large-Scale Numerical Optimization. SIAM, Philadelphia, pp. 92–112 (1990)
Polak E.: Computational Methods in Optimization: A Unified Approach. Academic Press, New York (1971)
Polyak, B.: Introduction to Optimization. Optimization Software, New York (1987)MATH
Polyak, R.: Algorithm for Simultaneous Solution Primal and Dual Convex Programming Problems, Transaction of the Scientific Seminar. Cibernetic Institute, Kiev (1966)
Polyak, R.: The Legendre Transformation in Modern Optimization in “Optimization and its Applications in Control and Data Sciences”. Springer, Berlin (2016)
Potra, F.: A quadratically convergent predictor - corrector method for solving linear programs from infeasible starting points. Math. Program. 67(3), 383–406 (1994)MathSciNetMATHCrossRef
Pshenichnyj, B.: The Linearization Method for Constrained Optimization. Springer, Berlin (1994)MATHCrossRef
Ray, A., Majumder, S.: Derivation of some new distributions in statistical mechanics using maximum entropy approach. Yugoslav J. Oper. Res. 24(1), 145–155 (2014)MathSciNetMATHCrossRef
Renegar, J.: A polynomial -time algorithm, based on Newton’s method, for linear programming. Math. Program. 40, 59–93 (1988)MathSciNetMATHCrossRef
Renegar, J.: A mathematical view of interior - point methods in convex optimization. In: MPS-SIAM Series on Optimization. SIAM, New York (2001)
Rockafellar, R.T.: A dual approach to solving nonlinear programming problems by unconstrained minimization. Math. Program. 5, 354–373 (1973)MATHCrossRef
Rockafellar, R.T., Wets R.J.-B: Variational Analysis. Springer, Berlin (2009)MATH
Roos, C., Terlaky, T.: Advances in linear optimization. In: Dell’Amico, M., Maffioli, F., Martello, S. (eds.) Annotated Bibliography in Combinatorical Optimization, Chapter 7. Wiley, New York (1997)
Roos, C., Vial, J.-Ph.: Analytic centers in linear programming. Technical Report 88–74, Faculty of Mathematics and Computer Science, TU Delft, NL-2628 BL Delft, The Netherlands (1988)
Roos, C., Terlaky, T., Vial, J.-Ph.: Theory and Algorithms for Linear Optimization: An Interior Point Approach. Wiley, Chichester (1997)MATH
Rozen, J.: The gradient projection method for nonlinear programming part 1: linear constraints. SIAM Journal Appl. Math. 8, 181–218 (1960)CrossRef
Rozen, J.: The gradient projection method for nonlinear programming part 2: nonlinear constraints. SIAM J. Appl. Math. 9, 514–553 (1961)CrossRef
Shor, N.: Nondifferentiable Optimization and Polynomial Problems. Kluwer Academic, Boston (1998)MATHCrossRef
Stiefel, E.: Note on Jordan elimination, linear programming and Tchebycheff approximation. Numerische Matematik 2(1), 1–17 (1960)MathSciNetMATHCrossRef
Todd, M.: Recent development and new directions in linear programming. In: Iri, M., Tanabe, K. (eds.) Mathematical programming: recent developments and applications, pp. 109–157. Kluwer Academic Press, Dordrecht (1989)
Todd, M.: A lower bound on the number of iterations of primal-dual interior-point methods for linear programming. In: Griffits, G.F. (ed.) Numerical Analysis (1993). Pitman Research, vol. 303
Todd, M., Ye, Y.: A lower bound on the number of iterations of long-step and polynomial interior-point linear programming algorithms. Ann. Oper. Res. 62, 233–252 (1996)MathSciNetMATHCrossRef
Tsuchiya, T.: Global convergence of the affine scaling methods for degenerate linear programming problems. Math. Program. 52, 377–404 (1991)MathSciNetMATHCrossRef
Tsuchiya, T.: Affine scaling algorithm. In: Terlaky, T. (ed.) Interior point methods of mathematical programming, pp. 35–82. Kluwer Academic Publishers, Dordrecht (1996)CrossRef
Tsuchiya, T., Muramatsu, M.: Global convergence of the long-step affine scaling algorithm for degenerate linear programming problems. SIAM J. Optim. 5(3), 525–551 (1995)MathSciNetMATHCrossRef
Vaidya, P.: An algorithm for linear programming which requires O((m + n)n 2 + (m + n)1.5 nL) arithmetic operations. Math. Program. 47, 175–201 (1990)
Vanderbei, R.: Linear Programming: Foundations and Extensions. Kluwer Academic, Boston (1996)MATH
Vanderbei, R., Meketon, M., Freedman, B.: A modification of Karmarkar’s linear programming algorithm. Algorithmica 1(4), 395–407 (1986)MathSciNetMATHCrossRef
Ye, Y., Pardalos, P.: A class of linear complementarity problems solvable in polynomial time. Linear Algebra Appl. 152, 3–17 (1991)MathSciNetMATHCrossRef
Ye, Y., Guler, O., Tapia, R., Zhang, Y.: A quadratically convergent \(O(\sqrt {n}L)\)-iteration algorithm for linear programming. Math. Program. 59, 151–162 (1993)
Ye, Y., Todd, M., Mizuno, S.: An \(O(\sqrt {n}L)\) - iteration homogeneous and self-dual linear programming algorithm. Math. Oper. Res. 19, 53–67 (1994)
Zhang, Y., Tapia, R.: Superlinear and quadratic convergence of primal-dual interior-point methods for linear programming revisited. J. Optim. Theory Appl. 73(2), 229–242 (1992)MathSciNetMATHCrossRef
Zoutendijk, G.: Methods of Feasible Directions. Elsevier, Amsterdam (1960)MATH
Zuchovitsky, S.: Algorithm for finding chebushev approximation of overdetermined system of linear equations. Dokl. Acad. Nauk SSSR 79(4), 561–564 (1951)
Zukhovitsky, S., Polyak, R., Primak, M.: An algorithm for solving convex Chebyshev approximation problem. Dokl. Acad. Nauk SSSR 151(1), 27–30 (1963)MathSciNet
Zukhovitsky, S., Polyak, R., Primak, M.: An algorithm for solving convex programming problem. Dokl. Acad. Nauk SSSR 153(3), 991–994 (1963a)MathSciNet
Zukhovitsky, S., Polyak, R., Primak, M.: Numerical method for solving convex programming problem in Hilbert space. Dokl. Acad. Nauk SSSR 163(2) (1965)
Metadaten
Titel
Basics in Linear and Convex Optimization
verfasst von
Roman A. Polyak
Copyright-Jahr
2021
Buch
Introduction to Continuous Optimization

Print ISBN: 978-3-030-68711-3

Electronic ISBN: 978-3-030-68713-7

Copyright-Jahr: 2021

DOI
https://doi.org/10.1007/978-3-030-68713-7_5