Skip to main content
Disciplines
Automotive Business IT + Informatics Construction + Real Estate Electrical Engineering + Electronics Energy + Sustainability Insurance + Risk Finance + Banking Management + Leadership Marketing + Sales Mechanical Engineering + Materials
Events
DE
EN
Books
Journals
Topic Page
Marketing
Start single access now
Access for companies
EXTENDED SEARCH
Log in
Top
Published in:
Introduction Read chapter Read first chapter

2021 | OriginalPaper | Chapter

5. Basics in Linear and Convex Optimization

Author : Roman A. Polyak

Published in: Introduction to Continuous Optimization

Publisher: Springer International Publishing

Log in

Activate our intelligent search to find suitable subject content or patents.

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).

Dont have a licence yet? Then find out more about our products and how to get one now:

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!

inform now

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!

inform now

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!

inform now
previous chapter Optimization with Equality Constraints
next chapter Self-Concordant Functions and IPM Complexity
Literature
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.: 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., 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)
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 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)
Metadata
Title
Basics in Linear and Convex Optimization
Author
Roman A. Polyak
Copyright Year
2021
Book
Introduction to Continuous Optimization

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

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

Copyright Year: 2021

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

Premium Partner

    Image Credits