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
Modul | LP1 | LP2 | LP3 | LP4 | Sommar | Ej LP | Tentamensdatum |
|---|---|---|---|---|---|---|---|
| 0103 Laboration 1,5 hp Betygsskala: UG | 1,5 hp | ||||||
| 0203 Tentamen 6 hp Betygsskala: TH | 6 hp |
|
I program
- MPCAS - KOMPLEXA ADAPTIVA SYSTEM, MASTERPROGRAM, Årskurs 1 (obligatoriskt valbar)
- MPCAS - KOMPLEXA ADAPTIVA SYSTEM, MASTERPROGRAM, Årskurs 2 (valbar)
- MPDSC - DATA SCIENCE OCH AI, MASTERPROGRAM, Årskurs 1 (obligatorisk)
- MPENM - MATEMATIK OCH BERÄKNINGSVETENSKAP, MASTERPROGRAM, Årskurs 1 (obligatorisk)
- MPICT - INFORMATIONS- OCH KOMMUNIKATIONSTEKNIK, MASTERPROGRAM, Årskurs 1 (obligatoriskt valbar)
- MPICT - INFORMATIONS- OCH KOMMUNIKATIONSTEKNIK, MASTERPROGRAM, Årskurs 2 (valbar)
- MPSYS - SYSTEMTEKNIK, REGLERTEKNIK OCH MEKATRONIK, MASTERPROGRAM, Årskurs 1 (obligatoriskt valbar)
- MPSYS - SYSTEMTEKNIK, REGLERTEKNIK OCH MEKATRONIK, MASTERPROGRAM, Årskurs 2 (valbar)
- TKAUT - AUTOMATION OCH MEKATRONIK, CIVILINGENJÖR, Årskurs 3 (valbar)
- TKGBS - GLOBALA SYSTEM, CIVILINGENJÖR, Årskurs 3 (obligatoriskt valbar)
- TKTEM - TEKNISK MATEMATIK, CIVILINGENJÖR, Årskurs 3 (valbar)
Examinator
Axel Ringh- Forskarassistent, Tillämpad matematik och statistik, Matematiska vetenskaper
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 6Sö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.