Osion kuvaus

  • History of optimization (in Finnish)

    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 jaJacobi
    • 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ä


◄ Previous section
History of optimization
Next section ►
Background in optimization (in Finnish)