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 20128
  • Sökbar för utbytesstudenterJa

Poängfördelning

0103 Laboration 1,5 hp
Betygsskala: UG
1,5 hp
    0203 Tentamen 6 hp
    Betygsskala: TH
    6 hp
    • 26 Okt 2023 fm J

    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.