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
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 also J.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 as
T.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 L. Walras
and A. 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 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.
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é (1946) 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
More links