TMA 4180 Optimeringsteori
Survey of the curriculum 2011Ê
Some general advice about the exam:
- No lengthy detailed and proofs will be required. Focus on the essential content
- Understand the ideas and apply themÊ to problems and exercises
- Computer demonstrations and case studies are not part of the curriculum
- Do not try to memorize difficult formulas (will be supplied on the exam)
Ê
The curriculum is found in the following material
Ê
- J. Nocedal and S.J. Wright: Numerical Optimization, 2nd Ed., Springer, 2006
- J.L. Troutman: Variational Calculus and Optimal Control, 2nd Ed., Springer, 1996
- A subset of the supplementary notes (see below)
- Exercises with the solutions
Ê
Note: Even if his list below is fairly detailed, Òcentral conceptsÓ may not be quite complete!
Ê
NB! Page number according to N&W Ed. 2Ê(differs from Ed. 1!)
1 Unconstrained Optimization
Nocedal & Wright and supplementary notes:
Ê
Section 2.1, 2.2 (survey only)
Central concepts:
- TaylorÕs formula in n dimensions (note)
- Convex sets and functions (note)
- Convex problems (note)
- Necessary and sufficient conditions for extrema
Ê
Section 3.1 - 3.3 (to p. 48)
Central concepts:
- What is a line search
- WolfeÕs conditions
- The quadratic test problemÊ (note)
- Steepest descent (note)
- The A-normÊ (note)
- Convergence speed of the steepest descentÊ (note)
Ê
Section 4.1 (to p. 76)
Central concepts:
- The Trust region-idea
- The Cauchy-point
- The dog-leg method
- Understand Theorem 4.1
Ê
Section 5.1, 5.2 (to p. 122)
Central concepts:
- The projection theorem in Hilbert space (note)
- The two main ideas behind the CG-algorithm for the quadratic problemÊ (note)
- Convergence (basic idea only, supplementary notes)
- CG-algorithm on non-quadratic problems (no details)
Ê
Section 6.1, 6.2
Central concepts:
- What is a quasi-Newton method
- SR1, BFGS (the idea)
Ê
Section 10.1 - 10.3 (to p. 262)
Central concepts:
- Jacobian and Hessian-matricesÊ (note)
- The linear problem (note)
- SVD (note)
- Gauss-NewtonÕs method (note)
- The Levenberg-Marquardt algorithm as a trust region method (note)
Ê
2 Constrained optimization
Section 12.1, 12.2, 12.3, 12.5
The supplementary note about the KKT-theorem covers all the theory.Ê
Central concepts:
- The KKT-conditions (Theorem 12.1)
- The LICQ condition
- Convexity and the KKT-theorem
- Second order conditions when the LICQ holds (the simplest aspects)
ÊSection 13.1, 13.2, 13.3, p. 378 Ð 382.
The supplementary note about LP cover the curriculum.
ÊCentral concepts:
- Reduction to standard form (slack and surplus variables)
- The s\duality theorem, application
- The Simplex
- Basic solutions and extreme points
- The fundamental theorem for LP
- One SIMPLEX-step
- How to start the SIMPLEX algorithm.
Section 16.1, 16.2, 16.4 (to p. 465), p. 472-475 (Example), 16.7 (the idea)
The supplementary notes cover the curriculum.
Central concepts:
- Explicit solutions for equality constraints
- The null-space method
- Direct solution of the KKT-equations
- The Active Set method Ê(idea only)
- Gradient projection Method (idea only)
ÊSection 17.1, 17.2 (to p. 511)
The note covers the curriculum.
ÊCentral concepts:
- Penalty-methods
- The eigenvalue distribution for the Hessian
- Barrier Methods
3 Variational Calculus
From Troutman.
ÊChapter 2.1, 2.2, 2.3, 2.4.
ÊCentral concepts:
- functionals
- The G‰teaux derivative
- How to compute derivatives
- Proposition 2.3
ÊChapter 3.1, 3.2, 3.3, 3.4, 3.5
ÊCentral concepts:
- convex functionals
- standard functional
- strong convexity
- Theorem 3.5
- Theorem 3.16Ê
3 Notes
All notes mentioned above are available on the Web page.
Some of the notes contain detailed proofs. These are not part of the curriculum.
Ê
Ê
4 Exercises
All analytical exercises and solutions are part of the curriculum (Not problems requiring numerical methods!)