[an error occurred while processing this directive]


Kungl Tekniska högskolan / Optimeringslära och systemteori /

[an error occurred while processing this directive]This is a printer-friendly version of https://math.kth.se/optsyst/grundutbildning/kurser/SF1861/kursPM10.html

« [an error occurred while processing this directive]Back
 


SF1861 Optimeringslära för T,   kursPM 2010.

Preliminärt

Kursens hemsida: http://www.math.kth.se/optsyst/grundutbildning/kurser/SF1861/.

Examinator och föreläsare:
Per Enqvist , penqvist@math.kth.se , rum 3705, Lindstedtsv 25, tfn 790 6298.

Assistenter vid räkneövningarna:
Amol Sasane, sasane@math.kth.se, rum 3711, tfn 790 7311.
Mikael Fallgren, werty@kth.se, rum 3726, tfn 790 7220

Kursmaterial:

Följande material säljs på Matematiks studentexpedition, Lindstedtsv 25.
Optimization, av Amol Sasane och Krister Svanberg.
(Engelsk översättning av det tidigare material som använts i kursen, med vissa tillägg så som exempel och illustrationer. Om du har tillgång till det gamla materialet så kan du använda det istället. )
Exempelsamling i Optimeringslära för T.  

Matlab-baserade hemuppgifter kommer att läggas upp på kursens hemsida.
Visst kompletterande material kommer också att läggas upp på hemsidan.

Vad är optimering ?

Optimeringslära handlar om att hitta den bästa lösningen bland en mängd tillåtna alternativ. Typiskt finns det oändligt många olika alternativa lösningar och de brukar beskrivas med olika variabler som i den här kursen är kontinuerliga. Det kan t.ex. vara dimensioner för olika balkar eller intensiteter för strålningsbehandling. För dessa variabler finns det vissa begränsningar, som t.ex. att de ska vara positiva, och dessa bivillkor definierar de tillåtna lösningarna. Vad som är den bästa lösningen kvantifieras genom att man definierar en målfunktion som ger en ranking av de tillåtna lösningar, typiskt kan man vilja minimera vikten av ett fackverk, maximera styvheten av detsamma, eller minimera kostnaden för ett transportproblem.

Mål

Målet är att efter kursen så ska man kunna:
  • förklara grundläggande begrepp och egenskaper för optimering, så som modelleringskonceptet variabler-målfunktion-bivillkor.
  • applicera och analysera algoritmerna som gås igenom i kursen för lösning av linjära, kvadratiska och ickelinjära problem.
  • använda linjär algebra, speciellt underrum och faktoriseringar, för att t.ex. beskriva tillåtna lösningar, riktningar och avgöra om funktioner är konvexa eller inte.
  • avgöra om en given lösning kan vara optimal till ett icke-linjärt problem med bivillkor
  • formulera optimeringsproblem i matematiska termer, och i de fall de faller inom de kategorier som behandlats i kursen veta hur man angriper dessa, lösa dem med lämpliga beräkningshjälpmedel samt analysera och presentera resultatet.

Preliminärt schema för föreläsningarna:

Nr  Datum  Tid  Sal  Innehåll 
1.  Ons 24/3  8-10  D2  Kursintroduktion. Linjär optimering (LP). 
2.  Fre 26/3  8-10  D2  Simplexmetoden för att lösa LP-problem. 
3.  Tis 30/3  13-15  D2  Baser till de fyra fundamentala underrummen. 
4.  Tor 1/4  10-12  D2  Optimering av flöden i nätverk. 
5.  Tis 13/4  13-15  D2  Dualitetssatsen och komplementaritetssatsen för LP. 
6.  Tor 15/4  10-12  M2  LDLT-faktorisering. Kvadratisk optimering. 
7.  Tis 20/4  13-15  D2  Kvadratisk optimering under likhetsbivillkor. 
8.  Tis 27/4  13-15  D2  Forts på ovanstående samt minsta-kvadratproblem. 
9.  Tor 29/4  10-12  D2  Konvexa funktioner och ickelinjär optimering. 
10.  Tis 4/5  15-17  E1  NLP utan bivillkor. Newtons metod. 
11.  Tor 6/5  10-12  D2  Ickelinjär optimering med bivillkor, spec KKT-villkoren. 
12.  Mån 10/5  15-17  D1  Mer om KKT-villkoren, speciellt för konvexa problem. 
13.  Tis 11/5  13-15  D2  Blandade kompletteringar.
14.  Tis 18/5  13-15  D2  Blandade kompletteringar och sammanfattning. 
15.  Tor 20/5  10-12  D2  Blandade kompletteringar och sammanfattning. 

