TMA4180 OPTIMERINGSTEORI

(Optimization Theory)

Spring 2005

Denne siden er nå utdatert. Lokale linker vil ikke fungere, og interesserte henvises til den nye Web-siden for våren 2006

http://www.math.ntnu.no/emner/TMA4180/

(denne blir klar ved semesterstart).

 

Some relevant info: 

 

 

 

EXERCISES:

Øvinger

Løsninger

Exercise 1

 

Exercise 2

 

Exercise 3, Matlab Code for CG

 

Exercise 4 NB: Changed sign in Biggs function 17 Feb.

 

Exercise 5

 

Midterm Test

 

Exercise 6

 

Exercise 7 (sign error in N&W)

 

The rest will be from the Variational Calculus part.

 

Exercise 8

 

Exercise 9

 

 

MIDTERM TEST

Review Questions for the curriculum covered by the test.

NOTES SPRING 2005

 

1. Basic facts from analysis:  FoundationsFromAnalysis I  Minor corrections Jan-26-2005. Thanks to Anders!

2. Basic facts from analysis:  FoundationsFromAnalysis II

3. The standard Matlab algorithms: Low-dimensional algorithms      MatlabCodeForAmoebaTesting

4. Summary of the Trust Region model problem

5. Notes about the  Conjugate Gradient method. Transparencies

6. Notes about Least Square Optimization

7. Inverse problems Presentation

8. Notes about the KKTtheorem (NB! New version from 22 Feb.)

9. Notes about Linear Programming(Revised 16/3) Primal/Dual example  LP-slides (revised 16/3)

10. Notes about Quadratic Programming: QPBasics  QPBasics Overheads   QP in Matlab

11. Summary note about penalty and barrier methods: Penalty and Barrier

12. Note about interchanging derivatives and integrals: Derivatives and Integrals

13. Slides about variational calculus, PDEs and the Finite Element Method VarCalcPDEsandFE.

14. Differentiable functional, the Fréchet derivative and variational calculus in mechanics:  FrechetAndMechanics

 

OLD EXAMS

Problems

Solutions

X2004

X2004 Solution

X2003kont

 

X2003

 

X2002

X2002 Solution

 

 

X2000 Draft

X2000 Solution

 

 

X1996

X1996 Solution

 

KURSETS INNHOLD OG IDE

Kurset tar sikte på å innøve fundamentale teknikker 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
        - noe om indre metoder

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

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

LÆREBØKER

  1.  J. Nocedal og S. Wright: Numerical Optimization, Springer, 1999.
  2.  J. L. Troutman: Variational Calculus and Optimal Control, 2nd Ed. Springer, 1996.

Det vil i tillegg bli gitt ut noen mindre notater i løpet av kurset

PENSUM

 

Pensum2005.

       

Institutt for matematiske fag, NTNU,
Desember 2004

Harald E. Krogstad

Tlf. 93536

e-mail: harald.krogstad@math.ntnu.no