Lecture plan
This is a tentative lecture plan, which is still subject to changes.
N&W always refers to the second edition of Nocedal & Wright, Numerical Optimization, Springer 2006.
Some of the notes below are from last year's edition of this course, and it is likely that they will be updated during this term.
Most of the code below will require the files TMA4180_definitions.py and LineSearchMethods.py. The former contains implementations of different test functions for optimisation; the latter contains impementations of various numerical methods discussed in the course. Make sure that you have an up-to-date version of this file (and all other necessary files) in your working directory before running any of the jupyter notebooks below.
| 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 | Note on unconstrained optimisation, Sec 1, 2 (last updated on February 29, 2024) N&W 1, 2.1 | Introduction Lecture 2 |
| Week 3 | Second order necessary and sufficient conditions Convex functions First and second order characterisations | Note on unconstrained optimisation, Sec 2, 3 (last updated on February 29, 2024) | Lecture 3 |
| Basic methods for free optimisation | |||
| Derivative free methods Gradient descent method Exact line search | N&W, 9.5 (be aware of the unusually large number of misprints in this chapter) N&W, 3.1 | Lecture 4 Nelder-Mead notebook NelderMead.py TMA4180_definitions.py |
|
| Week 4 | Armijo condition and backtracking Convergence of backtracking Goldstein conditions Algorithmic approach to Goldstein conditions Wolfe conditions Convergence rate of the gradient descent method | Note on convergence of backtracking N&W, 3.1-3.3 | Lecture 5 Gradient Descent notebook LineSearchMethods.py TMA4180_definitions.py Lecture 6 Goldstein conditions Rosenbrock function |
| Week 5 | Newton's method Modified Newton's method Linear Conjugate Gradient method Non-linear CG methods | N&W, 5.1, 5.2 | Lecture 7 Lecture 8 Gradient descent for a quadratic function Nonlinear CG methods |
| Theory and basic methods for constrained optimisation | |||
| Week 6 | 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 Lagrange multipliers Tangent cones for nonconvex sets Necessary conditions for non-convex sets Linearised feasible directions | Note on optimisation with convex constraints N&W 12.1, 12.2 | Lecture 9 Lecture 10 |
| Week 7 | Constraint qualifications LICQ Slater's constraint qualification Farkas' Lemma KKT-conditions Second order necessary and sufficient conditions | N&W 12.1-12.6 Note on optimisation with convex constraints, Section 4 | Lecture 11 Lecture 12 |
| Week 8 | KKT conditions for convex problems Review of KKT conditions Quadratic penalty method Logarithmic Barrier methods Augmented Lagrangian method | N&W 12.3, 12.5 N&W 17.1, 17.3, 17.4, 19.1 | Lecture 13 Lecture 14 Penalty methods |
| Advanced methods for free optimisation | |||
| Week 9 | Quasi-Newton methods SR1-method DFP and BFGS method | N&W 6.1, 6.2 (see N&W 7.2 for limited memory methods) | Lecture 15 Lecture 16 Quasi-Newton methods |
| Week 10 | Trust region methods Exact solution of the trust region problem Cauchy point Convergence of trust region methods Dogleg method | N&W 4.0, 4.3, 4.1 | Lecture 17 Trust region methods Lecture 18 |
| Advanced methods for constrained optimisation | |||
| Linear constraints Basics of linear programming | N&W 13.0, 13.2 | ||
| Week 11 | Quadratic programming Active set method Sequential Quadratic Programming (SQP) | N&W 16.1, 16.5 N&W 18.1, 18.3 | Lecture 19 Lecture 20 |
| Vector optimisation | |||
| Week 12 | Partial orders Ordered vector spaces and cones Pareto optimality Computation of Pareto optimal solutions Weighted sum method These lectures will be filmed, as the 3rd year IndMat students are on excursion Recording of Monday Recording of Friday | Multicriteria optimisation | Lecture 21 Lecture 22 |
| Week 13 | Easter holidays | ||
| Week 14 | No lecture on Monday (Easter holidays)! | ||
| Duality theory | |||
| Lagrangian duality Primal and dual linear programmes Weak duality Saddle points | Lagrangian duality (last updated on April 17, 2024) | Lecture 23 | |
| Week 15 | Strong duality for convex problems Duality in linear programming Legendre-Fenchel transform Dual methods for convex optimisation | Lagrangian duality (last updated on April 17, 2024) | Lecture 24 Lecture 25 |
| Week 16 | Primal-dual interior point method for linear programming Central path Path following methods | N&W, 14.1 | Lecture 26 Interior point method IntPoint.py |
| Summary | |||
| Friday: Summary | Summary | ||
| Week 17 | Monday: Question session | Problems | |
| Week 18 | Monday: Question session | ||