Preliminärt schema för räkneövningarna:

Nr  Datum   Tid  Salar  Innehåll 
1.  Tis 30/3  15-17  E51, E52  Simplexmetoden. Genomgång och gruppräkning. 
2.  Tor 1/4  13-15  E51, E52  Baser till de fyra underrummen. Minkostnadsflöden.
3.  Mån 19/4  13-15  E51, E52  Dualitet och komplementaritet för LP. 
4.  Tor 22/4  13-15  E51, E52  Kvadratisk optimering med likhetsbivillkor. 
5.  Tor 29/4  13-15  E51, E52  Linjära och ickelinjära minsta-kvadratproblem. 
6.  Tor 6/5  13-15  E51, E52  Ickelinjär optimering utan bivillkor. Konvexitet. 
7.  Ons 12/5  10-12  E51, E52  Ickelinjär optimering med bivillkor. KKT. 
8.  Tor 20/5  13-15  E51, E52  Blandade kompletteringar. 


Examination

Kursen examineras i de bägge momenten TEN1 och HEM1, dvs tentamen och hemuppgifter.

Tentamen (TEN1, 4.5 hp)
Ordinarie tentamenstillfället är torsdagen den 27:e maj, kl. 14.00-19.00. Observera att anmälan till tentamen är obligatorisk och kan göras via "Mina Sidor" mellan den 12:e april och 16:e maj.
Maximalt resultat på tentan är 50 poäng. Godkänd blir man på 25 poäng.
Preliminära betygsgränser:
43-50 poäng ger A, 38-42 poäng ger B, 33-37 poäng ger C,
28-32 poäng ger D, 25-27 poäng ger E, 23-24 poäng ger Fx.
Vid tentamen delas en kortfattad formelsamling ut. Inga andra hjälpmedel
är tillåtna. Ingen räknare på tentan!

Hemuppgifter (HEM1, 1.5 hp)
Frivilliga hemuppgifter i Matlab delas ut under kursens gång.
Tillsammans kan dessa ge upp till 12 hemtalspoäng.
Den som erhåller sammanlagt X hemtalspoäng blir belönad enligt följande:

  • X < 5 ger ingen belöning.
  • 5 =< X =< 8 medför att deluppgift 1.(a) ej behöver lösas på tentamen.
    De 5 tentamenspoängen för 1.(a) erhålls ändå.
  • 9 =< X medför att uppgift 1 ej behöver lösas på tentamen.
    De 5+4=9 tentamenspoängen för uppgift 1 erhålls ändå.
  • Den student som erhåller minst 9 hemtalspoäng blir inrapporterad
    godkänd på momentet HEM1.
  • Den student som INTE erhåller minst 9 hemtalspoäng blir ändå inrapporterad
    godkänd på momentet HEM1 den dag han/hon blir godkänd på tentamen
    och får momentet TEN1 inrapporterat.
Angående varaktigheten på bonusen från hemuppgifterna gäller följande:
Om man har blivit fullständigt godkänd på hemuppgiftsdelen, så att
denna har blivit inrapporterad i Ladok (1.5 poäng), ska man inte göra
några fler hemuppgifter i kursen. Bonusen att slippa hela uppgift 1 på
tentan gäller "för all framtid".
Om man enbart erhållit delbonusen att slippa uppgift 1.a på tentan, och
därmed ej fått hemuppgiftsdelen inrapporterad i ladok, så gäller denna
bonus endast ett år, dvs på ordinarie tentan och på (den enda) omtentan.

Komplettering
Studenter som får betyg Fx ges möjlighet att komplettera till betyg E.
Kompletteringen kommer att innehålla såväl skriftliga som muntliga inslag och måste
genomföras senast tre veckor efter att tentamensresultatet har rapporterats in i Ladok.
Den student som får betyget Fx och vill komplettera ska snarast möjligt
kontakta examinator (via e-mail).

Välkomna till kursen!