TMA4180 OPTIMERINGSTEORI

(Optimization Theory)

Våren/Spring 2007

NEWS (always on top)

Denne siden er nå strippet ned og vil ikke bli oppdatert.

Neste års hjemmeside er snart operativ.

LECTURERS

The course may be lectured in English. Textbooks and notes are all in English.

(Ja, kurset kan bli forelest på engelsk, men bare hvis det er behov for det!)

Harald E. Krogstad, room 1146,
Sentralbygg II, tel. 73 59 35 36,
e-post: harald.krogstad@math.ntnu.no

KURSETS INNHOLD OG IDE

Kurset tar sikte på å innøve fundamentale teknikker og metoder innen optimering. Målet er å gi studentene kjennskap til ulike optimeringsproblemer, de vanligste analyseteknikkene og algoritmene. Det vil legges vekt på geometrisk, matematisk forståelse heller enn algoritmiske detaljer, men slik at numeriske programpakker kan anvendes på en intelligent og kvalitetsbevisst måte. Siste del av kurset vil bli en innføring i variasjonsregning. Pensumvalget kan i noen grad være avhengig av deltakernes interesser, og det kan komme på tale å benytte gjesteforelesere for spesielle tema.

Stoffet krever noe bakgrunn i lineær algebra og lineær analyse. Dette er f.eks. dekket av kurset TMA4145 Lineære metoder, men er ikke et helt ufravikelig krav siden bøkene også gir nødvendig bakgrunnskunnskap.

Lineær programmering er godt dekket i andre kurs og vil ikke stå sentralt i dette kurset.

Med en viss rett kan en si at alle problemer lar seg formulere som optimeringsproblemer, og følgelig forekommer optimering i en mengde ulike situasjoner. Økonomi knyttet til produksjon, transport og distribusjon er velkjente eksempler, sammen med regulerings- og kontrollteori. Innen statistikk er optimering en sentral del av maximum likelihood og entropi, samt Bayes-teknikker. Optimal signalbehandling dreier seg om optimal filtrering og koding av signaler. Et ofte forekommende problem i praksis er å tilpasse en komplisert modell til et begrenset sett observasjoner. Dette leder til såkalte inverse problemer der tilleggsinformasjon, ofte i form av vår oppfatning av hva løsningen burde være, legges inn i en funksjonal som så optimaliseres. Variasjonsregning er den tradisjonelle betegnelsen på optimeringsproblemer med funksjoner som variable. I fysikk finnes en rekke prinsipper (f.eks. Huygens prinsipp i optikken og Hamiltons prinsipp i mekanikken) som egentlig er variasjonsproblemer. Variasjonsregning er også grunnlag for kontroll og reguleringsteknikk.

Kurset vil i hovedsak dreie seg om optimalisering av funksjonaler med et endelig antall ukjente. Enhver numerisk optimeringsalgoritme må nødvendigvis ha den formen selv om utgangspunktet er et variasjonsproblem.

Noe du lurer på? Ta kontakt eller se på http://www-fp.mcs.anl.gov/otc/Guide/

For en oversikt over lærebøkene anbefales WEB-sidene:

Numerical Optimization

http://www.amazon.com/exec/obidos/ASIN/0387945113/xq23-20/104-8199134-0514310

INNHOLD (I STORE TREKK)

1. Ikke-lineær optimering uten føringer
        - nødvendige og tilstrekkelige betingelser for ekstremum
        - konvekse funksjoner og mengder
        - litt om optimering i Hilbertrom (projeksjonssaten, beste approksimasjon etc.)
        - algoritmer
        - konvergenshastighet
        - søkemetoder i én dimensjon, amøbe-metoden
        - steepest descent, konjugert gradient og Newtons metoder
        - kvasi-Newton metoder

2. Kort oversikt over lineær optimering
        - reduksjon til standard form og basisløsninger
        - fundamentalteoremet i lineær optimering
        - simplex-metoden

- optimering av nettverksflyt

3. Ikke-lineær optimering med føringer
        - nødvendige og tilstrekkelige betingelser for ekstremum
        - Lagrange-multiplikatorer
        - Kuhn-Tuckers betingelser
        - direkte metoder
        - penalty- og barriere-metoder
        - dualitet
        - Lagrangemetoder

- Inverse problemer

4. Innføring i variasjonsregning
        - optimering av funksjonaler
        - Gâteauxderivert
        - konveks analyse
        - Euler-Lagrange ligningene
        - anvendelser