Hoppa till huvudinnehållet

SF1851 Optimeringslära 6,0 hp

Kursomgångar saknas för tidigare och kommande terminer, samt för innevarande termin.
Rubriker med innehåll från kursplan SF1851 (HT 2008–) är markerade med en asterisk ( )

Innehåll och lärandemål

Kursinnehå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.

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.

Kursupplägg

Ingen information tillagd

Kurslitteratur och förberedelser

Särskild behörighet

SF1608, SF1609, 5B1117 Analys och linjär algebra.

Rekommenderade förkunskaper

Ingen information tillagd

Utrustning

Ingen information tillagd

Kurslitteratur

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

Examination och slutförande

När kurs inte längre ges har student möjlighet att examineras under ytterligare två läsår.

Betygsskala

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

Examination

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

Examinator beslutar, baserat på rekommendation från KTH:s samordnare för funktionsnedsättning, om eventuell anpassad examination för studenter med dokumenterad, varaktig funktionsnedsättning.

Examinator får medge annan examinationsform vid omexamination av enstaka studenter.

Övriga krav för slutbetyg

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

Möjlighet till komplettering

Ingen information tillagd

Möjlighet till plussning

Ingen information tillagd

Examinator

Profile picture Ulf Jönsson

Etiskt förhållningssätt

  • Vid grupparbete har alla i gruppen ansvar för gruppens arbete.
  • Vid examination ska varje student ärligt redovisa hjälp som erhållits och källor som använts.
  • Vid muntlig examination ska varje student kunna redogöra för hela uppgiften och hela lösningen.

Ytterligare information

Kurswebb

Ytterligare information om kursen kan hittas på kurswebben via länken nedan. Information på kurswebben kommer framöver flyttas till denna sida.

Kurswebb SF1851

Ges av

SCI/Matematik

Huvudområde

Matematik, Teknik

Utbildningsnivå

Grundnivå

Påbyggnad

SF2812, SF2822.