SF1811 Optimeringslära 6,0 hp

Optimization

  • Utbildningsnivå

    Grundnivå
  • Huvudområde

    Matematik
    Teknik
  • Betygsskala

    A, B, C, D, E, FX, F

Kurstillfällen/kursomgångar

HT19 för programstuderande

HT18 Doktorand för fristående studerande

  • Perioder

    HT18 P2 (6,0 hp)

  • Anmälningskod

    10201

  • Kursen startar

    2018-10-29

  • Kursen slutar

    2019-01-14

  • Undervisningsspråk

    Engelska

  • Studielokalisering

    KTH Campus

  • Undervisningstid

    Dagtid

  • Undervisningsform

    Normal

  • Antal platser *

    Max. 1

    *) Vid fler sökande än platser kommer urval att ske.

  • Kursansvarig

    Anders Szepessy <szepessy@kth.se>

  • Lärare

    Anders Szepessy <szepessy@kth.se>

  • Målgrupp

    För doktorander på KTH

Lärandemål

Kursens övergripande mål är att studenten ska bli väl förtrogen med grundläggande begrepp, teori, modeller och lösningsmetoder för optimering. Vidare att studenten förvärvar basala färdigheter i att modellera och med hjälp av dator lösa tillämpade optimeringsproblem av skiftande slag.

Mätbara mål

För att bli godkänt i kursen ska studenten kunna följande:

  • Redogöra för grundläggande begrepp och teori inom optimeringsläran, speciellt modelleringskonceptet variabler-målfunktion-bivillkor och egenskaper hos konvexa optimeringsproblem, samt avgöra huruvida ett givet problem är konvext eller ej.
  • Med hjälp av papper och penna analysera och lösa givna (relativt små) problem av följande slag: linjär optimering med både likhets- och olikhetsbivillkor, duala problemet till ett linjärt optimeringsproblem, kvadratisk optimering utan bivillkor, kvadratisk optimering med linjära likhetsbivillkor, linjära minsta-kvadratproblem, minsta-normlösningen till linjära minsta-kvadratproblem, optimering av nätverksflöden med linjära eller kvadratiska kostnader, ickelinjär optimering utan bivillkor (med Newtons metod), ickelinjära minsta-kvadratproblem (med Gauss-Newtons metod).
  • Ställa upp relevanta optimalitetsvillkor och använda dessa för att avgöra huruvida en given tillåten lösning till ett givet konvext problem med bivillkor (t ex något av problemen under föregående punkt) är en globalt optimal lösning eller ej.
  • Bestämma samtliga punkter som uppfyller Karush-Kuhn-Tuckers optimalitetsvillkor för ett givet (typiskt tillrättalagt men eventuellt inte konvext) optimeringsproblem med ickelinjär målfunktion och ickelinjära likhets- och/eller olikhetsbivillkor, samt avgöra om någon av dessa utgör en global optimallösning.

För att uppnå högsta betyg ska studenten dessutom kunna följande:

  • Redogöra för begreppet Lagrangerelaxering och använda detta verktyg för att lösa separabla konvexa problem.
  • Formulera vissa (relativt renodlade) tillämpningsproblem, exempelvis optimering av länkflödena i olika typer av nätverk eller att bestämma den minsta sfär som omsluter ett mängd givna punkter i R^3, som optimeringsproblem på lämplig form samt med tillgänglig programvara i Matlab lösa dessa problem och tolka resultaten.
  • Kombinera samtliga ovannämnda begrepp och metoder för att lösa mer sammansatta problem.

Kursens huvudsakliga innehåll

Exempel på optimeringstillämpningar och formuleringsträning. Grundläggande begrepp och teori för optimering, speciellt teori för konvexa problem.

Linjär algebra i R^n, speciellt baser till nollrum och bildrum, samt LDLT-faktorisering.

Linjär optimering, inklusive dualitetsteori.

Optimering av flöden i nätverk.

Kvadratisk optimering med linjära bivillkor.

Linjära minsta-kvadratproblem, speciellt minsta-normlösningar.

Ickelinjär optimering utan bivillkor, t ex ickelinjära minsta-kvadratproblem.

Optimalitetsvillkor för ickelinjär optimering med bivillkor, speciellt för konvexa problem.

Lagrangerelaxering.

Behörighet

SF1604 Linjär algebra,
SF1602 + SF1603 Differential- och integralkalkyl.

Litteratur

Linear and Nonlinear Programming av Nash and Sofer, McGraw-Hill, samt kompendier från institutionen.

Examination

  • TEN1 - Skriftlig tentamen, 6,0, betygsskala: A, B, C, D, E, FX, F

Krav för slutbetyg

En skriftlig tentamen (TEN1; 6 hp).
Frivilliga datorlaborationer ger bonuspoäng till tentamen.

Ges av

SCI/Matematik

Kontaktperson

Anders Szepessy (szepessy@kth.se)

Examinator

Anders Szepessy <szepessy@kth.se>

Övrig information

SF1811 är numera identisk med SF1841, med gemensam undervisning och examination.

Påbyggnad

SF2812, SF2822.

Versionsinformation

Kursplan gäller från och med HT2008.
Examinationsinformation gäller från och med HT2007.