TMA 4180 Optimeringsteori

Survey of the curriculum 2010 

Some general advice about the exam:

    • No lengthy detailed and proofs will be required. Focus on the essential lcontent
    • 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

 

  1. J. Nocedal and S.J. Wright: Numerical Optimization, 2nd Ed., Springer, 2006
  2. J.L. Troutman: Variational Calculus and Optimal Control, 2nd Ed., Springer, 1996
  3. A subset of the supplementary notes (see below)
  4. 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
  • Understand Theorem 4.1 and the solution of the model problem (note)

 

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 (only survey)

Central concepts:

  • What is a quasi-Newton method

 

Section 10.1, 10.2 (to p. 264)

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 and the slides 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 15.1 – 15.3 (only survey material)

Section 16.1, 16.2, 16.4 (to p. 465), p. 472-475 (Example), 16.7 (the idea)

The supplementary notes and the slides 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 (only to p. 42, Application), 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 (not p. 69-71), 3.5

 Central concepts:

  • convex functionals
  • standard functional
  • strong convexity
  • Theorem 3.5
  • Theorem 3.16 

3 Notes

All notes are available on the Web page.

Some of the notes contain detailed proofs. These are not part of the curriculum.

 

Grading as follows:

***:     Essential

**:       Important

*:         Survey only (no details!)

0:         Not to be considered as a part of the curriculum

1.          Basic Mathematical Tools (2008 revision) *** (not complex proofs)

2.          Low-dimensional, unconstrained problems (2008 revision) **

3.          The Trust Region Quadratic Problem *

4.          Comments about the Conjugate Gradient Method **

5.          Least-Squares Optimization ***

6.          MATLAB Optimization Toolbox (unconstrained) 0

7.          Karush-Kuhn-Tucker Theorem  ** Example for the KKT Theorem **

8.          Linear Programming Tutorial (minor revisions, March 8) ***

9.          Slides about LP and optimal network flow *

10.      Quadratic Programming Basics   **

11.      QP Overheads  * (already covered in the note)

12.      Examples from Matlab Opt. Toolbox 0

13.      Penalty and Barrier Methods  (minor revisions, March 21) **

14.      Note about Inverse Problems  0

15.      Inverse Problems (OHs)  0

16.      Moving the Derivative Inside the Integral Sign *

17.      Minimum transit time - The Brachistochrone  *

Note: Some presentations, demonstrations etc. found on the Lecture plan and survey 2010 are not part of the curriculum.

 

4 Exercises

All analytical exercises and solutions are part of the curriculum (Not problems requiring numerical methods!)