## Osion kuvaus

### Lecturer: Harri Ehtamo

##### Assistant: Anton von Schantz

NOTE!

The first lecture is on Wed 16.1.2019 14:15-16:00 in U5,

and the first exercise session on Tue 22.1.2019 14:15-16:00 in U7.

Exam times:

Tue 9.4.2019 13-16

Fri 31.5.2019 13-16

#### Why this course?

This course examines dynamic (aka multistage) optimization models. They capture many relevant real-life problems: scheduling, route planning, solving optimal strategies for games, inventory control, investment problems, machine repair, text processing, dna sequence matching, stopping problems, airplane/rocket flight path optimization, minimum time/effort problems, optimal fishery management, saving/consumption optimization, optimal feedback controllers for plants and regulator problems and so on.

The models that are examined are

• Optimal control problem. Find control u(t) that makes the system  trace the optimal trajectory x*(t) that minimizes the cost .
Function a describes how the system behaves at state x(t) at time t under control u(t). The cost function J consists of start and end point costs and running cost that is given by function L that may depend on the state x(t) and control u(t).
• Calculus of variations. Find continuous/differentiable curve y(x) that is extremum for
• Dynamic Programming (DP) problem. Find optimal controls u_k (optimal policy) that minimizes the expected cost
of the discrete stochastic system
f_k describes how the system evolves to the next state x_k+1 when the state is x_k, control u_k is chosen and there is stochastic disturbance is w_k. The cost function is given by g_k. This is discrete version of the optimal control problem.

#### Practical matters

Teaching: Lectures (24h) and exercise sessions (24h)

Assessment methods: Exam (100%), extra points from homework and exercises

Language of instruction: English

Prerequisites: 1st and 2nd years math, recommended MS-C2105 Optimoinnin perusteet (or equivalent)

• ### Materiaalit

books: B=Bertsekas vol 1, K=Kirk, KS=Kamien/Schwartz

• ### Tehtävät

The deadline for returning homework (the last problem in the paper) is the following week's Tuesday 14:00. Hand written homework is returned on paper in return box (metal boxes opposite of Y192, first floor main building main corridor, next to the big bomb shelter door, find the course code MS-E2148 on right-middle). Matlab excercises are returned on My Courses. Computer written homework in pdf-format may be returned on My Courses (no scans of hand written work).

In each exercise session there will be 1-2 problems that students present on the blackboards. You will get the solutions for these problems beforehand in My Courses. If you are prepared to present the solutions for the problems you get 1 point. In the end of the course, these points will be scaled up to 2 exam points. Each homework will be graded 0-4. In the end of the course, the homework points will be scaled up to 4 exam points. The points are updated to this Google drive document throughout the course.

In addition to the home assignments and problems that students present, there are problems that you will try to solve during the exercise session. Some more advanced problems will be demonstrated by the course assistant.

• ### Aaltolaisille

Saatavilla vasta, kun: Kenttä Käyttäjätunnus sisältää (käytä: aalto.fi) sisältää aalto.fi

The main topics of the course are:

• Solving continuous problems using calculus of variations (including different end point and corner conditions). Kirk Section 4. Lectures 1-2.
• Solving optimal control problems (including different end point conditions, minimum principle, singular intervals). Kirk Section 5. Lectures 3-5.
• Solving discrete problems using DP-algorithm (including problems having stochastics and imperfect state information). Bertsekas Sections 1-5. Lectures 6-8.
• Solving infinite horizon discounted problems (including Bellman equation, value and policy iterations). Bertsekas vol 2. Section 1. Lecture 9.
• Solving optimal control problems using HJB equations. Kirk Section 3.11. Lecture 10
• Learning the relevant concepts and terminology.

Note that the
main equations are given in the exam paper and you don't have to learn them by heart. Also, bringing a calculator (memory emptied) to the exam is not a bad idea.

Suitable problems can be found in the exercises. You can practice solving them yourself. Similar problems and their solutions are presented in the course books. You can also find many solved problems in the Internet.

• ### History of optimization

(The English version is from http://www.mitrikitti.fi/opthist.html )

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

# 20th century

## 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

## 1970s-

• 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

# 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.
• 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
• 1857 Gibbs osoittaa, että kemiallinen tasapaino on energiaminimi

# Moderni aika

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

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

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 gikonvekseja ja hi 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ä xtVx (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)
• xi: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 bx(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ä
8. Muita tehtäviä

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
xk+1 = f(xk,xk-1,...), k=1,2,...
• Esim. funktion g lokaali minimi löydetään Newtonin iteroinnilla
xk+1 = xk - g'(xk)/g''(xk)
• Vastaavaa ratkaisutekniikkaa kutsutaan yleensä ohjelmoinniksi. Siis esim. lineaarinen ohjelmointi, dynaaminen ohjelmointi, jne.
• Teoriasta ja ratkaisumenetelmistä

4. Visualisointeja ja demonstraatioita

5. Kirjallisuus

6. Tieteellisiä seuroja ja lehtiä