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

Rainer Tichatschke

Discussiones Mathematicae, Differential Inclusions, Control and Optimization, Tome 32 (2012), p. 5-44 / Harvested from The Polish Digital Mathematics Library

Résumé

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.

Détail

Publié le : 2012-01-01

Zbl 1297.90001

EUDML-ID : urn:eudml:doc:270526

Bibliographie

[000] [1] N.I. Akhiezer, The Classical Problem of Moments (Fizmatgiz, Moscow, 1961). (in Russian) | Zbl 0124.06202

[001] [2] C. Baiocchi and A. Capelo, Variational and Quasi-Variational Inequalities: Applications to Free Boundary Problems (J. Wiley & Sons, Chichester, 1984).

[002] [3] A.V. Balakrishnan, Optimal control problems in Banach spaces, J. Soc. Ind. Appl. Math., Ser. A, Control 3 (1965) 152-180. | Zbl 0178.44601

[003] [4] E.M.L. Beale, The use of quadratic programming in stochastic linear programming, RAND Report P-2404 (RAND Corporation, 1961).

[004] [5] J.F. Benders, Partitioning procedures for solving mixed-variables programming problems, Numer. Math. 4 (1962) 238-252. doi: 10.1007/BF01386316 | Zbl 0109.38302

[005] [6] R. Bellman, Dynamic Programming (Princeton Univ. Press, Princeton, 1957).

[006] [7] L.D. Berkovitz, An existence theorem for optimal control, JOTA 4 (1969) 77-86. doi: 10.1007/BF00927413 | Zbl 0167.39201

[007] [8] V.G. Boltyanskij, Method of tents in the theory of extremum problems, Uspekhi Matem. Nauk 30 (1975) 3-55. (in Russian) | Zbl 0318.49017

[008] [9] V.G Boltyanskij, Mathematische Methoden der optimalen Steuerung (Akad. Verlagsgesellschaft Geest & Portig, Leipzig, 1971).

[009] [10] V.G. Boltyanskij, Optimale Steuerung diskreter Systeme (Akad. Verlagsgesellschaft Geest & Portig, Leipzig, 1976).

[010] [11] O. Bolza, Über Variationsprobleme mit Ungleichungen als Nebenbedingungen, Math. Abhandlungen 1 (1914) 1-18. | Zbl 45.0606.01

[011] [12] A.G. Butkovskij, Distributed Control Systems (Isd. Nauka, Moscow, 1969). (in Russian) | Zbl 0206.15004

[012] [13] C. Carathéodory, Calculus of Variations and Partial Differential Equations of the First Order (New York, Chelsea Publishing Co., 1982).

