MSE2148  Dynamic optimization, 16.01.201909.04.2019
This course space end date is set to 09.04.2019 Search Courses: MSE2148
Topic outline

(The English version is from http://www.mitrikitti.fi/opthist.html )
Lines of development, breakthroughs, applications and curiosities, and links
Antiquity
 Greek mathematicians solve some optimization problems that are related to their geometrical studies.
 300 bc Euclid considers the minimal distance between a point a line, and proves that a square has the greatest area among the rectangles with given total length of edges
 200 bc Zenodorus studies (according to Pappus & Theon) Dido's Problem that has been described in Virgil's Aeneid 19 bc
 100 bc Heron proves in Catoprica that light travels between two points through the path with shortest length when reflecting from a mirror
17th and 18th centuries
 Before the invention of calculus of variations only some separate optimization problems are being investigated.
 1615 J. Kepler figures out the optimal dimensions of wine barrel. He also formulated an early version of the secretary problem (a classical application of dynamic programming) when he started to look for a new wife
 1638 G. Galilei tries to figure out the shape of a hanging chain, but he fails
 1646 P. de Fermat shows that at the extreme point the gradient of a function vanishes. In 1657 Fermat shows that light travels between two points in minimal time
 1687 Newton studies the body of minimal resistance
 1696 Johann and Jacob Bernoulli study Brachistochrone's problem (see.iagsoft's Javaapplet), calculus of variations is born
 1712 J.S. König shows that the shape of honeycomb is optimal. The French Academy of Sciences declares the phenomenom as divine guidance
 1740 L. Euler's publication begins the research on general theory of calculus of variations
 1746 P.L.M. de Maupertuis formulates the principle of least action to explain physical phenomena
 1754 J.L. Lagrange makes his first findings within CoV at the age 19.In 1760 he formulates the Plateau's problem, the problem of minimal surfaces. In 1936 J. Douglas received a Fields Medal for his solution to the problem, in 1974 E. Bombieri received Fields Medal for his work on the topic
 1784 G. Monge investigates a combinatorial optimization problem known as the transportation problem
I. Newton (1660s) and G. W. von Leibniz (1670s) create mathematical analysis that forms the basis of calculus of variations (CoV). Some separate finite optimization problems are also considered19th century
 The first optimization algorithms are presented. K.T.W. Weierstrass,J. Steiner, W.R. Hamilton and C.G.J. Jacobi further develop CoV.
 1806 A.M. Legendre presents the least square method, which alsoJ.C.F. Gauss claims to have invented. Legendre made contributions in the field of CoV, too
 1815 The idea of a (quasi) concave function appears in economics asT.R. Malthus, R. Torrens, E. West, and D. Ricardo simultaneously introduce "the Law of Dimishing Returns" for production functions
 1826 J.B.J. Fourier formulates LPproblem for solving problems arising in mechanics and probability theory
 1846 M. Faustmann presents the formula for the present value of the income stream of forest rotation, the solution for the problem of maximizing Faustmann's formula was solved by B. Ohlin 1924 although some foresters were already aware of the correct solution in 1860's
 1847 A.L. Cauchy presents the gradient method
 1857 J.W. Gibbs shows that chemical equilibrium is an energy minimum
The marginalist revolution in economics during 1870s, e.g., the works of Walras and Cournot shifts the focus of economists to utility maximizing individuals  optimization becomes an integral part of economic theory.20th century
 CoV is further developed, e.g., by O. Bolza, C. Caratheodory andG.A. Bliss.
 1902 J. Farkas prsents his famous lemma which can be used in the proof of KarushKuhnTucker theorem
 Convexity concepts are created: J.L.W.V. Jensen introduces convex functions in 1905, the idea has already appeared in the works of J.S. Hadamard (1883), O.L. Hölder (1889), and O. Stolz (1893). H. Minkowski obtains the first results on convex sets in 1911, the earliest study on convex geometry was published by H. Brunn in 1887
 1917 H. Hancock publishes the first text book on optimization, Theory of Minima and Maxima
 1917 biomathematician D.W. Thompson writes the book On Growth and Form, in which he applies optimization to analyze the forms of living organisms
 1925 H.C.M. Morse presents his theory that generalizes CoV
 1928 F.P.P Ramsey applies CoV in his study on optimal economic growth, Ramsey's exercise is resurrected in 50's as the field of optimal growth theory starts to develop
 1931 J. Viner presents the VinerWong envelope theorem
 1932 K. Menger pressents a general formulation of the travelling salesman problem
 1939 L.V. Kantorovich presents LPmodel and an algorithm for solving it. In 1975 Kantorovich and T.C. Koopmans get the Nobel memorial price of economics for their contributions on LPproblem
 1944 J. von Neuman and O. Morgenstern solve sequential decision problems by using the idea of dynamic programming. A. Wald (1947) did related research. Another early application of DP is presented by P. Massé (1944) for reservoir management
 1947 G. Dantzig, who works for US airforces, presents the Simplex method for solving LPproblems, von Neumann establishes the theory of duality for LPproblems
 1949 the first international congress, International Symposium on Mathematical Programming, on optimization is held in Chicago. The number of papers presented in the congress is 34
After the world war II optimization develops simultaneously withoperations research. J. Von Neumann is an important person behind the development of operations research. The field of algorithmic research expands as electronic calculation develops.1950s
 1951 H.W. Kuhn and A.W. Tucker reinvent optimality conditions for nonlinear problems. F. John in 1948 and W. Karush in 1939 had presented similar conditions earlier
 1951 H. Markowitz presents his portfolio theory that is based on quadratic optimization. In 1990 Markowitz receives the Nobel memorial prize in economics
 1954 L.R. Ford's and D.R. Fulkerson's research on network problems is a starting point of research on combinatorial optimization
 Algorithms for unbounded problems, such as quasiNewton and conjugate gradient methods, are developed
 1954 IEEE Control Systems Society is founded
 1956 L.S. Pontryagin's research group presents maximum principle
 1957 R. Bellman presents the optimality principle
Optimal control theory begins to develop as a separate discipline from CoV. Space race gives additional boost for research in optimal control theory1960s
 Zoutendijk (1960) presents the methods of feasible directions to generalize the Simplex method for nonlinear programs. Rosen, Wolfe, and Powell develop similar ideas
 Sequential quadratic programming method is invented for the first time by Wilson 1963. Han 1975 and Powell 1977 present it anew
1970s
 1973 Mathematical Programming Society is founded
 1984 N. Karmarkar's polynomial time algorithm for LPproblems begins a boom of interior point methods.
The first polynomial time algorithm for LP, the ellipsoid method, was already presented by Khachiyan in 1979.
The complexity analysis developed in 60s and 70s begins to influence to the theory of optimization  80s as computers become more efficient, heuristic algorithms for global optimization and large scale problems begin to gain popularity
 90s the use of interior point methods expands to semidefinite optimization
 MacTutor history of mathematics
 History of mathematical symbols and terms (J. Miller)
 History of economics (The New School University)
 History of game theory (P. Walker)
 IEEE history pages
 Historia Mathematica journal
 Euclid's elements
 Wolfram's Mathworld
 Mathematical programming glossary (INFORMS)
 Von Neumann prize winners (INFORMS)
 Brief hostory of feedback control (F.L. Lewis)