Kursplan för Olinjär optimering

Kursplan fastställd 2023-02-14 av programansvarig (eller motsvarande).

Kursöversikt

  • Engelskt namnNonlinear optimisation
  • KurskodTMA947
  • Omfattning7,5 Högskolepoäng
  • ÄgareMPENM
  • UtbildningsnivåAvancerad nivå
  • HuvudområdeInformationsteknik, Matematik
  • InstitutionMATEMATISKA VETENSKAPER
  • BetygsskalaTH - Mycket väl godkänd (5), Väl godkänd (4), Godkänd (3), Underkänd

Kurstillfälle 1

  • Undervisningsspråk Engelska
  • Anmälningskod 20144
  • Sökbar för utbytesstudenterJa

Poängfördelning

0103 Laboration 1,5 hp
Betygsskala: UG		1,5 hp0 hp0 hp0 hp0 hp0 hp
0203 Tentamen 6 hp
Betygsskala: TH		6 hp0 hp0 hp0 hp0 hp0 hp

I program

Examinator

Gå till kurshemsidan (Öppnas i ny flik)

Behörighet

Grundläggande behörighet för avancerad nivå
Sökande med en programregistrering på ett program där kursen ingår i programplanen undantas från ovan krav.

Särskild behörighet

Engelska 6
Sökande med en programregistrering på ett program där kursen ingår i programplanen undantas från ovan krav.

Kursspecifika förkunskaper

Grundkurser i linjär algebra samt en- och flervariabelanalys

Syfte

Syftet med kursen är att ge en god teoretisk grund inom några av de viktigaste områdena inom optimering: konvex optimering, linjär optimering och olinjär optimering. Kursen behandlar principer för analys av ett specifikt optimeringsproblems egenskaper, samt karakteriseringar av tillåtna lösningar som är (lokalt) optimala. Denna teori används sedan för att utveckla ett antal exempel på optimeringsmetoder som kan användas för att lösa praktiska optimeringsproblem. Kursen ämnar även ge viss praktisk träning inom matematisk modellering och problemlösning med hjälp av optimering. 

Lärandemål (efter fullgjord kurs ska studenten kunna)

Målsättningen är att du, efter fullgjord kurs, ska behärska delar av teorin för optimalitet, dualitet och konvexitet, och deras inneboende samband. På så sätt kan du analysera olika optimeringsproblem, och både klassificera dem och ange riktlinjer för hur de ska angripas praktiskt. Det senare är den mer praktiska målsättningen i en annars främst teoretisk kurs.

Mer specifik, efter fullgjord kurs ska du kunna:
  • ange och förklara de viktigaste koncepten inom konvex analys, konvex optimering och dualitet, och kunna tillämpa teorin på konkreta exempel.
  • ange och förklara grunderna för nödvändiga och tillräckliga optimalitetsvillkor, särskilt KKT-villkoren, och kunna utnyttja teorin för att analysera och lösa konkreta exempel.
  • analysera linjärprogrammeringsproblem med hjälp av koncept som dualitet och känslighet; lösa linjärprogrammeringsproblem med simplexmetoden och förklara hur metoden fungerar.
  • förklara begrepp som descent- och tillåten riktning, och använda dessa begrepp för att förklara principerna bakom, analysera och tillämpa klassiska optimeringsmetoder, exempelvis brantaste lutnings-metoden, variationer av Newtons metod, Frank-Wolfe-metoden och straff-metoder; kunna specificera förutsättningar under vilka dessa metoder konvergera.
  • formulera relevanta delar av ett verkligt problem i form av en matematisk optimeringsmodell, analysera modellen med lämpliga verktyg och metoder, och tillämpa lämpliga lösningsalgoritmer.

Innehåll

Denna grundkurs i optimering beskriver de mest relevanta matematiska principerna som används vid analys och lösande av optimeringsproblem med kontinuerliga variabler. En grov uppdelning av och översikt över innehållet är som följer.
  • Konvexanalys: konvex mängd, polytop, polyeder, kon, representationssatsen, extrempunkter, Farkas lemma, konvex funktion
  • Optimalitetsvillkor och dualitet: globalt/lokalt optimum, existens och unikhet av optimala lösningar, variationsolikhet, Karush-Kuhn-Tucker (KKT) villkor, komplementaritetsvillkor, Lagrange-multiplikator, Lagrangedualt problem, globala optimalitetsvillkor, svag/stark dualitet
  • Linjärprogramering (LP): LP-modeller, LP-algebra och geometri, tillåten baslösning (BFS), Simplexmetoden, LP-dualitet, optimalitetsvillkor, stark dualitet, komplementaritet, inre punkts-metoder, känslighetsanalys
  • Ickelinjära optimeringsmetoder: descent-riktning, linjesökning, (quasi-)Newton metoder, Frank-Wolfe-metoden, gradientprojektion, yttre och inre straff-metoder.

Organisation

Föreläsningar, lektioner, två datoruppgifter, samt en projektuppgift som innehåller matematisk modellering och lösning av ett konkret optimeringsproblem med industrirelevans. Dessutom kan det även förekomma frivilliga moment som kan ge bonuspoäng på tentan.

Litteratur

"An Introduction to Continuous Optimization", av Niclas Andréasson, Anton Evgrafov, och Michael Patriksson, med Emil Gustavsson, Zuzana Nedělková, Kin Cheong Sou, och Magnus Önnheim, tredje upplagan, publicerad av Studentlitteratur 2016.

Examination inklusive obligatoriska moment

Projektuppgift (laboration), datoruppgifter, skriftlig tentamen. Frivilliga moment som kan ge bonuspoäng på tentan kan förekomma.

Kursens examinator får examinera enstaka studenter på annat sätt än vad som anges ovan om särskilda skäl föreligger, till exempel om en student har ett beslut från Chalmers om pedagogiskt stöd på grund av funktionsnedsättning.