Doktorandkurs i olinjär optimering

Nyckelord:

Olinjär optimering med eller utan bivillkor, optimalitetsvillkor, iterativa algoritmer, konvergensanalys, dualitet, numeriska metoder

Vem bör läsa kursen?

Kursen riktar sig till alla studenter i högre årskurs och doktorander med tillräckliga förkunskaper inom analys, linjär algebra och kontinuerlig optimering och som är intresserade av att fördjupa sina kunskaper inom teorin för olinjär optimering och klassiska såväl som moderna metodansatser.

Tid:

Höstterminen 1999

Omfattning:

Sex poäng inom forskarutbildningen

Kursstart

Onsdagen den 8 september klockan 10.00 i sal MD9

Undervisningsschema:

Onsdagar klockan 10.00-11.45 i sal ?.

Första två veckorna är dock schemat följande:
15 september klockan 15.15-17.00 i sal S1
22 september klockan 15.15-17.00 i sal S2

Lärare:

Axel Ruhe (numerisk analys), tel: 772 10 96, e-post: ruhe@cs.chalmers.se

Michael Patriksson (tillämpad matematik), tel: 772 35 29, e-post: mipat@math.chalmers.se

Kurslitteratur:

Dimitri P. Bertsekas: Nonlinear Programming
Athena Scientific, Belmont, MA, 1995
ISBN 1-886529-14-0

Boken köpes t.ex. via Amazon (www.amazon.com) till priset $79.

Boken är pedagogiskt upplagd och lämpar sig särskilt väl för självstudier.

Därutöver kommer det att delas ut kopior av forskningsartiklar, speciellt för projektuppgifterna.

Kursinformation:

Undervisningstillfällena ägnas framför allt åt att ge en vägledning till eget inhämtande av kursmaterialet, men kan också komma att användas till en mer detaljerad genomgång av delar ur kursmaterialet.

Vid särskilda tillfällen redovisas och diskuteras övnings- och projektuppgifterna.

Övningsuppgifterna, som främst baseras på bokens, är av blandad karaktär, och innehåller uppgifter av repetitionskaraktär (som görs av alla), numeriska beräkningar lämpliga för t.ex. Matlab (som kan delas upp mellan deltagarna) och teoretiska uppgiter med karaktären av specialiseringar/generaliseringar av teorin i kursmaterialet (som också kan delas upp på lämpligt sätt mellan deltagarna).

Till kursen hör ett (eller ett par) projekt vilket syftar till att utveckla och utvärdera en algoritm för lösandet av ett olinjärt optimeringsproblem. Ambitionen är att problemen skall ha praktisk relevans, och uppgiften utförs genom utnyttjande av programvara, i mån av tillgänglighet, eller genom egna implementeringar t.ex. i Matlab. Dessa projekt kan i viss mån väljas efter eget intresse. Projekten utförs normalt i grupper om två deltagare.

Examination:

Godkända övningsuppgifter och projektuppgifter.

Ungefärligt innehåll:

Kapitel 1 (Unconstrained Optimization) (Axel Ruhe): Optimalitetsvillkor, gradientmetoder, minsta kvadratproblem, konjugerade gradientmetoder, konvergensanalys (September månad).
Läsanvisning, uppgifter och projektförslag finns här.
Kapitel 2 (Optimization Over a Convex Set) (Michael Patriksson): Optimalitetsvillkor, gradientprojektionsmetoder, simplicial decomposition, orientering om dekomposition av begränsade optimeringsproblem över Cartesiska produktmängder, konvergensanalys (Oktober månad).
Läsanvisning, uppgifter och projektförslag finns här. (Uppdaterat 991021)
Kapitel 3 (Lagrange Multiplier Theory) (Michael Patriksson): Nödvändiga och tillräckliga villkor för optimalitet, Farkas Lemma, känslighetsanalys (Oktober månad)
Läsanvisning, uppgifter och projektförslag finns här. (Uppdaterat 991021)
Kapitel 4 (Lagrange Multiplier Algorithms) (Axel Ruhe): Barriär- och andra straffunktionsmetoder, sekventiell kvadratisk programmering (SQP), inre-punktsmetoder, konvergensanalys (November månad)
Läsanvisning, uppgifter och projektförslag finns här.
Kapitel 5 (Duality and Convex Programming) (Michael Patriksson): Dualitetsteori, svag och stark dualitet, dualitetsgap (November månad)
Läsanvisning, uppgifter och projektförslag finns här.
Kapitel 6 (Dual Methods) (Gästföreläsare): Icke-differentierbar optimering, subgradientmetoder, dual ascent, ergodicitet, dekomposition/koordination (December månad)
Läsanvisning, uppgifter och projektförslag finns här.