SF1861 Optimeringslära för T,   hemsida 2011

Undervisningsmaterial:

Det blev något fel vid tryckningen av Optimeringskompendiet och sidan 2 kom inte med, den kan ni nu hitta här.

• Föreläsning 1 (LP)
• Föreläsning 2 (Simplex) och eventuellt föreläsning 3.
• Föreläsning 4 (LA)
  Föreläsning 4 kommer vi att börja med linjär algebra. Förkunskaperna inom linjär algebra brukar skifta, men för de flesta brukar det vara ovant att arbeta med underrum och de baser som spänner upp dessa som vi gör i denna kurs. Så det kan vara nyttigt att kolla igenom innehållet i förväg och eventuellt gå in på länkarna nedan.
  • Om man vill ha lite mera bakgrund i linjär algebra så kan man titta på följande inspelade lektioner av Gilbert Strang från MIT. Gå till streaming lectures och börja med lektion 6. (finns även på youtube)
• Föreläsning 5 (Nätverksproblem)
• Föreläsning 5-6 (Transportproblem)
• Föreläsning 6-7 (Dualitet)
• Föreläsning 7-9 (Kvadratiska problem, LDL^T)
  Matlabprogram för att plotta de olika kvadratiska funktionerna som visades på lektionen.
• Föreläsning 11 (NLP - Gradient och Newtons metod)
• Föreläsning 12 (Konvex optimering)
• Föreläsning 13 (Ickelinjärt med likhetsbivillkor)
• Föreläsning 14 (Ickelinjärt med olikhetsbivillkor)

• Övning 1:
  (Med förbehåll för skrivfel, finns här Johan Thunbergs övningsanteckningar för er som vill gå igenom de iterationer av simplex som inte hanns med under lektionen)
  anteckningar och simplexschema
• Övning 4:
  De kvadratiska problemen som illustrerades på övningen
• Övning 5:
  (Med förbehåll för skrivfel, finns här Johan Markdahls övningsanteckningar för er som vill gå igenom de iterationer av Gauss-Newtons metod som inte hanns med under lektionen)
  anteckningar

• Impedanser FreeSpaceZ.m, Loudspeaker_ZK.mat
Om ni får problem att ladda ner någon fil, skicka ett mail så mailar jag tillbaka filen. (Om man sparar ner .mat filen på en PC kan man få en fil med ändelsen .mat.htm istället. Prova i så fall att bara ta bort .htm från namnet)

Lästips inför resp föreläsning: (uppdateras under kursens gång)
OK = Optimeringskompendiet av Amol Sasane och Krister Svanberg

Inför föreläsning nr 1:     Kapitel 1,2 och 3 i OK.
(Kapitel 1 i gröna häftet.)

Inför föreläsning nr 2:     Kapitel 4 och 5 i OK.
(Kapitel 3 i gröna häftet.)

Inför föreläsning nr 3:     Kapitel 5 i OK.
(Kapitel 3 i gröna häftet.)
Vi kommer att räkna ett exempel på föreläsningen, som finns på slides för föreläsning 2, och gå igenom olika egenskaper för simplexmetoden.

Inför föreläsning nr 4:     Kapitel 23-26 i OK.
(Kapitlen 4 - 6 i gula häftet.)

Inför föreläsning nr 5:     Kapitel 7.2 i OK.
(Kapitel 6 i gröna häftet.)

Inför föreläsning nr 6:     Kapitel 6 i OK. (6.7 kursivt)
(Kapitel 4 i gröna häftet.)

Inför föreläsning nr 7:     Kapitel 9.1-2 och 26 i OK.
(Kapitel 1.1-3, 2.1-2 i blå häftet)

Inför föreläsning nr 8:     Kapitel 9 och 27 i OK.
(Kapitel 2 i blå häftet och kapitel 7 i gula häftet.)

Inför föreläsning nr 9:     Kapitel 10 i OK.
(Kapitel 3 i blå häftet.)

Inför föreläsning nr 10:     Kapitel 11.1-6 i OK.
(Kapitel 5.1-6 i blå häftet.)

Inför föreläsning nr 11:     Kapitel 12-14, 16-17 i OK.
(Kapitel 1-3, 5-8, i grå häftet.)

Inför föreläsning nr 12:     Kapitel 15 i OK.
(Kapitel 4 i grå häftet.)

Inför föreläsning nr 13:     Kapitel 18 och 19 i OK.
Det kan även vara bra att repetera nollrumsmetoden och Lagrangemetoden för kvadratiska problem.
(Kapitel 9 och 10 i grå häftet.)

Inför föreläsning nr 14:     Kapitel 20 och 21 i OK.
(Kapitel 11 och 12 i grå häftet.)

