History of Optimization

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

19th century

20th century
CoV is further developed, e.g., by O. Bolza, C. Caratheodory and G.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 with operations 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

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