Chalmers tekniska högskola/Göteborgs universitet Optimeringslära Matematiska institutionen Kursinformation 2002 Michael Patriksson 17 januari 2002

TMA946 Tillämpad optimeringslära TM, 5 p. MAN280 Optimeringslära, 5 p.

Kursen utgör en grundläggande kurs i optimeringslära.

Kursen avser att ge

(I) en kännedom om vissa viktiga klasser av optimeringsproblem och olika tillämpningsområden för optimeringsmodeller och -metodik;

(II) övning i att beskriva relevanta delar av verkliga problem i en matematisk modell;

(III) kunskap om och förståelse för den grundläggande matematiska teorin på vilken optimalitetskriterier bygger;

(IV) exempel på optimeringsmetoder som kan utvecklas från denna teori för att lösa praktiska optimeringsproblem.

FÖRELÄSARE/EXAMINATOR: Michael Patriksson, docent, Matematiskt Centrum, rum 5218; tel: 772 3529; e-post: mipat@math.chalmers.se

FÖRELÄSARE: Ann-Brith Strömberg, forskarassistent, Matematiskt Centrum, rum 5266; tel: 772 5372; e-post: anstr@math.chalmers.se

FÖRELÄSARE: Tuomo Takkula, Matematiskt Centrum, rum 2442; tel: 772 1052; e-post: tuomo@cs.chalmers.se

LEKTIONSASSISTENT: Fredrik Altenstedt, doktorand, Matematiskt Centrum, rum 5267; tel: 772 5379; e-post: alten@math.chalmers.se

LEKTIONSASSISTENT: Anton Evgrafov, doktorand, Matematiskt Centrum, rum 5217; tel: 772 5373; e-post: toxa@math.chalmers.se

Kurspresentation

INNEHÅLL: Kursen är bred till ämnesvalet men har sin huvudsakliga inriktning mot optimeringsproblem i kontinuerliga variabler, och kan där indelas i två huvuddelar efter två viktiga områden:

Linjärprogrammering: Linjära optimeringsmodeller, linjärprogrammeringens teori och geometri, simplexmetoden, dualitet, inre-punktsalgoritmer, känslighetsanalys, modelleringsspråk;

Icke-linjär programmering: Icke-linjära optimeringsmodeller, konvexitetsteori, optimalitetsvillkor, sökmetoder för optimeringsproblem med/utan bivillkor, relaxeringar, straffunktioner, Lagrange-dualitet.

En kortare översikt ges också av tre andra viktiga problemområden inom optimeringslära, heltalsoptimering, nätverksoptimering och stokastisk optimering.

ORGANISATION: Föreläsningar, lektioner, datorlaborationer och projektuppgift.

KURSLITTERATUR:

(i) Linear and Nonlinear Programming (bok; S G Nash och A Sofer, 1996) [Cremona]

     Errata: http://www.gmu.edu/departments/ore/books/naso/ns-errata.html.

(ii) Utdelat material i form av kopior ur böcker

(iii) Exempelsamling i tillämpad optimering [säljes av institutionen]

KURSFORDRINGAR: Kursinnehållet definieras av litteraturhänvisningarna i undervisningsplanen nedan.

EXAMINATION:

• Skriftlig tentamen (första tillfälle 11/3 e.m., M-huset, omtentamen 29/5 f.m., Vhuset, och i augusti)

• Projektuppgift

• Två laborationer

SCHEMA:

Föreläsningar: Normalt tisdagar 13.15–15.00 och torsdagar 8.00–9.45 i hörsalen, MDhuset. Undantag: föreläsning 1 och 2 ges 22/1 13.15–17.00; ingen föreläsning 12/2 (Charm). Föreläsningarna ges på engelska.

Lektioner: I två parallella grupper; undervisning på svenska (Fredrik) normalt tisdagar 15.15–17.00 och torsdagar 10.00–11.45 i MD6, undervisning på engelska (Anton) normalt tisdagar 15.15–17.00 och torsdagar 10.00–11.45 i MD9. Undantag: ingen lektion 22/1 (se Föreläsningar ovan); ingen lektion 12/2 (Charm).