Lämpliga räkneexempel efter resp föreläsning: (uppdateras under kursens gång)

Efter föreläsning nr 1 rekommenderas
  Exercise 2.1 i Optimization-kompendiet (OK)
  De två övningarna sist i OH-bilderna för lektion 1.

Efter föreläsning nr 2 rekommenderas
  Uppgift 2a i tentamen 2009-08-25
  Uppgift 2 i tentamen 2009-05-19

Efter föreläsning nr 3 rekommenderas
  Två exempel som Mikael Fallgren sammanställt simplexexempel
  Exercise 5.4-5.10 i OK

Efter föreläsning nr 4 rekommenderas
  Gå igenom sista delen av beräkningen av alla fundamentala underrum som jag inte hann slutföra på lektionen. pdf
  Gå igenom exempel 26.8 i OK (sid 31 Gula häftet). Räkna gärna på egen hand först.
  Ett exempel till Gauss-Jordan exempel 2

Efter föreläsning nr 5 rekommenderas
  att man gör iteration 2 av nätverksproblemet i bilderna från föreläsningen.
  Uppgift 2.3, 2.4 och 2.9 i exempelsamlingen

Efter föreläsning nr 6 rekommenderas
  Uppgift 1.8 a,(b) i exempelsamlingen
  Uppgift 2.1 a,(b) och 2.6 a i exempelsamlingen
  Uppgift 2.8 (lite svårare tal) i exempelsamlingen

  att man gör om transportproblemet genom att hitta en egen startbaslösning där man börjar med det "nordöstra" hörnet i tablån.
  Räkna följande exempel Dualitet ex 1a, Dualitet ex 1b. (Varianter på det simplextal ni löste på första övningen)

Efter föreläsning nr 7 rekommenderas
  Uppgift 2.1 c,d och 2.6 b i exempelsamlingen

Efter föreläsning nr 8 rekommenderas
  att man tränar på LDL^T faktorisering. Se t.ex. LDL^Texempel.   teori i OK sid 188, ex. sid 191-2, 195, och övning 27.22.
  att man räknar tal 4.3 (a) och 4.7 i exempelsamlingen.
  att man bestämmer alla optimala lösningar till de olika kvadratiska funktionerna i Matlabprogram, dvs lösningar till Hx=-c om H är positivt semidefinit, och jämför med figurerna.

Efter föreläsning nr 9 rekommenderas
  att man räknar tal 4.13 i exempelsamlingen.
  att man räknar tal 10.8 och 10.9 i OK
  att man tittar igenom exemplet om fackverk, för en intressant tillämpning. Problemet i hemtal 2 var ett specialfall som kunde lösas med LP, men generellt krävs kvadratisk programmering.

Efter föreläsning nr 10 rekommenderas
  att man räknar tal 4.1 i exempelsamlingen.

Efter föreläsning nr 11 rekommenderas
  att man räknar tal 4.6 i exempelsamlingen.

Efter föreläsning nr 12 rekommenderas
  att man räknar tal 4.2 och 4.3 b i exempelsamlingen,
  att man räknar tal 15.11 och 15.12 i OK.

Efter föreläsning nr 13 rekommenderas
  att man räknar tal 4.10 a,b och 4.11 a,b,c i exempelsamlingen.

Efter föreläsning nr 14 rekommenderas
  att man räknar tal 5.2 a,b och 5.3 i exempelsamlingen. Man kan även gå tillbaka till talen 4.4, 4.5 och kolla KKT-villkoren för de grafiskt framtagna lösningarna där.


Lämpliga förberedelser inför övningarna:

Inför övning nr 1 rekommenderas
  att man har lite koll på simplexalgoritmen, efersom assistenterna först går igenom ett tal, och sedan ska ni på egen hand, eller i grupp, räkna själva.

Inför övning nr 2 rekommenderas
  att man repeterar linjär algebra och minkostnadsflöden i nätverk.

Inför övning nr 3 rekommenderas
  att man repeterar dualitet, komplementaritet

Inför övning nr 4 rekommenderas
  att man repeterar LDL^T-faktorisering, och kvadratisk optimering.


Inför övning nr 5 rekommenderas
  att man repeterar minsta kvadratproblem,

Inför övning nr 6 rekommenderas
  att man repeterar konvexitet, Gradientmetoden och Newtons metod.


Inför övning nr 7 rekommenderas
  att man repeterar optimalitetsvillkor för ickelinjära problem med likhets- och olikhetsbivillkor.

Notera att handskrivna lösningar till övningarna i OK finns nederst på optimeringslära för F's hemsida.

Senaste årets tentor + lösningar: