In English Utskrift Sök Innehåll Kontakt

Optimeringslära och systemteori
Optimeringslära och systemteori


Seminarier »
Personal
Forskning »
Utbildning
Mastersprogram »
Kurser

Läsåret 07/08
Läsåret 06/07
Fördjupningar »
Examensarbeten »
Kontakt
Forskningscentra
Konferens- information
KTH / Teknikvetenskap / Matematik / Optimeringslära och systemteori

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

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:
Johan Markdahl, markdahl@math.kth.se, rum 3738, tfn 790 7132.
Johan Thunberg, jthu02@kth.se, rum 3737, tfn 790 7507

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.  Mån 21/3  13-15  B1  Kursintroduktion. Linjär optimering (LP). 
2.  Ons 23/3  10-12  B1  Simplexmetoden för att lösa LP-problem. 
3.  Mån 28/3  13-15  B1  Simplex exempel: Degenererade baser, obegränsade problem, fas I.  
4.  Mån 4/4  13-15  B1  Baser till de fyra fundamentala underrummen. 
5.  Tis 5/4  13-15  B1  Optimering av flöden i nätverk. 
6.  Mån 11/4  13-15  B1  Dualitetssatsen och komplementaritetssatsen för LP.  
7.  Tis 12/4  13-15  B1  LDLT-faktorisering. Kvadratisk optimering.  
8.  Tor 14/4  10-12  B1  Kvadratisk optimering under likhetsbivillkor. 
9.  Tis 26/4  13-15  B1  Forts på ovanstående samt minsta-kvadratproblem. 
10.  Mån 2/5  13-15  B1  Konvexa funktioner och ickelinjär optimering. 
11.  Tis 3/5  13-15  D2  NLP utan bivillkor. Newtons metod. 
12.  Mån 9/5  13-15  B1  Ickelinjär optimering med bivillkor, spec KKT-villkoren.  
13.  Tis 10/5  13-15  D2  Mer om KKT-villkoren, speciellt för konvexa problem.
14.  Mån 16/5  13-15  D2  Blandade kompletteringar och sammanfattning. 
15.  Tor 19/5  10-12  D2  Blandade kompletteringar och sammanfattning. 

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

Nr  Datum   Tid  Salar  Innehåll 
1.  Ons 30/3  10-12  E51, E52  Simplexmetoden. Genomgång och gruppräkning. 
2.  Ons 6/4  10-12  E51, E52  Baser till de fyra underrummen. Minkostnadsflöden.
3.  Ons 13/4  10-12  E51, E52  Dualitet och komplementaritet för LP. 
4.  Ons 27/4  10-12  E51, E52  Kvadratisk optimering med likhetsbivillkor. 
5.  Ons 4/5  10-12  E51, E52  Linjära och ickelinjära minsta-kvadratproblem. 
6.  Ons 11/5  10-12  E51, E52  Ickelinjär optimering utan bivillkor. Konvexitet. 
7.  Ons 18/5  10-12  E51, E52  Ickelinjär optimering med bivillkor. KKT. 
8.  Tor 19/5  13-15  E31, E35  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 tisdagen den 24:e maj, kl. 14.00-19.00. Observera att anmälan till tentamen är obligatorisk och kan göras via "Mina Sidor" mellan den 18:e april och 8: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!