SF2822 Tillämpad ickelinjär optimering 7,5 hp

• Utbildningsnivå

  Avancerad nivå

• Kursnivå (A-D)

  D

• Huvudområde

  Matematik
  

• Betygsskala

  A, B, C, D, E, FX, F

• Länk till hemsida

• Kurssida på KTH Social

Lärandemål

Kursens övergripande mål är dels att studenten ska behärska modeller, metoder och teori för olika varianter av ickelinjär optimering, dels att studenten ska kunna modellera och mha befintlig programvara lösa realistiska ickelinjära optimeringsproblem, samt presentera resultaten muntligt och skriftligt.

Mätbara mål

Efter genomgången kurs ska studenten kunna:

• Förklara hur steepest-descentmetoden, konjugerade gradientmetoden och kvasi-Newtonmetoder fungerar för att minimera en strikt konvex kvadratisk funktion.
• Förklara hur active-set-metoder för konvexa kvadratiska programmeringsproblem fungerar.
• Förklara hur sekvensiella kvadratiska programmeringsmetoder fungerar.
• Förklara hur primal-duala inrepunktsmetoder för kvadratiska och ickelinjära programmeringsproblem fungerar.
• Utgående från en tillrättalagd problembeskrivning formulera ett ickelinjärt programmeringsproblem och lösa det med hjälp av det modelleringsspråk som används i kursen.
• Tolka svaren i de lösta tillrättalagda verkliga problem med hjälp av fundamentala begrepp som känslighetsanalys.
• Under lämpliga förutsättninga kunna härleda optimalitetsvillkor för ickelinjära optimeringsproblem.
• Använda lämpliga optimalitetsvillkor för att avgöra om en given punkt är en lokal, eller till och med global, minpunkt till ett givet ickelinjärt programmeringsproblem.
• Kunna redogöra för om erhållen lösning till det tillrättalagda problemet är en lokal eller global minpunkt beroende på egenskaper hos problemfunktionerna.
• Beskriva vad relaxeringar är

Studenter som tillgodogjort sig kursen väl ska dessutom kunna:

• I tillämpliga fall kunna avgöra kvalitet hos lösningar till problem genom att relatera till konvexa relaxerade problem.
• Redogöra för hur kvasi-Newtonmetoder för ickelinjära programmeringsproblem fungerar. Ge exempel på hur sekvensiella kvadratisk programmeringsmetoder och inrepunktsmetoder kan modifieras för ickekonvexa problem samt ange grundläggande egenskaper hos meritfunktioner i sådana metoder.
• Definiera semidefinita programmeringsproblem samt förklara hur primal-duala interpunktsmetoder för semidefinit programmering fungerar.

Kursens huvudsakliga innehåll

Teori och metoder:

Ickelinjär optimering utan bivillkor: optimalitetsvillkor, Newtonmetoder, kvasi-Newtonmetoder, konjugerade gradientmetoder, ickelinjära minsta-kvadratproblem. Ickelinjär optimering med bivillkor: optimalitetsvillkor, kvadratisk programmering, sekvensiell kvadratisk programmering, barriärmetoder, primal-duala inrepunktsmetoder. Semidefinit programmering med inrepunktsmetoder. Konvexitet och konvexa relaxeringar.

Projektuppgifter:

Denna del av kursen är uppbyggd kring praktisk optimeringsmodellering och problemlösning. Här ska man formulera optimeringsproblem, tillämpa sina metodkunskaper och lösa problemen med befintlig optimeringsprogramvara. Detta genomförs i form av projekt i mindre grupper. Ett viktigt inslag är samarbete inom gruppen samt muntlig och skriftlig presentation av resultaten.

Behörighet

Allmänt:

150 hp inklusive 28 hp inom matematik, 6 hp inom matematisk statistik och 6 hp inom optimeringslära. Engelska B.

Mer precist för KTH-studenter:

Avklarade kurser i en- och flervariabelanalys, linjär algebra, differentialekvationer, matematisk statistik, numerisk analys, optimeringslära. En avklarad fortsättningskurs i numerisk analys är en fördel.

Litteratur

Anges vid kursstart. Preliminär kurslitteratur:

Linear and Nonlinear Programming av S.G.Nash och A.Sofer, McGraw-Hill, samt kompletterande material från institutionen.

Examination

• PRO1 - Projektuppgift 1, 1,5 hp, betygsskala: A, B, C, D, E, FX, F
• PRO2 - Projektuppgift 2, 1,5 hp, betygsskala: A, B, C, D, E, FX, F
• TEN1 - Tentamen, 4,5 hp, betygsskala: A, B, C, D, E, FX, F

Krav för slutbetyg

En skriftlig tentamen (TEN1; 4,5 hp).
Projektuppgifter (PRO1; 3 hp).

Ges av

SCI/Matematik

Examinator

Anders Forsgren <andersf@kth.se>

Versionsinformation

Kursplan giltig från och med VT11.
Examinationsinformation giltig från och med HT07.