Hoppa till huvudinnehållet
Till KTH:s startsida Till KTH:s startsida

FEG3324 Tillämpad optimering och matematiska dekompositioner 10,0 hp

Administrera Om kursen

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. 

Kursomgångar saknas för aktuella eller kommande terminer.
Rubriker med innehåll från kursplan FEG3324 (VT 2023–) är markerade med en asterisk ( )

Innehåll och lärandemål

Kursupplägg

Föreläsningar (15), gästföreläsningar (3), seminarier samt avslutande forskningsartikel.

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

  1. Föreläsningsmaterial och relevanta forskningsartiklar
  2. 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

Profile picture Mohammad Reza Hesamzadeh

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

EECS/Elkraftteknik

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.

Forskarkurs

Forskarkurser på EECS/Elkraftteknik