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

Tichatschke, Rainer

Discussiones Mathematicae. Differential Inclusions, Control and Optimization, Tome 32 (2012) no. 1, pp. 5-44.

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:

Détail

Keywords: history, mathematical programming

Bibliographie

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

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

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

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

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

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

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

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

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

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

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

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

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

[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

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

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

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

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

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

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

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

[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] 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] W.C. Davidon, Variable Metric Methods for Minimization, A.E.C. Res. and Develop. Report ANL-5990 (Argonne National Laboratory, Illinois, 1959).

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

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

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

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

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

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

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

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

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

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

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

[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

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

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

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

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

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

[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

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

[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

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

[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

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

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

[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] 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] P. Kall, Stochastic Linear Programming (Springer Verlag, Berlin, 1976). doi: 10.1007/978-3-642-66252-2

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

[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] L.V. Kantorovich, Fuctional analysis and applied mathematics, Uspekhi Matem. Nauk 6 (1948) 89-185. (in Russian)

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

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

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

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

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

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

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

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

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

[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] T.C. Koopmans, Activity Analysis of Production and Allocation (Wiley, New York, 1951).

[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] M.G. Krein and A.A. Nudelman, Markov's Problem of Moments and Extremum Problems (Nauka, Moscow, 1973). (in Russian)

[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] H.W. Kuhn and A.W. Tucker, Linear and nonlinear programming, Per. Res. 5 (1957) 244-257.

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

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

[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

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

[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] J.K. Lenstra, A.H.G. Rinnooy Kan and A. Schrijver, History of Mathematikal Programming (CWI North-Holland, 1991).

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

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

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

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

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

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

[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] J.J. Moreau, Proximité et dualité dans un espace Hilbertien, Bull. Soc. Math. France 93 (1965) 273-299.

[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] J.v. Neumann, Zur Theorie der Gesellschaftsspiele, Math. Ann. 100 (1928) 295-320. doi: 10.1007/BF01448847

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

[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] M. Padberg, Linear Optimization and Extensions (Springer, 1961).

[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] B.T. Polyak, History of mathematical programming in the USSR, Math. Programming (B) 91 (2002) 401-416. doi: 10.1007/s101070100258

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

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

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

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

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

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

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

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

[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

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

[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

[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] M. Slater, Lagrange Multipliers Revisited, Cowles Commission Discussion Paper, No. 403.

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

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

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

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

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

[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] G. Tintner, Stochastic linear programming with applications to agricultural economics, 2nd Symp. Linear programming 2 (1955) 197-228.

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

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

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

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

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

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