Behörighetskrav

Kandidatexamen inklusive matematik 20 p/30 hp, Programmeringsteknik NV2 och Beräkningsvetenskap NV2. Alternativt inom datavetenskapliga programmet Algoritmer och datastrukturer DV1, Teknisk databehandling DV1, 10 p/15 hp och Beräkningsvetenskap NV2, 5 p/7,5 hp eller motsvarande.

Mål

För godkänt betyg ska studenten kunna

• formulera fundamentala planerings- och resursallokeringsproblem som linjära program;
• lösa små linjära program grafiskt;
• förklara och tillämpa grundläggande begrepp inom optimeringsläran, t ex konvexitet, baslösningar, extrempunkter, dualitet, konvergenshastighet, Lagrangian, KKT-villkor;
• välja lämplig numerisk metod för olika klasser av optimeringsproblem med utgångspunkt från metodernas fördelar och begränsningar för olika problem;
• välja och använda färdig programvara för lösning av optimeringsproblem

Innehåll

Exempel på optimeringsproblem för operationsanalys och för tekniska, naturvetenskapliga och finansiella tillämpningar. Linjära program (LP), omformuleringar, grafisk lösning. Algebraiska och geometriska egenskaper hos LP. Simplexmetoden för LP, dualitet och komplementaritet för LP.

Konvexitet och optimalitet. Optimalitetsvillkor för obegränsad optimering. Numeriska metoder för obegränsad optimering: Newtons metod, brantaste lutningsmetoden, och kvasi-Newtonmetoder. Metoder för att garantera descentriktnigar, linjesökning. Icke-linjära minstakvadratmetoder (Gauss-Newton, Levenberg-Marquard).

Numerisk beräkning av derivator (finita differenser, automatisk differentiering). Optimalitetsvillkor för optimering med bivillkor (KKT villkor). Kvadratiska program. Orientering om metoder för optimering med bivillkor (straff- och barriärmetoder, sekvensiell kvadratisk programmering).

Undervisning

Föreläsningar och obligatoriska inlämningsuppgifter.

Examination

Skriftligt prov (4,5 hp) samt inlämningsuppgifter (3 hp).