SF1861 Optimeringslära 6,0 hp

• Utbildningsnivå

  Grundnivå

• Kursnivå (A-D)

  C

• Huvudområde

  Matematik
  Teknik
  

• Betygsskala

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

• Länk till hemsida

• Kurssida på KTH Social

Lärandemål

Kursens övergripande mål är att studenten ska bli förtrogen med grundläggande begrepp, teori, modeller och lösningsmetoder för optimering.

Vidare att studentens färdigheter i linjär algebra förstärks, samt 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 inom optimeringsläran, speciellt modelleringskonceptet variabler-målfunktion-bivillkor.
• Redogöra för begreppen underrum, bas och ortogonalt komplement, med hjälp av Gauss-Jordans metod bestämma baser för vart och ett av de fyra fundamentala underrummen till en given matris, samt med hjälp av LDLT-faktorisering avgöra om en given symmetrisk matris är positivt definit 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.
• Ställa upp relevanta optimalitetsvillkor och använda dessa för att avgöra huruvida en given tillåten lösning till ett problem av något av ovannämnda slag (under föregående punkt) är en optimal lösning eller ej.
• Formulera vissa (relativt renodlade) tillämpningsproblem, exempelvis optimering av länkflödena i ett nätverk eller av stångtvärsnittsareorna i en fackverksstruktur, som linjära eller kvadratiska eller allmänt ickelinjära optimeringsproblem, samt med tillgänglig programvara i Matlab lösa dessa problem och tolka resultaten.

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

• Redogöra för grundläggande teoretiska egenskaper hos konvexa optimeringsproblem, samt avgöra huruvida ett givet problem är konvext eller ej.
• Ställa upp relevanta optimalitetsvillkor och använda dessa för att avgöra huruvida en given tillåten lösning till ett givet ickelinjärt konvext problem med bivillkor är en globalt optimal lösning eller ej.
• Med hjälp av papper och penna analysera och lösa givna (relativt små) problem av följande slag: ickelinjär optimering utan bivillkor (med Newtons metod), ickelinjära minsta-kvadratproblem (med Gauss-Newtons metod).
• 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.
• Kombinera 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, speciellt ickelinjära

minsta-kvadratproblem.

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

Behörighet

SF1618 + SF1619 Analytiska metoder och linjär algebra.

Litteratur

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

Examination

• HEM1 - Hemuppgiter, 1,5 hp, betygsskala: P, F
• TEN1 - Tentamen, 4,5 hp, betygsskala: A, B, C, D, E, FX, F

Krav för slutbetyg

En skriftlig tentamen (TEN1; 4,5 hp).
Hemuppgifter (HEM1; 1,5 hp).

Ges av

SCI/Matematik

Examinator

Påbyggnad

SF2812, SF2822.

Versionsinformation

Kursplan giltig från och med HT08.
Examinationsinformation giltig från och med HT07.