Projektet: En tid är bokad i datorsalar för arbete med projektet då lärare är närvarande, 18/2 (salar: B, C, H), klockan 17.15–21.00. (Det är inte obligatorisk närvaro.) I övrigt sker arbetet med projektet enskilt. Sista datum för inlämning av modell: 31/1. Utdelning av korrekt AMPL-modell: 8/2. Sista datum för inlämning av skriftlig rapport: 22/2.

Laborationer: Vardera laboration har en schemalagd tid i datorsalar då lärare är närvarande, 11/2 respektive 28/2 (salar vid båda tillfällena: B, C, H), i båda fall klockan 17.15–21.00 (sal H är bokad från klockan 19.00). (Det är inte obligatorisk närvaro.) Vi räknar med att laborationerna kan utföras enskilt. Sista datum för inlämning av en skriftlig rapport: en vecka efter vardera laboration.

Information om projektuppgift och laborationer, ges senare på kursens hemsida,

http://www.md.chalmers.se/~mipat/TOkurs.html.

Denna kursinformation och annat utdelat material finns också på kursens hemsida.

UNDERVISNINGSPLAN FÖRELÄSNINGAR:

\underline{Fö 1} (22/1) Kurspresentation. Inledande ämnesbeskrivning. Applikationer. Modellering, problemanalys. Klassificering. (i): Kapitel 1 (ii): Kursinformationen (detta dokument); ett häfte med tillämpningar

\underline{Fö 2} (22/1) Linjärprogrammering. Lösning av ett enkelt linjärt problem med hjälp av DUPLO. Fundamenta. Lokal och global optimalitet. Konvexa mängder och funktioner. (i): Kapitel 4.1–2, 2.2–3 (ii): “Introduktion till linjärprogrammering”

\underline{Fö 3} (24/1) Linjärprogrammering. Problembeskrivning. Polyedriska mängder. Baslösningar och extrempunkter (algebra kontra geometri i linjärprogrammering). Representationssatsen. Simplexmetoden, inledning. (i): Kapitel 4.3–4, 5.1–2

\underline{Fö 4} (29/1) Linjärprogrammering. Simplexmetoden. Matris- och tablåform. Fas 1 och 2. Degeneration. Terminering. Reviderad simplex. Komplexitet. (i): Kapitel 5.3–5.6, 9.3

\underline{Fö 5} (31/1) Linjärprogrammering. Optimalitet. Dualitet. Känslighetsanalys. (i): Kapitel 6.1–4, 7.4–7.6

\underline{Fö 6} (5/2) Linjärprogrammering. Modelleringsspråk. Programvara. Nätverksoptimering. Grafteori. Tillämpningar. Unimodularitet. Baser och träd. Minkostnadsflödesproblemet. Simplexmetoden i nätverk. Transportproblemet. Billigaste vägproblemet. Maxflöde-min-snittsteoremet. Minimalt uppspännande träd. (i): Kapitel 8.1–5 (ii): Om tillämpningar och algoritmer för vissa flödesproblem

\underline{Fö 7} (7/2) Heltalsprogrammering. Tillämpningar. Modellering. Implicit uppräkning. Heuristiker. (ii): Om heltalsprogramming

\underline{Fö 8} (14/2) Obegränsad optimering. Optimalitet. Sökmetoder. Sökriktningar. Linjesökningar. Avbrottskriterier. Brantaste lutningsmetoden. (i): Kapitel 10.1–5, 11.4.1, 11.5, 11.1–2

\underline{Fö 9} (19/2) Obegränsad optimering. Newtonmetoder. Derivata-fria metoder för obegränsad optimering. Begränsad optimering. Primala optimalitetsvillkor. (i): Kapitel 11.3, 12.2–3, 12.6, 11.4.3, 14.1 (ii): Övrigt material om bl.a. derivata-fria metoder

\underline{Fö 10} (21/2) Begränsad optimering. Primala algoritmer. Gradientprojektion. Duala optimalitetsvillkor (KKT), inledning. (i): Kapitel 14.2–7 (ii): Om primala algoritmer

