Föreläsningar (15), gästföreläsningar (3), seminarier samt avslutande forskningsartikel.
FEG3324 Tillämpad optimering och matematiska dekompositioner 10,0 hp
Kursen skapar en förståelse kring optimeringsmodeller och dess lösningsalgoritmer i en applicerad kontext. 1 del 1 kommer standardtyper av optimeringsmodeller att diskuteras. Linjära problem (LP), konvexa kvadratiska problem (QP), kvadratiska problem med kvadratiska bivillkor (QCQP), andra ordningens koniska problem (SOCP), semidefinita problem (SDP) och konvexa dynamiska problem (DP). I del 2 diskuteras tre särskilda slags ickekonvexa optimeringsmodeller med speciella matematiska egenskaper. Dessa är konvexa blandade heltalsproblem, kvasi-konvexa optimeringsmodeller and ”inomellipsoid-utanför-sfär-modeller”. Vi diskuterar dessa problems intressanta matematiska egenskaper och hur dessa egenskaper kan användas för att lösa generella icke-konvexa optimeringsproblem. I del 3 kommer utvalda och icke-konvexa optimeringsmodeller att diskuteras, disjunktiva problem, logikbaserade problem, stokastiska problem och multinivåproblem. Komplementaritetsproblem uppstår inom många användningsområde i verkliga livet. Därav kommer vi diskutera linjära komplementaritetsproblem (LCPs) och blandade komplementaritetsproblem (MCPs) samt lösningsalgoritmer. Om ett optimeringsproblem har komplementaritetsvillkor leder det till matematiska problem med jämviktsbivillkor (MPEC) och jämviktsproblem med jämviktsbivillkor (EPEC). Komplementaritetsproblems matematik kommer att diskuteras i del 4 av denna kurs. Därav kommer tre viktiga och välkända dekompositionstekniker att diskuteras i del 5 av kursen, mer specifikt kommer olika varianter av Benders dekomposition, Lagrangedekomposition och hybriddekomposition att diskuteras. I del 6 kommer ett flertal användningsområden för de matematiska begrepp som presenterats i del 1-5 att diskuteras. Del 7 av kursen ska bidra med grundläggande kunskaper kring processen att skapa optimeringsbaserade modeller. Vi kommer att diskutera och presentera ett systematiskt angreppssätt för att hantera problem i verkliga livet.
Information per kursomgång
Kursomgångar saknas för aktuella eller kommande terminer.
Kursplan som PDF
Notera: all information från kursplanen visas i tillgängligt format på denna sida.
Kursplan FEG3324 (VT 2023–)Information för forskarstuderande om när kursen ges
Kursen kommer att erbjudas i period 4 varannat år.
Rubriker med innehåll från kursplan FEG3324 (VT 2023–) är markerade med en asterisk ( )
Innehåll och lärandemål
Kursupplägg
Kursinnehåll
Doktorandkurs om:
Tillämpad optimering och matematiska dekompositioner
Dr Mohammad Reza Hesamzadeh
Del 1: Konvexa optimeringsproblem
Linjära problem (LP)
- Generella formulering
- Lösningsalgoritmer
- - Simplexmetoden
- - Inre punkt-metoden
- Exempel
Konvexa kvadratiska problem
- Generelll formulering
- Lösningsalgoritmer
- Exempel
Konvexa kvadratiska problem med kvadratiska bivillkor (QCQP)
- Generell formulering
- Lösningsalgoritmer
- Exempel
Andra ordningend koniska problem (SOCP)
- Generell formulering
- Lösningsalgoritmer
- Exempel
Semidefinita problem (SDP)
- Generell formulering
- Lösningsalgoritmer
- Exempel
Dynamiska problem (DP) och dynamiska duala problem (DDP)
- Generell formulering
- Lösningsalgoritmer
- Exempel
Del 2: Icke-konvexa optimeringsproblem med särskilda egenskaper
Linjära blandade heltalsproblem (MILP)
- Generell formulering
- Lösningsalgoritmer
- - ”Branch and Bound”
- - ”Branch and Cut”
- Exempel
- Generaliserade konvexa blandade heltalsproblem (MICP)
Kvasikonvexa optimeringsproblem
- Generell formulering
- Lösningsalgoritmer
- Exempel
“Inom-ellipsoid-utanfär-sfär-problem” (IEOSP)
- Generell formulering
- Lösningsalgoritmer
- Exempel
Del 3: Utvalda icke-konvexa optimeringsproblem
Disjunktiva problem
- Generell formulering
- Lösningsalgoritmer
- Exempel
Logikbaserade problem
- Generell formulering
- Lösningsalgoritmer
- Exempel
Stokastiska problem
- Generell formulering
- Lösningsalgortimer
- Exempel
Bi- och trinivåproblem
- Generell formulering
- Lösningsalgoritmer
- Exempel
Del 4: Komplementaritetsproblem
Linjära komplementaritetsproblem (LCP)
- Generell formulering
- Lösningsalgoritmer
- Exempel
Blandade komplementaritetsproblem (MCP)
- Generell formulering
- Lösningsalgoritmer
- Exempel
Matematiska problem med jämviktsbivillkor (MPEC)
- Generell formulering
- Lösningsalgoritmer
- Exempel
Jämviktsproblem med jämviktsbivillkor (EPEC)
- Generell formulering
- Lösningsalgoritmer
- Exempel
Del 5: Matematiska nedbrytningar
Benders nedbrytning och dess varianter
- Grundläggande teori
- Varianter
- Exempel
Lagrangenedbrytning och dess varianter
- Grundläggande teori
- Varianter
- Exempel
Hybridnedbrytning och dess varianter
- Grundläggande teori
- Varianter
- Exempel
Del 6: Tillämpningar inom elnätsoptimering
Utbyggnad av överföringskapacitet: LP-modell
Investeringsplanering av överföring: MILP-modell
Överföringsplanering med kvadratisk kostnadsfunktion för generering: MIQP Överföringsplanering med ohmsk förlustfunktion: MIQCQP
Dynamiska problem och duala dynamiska problem
Reglering av överingsinvestering: Disjunktivt problem
Driftkoordinering mellan TSO-DSO: Logikbaserat problem
Transmission investment under uncertainty: Stochastic program Marknadsbaserad överföringsinvestering: LCP and MCP
Optimalt budande för vattenkraft: MPEC
Nash-jämvikt: EPEC
Del 7: Grunderna för den matematiska modelleringsprocessen
A: Konvex modell eller icke-konvex modell?
B: För icke-konvexa modeller:
- Identifiera den underliggande konvexa strukturen
- Konvex approximering
- Konvex relaxation
- Omformulering till ett icke-konvext problem med särskilda egenskaper
- Lös problemet med en färdig standardlösare
C: Vad gäller den ursprungliga icke-konvexa strukturen? Nya teorier och insikter…
Referenser:
- Föreläsningsmaterial och forskningsartiklar
- R. Baldick, “Applied Optimization Formulation and algorithms for Engineering Systems”, Cambridge University Press, 2006.
Lärandemål
Efter kursen ska studenten kunna:
- Förstå och beskriva teorin om konvexa och icke-konvexa optimeringsproblem,
- Undersöka och jämföra praktiska konvexa optimeringsmodeller (LP, QCQP, SOCP, SP, DP),
- Undersöka och jämföra praktiska icke-konvexa optimeringsmodeller (MILP, Quasiconvex optimization, IEOSP),
- Undersöka och testa utvalda praktiska icke-konvexa optimeringsmodeller,
- Undersöka och testa tillämpade komplementaritetsproblem (LCP, MCP, MPEC, EPEC),
- Tillämpa olika varianter av dekompositionsalgoritmer,
- Förstå olika tillämpningar av ovanstående modeller och lösningsalgoritmer inom elnätsoptimering,
- Undersöka och praktisera ABC i optimeringsmodelleringsprocessen.
Kurslitteratur och förberedelser
Särskild behörighet
Ingen särskild behörighet.
Rekommenderade förkunskaper
Generell kunskap om variabelanalys, sannolikhetslära och optimeringsteori krävs.
Utrustning
Nödvändig programvara kommer att introduceras i början av kursen.
Kurslitteratur
- Föreläsningsmaterial och relevanta forskningsartiklar
- R. Baldick, Applied Optimization Formulation and algorithms for Engineering Systems, Cambridge University Press, 2006
Examination och slutförande
När kurs inte längre ges har student möjlighet att examineras under ytterligare två läsår.
Betygsskala
P, F
Examination
- EXA1 - Examination, 10,0 hp, betygsskala: P, F
Examinator beslutar, baserat på rekommendation från KTH:s handläggare av stöd till studenter med 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.
Examinationen baseras på ett seminarium, flera kursprojekt, en forskningartikel och en slutrapport. Varje student ska ge en seminariepresentation av ett utvalt ämne som är relevant för kursen. Under kursen kommer flera projekt att definieras där studenterna praktiserar olika optimeringsmodeller och mjukvarupaket. Dessutom kommer en forskningsartikel baserat på det valda ämnet att skrivas av studenten. Den slutgiltiga examinationen baseras på studentens slutrapport.
Övriga krav för slutbetyg
En slutrapport som inkluderar seminariepresentation, kursprojekt och forskningartikel.
Möjlighet till komplettering
Ingen information tillagd
Möjlighet till plussning
Ingen information tillagd
Examinator
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
Kursrum i Canvas
Registrerade studenter hittar information för genomförande av kursen i kursrummet i Canvas. En länk till kursrummet finns under fliken Studier i Personliga menyn vid kursstart.
Ges av
Huvudområde
Denna kurs tillhör inget huvudområde.
Utbildningsnivå
Forskarnivå
Påbyggnad
Ingen information tillagd
Kontaktperson
Mohammad Reza Hesamzadeh (mrhesa@kth.se)
Övrig information
Den detaljerade kursplanen är bifogad till detta formulär.