[013] [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 | Zbl 0064.39601

[014] [15] A. Charnes and W.W. Cooper, Chance-constrained programming, Management Sci. 5 (1959) 73-79. | Zbl 0995.90600

[015] [16] F.H. Clarke, Optimization and Nonsmooth Analysis (Wiley, New York, 1983). | Zbl 0582.49001

[016] [17] F.H. Clarke, V.F. Demynov and F. Gianessi, Nonsmooth Optimization and Related Topics (Plenum Press, New York, 1989).

[017] [18] G.B. Dantzig, Linear Programming and Extensions (Princeton, 1963).

[018] [19] G.B. Dantzig, Linear Inequalities and Related Systems (Princeton Univ. Press, Princeton, 1966).

[019] [20] G.B. Dantzig, Lectures in Differential Equations (Van Nostrand, Reinhold Co., New York, 1969).

[020] [21] G.B. Dantzig, Linear programming under uncertainty, Management Sci. 1 (1955) 197-206. doi: 10.1287/mnsc.1.3-4.197 | Zbl 0995.90589

[021] [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).

[022] [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

[023] [24] W.C. Davidon, Variable Metric Methods for Minimization, A.E.C. Res. and Develop. Report ANL-5990 (Argonne National Laboratory, Illinois, 1959).

[024] [25] V.F. Demyanov and A.M. Rubinov, Approximate Methods for Solving Extremum Problems (Leningrad State Univ., Leningrad, 1968). (in Russian)

[025] [26] V.F. Demyanov and V.N. Malozemov, Introduction to Minimax (Nauka, Moscow, 1972). (in Russian)

[026] [27] V.F. Demyanov and L.V. Vasiliev, Nondifferentiable Optimization (Nauka, Moscow, 1981). (in Russian)

[027] [28] V.F. Demyanov and A.M. Rubinov, Fundations of Nonsmooth Analysis and Quasidifferential Calculus (Nauka, Moscow, 1990). (in Russian)

[028] [29] J. Dennis and R. Schnabel, Numerical Methods for Unconstrained Optimization and Nonlinear Equations (Prentice-Hall, Englewood Cliffs, 1983). | Zbl 0579.65058

[029] [30] I. Dikin, An iterative solution of problems of linear and quadratic programming, Doklady AN SSSR 174 (1967) 747-748. (in Russian) | Zbl 0189.19504

[030] [31] A.Ya. Dubovitskij and A.A. Milyutin, Extremum problems under constraints, Doklady AN SSSR 149 (1963) 759-762. (in Russian)

[031] [32] Y.M. Ermoliev, Stochastic Programming Methods (Nauka, Moscow, 1976). (in Russian)

[032] [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. | Zbl 0788.01072

[033] [34] J. Farkas, Theorie der einfachen Ungleichungen, Journal für die Reine und Angewandte Mathematik 124 (1902) 1-27. | Zbl 32.0169.02

[034] [35] A.V. Fiacco and G.P. McCormick, Nonlinear Programming: Sequential Unconstrained Minimization Techniques (Wiley, 1968).

[035] [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 | Zbl 0132.11701

[036] [37] L.R. Ford and D.R. Fulkerson, Flows in Networks (Princeton Univ. Press, Princeton, 1962). | Zbl 0106.34802

[037] [38] J.B. Fourier, Analyse des Équations Déterminées (Navier, Paris, 1831).

[038] [39] L. Garding, The Dirichlet problem, Math. Intelligencer 2 (1979) 42-52. doi: 10.1007/BF03024386

[039] [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). | Zbl 1060.90001

[040] [41] R. Glowinski, J.L. Lions and R. Trémolières, Numerical Analysis of Variational Inequalities (North-Holland, Amsterdam, 1981).

[041] [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 | Zbl 0185.42602

[042] [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. | Zbl 0072.37601

[043] [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 | Zbl 0085.35807

[044] [45] H. Halkin, A maximum principle of Pontryagin, SIAM J. Control 4 (1966) 90-112. doi: 10.1137/0304009

[045] [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 | Zbl 0048.09901

[046] [47] M.R. Hestenes, Calculus of Variational and Optimal Control Theory (Wiley, New York, 1966).

[047] [48] A.D. Ioffe and V.M. Tikhomirov, Theory of Extremum Problems (Nauka, Moscow, 1974). (in Russian) | Zbl 0191.13101

[048] [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).

[049] [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.

[050] [51] P. Kall, Stochastic Linear Programming (Springer Verlag, Berlin, 1976). doi: 10.1007/978-3-642-66252-2

[051] [52] L.V. Kantorovich, Mathematical Methods for Production Organization and Planning (Leningrad, 1939). (in Russian)

[052] [53] L.V. Kantorovich, On an efficient method for solving some classes of extremum problems, Doklady AN SSSR 28 (1940) 212-215. (in Russian)

[053] [54] L.V. Kantorovich, Fuctional analysis and applied mathematics, Uspekhi Matem. Nauk 6 (1948) 89-185. (in Russian) | Zbl 0034.21203

[054] [55] L.V. Kantorovich, Functional Analysis (Nauka, Moscow, 1959). (in Russian) | Zbl 0127.06102

[055] [56] L.V. Kantorovich, Economical Calculation of the Best Utilization of Ressources (Moscow, Academy of Sciences, 1960). (in Russian)

[056] [57] L.V. Kantorovich, The Best Use of Economic Resources (Harvard U. Press, Cambridge, 1965).

[057] [58] N. Karmarkar, A new polynomial time algorithm for linear programming, Combinatorica 4 (1984) 373-395. doi: 10.1007/BF02579150 | Zbl 0557.90065

[058] [59] W. Karush, Minima of functions of several variables with inequalities as side conditions, MSc Thesis (Univ. of Chicago, 1939).

[059] [60] L. Khachiyan, A polynomial algorithm in linear programming, Doklady AN SSSR 244 (1979) 1093-1096. (in Russian) | Zbl 0414.90086

[060] [61] D. Kinderlehrer and G. Stampacchia, An Introduction to Variational Inequalities and their Applications (Acad. Press, New York-London, 1980). | Zbl 0457.35001

[061] [62] K. Kiwiel, Proximal level bundle methods for convex nondifferentiable optimization, saddle point problems and variational inequalities, Math. Programming 69 (B) (1995) 89-109. | Zbl 0857.90101

[062] [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. | Zbl 0297.90047

[063] [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).

[064] [65] T.C. Koopmans, Activity Analysis of Production and Allocation (Wiley, New York, 1951). | Zbl 0045.09503

[065] [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.

[066] [67] M.G. Krein and A.A. Nudelman, Markov's Problem of Moments and Extremum Problems (Nauka, Moscow, 1973). (in Russian)

[067] [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.

[068] [69] H.W. Kuhn and A.W. Tucker, Linear and nonlinear programming, Per. Res. 5 (1957) 244-257.

[069] [70] J.L. Lagrange, Théorie des Fonctions Analytiques (Journal de l'École Polytechnique, 1797).

[070] [71] J.L. Lagrange, Mécanique Analytique (Journal de l'École Polytechnique, 1788).

[071] [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 | Zbl 0825.90785

[072] [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). | Zbl 0745.00069

[073] [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.

[074] [75] J.K. Lenstra, A.H.G. Rinnooy Kan and A. Schrijver, History of Mathematikal Programming (CWI North-Holland, 1991).

[075] [76] K. Levenberg, A method for the solution of certain nonlinear problems in least squares, Quarterly of Applied Mathem. 2 (1944) 164-168. | Zbl 0063.03501

[076] [77] E.S. Levitin and B.T. Polyak, Minimization methods under constraints, Zhurn. Vychisl. Matem. i Matem. Fiz. 6 (1966) 787-823. (in Russian) | Zbl 0184.38902

[077] [78] J.L. Lions and G. Stampacchia, Variational inequalities, Comm. Pure Appl. Math. 20 (1967) 493-519. doi: 10.1002/cpa.3160200302 | Zbl 0152.34601

[078] [79] O.G. Mancino and G. Stampacchia, Convex programming and variational inequalities, JOTA 9 (1972) 3-23. doi: 10.1007/BF00932801 | Zbl 0213.45202

[079] [80] B. Martinet, Régularisation d'inéquations variationelles par approximations successives, RIRO 4 (1970) 154-159.

[080] [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. | Zbl 28.0427.01

[081] [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.

[082] [83] J.J. Moreau, Proximité et dualité dans un espace Hilbertien, Bull. Soc. Math. France 93 (1965) 273-299. | Zbl 0136.12101

[083] [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

[084] [85] J.v. Neumann, Zur Theorie der Gesellschaftsspiele, Math. Ann. 100 (1928) 295-320. doi: 10.1007/BF01448847

[085] [86] J.v. Neumann and O. Morgenstern, The Theory of Games and Economic Behavior (Springer, New York, 1944). | Zbl 0063.05930

[086] [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

[087] [88] M. Padberg, Linear Optimization and Extensions (Springer, 1961).

[088] [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

[089] [90] B.T. Polyak, History of mathematical programming in the USSR, Math. Programming (B) 91 (2002) 401-416. doi: 10.1007/s101070100258 | Zbl 1030.90001

[090] [91] L.S. Pontryagin, V.G. Boltyanski and R.V. Gamkrelidse, Mathematical Theory of Optimal Processes (Nauka, Moscow, 1956). (in Russian)

[091] [92] M. Powell, A method for nonlinear constrainets in minimization problems, in: Fletcher, R. (ed.): Optimization (Acad. Press, New York, 1969) 283-298.

[092] [93] B.N. Pshenichnyj, Necessary Conditions for Extrema (Nauka, Moscow, 1969). (in Russian)

[093] [94] B.N. Pshenichnyj, Convex Analysis and Extremum Problems (Nauka, Moscow, 1980). (in Russian)

[094] [95] C.J. Poussin, Sure la méthode de l'approximation minimum, Anales de la Societe Scientifique de Bruxelles 35 (1911) 1-16.

[095] [96] E.Ya. Remez, Foundations of Numerical Methods for Chebyshev Approximation (Naukova Dumka, Kiew, 1969). (in Russian)

[096] [97] R.T. Rockafellar, Convex Analysis (Princeton University Press, 1972). | Zbl 0224.49003

[097] [98] R.T. Rockafellar, Monotone operators and the proximal point algorithm, SIAM J. Control Optim. 14 (1976) 877-898. doi: 10.1137/0314056 | Zbl 0358.90053

[098] [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 | Zbl 0364.34022

[099] [100] E. Roxin, The existence of optimal control, Michigan Math. J. 9 (1962) 109-119. doi: 10.1307/mmj/1028998668

[100] [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 | Zbl 0761.90090

[101] [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)

[102] [103] M. Slater, Lagrange Multipliers Revisited, Cowles Commission Discussion Paper, No. 403.

[103] [104] G. Stampacchia, Formes bilineares coercives sur les ensembles convexes, Comptes Rendus Acad. Sciences Paris 258 (1964) 4413-4416. | Zbl 0124.06401

[104] [105] G.J. Stiegler, Journal Econometrica (1949).

[105] [106] R. Tichatschke, Proximal Point Methods for Variational Problems (2011), http://www.math.uni-trier.de/~tichatschke/monograph.de.html

[106] [107] A.N. Tikhonov, Improper problems of optimal planning and stable methods of their solution, Soviet Math. Doklady 6 (1965) 1264-1267 (in Russian). | Zbl 0141.17301

[107] [108] A.N. Tikhonov, Methods for the regularization of optimal control problems, Soviet Math. Doklady 6 (1965) 761-763 (in Russian). | Zbl 0144.12704

[108] [109] A.N. Tikhonov, On the stability of the functional optimization problems, J. Num. Mat. i Mat. Fis. 6 (1966) 631-634 (in Russian).

[109] [110] G. Tintner, Stochastic linear programming with applications to agricultural economics, 2nd Symp. Linear programming 2 (1955) 197-228.

[110] [111] E.S. Ventzel, Elements of Game Theory (Fizmatgis, Moscow, 1959). (in Russian)

[111] [112] N.N. Vorobyev, Finite non-coallition games, Uspekhi Matem. Nauk 14 (1959) 21-56. (in Russian)

[112] [113] D.B. Yudin and E.G. Golstein, Problems and Methods of Linear Programming (Sov. Radio, Moscow, 1961). (in Russian)

[113] [114] D.B. Yudin and A.S. Nemirovskij, Complexity of Problems and Efficiency of Optimization Methods (Nauka, Moscow, 1979). (in Russian) | Zbl 0501.90061

[114] [115] A.P. Yushkevich, Histrory of Mathematics in Russia before 1917 (Nauka Moscow, 1968). (in Russian)

[115] [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)