KursPM: 5B1760 Linjär och kvadratisk optimering, ht 2003

KursPM: 5B1760 Linjär och kvadratisk optimering, 4p, ht 2003

Examinator och föreläsare

Krister Svanberg (krille@math.kth.se), rum 3704, Lindstedtsvägen 25, tel. 790 71 37.

Övningsledare

Tove Gustavi (gustavi@math.kth.se), rum 3736, tfn 790 6294.
Johan Karlsson (johan.karlsson@math.kth.se), rum 3737, tfn 790 7507.
Mats Werme (werme@math.kth.se), rum 3713, tfn 790 8433.
Stefan Almér (almer@math.kth.se), rum 3713, tfn 790 7504.

Kursmaterial

Linear Algebra and its Applications, av Gilbert Strang. Säljs på KTH:s bokhandel.
Exempelsamling. Säljs på matematikinstitutionens studentexpedition, Lindstedtsvägen 25.
Kompletteringar till kursboken, av Krister Svanberg. Säljs också på studentexpeditionen.
Hemuppgifter i Matlab. Delas ut under kursens gång.
Rekommenderas: Användarhandledning för MATLAB. Säljs på NADA:s studentexp., Lindstedtsv.3.

Examination

Kursen examineras i de bägge momenten TEN1 och HEM1, dvs tentamen och hemuppgifter.

Tentamen (TEN1, 3p)
Tentamen består av 5 uppgifter som vardera kan ge 10 poäng. Godkänd blir man på 24 poäng.
Den första uppgiften, som är kopplad till hemtalen enligt nedan, är tredelad med delpoängen 4+4+2.
Vid tentamen delas en kortfattad formelsamling ut. Inga andra hjälpmedel är tillåtna.
Första tentamenstillfälle är onsdagen den 17 december 2003 kl 14-19.

Hemuppgifter (HEM1, 1p)
4 st frivilliga hemuppgifter i Matlab delas ut under kursens gång.
Tillsammans kan dessa ge upp till 12 hemtalspoäng.
Den som erhåller sammanlagt X hemtalspoäng blir belönad enligt följande:

X < 4 ger ingen belöning.
4 =< X =< 7 medför att deluppgift 1.a ej behöver lösas på tentamen.
De 4 tentamenspoängen för denna deluppgift erhålls ändå.
8 =< X =< 9 medför att deluppgifterna 1.a och 1.b ej behöver lösas på tentamen.
De 8 tentamenspoängen för dessa deluppgifter erhålls ändå.
10 =< X medför att uppgift 1 ej behöver lösas på tentamen.
De 10 tentamenspoängen för denna uppgift erhålls ändå.
Den student som erhåller minst 8 hemtalspoäng blir inrapporterad godkänd på momentet HEM1.
Den student som INTE erhåller minst 8 hemtalspoäng blir ändå inrapporterad godkänd på
momentet HEM1 den dag han/hon blir godkänd på tentamen och får momentet TEN1 inrapporterat.

SISTA INLÄMNINGSTIDPUNKT för de olika hemuppgifterna:

Uppgift 1: Torsdag 6/11 kl 12.00
Uppgift 2: Måndag 17/11 kl 16.00
Uppgift 3: Torsdag 27/11 kl 12.00
Uppgift 4: Måndag 8/12 kl 17.00

Preliminärt schema för föreläsningarna

