Lecture plan
| Date | Topics | Reading |
|---|---|---|
| Introduction, modelling, and existence of solutions | ||
| Week 2 | Examples of minimization problems Formulation of a minimization problem Feasible set Definitions of minima Lower semi-continuity and coercivity Existence theorems for minima | N&W, Chapters 1, 2.1 Minimisers of Unconstrained Optimisation Problems |
| Theory and methods for unconstrained optimization | ||
| Week 3 | Taylor's theorem in higher dimensions 1st and 2nd order necessary and sufficient conditions Convex sets and functions (basic properties) | N&W, Chapter 2.1 Basic Properties of Convex Functions |
| Line search methods Backtracking (Armijo) line search The Wolfe conditions | N&W, Chapters 3.1, 3.2 | |
| Week 4 | Backtracking and the Wolfe conditions Algorithmic treatment of the Wolfe conditions Zoutendijk's result Convergence rate of line search methods | N&W, Chapters 3.1-3.3 |
| Week 5 | Convergence rate of Newton's method | N&W, Chapter 3.3 |
| Conjugate Gradient methods | N&W, Chapters 5.1-5.2 | |
| Week 6 | Nonlinear Conjugate Gradient methods Fletcher-Reeves and Polack-Ribière | N&W, Chapter 5.2 |
| Quasi-Newton methods DFP and BFGS methods Superlinear Convergence of the BFGS method | N&W, Chapters 6.1, 6.4 | |
| Summary of Line Search methods | ||
| Week 7 | Trust-region methods Cauchy point and dogleg method Two-dimensional subspace minimisation Overview of convergence results | N&W, Chapters 4.1-4.3 |
| Non-linear least-squares problems Gauss-Newton method Levenberg-Marquardt method | N&W Chapter 10.3 | |
| Theory and methods for constrained optimization | ||
| Week 8 | Basics of constrained optimization Non-smooth unconstrained and smooth constrained problems Tangent cones Feasible and linearized feasible directions Constraint qualifications Necessary conditions KKT-conditions | N&W Chapters 12.1-12.4 For the Monday lecture, I suggest to look in particular into Section 12.2, especially examples 12.4 and 12.5; also: Theorem 12.3 (p. 325). For the Thursday lecture, I suggest to look through Lemma 12.2 and also recall the implicit function theorem (Calculus II and/or Theorem A.2 in N&W). |
| Week 9 | KKT conditions Conditions for linear constraints Conditions for convex problems Second order necessary and sufficient conditions | N&W Chapters 12.3, 12.5, 12.6 For the Monday lecture I suggest to look into Chapter 12.3 (formulation of the KKT conditions). On Thursday we will discuss the 2nd order necessary and sufficient conditions covered in Chapter 12.5. |
| Week 10 | Quadratic penalty method for equality constrained optimisation Nonsmooth penalty methods Augmented Lagrangian method Penalty methods for inequality constraints | N&W Chapters 17.1-17.3 On Monday we will discuss the quadratic penalty method described in Chapter 17.1. Note that this method is also required in the project. |
| Week 11 | There will be no lectures this week. I will be available during the usual lecture hours in the usual lecture rooms for questions concerning the project. | |
| Week 12 | Easter holidays. | |
| Week 13 | Augmented Lagrangian method Non-smooth penalty methods (overview) Penalty methods for constrained optimisation problems (overview) | N&W Chapters 17.1-17.3 I suggest to review the definitions of the quadratic penalty method and the Augmented Lagrangian method for the lecture (i.e., equations 17.2 and 17.36, as well as Framework 17.3). |
| Week 14 | Barrier methods for inequality constrained optimisation Sequential Quadratic Programming Merit functions Treatment of inequality constraints | N&W Chapters 19.6, 19.1, 18.1-18.4 On Monday we will discuss very briefly the usage of logarithmic barrier functions for inequality constrained optimisation, which is closely connected to the concept of interior point methods. Afterwards we will start the discussion of SQP. I suggest to read 19.6 for the barrier functions and the first parts of 18.1 dealing with problems with equality constraints. |
| Week 15 | Linear optimisation Basic properties of linear programmes KKT-conditions and duality Overview of the simplex method Interior point methods for linear optimisation | N&W Chapters 13.1-13.3, 12.9, 14.1 I suggest to look briefly through the first pages of the chapter of linear optimisation, which contain the most important notions in linear optimisation apart from duality. Concerning duality, I suggest to read the first two pages of 12.9 both before the lecture on Monday and again for the lecture on Thursday. |
| Week 16 | Interior point methods for linear programming Basics of quadratic programming Interior point methods for quadratic programming | N&W, Chapters 14.1, 16.1, 16.4, 16.6 |
| Week 17 | Repetition | N&W, Chapters 1-6, 10-18 |
N&W always refers to the textbook J. Nocedal and S. Wright: Numerical Optimization, 2nd Edition. Springer, 2006.