"On the Shoulders of Giants" A brief excursion into the history of mathematical programming

Rainer Tichatschke

Discussiones Mathematicae, Differential Inclusions, Control and Optimization (2012)

  • Volume: 32, Issue: 1, page 5-44
  • ISSN: 1509-9407

Abstract

top
Similar to many mathematical fields also the topic of mathematical programming has its origin in applied problems. But, in contrast to other branches of mathematics, we don't have to dig too deeply into the past centuries to find their roots. The historical tree of mathematical programming, starting from its conceptual roots to its present shape, is remarkably short, and to quote Isaak Newton, we can say: "We are standing on the shoulders of giants". The goal of this paper is to describe briefly the historical growth of mathematical programming from its beginnings to the seventies of the last century and to review its basic ideas for a broad audience. During this process we will demonstrate that optimization is a natural way of thinking which follows some extremal principles.

How to cite

top

Rainer Tichatschke. ""On the Shoulders of Giants" A brief excursion into the history of mathematical programming." Discussiones Mathematicae, Differential Inclusions, Control and Optimization 32.1 (2012): 5-44. <http://eudml.org/doc/270526>.

@article{RainerTichatschke2012,
abstract = { Similar to many mathematical fields also the topic of mathematical programming has its origin in applied problems. But, in contrast to other branches of mathematics, we don't have to dig too deeply into the past centuries to find their roots. The historical tree of mathematical programming, starting from its conceptual roots to its present shape, is remarkably short, and to quote Isaak Newton, we can say: "We are standing on the shoulders of giants". The goal of this paper is to describe briefly the historical growth of mathematical programming from its beginnings to the seventies of the last century and to review its basic ideas for a broad audience. During this process we will demonstrate that optimization is a natural way of thinking which follows some extremal principles. },
author = {Rainer Tichatschke},
journal = {Discussiones Mathematicae, Differential Inclusions, Control and Optimization},
keywords = {history; mathematical programming; optimization},
language = {eng},
number = {1},
pages = {5-44},
title = {"On the Shoulders of Giants" A brief excursion into the history of mathematical programming},
url = {http://eudml.org/doc/270526},
volume = {32},
year = {2012},
}

TY - JOUR
AU - Rainer Tichatschke
TI - "On the Shoulders of Giants" A brief excursion into the history of mathematical programming
JO - Discussiones Mathematicae, Differential Inclusions, Control and Optimization
PY - 2012
VL - 32
IS - 1
SP - 5
EP - 44
AB - Similar to many mathematical fields also the topic of mathematical programming has its origin in applied problems. But, in contrast to other branches of mathematics, we don't have to dig too deeply into the past centuries to find their roots. The historical tree of mathematical programming, starting from its conceptual roots to its present shape, is remarkably short, and to quote Isaak Newton, we can say: "We are standing on the shoulders of giants". The goal of this paper is to describe briefly the historical growth of mathematical programming from its beginnings to the seventies of the last century and to review its basic ideas for a broad audience. During this process we will demonstrate that optimization is a natural way of thinking which follows some extremal principles.
LA - eng
KW - history; mathematical programming; optimization
UR - http://eudml.org/doc/270526
ER -

References

top
  1. [1] N.I. Akhiezer, The Classical Problem of Moments (Fizmatgiz, Moscow, 1961). (in Russian) Zbl0124.06202
  2. [2] C. Baiocchi and A. Capelo, Variational and Quasi-Variational Inequalities: Applications to Free Boundary Problems (J. Wiley & Sons, Chichester, 1984). 
  3. [3] A.V. Balakrishnan, Optimal control problems in Banach spaces, J. Soc. Ind. Appl. Math., Ser. A, Control 3 (1965) 152-180. Zbl0178.44601
  4. [4] E.M.L. Beale, The use of quadratic programming in stochastic linear programming, RAND Report P-2404 (RAND Corporation, 1961). 
  5. [5] J.F. Benders, Partitioning procedures for solving mixed-variables programming problems, Numer. Math. 4 (1962) 238-252. doi: 10.1007/BF01386316 Zbl0109.38302
  6. [6] R. Bellman, Dynamic Programming (Princeton Univ. Press, Princeton, 1957). 
  7. [7] L.D. Berkovitz, An existence theorem for optimal control, JOTA 4 (1969) 77-86. doi: 10.1007/BF00927413 Zbl0167.39201
  8. [8] V.G. Boltyanskij, Method of tents in the theory of extremum problems, Uspekhi Matem. Nauk 30 (1975) 3-55. (in Russian) Zbl0318.49017
  9. [9] V.G Boltyanskij, Mathematische Methoden der optimalen Steuerung (Akad. Verlagsgesellschaft Geest & Portig, Leipzig, 1971). 
  10. [10] V.G. Boltyanskij, Optimale Steuerung diskreter Systeme (Akad. Verlagsgesellschaft Geest & Portig, Leipzig, 1976). 
  11. [11] O. Bolza, Über Variationsprobleme mit Ungleichungen als Nebenbedingungen, Math. Abhandlungen 1 (1914) 1-18. Zbl45.0606.01
  12. [12] A.G. Butkovskij, Distributed Control Systems (Isd. Nauka, Moscow, 1969). (in Russian) Zbl0206.15004
  13. [13] C. Carathéodory, Calculus of Variations and Partial Differential Equations of the First Order (New York, Chelsea Publishing Co., 1982). 
  14. [14] A. Charnes, W.W. Cooper and B. Mellon, A model for optimizing production by reference to cost surrogates, Econometrica 23 (1955) 307-323. doi: 10.2307/1910387 Zbl0064.39601
  15. [15] A. Charnes and W.W. Cooper, Chance-constrained programming, Management Sci. 5 (1959) 73-79. Zbl0995.90600
  16. [16] F.H. Clarke, Optimization and Nonsmooth Analysis (Wiley, New York, 1983). Zbl0582.49001
  17. [17] F.H. Clarke, V.F. Demynov and F. Gianessi, Nonsmooth Optimization and Related Topics (Plenum Press, New York, 1989). 
  18. [18] G.B. Dantzig, Linear Programming and Extensions (Princeton, 1963). 
  19. [19] G.B. Dantzig, Linear Inequalities and Related Systems (Princeton Univ. Press, Princeton, 1966). 
  20. [20] G.B. Dantzig, Lectures in Differential Equations (Van Nostrand, Reinhold Co., New York, 1969). 
  21. [21] G.B. Dantzig, Linear programming under uncertainty, Management Sci. 1 (1955) 197-206. doi: 10.1287/mnsc.1.3-4.197 Zbl0995.90589
  22. [22] G.B. Dantzig and A. Madanski, On the solution of two-stage linear programs under uncertainty, in: Proc. 4th Berkeley Symp. Math Stat. Prob. (Berkeley, 1961). 
  23. [23] G.B. Dantzig and Ph. Wolfe, Decomposition principles for linear programs, Oper. Res. 8 (1960) 101-111. doi: 10.1287/opre.8.1.101 
  24. [24] W.C. Davidon, Variable Metric Methods for Minimization, A.E.C. Res. and Develop. Report ANL-5990 (Argonne National Laboratory, Illinois, 1959). 
  25. [25] V.F. Demyanov and A.M. Rubinov, Approximate Methods for Solving Extremum Problems (Leningrad State Univ., Leningrad, 1968). (in Russian) 
  26. [26] V.F. Demyanov and V.N. Malozemov, Introduction to Minimax (Nauka, Moscow, 1972). (in Russian) 
  27. [27] V.F. Demyanov and L.V. Vasiliev, Nondifferentiable Optimization (Nauka, Moscow, 1981). (in Russian) 
  28. [28] V.F. Demyanov and A.M. Rubinov, Fundations of Nonsmooth Analysis and Quasidifferential Calculus (Nauka, Moscow, 1990). (in Russian) 
  29. [29] J. Dennis and R. Schnabel, Numerical Methods for Unconstrained Optimization and Nonlinear Equations (Prentice-Hall, Englewood Cliffs, 1983). Zbl0579.65058
  30. [30] I. Dikin, An iterative solution of problems of linear and quadratic programming, Doklady AN SSSR 174 (1967) 747-748. (in Russian) Zbl0189.19504
  31. [31] A.Ya. Dubovitskij and A.A. Milyutin, Extremum problems under constraints, Doklady AN SSSR 149 (1963) 759-762. (in Russian) 
  32. [32] Y.M. Ermoliev, Stochastic Programming Methods (Nauka, Moscow, 1976). (in Russian) 
  33. [33] L. Euler, Methodus inveniendi lineas curvas maximi minimive proprietate gaudentes, sive solutio problematis isoperimetrici latissimo sensu accepti, Opera Omnia, Series 1, Volume 24, 1744. Zbl0788.01072
  34. [34] J. Farkas, Theorie der einfachen Ungleichungen, Journal für die Reine und Angewandte Mathematik 124 (1902) 1-27. Zbl32.0169.02
  35. [35] A.V. Fiacco and G.P. McCormick, Nonlinear Programming: Sequential Unconstrained Minimization Techniques (Wiley, 1968). 
  36. [36] R. Fletcher and C.M. Reeves, Function minimization by conjugate gradient, Computer J. 7 (1964) 149-154. doi: 10.1093/comjnl/7.2.149 Zbl0132.11701
  37. [37] L.R. Ford and D.R. Fulkerson, Flows in Networks (Princeton Univ. Press, Princeton, 1962). Zbl0106.34802
  38. [38] J.B. Fourier, Analyse des Équations Déterminées (Navier, Paris, 1831). 
  39. [39] L. Garding, The Dirichlet problem, Math. Intelligencer 2 (1979) 42-52. doi: 10.1007/BF03024386 
  40. [40] S.I. Gass and A.A. Assad, An annotated timeline of operations research: an informal history, Int. Ser. in OR & Management Sci. 75 (2005). Zbl1060.90001
  41. [41] R. Glowinski, J.L. Lions and R. Trémolières, Numerical Analysis of Variational Inequalities (North-Holland, Amsterdam, 1981). 
  42. [42] D. Goldfarb, Extension of Davidon's variable metric method to maximization under linear inequality and equality constraints, SIAM J. Appl. Math. 17 (1969) 739-764. doi: 10.1137/0117067 Zbl0185.42602
  43. [43] A.J. Goldman and A.W. Tucker, Theory of linear programming, in: Kuhn and Tucker (eds.), Linear Inequalities and Related Systems (Princeton, 1956), pp. 53-97. Zbl0072.37601
  44. [44] R. Gomory, Outline of an algorithm for integer solutions to linear programs, Bull. Amer. Math. Soc. 64 (1958) 275-278. doi: 10.1090/S0002-9904-1958-10224-4 Zbl0085.35807
  45. [45] H. Halkin, A maximum principle of Pontryagin, SIAM J. Control 4 (1966) 90-112. doi: 10.1137/0304009 
  46. [46] M.R. Hestenes and E. Stiefel, Methods of conjugate gradients for solving linear systems, J. Res. Natl. Bur. Stand. 49 (1952) 409-436. doi: 10.6028/jres.049.044 Zbl0048.09901
  47. [47] M.R. Hestenes, Calculus of Variational and Optimal Control Theory (Wiley, New York, 1966). 
  48. [48] A.D. Ioffe and V.M. Tikhomirov, Theory of Extremum Problems (Nauka, Moscow, 1974). (in Russian) Zbl0191.13101
  49. [49] C.G.J. Jacobi, Vorlesungen über analytische Mechanik : Berlin 1847/48, (Nach einer Mitschr. von Wilhelm Scheibner), Hrsg. von Helmut Pulte, Deutsche Mathematiker-Vereinigung (Braunschweig, Vieweg, 1996). 
  50. [50] F. John, Extremum problems with inequalities as subsidiary conditions, in: Studies and Essays, Presented to R. Courant on his 60th Birthday, Jan. 1948 (Interscience, New York), 187-204. 
  51. [51] P. Kall, Stochastic Linear Programming (Springer Verlag, Berlin, 1976). doi: 10.1007/978-3-642-66252-2 
  52. [52] L.V. Kantorovich, Mathematical Methods for Production Organization and Planning (Leningrad, 1939). (in Russian) 
  53. [53] L.V. Kantorovich, On an efficient method for solving some classes of extremum problems, Doklady AN SSSR 28 (1940) 212-215. (in Russian) 
  54. [54] L.V. Kantorovich, Fuctional analysis and applied mathematics, Uspekhi Matem. Nauk 6 (1948) 89-185. (in Russian) Zbl0034.21203
  55. [55] L.V. Kantorovich, Functional Analysis (Nauka, Moscow, 1959). (in Russian) Zbl0127.06102
  56. [56] L.V. Kantorovich, Economical Calculation of the Best Utilization of Ressources (Moscow, Academy of Sciences, 1960). (in Russian) 
  57. [57] L.V. Kantorovich, The Best Use of Economic Resources (Harvard U. Press, Cambridge, 1965). 
  58. [58] N. Karmarkar, A new polynomial time algorithm for linear programming, Combinatorica 4 (1984) 373-395. doi: 10.1007/BF02579150 Zbl0557.90065
  59. [59] W. Karush, Minima of functions of several variables with inequalities as side conditions, MSc Thesis (Univ. of Chicago, 1939). 
  60. [60] L. Khachiyan, A polynomial algorithm in linear programming, Doklady AN SSSR 244 (1979) 1093-1096. (in Russian) Zbl0414.90086
  61. [61] D. Kinderlehrer and G. Stampacchia, An Introduction to Variational Inequalities and their Applications (Acad. Press, New York-London, 1980). Zbl0457.35001
  62. [62] K. Kiwiel, Proximal level bundle methods for convex nondifferentiable optimization, saddle point problems and variational inequalities, Math. Programming 69 (B) (1995) 89-109. Zbl0857.90101
  63. [63] V. Klee and G. Minty, How good is the simplex algorithm? in: Inequalities III, O. Shisha, ed. (Academic Press, New York, 1972), 159-175. Zbl0297.90047
  64. [64] T.C. Koopmans, Exchange Ratios between Cargoes on Various Routes (Non-Refrigerated Dry Cargoes), Memorandum for the Combined Shipping Adjustment Board (Washington, D.C., 1942). 
  65. [65] T.C. Koopmans, Activity Analysis of Production and Allocation (Wiley, New York, 1951). Zbl0045.09503
  66. [66] T.C. Koopmans and M. Montias, On the Description and Comparison of Economic Systems, in: Comparison of Economic Systems (Univ. of California Press, 1971), 27-78. 
  67. [67] M.G. Krein and A.A. Nudelman, Markov's Problem of Moments and Extremum Problems (Nauka, Moscow, 1973). (in Russian) 
  68. [68] H.W. Kuhn and A.W. Tucker, Nonlinear Programming, Proc. of the Second Berkeley Symp. in Math., Statistics and Probability (Univ. of California Press, Berkeley, 1951), 481-492. 
  69. [69] H.W. Kuhn and A.W. Tucker, Linear and nonlinear programming, Per. Res. 5 (1957) 244-257. 
  70. [70] J.L. Lagrange, Théorie des Fonctions Analytiques (Journal de l'École Polytechnique, 1797). 
  71. [71] J.L. Lagrange, Mécanique Analytique (Journal de l'École Polytechnique, 1788). 
  72. [72] L.M. Lancaster, The history of the application of mathematical programming to menu planning, Europian Journal of Operation Research 57 (1992) 339-347. doi: 10.1016/0377-2217(92)90345-A Zbl0825.90785
  73. [73] L.J. Leifman, Functional Analysis, Optimization and Mathematical Economics: A Collection of Papers Dedicated to the Memory of L.V. Kantorovich (Oxford Univ. Press, 1990). Zbl0745.00069
  74. [74] C. Lemarechal, Lagrangian decomposition and nonsmooth optimization: Bundle algorithm, prox iterations, augmented Lagrangian, in: Nonsmooth Optimization: Methods and Applications (Erice, 1991) Gordon and Breach (Montreux, 1992), 201-206. 
  75. [75] J.K. Lenstra, A.H.G. Rinnooy Kan and A. Schrijver, History of Mathematikal Programming (CWI North-Holland, 1991). 
  76. [76] K. Levenberg, A method for the solution of certain nonlinear problems in least squares, Quarterly of Applied Mathem. 2 (1944) 164-168. Zbl0063.03501
  77. [77] E.S. Levitin and B.T. Polyak, Minimization methods under constraints, Zhurn. Vychisl. Matem. i Matem. Fiz. 6 (1966) 787-823. (in Russian) Zbl0184.38902
  78. [78] J.L. Lions and G. Stampacchia, Variational inequalities, Comm. Pure Appl. Math. 20 (1967) 493-519. doi: 10.1002/cpa.3160200302 Zbl0152.34601
  79. [79] O.G. Mancino and G. Stampacchia, Convex programming and variational inequalities, JOTA 9 (1972) 3-23. doi: 10.1007/BF00932801 Zbl0213.45202
  80. [80] B. Martinet, Régularisation d'inéquations variationelles par approximations successives, RIRO 4 (1970) 154-159. 
  81. [81] H. Minkowski, Allgemeine Lehrsätze über konvexe Polyeder. Nachrichten von der königlichen Gesellschaft der Wissenschaften zu Göttingen, Math.-Physik. Klasse (1897) 198-219. Zbl28.0427.01
  82. [82] G. Monge, Mémoire sur la théorie des déblais et de remblais. Histoire de l' Académie Royale des Sciences de Paris, avec les Mémoires de Mathématique et de Physique pour la même année (1781) 666-704. 
  83. [83] J.J. Moreau, Proximité et dualité dans un espace Hilbertien, Bull. Soc. Math. France 93 (1965) 273-299. Zbl0136.12101
  84. [84] U. Mosco, Convergence of convex sets and of solutions of variational inequalities, Advances in Mathematics 3 (1969) 510-585. doi: 10.1016/0001-8708(69)90009-7 
  85. [85] J.v. Neumann, Zur Theorie der Gesellschaftsspiele, Math. Ann. 100 (1928) 295-320. doi: 10.1007/BF01448847 
  86. [86] J.v. Neumann and O. Morgenstern, The Theory of Games and Economic Behavior (Springer, New York, 1944). Zbl0063.05930
  87. [87] L.W. Neustadt, The existence of the optimal control in the absence of convexity conditions, J. Math. Anal. Appl. 7 (1963) 110-117. doi: 10.1016/0022-247X(63)90081-7 
  88. [88] M. Padberg, Linear Optimization and Extensions (Springer, 1961). 
  89. [89] C. Panne and W. Poop, Minimum-cost cattle feed under probabilistic problem constraint, Management Sci. 9 (1963) 405-430. doi: 10.1287/mnsc.9.3.405 
  90. [90] B.T. Polyak, History of mathematical programming in the USSR, Math. Programming (B) 91 (2002) 401-416. doi: 10.1007/s101070100258 Zbl1030.90001
  91. [91] L.S. Pontryagin, V.G. Boltyanski and R.V. Gamkrelidse, Mathematical Theory of Optimal Processes (Nauka, Moscow, 1956). (in Russian) 
  92. [92] M. Powell, A method for nonlinear constrainets in minimization problems, in: Fletcher, R. (ed.): Optimization (Acad. Press, New York, 1969) 283-298. 
  93. [93] B.N. Pshenichnyj, Necessary Conditions for Extrema (Nauka, Moscow, 1969). (in Russian) 
  94. [94] B.N. Pshenichnyj, Convex Analysis and Extremum Problems (Nauka, Moscow, 1980). (in Russian) 
  95. [95] C.J. Poussin, Sure la méthode de l'approximation minimum, Anales de la Societe Scientifique de Bruxelles 35 (1911) 1-16. 
  96. [96] E.Ya. Remez, Foundations of Numerical Methods for Chebyshev Approximation (Naukova Dumka, Kiew, 1969). (in Russian) 
  97. [97] R.T. Rockafellar, Convex Analysis (Princeton University Press, 1972). Zbl0224.49003
  98. [98] R.T. Rockafellar, Monotone operators and the proximal point algorithm, SIAM J. Control Optim. 14 (1976) 877-898. doi: 10.1137/0314056 Zbl0358.90053
  99. [99] N. Rouche, P. Habets and M. Laloy, Stability Theory by Lyapunov's Direct Method (Springer, 1977). doi: 10.1007/978-1-4684-9362-7 Zbl0364.34022
  100. [100] E. Roxin, The existence of optimal control, Michigan Math. J. 9 (1962) 109-119. doi: 10.1307/mmj/1028998668 
  101. [101] H. Schramm and J. Zowe, A version of the bundle idea for minimizing a nonsmooth function: Conceptual idea, convergence analysis, numerical results, SIAM J. Optim. 2 (1992) 121-152. doi: 10.1137/0802008 Zbl0761.90090
  102. [102] N. Shor, Application of the subgradient method for the solution of network transport problems (Notes of Sc. Seminar, Ukrainian Acad. of Sci., Kiew, 1962). (in Russian) 
  103. [103] M. Slater, Lagrange Multipliers Revisited, Cowles Commission Discussion Paper, No. 403. 
  104. [104] G. Stampacchia, Formes bilineares coercives sur les ensembles convexes, Comptes Rendus Acad. Sciences Paris 258 (1964) 4413-4416. Zbl0124.06401
  105. [105] G.J. Stiegler, Journal Econometrica (1949). 
  106. [106] R. Tichatschke, Proximal Point Methods for Variational Problems (2011), http://www.math.uni-trier.de/~tichatschke/monograph.de.html 
  107. [107] A.N. Tikhonov, Improper problems of optimal planning and stable methods of their solution, Soviet Math. Doklady 6 (1965) 1264-1267 (in Russian). Zbl0141.17301
  108. [108] A.N. Tikhonov, Methods for the regularization of optimal control problems, Soviet Math. Doklady 6 (1965) 761-763 (in Russian). Zbl0144.12704
  109. [109] A.N. Tikhonov, On the stability of the functional optimization problems, J. Num. Mat. i Mat. Fis. 6 (1966) 631-634 (in Russian). 
  110. [110] G. Tintner, Stochastic linear programming with applications to agricultural economics, 2nd Symp. Linear programming 2 (1955) 197-228. 
  111. [111] E.S. Ventzel, Elements of Game Theory (Fizmatgis, Moscow, 1959). (in Russian) 
  112. [112] N.N. Vorobyev, Finite non-coallition games, Uspekhi Matem. Nauk 14 (1959) 21-56. (in Russian) 
  113. [113] D.B. Yudin and E.G. Golstein, Problems and Methods of Linear Programming (Sov. Radio, Moscow, 1961). (in Russian) 
  114. [114] D.B. Yudin and A.S. Nemirovskij, Complexity of Problems and Efficiency of Optimization Methods (Nauka, Moscow, 1979). (in Russian) Zbl0501.90061
  115. [115] A.P. Yushkevich, Histrory of Mathematics in Russia before 1917 (Nauka Moscow, 1968). (in Russian) 
  116. [116] S.I. Zukhovitskij, On the approximation of real functions in the sense of P.L. Chebyshev, Uspekhi Matem. Nauk 11 (1956) 125-159. (in Russian) 

NotesEmbed ?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.