Typ	Datum	Tid	Sal	Ämne
F1.	27/10	14-16	V2	Exempel på optimeringsproblem. Gauss-Jordan som matrisfaktorisering. Häftet: kapitlen 1 och 2. Boken: 1.1-1.4, 1.6.
F2.	28/10	15-17	D2	Underrum i R^n. De fyra fundamentala underrummen till en matris. Häftet: kap 3+7+8+9. Boken: 2.1-2.4.
F3.	30/10	10-12	D2	LP-formuleringar. Grafisk lösning av små LP-problem. Algebraisk identifikation av hörnlösningar. Häftet: 4.1-4.6. Boken: 8.1.
F4.	3/11	14-16	V2	Simplexmetoden för att lösa LP-problem, inklusive geometrisk tolkning. Häftet: 4.7-4.14. Boken: 8.2 t.o.m rad 9 på sid 397.
F5.	4/11	15-17	D2	Dualitetssatsen och komplementaritetssatsen för LP. Häftet: kap 5. Boken: 8.3 t.o.m rad 12 på sid 416.
F6.	6/11	10-12	F2	LU-faktorisering. Positivt definita matriser och LDLT-faktorisering. Häftet: kap 6 och 10. Boken: 1.5, 6.1-6.2.
F7.	10/11	14-16	V2	Minimering av kvadratiska funktioner, inklusive MK-problem. Häftet: kap 11, 13.1-13.5. Boken: 3.3 och sid 347-348.
F8.	11/11	15-17	D2	Minimering av kvadratiska funktioner under linjära bivillkor. Häftet: kap 12.
F9.	13/11	10-12	V2	Min-normlösning till MK-problem. Pseudoinversen till en matris. Häftet: 13.6-13.8 och kapitel 14.
F10.	17/11	14-16	V2	Ortogonala projektioner och matriser. Gram-Schmidt och QR-faktorisering. MK-problem igen. Häftet: kap 15 och 16. Boken: 3.1-3.4.
F11.	18/11	15-17	D2	Spektralfaktorisering av symmetriska matriser. Minimering av kvadratisk form under normvillkor. Häftet: kap 17. Boken: 5.1-5.2, sid 296 och 349.
F12.	24/11	14-16	V2	Singulärvärdesfaktorisering. Pseudoinversen igen. Häftet: kap 18. Boken: Appendix A.
F13.	27/11	10-12	V2	Uppsamling och tillämpningar.
F14.	1/12	14-16	V2	Kompletteringar och repetition.

Preliminärt schema för övningarna

Typ	Datum, Tid, Sal (gr 1-2)	Datum, Tid, Sal (gr 3-4)	Ämne
Ö1.	29/10 kl 10-12, B23,B24	29/10 kl 15-17, B23,B24	Gauss-Jordan som matrisfaktorisering. Partitionerade matriser.
Ö2.	30/10 kl 13-15, M21,M22	30/10 kl 15-17, M21,M22	Baser till de fyra fundamentala underrummen. LP-formuleringar.
Ö3.	5/11 kl 10-12, B23,B24	5/11 kl 15-17, B23,B24	Simplexmetoden.
Ö4.	6/11 kl 13-15, M21,M22	6/11 kl 15-17, M21,M22	Dualitet och komplementaritet vid LP.
Ö5.	12/11 kl 10-12, L41,L42	12/11 kl 15-17, L43,L44	LU-faktorisering. Positivt definita matriser och LDLT-faktorisering. MK-problem.
Ö6.	13/11 kl 13-15, M21,M22	13/11 kl 15-17, M21,M22	Minimering av kvadratiska funktioner under linjära bivillkor.
Ö7.	19/11 kl 10-12, L31,L44	19/11 kl 15-17, L31,L43	Min-normlösning till MK-problem. Pseudoinverser.
Ö8.	26/11 kl 10-12, B24,L31	26/11 kl 15-17, L21,L43	Gram-Schmidt och QR-faktorisering. Ortogonala projektioner.
Ö9.	27/11 kl 13-15, M23,M24	27/11 kl 15-17, M23,M24	Spektralfaktorisering. Minimering av kvadratisk form under normvillkor.
Ö10.	3/12 kl 10-12, M21,M22	3/12 kl 15-17, M22,M23	Singulärvärdesfaktorisering och pseudoinverser.

Välkomna till kursen!

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

5B1760 Linjär och kvadratisk optimering

Modifierad: oktober 2003 av Krister Svanberg, krille@math.kth.se.