5B1817 Tillämpad ickelinjär optimering, 5p, 2006/2007

Examinator och föreläsare

Anders Forsgren (andersf@kth.se), rum 3703, Lindstedtsv. 25, tel. 790 71 27.
Mottagningstid: Måndag 10-12. (Eller enligt överenskommelse.)

Övningsledare

Mats Werme (werme@math.kth.se), rum 3712, Lindstedtsv. 25, tel. 790 84 33.
Mottagningstid: Tisdag 10-12 och fredag 13-15. (Eller enligt överenskommelse.)

Kursmaterial

Linear and nonlinear programmering, av S. G. Nash och A. Sofer. McGraw Hill, 1996.
Exempelsamling i tillämpad ickelinjär optimering, 2006/2007. Säljs på institutionens elevexpedition, Lindstedtsv. 25. (Pris 30 kr.)
Några kompletteringar till kursmaterialet i tillämpad ickelinjär optimering, 2006/2007. Säljs på institutionens elevexpedition, Lindstedtsv. 25. (Pris 20 kr.)
Föreläsningsanteckningar i tillämpad ickelinjär optimering 2006/2007. Säljs på institutionens elevexpedition, Lindstedtsv. 25. (Pris 20 kr.)
GAMS, A user's guide. Säljs på institutionens elevexpedition, Lindstedtsv. 25. (Pris 50 kr.) Ytterligare GAMS-dokumentation finns även tillgänglig på nätet.
GAMS. GAMS finns installerat i datorsalarna som tillhör F och MMT. Kan också laddas ner från nätet för användande på egen dator.
Två projektuppgifter delas ut under kursens gång, 6/11 respektive 20/11.

Eventuellt kompletterande lösblad som delas ut under kursens gång ingår också.

Examination

Kursen examineras i två olika moment, projektuppgifter och tentamen. För godkänt i kursen krävs:

Godkänt på projektuppgift 1, obligatorisk närvaro vid redovisningstillfället, måndag 20/11 kl. 13-15 i sal D31.
Godkänt på projektuppgift 2, obligatorisk närvaro vid redovisningstillfället, måndag 4/12 kl. 13-15 i sal D31.
Godkänd tentamen.

Kursanmälan

På grund av kursens projektnatur är det obligatorisk anmälan till kursen senast torsdag 2/11. Anmälningslistor kommer att finnas vid de inledande lektionerna. Varje kursdeltagare ska ange en e-postadress där han eller hon kan nås.

Projektuppgifterna

Projektuppgifterna utförs i grupper, där kursledaren bestämmer gruppindelningen som ändras mellan de båda uppgifterna. Uppgift 1 kan utföras med hjälp av modelleringsspråket GAMS. Uppgift 2 kan väljas mellan en modelleringsuppgift som kan utföras med hjälp av GAMS och en metoduppgift som kan utföras med Matlab. Uppgifterna ska utföras under kursens gång och redovisas vid de ovan nämnda redovisningstillfällena. Därmed är det obligatorisk närvaro vid dessa redovisningstillfällen. För godkänt projekt krävs följande.

Varje grupp ska vid redovisningstillfället lämna in en välskriven rapport som beskriver uppgiften samt gruppens förslag till lösning. Lämpligt ordbehandlingsprogram ska användas. Rapporten ska ligga på en nivå sådan att den vänder sig till en annan kursdeltagare som inte är insatt i gruppens specifika problem.
Vid redovisningstillfället kommer några grupper att göra en muntlig presentation. Denna presentation vänder sig mot de övriga kursdeltagarna, och den ska innehålla beskrivning av uppgiften samt gruppens förslag till lösning. Det ska vara en professionell presentation, dvs oh-bilder eller motsvarande bör användas. Varje grupp som redovisar får 20 minuter till sitt förfogande, där det bör finnas tid för frågor och diskussion. Övriga grupper förväntas ställa frågor och delta i diskussionen.
De grupper som inte redovisar muntligt vid redovisningstillfället ska boka tid för muntlig diskussion med kursledarna. Här gör grupperna ingen presentation, utan dessa diskussioner är i form av en frågestund om 20 minuter, en grupp i taget. Tider kommer att finnas dagarna efter redovisningstillfället.

Vilka grupper som ska göra muntlig presentation meddelas i förväg per e-post (den 13/11 respektive 27/11). Samtidigt anslås då en lista för bokning av tider för muntlig diskussion på avdelningens anslagstavla, Lindstedtsvägen 25, plan 7. Denna lista tas ned i samband med redovisningstillfället (den 20/11 respektive 4/12). Val mellan modelleringsuppgift och metoduppgift till uppgift 2 ska meddelas till examinator senast den 16/11. Vid uteblivet val erhålls en modelleringsuppgift.

På varje projektuppgift ges ett betyg som är antingen underkänt eller godkänt med gradering 3, 4 eller 5. Här vägs såväl den matematiska behandlingen av problemet som rapporten och den muntliga redovisningen eller diskussionen in. Projektuppgifterna består av basuppgifter och extrauppgifter. Nöjaktig behandling av basuppgifterna ger normalt betyg 3 och nöjaktig behandling av basuppgifterna och extrauppgifterna ger normalt betyg 4. För högre betyg krävs korrekt och mycket väl genomförd uppgift. I normalfallet får hela gruppen samma betyg.

Varje grupp ska själv lösa sin uppgift. Diskussion mellan grupperna om uppgiftstolkningar med mera uppmuntras, men varje grupp ska arbeta självständigt utan att använda andras lösningar. Alla grupper kommer inte att ha samma uppgifter.

Tentamen

