Optimoinnin historiaa
Antiikki
Kreikkalaiset matemaatikot kiinnostuvat geometriasta ja ratkovat myös
muutamia geometrisia optimointitehtäviä
-
300 eaa
Eukleides tarkastelee pisteen etäisyyttä suoraan ja osoittaa myös, että
neliö on suurin niistä suorakulmioista, joiden yhteenlaskettu
särmien pituus on kiinnitetty (kts. todistus)
-
200 eaa Zenodorus
tutkii (Pappuksen & Theonin mukaan) Didon ongelmaa, jota on kuvattu myös Virgilin aeneidissa 19 eaa
-
100 eaa Heron
osoittaa Catopricassa, että valo kulkee lyhintä polkua kahden pisteen välillä heijastuessaan peilistä
Uusi aika
Ennen variaatiolaskennan syntyä tutkitaan joitakin yksittäisiä optimointitehtäviä
-
1615 Kepler
pohtii optimaalista viinitynnyriä
-
1638
Galileo
Galilei yrittää ratkaista miten riippuva ketju asettuu mutta epäonnistuu
-
1646 Fermat esittää, että funktion ääriarvoa tulee etsiä gradientin nollakohdasta. Vuonna 1657 Fermat osoittaa, että valo kulkee matkan kahden pisteen välillä minimiajassa
Newton (1660-luvulla) ja Leibniz (1670 luvulla) kehittävät analyysin,
joka on variaatiolaskennan perustana.
Myös yksittäisiä äärellisiä
optimointiongelmia tutkitaan
-
1687 Newton tutkii minkä muotoisella kappaleella on pienin
vastus väliaineessa (lisätietoa)
-
1696
Johann
ja Jacob
Bernoulli tutkivat
Brakistokronen
ongelmaa (kts. iagsoftin Java-animaatio), variaatiolaskenta syntyy
-
1712 Samuel König osoittaa, että mehiläiskennon
muoto on optimaalinen (lisätietoa). Ranskan tiedeakatemia julistaa, että kyseessä on jumalan johdatus
-
1740 Eulerin julkaisu aloittaa variaatiolaskennan yleiseen teoriaan
tähtäävän tutkimuksen
-
1754
Lagrange tekee ensimmäiset löytönsä variaatiolaskennassa 19 vuotiaana
Ensimmäiset
optimointialgoritmit kehitetään 1800-luvulla.
Variaatiolaskentaa
tutkivat mm. Weierstrass,
Steiner,
Hamilton ja
Jacobi
-
1806
Legendre
esittää pienimmän neliösumman menetelmän, jonka myös Gauss
väittää keksineensä. Legendre vaikutti myös variaatiolaskennan alalla
-
1826 Fourier muotoilee LP-tehtävän mekaniikan ja todennäköisyyslaskun ongelmiin
-
1847
Cauchy esittää gradienttimenetelmän
-
1857
Gibbs osoittaa, että kemiallinen tasapaino on energiaminimi
Moderni aika
Variaatiolaskenta kehittyy, mm Bolza,
Caratheodory ja
Bliss
tutkivat variaatiolaskentaa 1900-luvun alussa.
Optimoinnin kannalta keskeiset konveksisuuskäsitteet luodaan: konveksi funktio Jensen 1905,
konveksi joukko
Minkowski 1911
-
1917 Harris Hancock julkaisee ensimmäisen optimoinnin oppikirjan, Theory of Minima and Maxima
-
1917 biomatemaatikko D'Arcy Thompson julkaisee kirjan On Growth and Form, jossa hän
soveltaa optimointia eliöiden muotojen analysointiin
-
1939 Kantorovitsh esittää LP-mallin ja algoritmin LP-tehtävän
ratkaisemiseksi. Vuonna 1975 Kantorovitsh ja Koopmans saavat taloustieteen Nobelin LP-tehtävän tutkimisesta
Toisen maailmansodan jälkeen optimointia aletaan
ensimmäisenä soveltaa operaatiotutkimuksessa ja taloustieteessä.
Elektronisen laskennan kehittyessä
optimointialgoritmien tutkimus laajenee.
Von
Neumann on tärkeä taustavaikuttaja optimoinnin kehittymisessä
-
1947
USA:n ilmavoimille työskentelevä
Dantzig
esittää Simplex-menetelmän LP-tehtävän ratkaisemiseksi
- 1949 järjestetään Chicagosssa alan ensimmäinen kansainvälinen kokous International Symposium on Mathematical Programming, jossa esitetään 34 julkaisua
1950-luku
-
1951 Kuhn ja Tucker esittävät optimaalisuusehdot ehdot
epälineaariselle tehtävälle. John vuonna 1948 ja Karush vuonna 1939
ovat löytäneet samaiset ehdot
-
dynaaminen optimointi kehittyy Pontrjaginin
tutkimusryhmän ja Bellmanin ansiosta.
Optimisäätöteoria alkaa kehittyä omaksi alakseen variaatiolaskennasta
- Fordin ja Fulkersonin tutkimus verkkotehtävistä 1954 aloittaa kombinatorisen optimoinnin yleisemmän tutkimuksen
-
rajoittamattoman optimoinnin algoritmit, kuten kvasi-Newton ja
konjugaattigradienttimenetelmät, alkavat kehittyä
1960-luku
-
Zoutendijk esittää käypien suuntien menetelmät (1960) pyrkimyksenään
yleistää simplex epälineaarisille tehtäville. Samantyyppisiä algoritmeja kehittelevät myös Rosen, Wolfe ja Powell
-
SQP keksitään ensimmäisen kerran (Wilson 1963) ja uudemman kerran sen
löytävät Han 1975 ja Powell 1977
1970-
-
Mathematical Programming
Society perustetaan 1973
-
Karmarkarin 1984 esittämä polynomiaikainen menetelmä LP-tehtävälle
nostaa sisäpistemenetelmät suosioon.
Ensimmäinen polynomiaikainen menetelmä LP-tehtävälle löydettiin jo
aikaisemmmin (ellipsoidimenetelmä, Hatshian
1979).
Taustalla on laskennan kompleksisuusanalyysin
kehittyminen 60- ja 70-luvuilla
-
80-luvulla aletaan kehitellä heuristiikkoja hankaliin
optimointitehtäviin
- 90-luvulla sisäpistemenetelmien käyttö yleistyy semidefiniittiin optimointiin
Linkkejä