Kurs: MS-E2148 - Dynamic optimization, 16.01.2019-09.04.2019, Sektion: Background in optimization (in Finnish)

Översikt

Background in optimization (in Finnish)

Mitä on optimointi?

Optimointimalli koostuu päätösvaihtoehdoista, näitä koskevista rajoituksista ja optimoitavasta kohdefunktiosta. Päätösvaihtoehdot x₁,...,x_n 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ö:

Optimointitehtävien luokittelu
Optimointimallin muodostaminen
Optimointitehtävien ratkaiseminen ja ohjelmistot
Visualisointeja ja demonstraatioita
Kirjallisuus
Tieteellisiä seuroja ja lehtiä
Muita optimointikursseja
Muita linkkilistoja

1. Optimointitehtävien luokittelu

Lineaarinen tehtävä (Lineaarinen optimointi; MS-E2140)
- Kohdefunktio ja rajoitukset lineaarisia
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.
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.
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.
Kokonaislukutehtävä (Kokonaislukuoptimointi; MS-E2146)
- x_i:t kuuluvat kokonaislukuihin
- Jos tehtävässä on sekä kokonaisluku-, että reaalilukumuuttujia, niin kyseessä on sekalukutehtävä.
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
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.
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ä
- Konveksisuudesta
  - CCA, laskennallisen konveksin analyysin projekti
  - Konveksin analyysin perusteita taloustieteilijöille
- LP-tehtävistä
- Globaali optimointi; MS-E2191
- FAQ-listoja
  - Lineaarinen ja epälineaarinen ohjelmointi
- Ohjelmistoja
  - Vinkkejä
  - 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
TKK:n kirjaston elektroniset lehtitietokannat
Optimointilehtiä
OR-lehtiä

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

MS-E2148 - Dynamic optimization, 16.01.2019-09.04.2019

Översikt

Background in optimization (in Finnish)

Students

Teachers

Service