\underline{Fö 11} (26/2) Begränsad optimering. Farkas Lemma. Fritz Johns villkor. Karush–Kuhn– Tucker-villkoren. Lagrangedualitet, inledning. (i): Kapitel 14.2–7, 14.8.2–3 \underline{Fö 12} (28/2) Begränsad optimering. Lagrangedualitet. Svag och stark dualitet. Dualitetsgap. Ickedifferentierbar optimering. (i): Kapitel 14.8.2–3 (ii): Om algoritmer för Lagrangeduala problem

\underline{Fö 13} (5/3) Begränsad optimering. Straff- och barriärmetoder. Inre punktsmetoder för linjärprogrammering, orientering. Generaliserad reducerad gradient (GRG), orientering. Utvidgade Lagrangianen. (i): Kapitel 16.1–3, 17.3–4, 16.5, 15.5, 16.6 (ii): Om algoritmer för begränsad optimering

\underline{Fö 14} (7/3) Optimering under osäkerhet. En översikt av kursen. (ii): Om applikationer och algoritmer för optimering under osäkerhet.

UNDERVISNINGSPLAN LEKTIONER:

Listan omfattar fler uppgifter än de som hinnes med. De som vi räknar med skall hinnas med anges på kursens hemsida efter hand som kursen framskrider; de övriga är rekommenderade hemuppgifter.

\underline{Le 1} (24/1) Modellering. Geometrisk lösning av linjära optimeringsproblem. (i): 4.1.1–2 (iii): 2.1.1–2.1.13, 2.4.5–2.4.7, 3.1.1–3.1.7

\underline{Le 2} (29/1) Konvexitet. (i): 2.2.3, 4, 6, 8, 9; 2.3.1–6, 8–17 (iii): 1.1.29–1.1.41

\underline{Le 3} (31/1) Simplexmetoden. Geometri, baser. (i): 4.2.1–6; 4.3.1–3, 6, 10; 4.4.6–8 (iii): 2.4.4, 2.3.1–2.3.3, 2.3.18, 2.3.24

\underline{Le 4} (5/2) Simplexmetoden. Matrisform. Tablåform. Fas 1 och 2. (i): 5.2.2–6, 8; 5.3.4–5; 5.4.2, 4; 5.5.1, 2(a), 3(a), 4, 6–7, 10 (iii): 2.4.1–2.4.3, 2.3.5–2.3.9, 2.3.25, 2.4.19

\underline{Le 5} (7/2) Simplexmetoden. Optimalitet. Dualitet. Känslighetsanalys. (i): 6.1.1–7; 6.2.1–5, 7, 9, 11–12, 15; 5.2.8; 6.3.1–2, 4–9; 6.4.1–3; 7.5.3–5 (iii): 2.2.1–2.2.5, 2.3.10–2.3.13, 2.2.6–2.2.9, 2.4.9, 2.3.15

\underline{Le 6} (14/2) Nätverksoptimering. Modellering. Nätverksalgoritmer. (i): 8.2.1–3, 6–12; 8.3.1, 3–5, 7–8 (iii): 4.2.1, 4.2.6, 4.2.21

\underline{Le 7} (19/2) Heltalsoptimering. Modellering. Implicit uppräkning. Heuristiker. (ii): Om heltalsoptimering

\underline{Le 8} (21/2) Obegränsad optimering. (i): 10.2.1–7, 10–12, 17–18; 10.5.2–6, 9; 11.4.7–9; 11.1.1–2, 6–7, 10; 10.3.2–4, 6, 12 (iii): 3.3.1–3.3.11, 3.2.1

\underline{Le 9} (26/2) Obegränsad optimering, fortsättning.

\underline{Le 10} (28/2) Optimalitetsvillkor. (i): 14.2.4–6; 14.4.4; 14.5.3 (iii): 3.5.1–3.5.7, 3.5.20–3.5.22, 3.5.26

\underline{Le 11} (5/3) Lagrangedualitet. (i): 14.8.4–8, 10 (iii): 3.4.1

\underline{Le 12} (7/3) Straff- och barriärmetoder. Repetition. (i): 16.2.1–4; 16.5.1–2; 15.5.1–3, 5; 16.6.1, 5–6 (iii): 6.1.1–6.1.4