Lecture Plan
| Date | Topics | Reading | Slides and code |
|---|---|---|---|
| Introduction, notion and existence of solutions | |||
| Week 2 | Overview Formulation of a minimization problem Definitions of minima Lower semi-continuity and coercivity Existence theorems for minima First order necessary conditions Second order necessary and sufficient conditions | N&W, Chapters 1, 2.1 Minimisers of Optimisation Problems | Introduction |
| Week 3 | Convex functions First and second order characterisations | Basic Properties of Convex Functions | |
| Line search methods for free optimization | |||
| Gradient descent method Exact line search methods Armijo condition Wolfe conditions | N&W, Chapter 3.1 | ||
| Week 4 | Line search methods Zoutendijk's result Method for Wolfe conditions Backtracking line search Convergence of Steepest Descent Newton's method Damped Newton's method | N&W, Chapter 3.1-3.2 Convergence of descent methods with backtracking N&W, Chapter 3.3 | |
| Week 5 | Linear Conjugate Gradient Methods Fletcher–Reeves method Polak–Ribière method | N&W, Chapter 5.1-2 | Conjugate gradient and steepest descent Comparison of line search methods (version 2)1) |
| Week 6 | Least Squares problems Gauss–Newton Method | N&W, Chapter 10.1,10.3 (to page 257) | |
| Theory and basic methods for constrained optimization | |||
| Constrained optimisation over convex sets Feasible directions First order optimality conditions for convex sets Projections on convex sets Gradient projection method Normal cones Conditions for linear constraints | Optimisation with convex constraints N&W, Chapter 12.1–12.4.2) | ||
| Week 7 | Tangent cones for nonconvex sets Necessary conditions for non-convex sets Linearised feasible directions Constraint qualifications LICQ Farkas' Lemma KKT-conditions Second order necessary and sufficient conditions | N&W, Chapter 12.2–12.5 | |
| Week 8 | Quadratic penalty method Nonsmooth penalty methods Augmented Lagrangian method | N&W, Chapters 17.1–17.3 | |
| Week 9 | No new material lectured this week. Work on project. | ||
| Week 10 | Penalty methods for inequality constraints Logarithmic Barrier Methods | N&W, Chapter 17.4 N&W 19.6 | |
| Advanced methods for free optimization | |||
| Quasi-Newton Methods SR1-method (DFP Method) BFGS Method | N&W, Chapter 6.1,6.2,6.4 | quasinewton.ipynb Quasi-Newton methods compared with Newton and steepest descent. | |
| Week 11 | Limited memory BFGS Trust region methods Exact solution of the trust region problem | N&W, Chapter 7.2 N&W Chapter 4.1 | |
| Week 12 | Exact solution of the trust region problem Cauchy point Dogleg method Convergence of trust region methods | N&W Chapter 4.3 N&W Chapter 4.1, 4.2 | |
| Advanced methods for constrained optimization | |||
| Linear programs Lagrangian duality Primal and dual linear programs | N&W Chapter 13.1 N&W Chapter 12.9 | ||
| Week 13 | Primal-dual interior point method for linear programs Central path Path following methods Quadratic programs Direct solution of equality constrained problems Active set methods | N&W Chapter 14.1 N&W, Chapters 16.1, 16.2, 16.5 | |
| Week 14 | SQP method (equality constraints) Newton's method for KKT equations. Merit functions Maratos effect | N&W, Chapters 18.1, 18.3 N&W, Chapters 15.4, 15.5 | |
| Week 15 | Easter break | ||
| Week 16 | Summary / Questions | ||
| Week 17 | Summary / Questions | ||