Tentamen består av fem uppgifter och ger maximalt 50 poäng. På tentamen ges betyg underkänt eller godkänt med gradering 3, 4 och 5. För godkänt på tentamen krävs preliminärt 24 poäng. Tillåtna hjälpmedel är penna och radergummi, plus institutionens miniräknare som delas ut vid tentamenstillfället.

Den som får 21, 22 eller 23 poäng på tentamen kan få komplettera till betyg 3. Den som vill komplettera ska kontakta examinator. För godkänd komplettering krävs att två uppgifter löses på egen hand: dels en teoriuppgift bland de utdelade och dels en annan uppgift från tentamen. Examinator väljer dessa uppgifter individuellt. Lösningar ska lämnas in skriftligt till examinator och även redovisas muntligt i samband med inlämnandet. Komplettering ska ske inom tre veckor från att tentamensresultatet anslagits.

Ordinarie tentamenstillfälle är onsdag 20 december kl. 14.00-19.00.

Betyg

Betyget bestäms av projektuppgifterna och tentamen tillsammans enligt ( (betyg på proj 1) + (betyg på proj 2) + 3 * (betyg på tentamen) )/5, då projekten omfattar 2 poäng och tentamen omfattar 3 poäng. Det ger följande tabell:

Slutbetyg	Summa 6 på projekten	Summa 7 på projekten	Summa 8 på projekten	Summa 9 på projekten	Summa 10 på projekten
3 på tentamen	3	3	3	4	4
4 på tentamen	3	4	4	4	4
5 på tentamen	4	4	5	5	5

Preliminärt schema

Typ	Dag	Datum	Tid	Sal	Ämne
F1.	Ons	25/10	8-10	D31	Introduktion till kursen. Ickelinjära optimeringsmodeller. (ps) (pdf)
F2.	Tor	26/10	13-15	E35	Optimalitetsvillkor för problem med linjära bivillkor. (ps) (pdf)
F3.	Mån	30/10	13-15	D31	Optimalitetsvillkor för problem med ickelinjära bivillkor. (ps) (pdf)
Ö1.	Tis	31/10	8-10	D41	Optimalitetsvillkor.
F4.	Ons	1/11	8-10	D41	Metoder för problem utan bivillkor. (ps) (pdf)
F5.	Tor	2/11	10-12	E32	Metoder för problem utan bivillkor, forts. (ps) (pdf)
P1.	Mån	6/11	13-15	D31	Introduktion till GAMS.
Ö2.	Tis	7/11	8-10	D41	Metoder för problem utan bivillkor.
F6.	Ons	8/11	8-10	D41	Kvadratisk programmering med likhetsbivillkor. (ps) (pdf)
F7.	Tor	9/11	10-12	D41	Kvadratisk programmering med olikhetsbivillkor. (ps) (pdf)
P2.	Mån	13/11	13-15		Kursledarna finns anträffbara på sina rum.
F8.	Tis	14/11	8-10	D41	Kvadratisk programmering med olikhetsbivillkor, forts. (ps) (pdf)
Ö3.	Ons	15/11	8-10	D41	Kvadratisk programmering.
F9.	Tor	16/11	10-12	D31	Sekvensiell kvadratisk programmering. (ps) (pdf)
P3.	Mån	20/11	13-15	D31	Redovisning av projektuppgift 1.
Ö4.	Tis	21/11	8-10	D41	Sekvensiell kvadratisk programmering.
F10.	Ons	22/11	8-10	D31	Inrepunktsmetoder. Straff- och barriärmetoder. (ps) (pdf)
Ö5.	Tor	23/11	10-12	D31	Inrepunktsmetoder. Straff- och barriärmetoder.
P4.	Mån	27/11	13-15		Kursledarna finns anträffbara på sina rum.
F11.	Ons	29/11	8-10	D31	Semidefinit programmering. (ps) (pdf)
Ö6.	Tor	30/11	10-12	D31	Semidefinit programmering.
P5.	Mån	4/12	13-15	D31	Redovisning av projektuppgift 2.
F12.	Ons	6/12	10-12	D34	Semidefinit programmering. Repetition
Ö7.	Tor	7/12	10-12	E35	Repetition.

Välkomna till kursen!

Kursinnehåll avseende teori och metoder

Ickelinjär programmering utan bivillkor
Grundläggande teori, speciellt optimalitetsvillkor.
Linjesökningsalgoritmer, steepest descent, Newtons metod.
Konjugerade riktningar och konjugerade gradientmetoden.
Kvasi-Newtonmetoder.
(Kapitel 10.1-10.5, 11.1-11.3, 12.1-12.2 samt 12.4 i Nash och Sofer.)
Ickelinjär programmering med bivillkor
Grundläggande teori, optimalitetsvillkor, lagrangemultiplikatorer och känslighetsanalys.
Kvadratisk programmering.
Primala metoder, speciellt ``active-set methods''.
Straffmetoder och barriärmetoder, speciellt primal-duala metoder.
Duala metoder, lokal dualitet, separabla problem.
Lagrangemetoder, speciellt sekventiell kvadratisk programmering.
(Kapitel 3 i Nash och Sofer. Kapitel 14-16 i Nash och Sofer, utom 14.8.1, 14.9, 15.5, 15.6, 16.4, 16.6.1. Kapitel 9.6, 17.1, 17.2, 17.4 i Nash och Sofer. Separat material i kompletteringsbunten om sekvensiell kvadratisk programmering.)
Semidefinit programmering
Grundläggande teori.
(Separat artikel i kompletteringsbunten. Endast grundläggande begrepp ingår.)

Kursinformation finns på www, adress http://www.math.kth.se/optsyst/studinfo/5B1817.

5B1817 Tillämpad ickelinjär optimering

av Anders Forsgren.