Osion kuvaus

• History of optimization
  (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
  
  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 considered
  
  
  • 1687 Newton studies the body of minimal resistance
  • 1696 Johann and Jacob Bernoulli study Brachistochrone's problem (see.iagsoft's Java-applet), 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

  19th 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 LP-problem 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 Karush-Kuhn-Tucker 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 Viner-Wong envelope theorem
  • 1932 K. Menger pressents a general formulation of the travelling salesman problem
  • 1939 L.V. Kantorovich presents LP-model and an algorithm for solving it. In 1975 Kantorovich and T.C. Koopmans get the Nobel memorial price of economics for their contributions on LP-problem
  
  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.
  
  
  • 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 air-forces, presents the Simplex method for solving LP-problems, von Neumann establishes the theory of duality for LP-problems
  • 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

  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 quasi-Newton and conjugate gradient methods, are developed
  
  Optimal control theory begins to develop as a separate discipline from CoV. Space race gives additional boost for research in optimal control theory
  • 1954 IEEE Control Systems Society is founded
  • 1956 L.S. Pontryagin's research group presents maximum principle
  • 1957 R. Bellman presents the optimality principle

  1960s

  • 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 LP-problems 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

  
  More links
  
  

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