MS-E2148 - Dynamic optimization, 16.01.2019-09.04.2019

Topic outline

• Background in optimization (in Finnish)
  Mitä on optimointi?

  Optimointimalli koostuu päätösvaihtoehdoista, näitä koskevista rajoituksista ja optimoitavasta kohdefunktiosta. Päätösvaihtoehdot x1,...,xn saavat joko reaaliluku- tai kokonaislukuarvoja. Dynaamisessa optimoinnissa päätösvaihtoehdot ovat ajan, tai muun sopivan parametrin funktioita. Mallin ratkaisu antaa sen päätösvaihtoehdon arvon, joka optimoi (maksimoi tai minimoi) kohdefunktion arvon ja toteuttaa rajoitukset.

  Principia Cybernetica: Mitä on optimointi?  Optimointisanasto (englanniksi)

  Sisältö:

  1. Optimointitehtävien luokittelu
  2. Optimointimallin muodostaminen
  3. Optimointitehtävien ratkaiseminen ja ohjelmistot
  4. Visualisointeja ja demonstraatioita
  5. Kirjallisuus
  6. Tieteellisiä seuroja ja lehtiä
  7. Muita optimointikursseja
  8. Muita linkkilistoja

  
  1. Optimointitehtävien luokittelu

  1. Lineaarinen tehtävä (Lineaarinen optimointi; MS-E2140)
     • Kohdefunktio ja rajoitukset lineaarisia
       
  2. Epälineaarinen tehtävä (Epälineaarinen optimointi; MS-E2139)
     • Kohde- ja rajoitefunktiot epälineaarisia 
       
       
     • Epälineaarisen tehtävän erikoistapauksena on konveksi optimointitehtävä, jossa kohdefunktio f ja rajoitusfunktiot g_ikonvekseja ja h_i lineaarisia.
  3. Monitavoitetehtävä (Monitavoiteoptimointi; MS-E2144)
     • Monta kohdefunktiota
     • Esim. portfolion (arvopaperien) optimointi; katso myös MCS:nportfolioesimerkki.
       • Maksimoidaan hyödyn odotusarvoa E(c)^tx (lineaarinen tehtävä), missä c on satunnaismuuttuja ja E(c) sen odotusarvo.
       • Minimoidaan riskiä x^tVx (kvadraattinen tehtävä), missä V on c:n kovarianssimatriisi.
       • Halutaan siis sekä maksimoida hyötyä, että minimoida riskiä; päädytään monitavoitetehtävään.
       • Tehtävä on lisäksi stokastinen, ks. kohta 7.
  4. Verkkotehtävä (Verkko-optimointi; MS-E2143)
     • Tyypillisesti tehtävä on samaa muotoa kuin kohdassa 1
     • Lisäksi yleensä kokonaislukumuuttujia
     • Esim. Määrättävä kahden kaupungin välinen lyhin tie olemassaolevaan tieverkostoon.
  5. Kokonaislukutehtävä (Kokonaislukuoptimointi; MS-E2146)
     • x_i:t kuuluvat kokonaislukuihin
     • Jos tehtävässä on sekä kokonaisluku-, että reaalilukumuuttujia, niin kyseessä on sekalukutehtävä.
  6. Dynaaminen tehtävä (Dynaaminen optimointi; MS-E2148)
     • Esimerkki: Määrää L pituisen köyden x(s) rajoittama maksimipinta-ala s.e. köyden päät ovat pisteissä a ja b, x(a) = x(b) = 0. Tämä on Tyrian prinsessa Didon ongelma, jonka ratkaisu johti Karthagon perustamiseen. Tehtävä on muotoa
       
  7. Stokastinen tehtävä
     • Tehtävä sisältää satunnaismuuttujia
     • Tyypillisesti minimoidaan riskejä ja maksimoidaan hyödyn odotusarvoa; saadaan monitavoitetehtävä
       • Esim. portfolion (arvopaperien) optimointi
       • MCS:n portfolioesimerkki.
  8. Muita tehtäviä
     • Semidefiniitti ohjelmointi
     • Komplementaarisuusongelmat
     • Epäsileä ja aligradienttioptimointi

  2. Optimointimallin muodostaminen

  • Vuorovaikutteisesti OR-asiantuntijan (voi olla joukko asiantuntijoita) ja asiakkaan välillä. (OR = Operations Research = Operaatiotutkimus)
  • Mallinrakennuksen vaiheet (yleensäkin matemaattisessa mallintamisessa):
    1. Tehtävän määrittely
    2. Mallin muodostaminen
    3. Mallin ratkaiseminen
    4. Mallin validointi
    5. Ratkaisun käyttöönotto ja ylläpito
    Kohta 3 on ylläolevista suoraviivaisin koska se perustuu yleensä hyvin määriteltyyn matemaattiseen teoriaan. Optimointitehtävää määriteltäessä valitaan päätösmuuttujat, näitä koskevat rajoitukset ja optimoitava kohdefunktio. Mallin muodostaminen tarkoittaa edellä olevan pukemista matemattiselle kielelle. Mallin validointivaiheessa tutkitaan vastaako malli niihin kysymyksiin, joihin sen piti vastata. Ratkaisun käyttöönotto ja ylläpito pitää sisällään joukon yksinkertaisia toimintaohjeita mallin käyttäjille.

  
  3. Optimointitehtävien ratkaiseminen ja ohjelmistot

  • Optimointitehtävän ratkaiseminen tapahtuu numeerisesti iteroimalla
    x_k+1 = f(x_k,x_k-1,...), k=1,2,...
  • Esim. funktion g lokaali minimi löydetään Newtonin iteroinnilla
    x_k+1 = x_k - g^'(x_k)/g^''(x_k)
  • Vastaavaa ratkaisutekniikkaa kutsutaan yleensä ohjelmoinniksi. Siis esim. lineaarinen ohjelmointi, dynaaminen ohjelmointi, jne.
  • Teoriasta ja ratkaisumenetelmistä
    • Yleistä
      • Numeerisia reseptejä
      • Math Archives
      • Kompleksisuusanalyysistä
      • Operaatiotutkimuksesta
    • Konveksisuudesta
      • CCA, laskennallisen konveksin analyysin projekti
      • Konveksin analyysin perusteita taloustieteilijöille
    • LP-tehtävistä
      • Lineaaristen tehtävien ratkaiseminen
      • Sisäpistemenetelmiä lineaarisille tehtäville
      • Primaali-duaali sisäpistemenetelmiä lineaarisille tehtäville
      • Sisäpistemenetelmiä
    • Globaali optimointi; MS-E2191
      • Geneettisistä algoritmeista
      • Simuloidusta jäähdytyksestä
      • Klusterointimenetelmä
      • Heuristiikat
      • Menetelmiä, ohjelmistoja ja testiongelmia
      • Globaalien optimointimenetelmien vertailua
    • FAQ-listoja
      • Lineaarinen ja epälineaarinen ohjelmointi
    • Ohjelmistoja
      • Vinkkejä
        • NEOS optimointiohjelmisto-opas
        • LP ohjelmisto katsaus
        • Tutkimus viimeisimmistä trendeistä matemaattisessa ohjelmoinnissa
        • Päätöspuu optimointiohjelmistojen valitsemiseksi
        • Optimointi internetresurssina
      • Yleiskäyttöisiä ohjelmistoja
        • Excelin Solver
        • Optimointityökaluja Matlabiin
      • Epälineaarinen optimointi
        • FSQP, käypä toistettu neliöllinen optimointi
        • DONLP2
        • SUMT, toistettu rajoittamaton minimointitekniikka, klassikko
        • Lindo
      • Lineaarinen-, verkko- ja sekalukuoptimointi
        • GLPK - GNU:n paketti lineaaristen tehtävien ratkaisemiseen
        • Ilog Cplex
        • LP-Solve
        • RELAX IV
        • GIDEN - graafinen ympäristö verkkotehtävien optimointiin
        • Java-ohjelmia operaatiotutkimukseen ja WWW linkkejä
      • Dynaaminen optimointi
        • RIOTS: Matlab työkaluja optimiohjaustehtävien ratkaisemiseksi
        • DIRCOL ja PAREST
    • Mallinnuskieliä
      • GAMS (General Algebraic Modeling System; eräs vanhimmista)
      • AMPL (A Modeling Language for Mathematical Programming)
      • MPL (Mathematical Programming Language; uudehko, opiskelijaversio saatavilla www-sivuilta)
    • Johdantoa ohjelmistoihin
      • Janne Kettunen - Xpress
      • Janne Karelahti - Snopt

  
  4. Visualisointeja ja demonstraatioita

  • Lineaarisille tehtäville
    • Primaali-Duaali sisäpistemenetelmä LP-tehtävälle
    • Anima-LP
    • LP Explorer 1.0
  • Epälineaarisille tehtäville
    • Kvadraattiset funktiot
  • Geneettisille algoritmeille
  • Dynaamisille tehtäville
  • Erilaisten optimointitehtävien demonstraatioita ja visualisointeja
  • Konveksin kuoren laskeminen

  
  5. Kirjallisuus

  • Perusteoksia
    • H. A. Taha, Operations Research, An Introduction, Prentice-Hall International, Inc., 1997
    • D. P. Bertsekas, Network optimization, Athena Scientific, 1998
    • R. Fletcher, Practical Methods of Optimization, Wiley, 1995
    • R. J. Vanderbei, Linear Programming, Foundations and Extensions, Kluwer, 1996
    • D. Bertsimas, & J.N. Tsitsiklis, Introduction to Linear Optimization, Athena Scientific, 1997.
    • M. S. Bazaraa, H. D. Sherali, & C. M. Shetty, Nonlinear Programming: Theory and Algorithms, Wiley, 1993.
    • Chong, E., & Zak, S., An Introduction to Optimization, Wiley-interscience, 2nd edition, 2001 (90.48 EUR postikuluineen)
    • Haataja, Optimointitehtävien ratkaiseminen, CSC, 1996
    • D. G. Luenberger, Introduction to Linear and Nonlinear Programming, Addison-Wesley, 1984.
    • Mangasarian, Nonlinear Programming, McGraw-Hill, 1969.
    • Nash, S.G. & Sofer, A., Linear and Nonlinear Programming, McGraw-Hill, 1995 (110.57 EUR postikuluineen)
    • Winston W.L., Operations Research Applications and Algorithms, Duxbury Press, 3rd edition, 1997 (65.09 EUR postikuluineen)
  • Algoritmien "keittokirjoja"
    • R. Fletcher, Practical Methods of Optimization, Wiley, 1987.
    • D. P. Bertsekas, Nonlinear Programming, Aethena Scientific, 1995.
    • N. Drakos, Mathematical optimization, verkkojulkaisu, 1995.
  • Numeeriikkaa
    • P. E. Gill, W. Murray, and M. H. Wright, Practical Optimization, Academic Press, 1981.
    • P. E. Gill, W. Murray, and M. H. Wright, Numerical Methods for Linear Algebra and Optimization: Volume 1, Addison Wesley, 1991.
    • Haataja, Heikonen, Leino, Rahola, Ruokolainen ja Savolainen, Numeeriset menetelmät käytännössä, CSC - Tieteellinen laskenta Oy, 1999.
  • Konveksin analyysin raamattu
    • Rockafellar, Convex Analysis, Princeton, 1970.
  • Tehtävistä, joissa käypä alue on ei-konveksi
    • A. V. Fiacco and G. P. McCormick, Nonlinear Programming; Sequential Unconstrained Minimization Techniques, John Wiley, 1968.
  • Tehtävistä, joissa rajoite-ehdoissa on optimointitehtävä
    • J.F. Bard, Practical Bilevel Optimization, Kluwer Academic Publishers, 1999.
  • Epäsileästä optimoinnista
    • F.H. Clarke, Optimization and Nonsmooth Analysis, Classics in Applied Mathematics 5., Society for Industrial and Applied Mathematics, 1990.
  • Monitavoiteoptimointi
    • P.-L. Yu, Multiple-Criteria Decision Making: Concepts, Techniques, and Extensions, Plenum Press, 1985.
    • R.E. Steuer, Multiple Criteria Optimization: Theory, Computation and Application, John Wiley & Sons, 1986.
    • K. Miettinen, Nonlinear Multiobjective Optimization, Kluwer Academic Publishers, Boston, 1999
  • Heuristiset optimointimenetelmät
    • L. F. Landweber and E. Winfree, Evolution as Computation, Springer, 2002
    • R. L. Haupt and S. E. Haupt, Practical Genetic Algorithms, Wiley, 1998
    • N. Ansari and E. Hou, Computational Intelligence for Optimization, Kluwer, 1997
    • W. M. Spears, Evolutionary Algorithms, Springer, 2000
    • H. Dawid, Adaptive Learning by Genetic Algorithms, Springer, 1999
    • D. L. Kreher and D. R. Stinson, Combinatorial Algorithms, CRC, 1999
  • LP-mallien kirjallisuuskokoelma

  6. Tieteellisiä seuroja ja lehtiä

  • Seuroja
    • Mathematical Programming Society
    • SIAM Activity Group on Optimization
    • Suomen Operaatiotutkimusseura
    • IFORS
    • IEEE Control System Society
    • IEEE System, Man, and Cybernetics Society
    • The International Society of Dynamic Games
  • TKK:n kirjaston elektroniset lehtitietokannat
  • Optimointilehtiä
    • SIAM Journal on Optimization
    • Applied Mathematics & Optimization
    • Mathematical programming
    • Journal of Global Optimization
    • Journal of Optimization Theory and Applications
    • Computational Optimization
    • Optimization online
    • Journal of Convex Analysis
  • OR-lehtiä
    • Computers & Operations Research
    • European Journal of Operational Research
    • Operations Research Letters
    • Management Science
    • Mathematics of Operations Research
    • Operations Research
    • Mathematical Methods of Operations Research

  
  7. Muita optimointikursseja

  • Yleisiä
    • Cambridge, Englanti
    • Princetonin yliopisto, USA
    • Wisconsinin yliopisto, USA
    • Tampereen teknillinen korkeakoulu, Suomi
    • Linköpingin yliopisto, Ruotsi (på svenska)
    • Uppsalan yliopisto, Ruotsi
    • Uumajan yliopisto, Ruotsi (på svenska)
  • Epälineaarinen ohjelmointi
    • MIT, USA
    • Stanford, USA
    • New Yorkin yliopisto, USA
    • Illinois, USA
    • Jerusalemin hebrean kielinen yliopisto, Israel
  • Lineaarinen ohjelmointi
    • Denverin yliopisto, USA
  • Muita
    • Konvekseista joukoista, Moskovan riippumaton yliopisto, Venäjä (po russkij)
    • Geneettisistä algoritmeista, Lillen teknillinen korkeakoulu, Ranska (en français)
    • Verkkomallit, Helsingin Kauppakorkeakoulu
    • Diskreetti optimointi, Münchenin teknillinen korkeakoulu, Saksa (auf Deutsch)
    • Algoritmien suunnittelu ja analyysi, Teknillinen Korkeakoulu, Suomi

  
  8. Muita linkkilistoja

  • Kaisa Miettinen
  • Tom Cavalier