Lecture Plan
The topic videos can be found on Blackboard under "Learning materials".
| 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 | General Information Introduction Minima Necessary and Sufficient Optimality Conditions |
| Week 3 | Convex functions First and second order characterisations | Basic Properties of Convex Functions | Convexity |
| Line search methods for free optimization | |||
| Gradient descent method Exact line search methods Armijo condition Wolfe conditions | N&W, Chapter 3.1 | Descent Methods Gradient Descent Methods Line Search Methods Inexact Line Search Methods | |
| 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 | Convergence of Line Search Methods - Zoutendijk's Result Rate of Convergence Convergence Rate of Steepest Descent Newton's Method Question Session Sufficient Decrease and Backtracking |
| Week 5 | Linear Conjugate Gradient Methods | N&W, Chapter 5.1 | Conjugate Gradient Methods 1 Conjugate Gradient Methods 2 Conjugate Gradient Methods 3 |
| Week 6 | Least Squares problems Gauss–Newton Method | N&W, Chapter 10.1,10.3 (to page 257) | Least-Squares Problems (updated version with a typo corrected) |
| 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 | Optimisation with convex constraints N&W, Chapter 12.1–12.4.1) | Optimization with Convex Constraints I Optimization with Convex Constraints I - with Notes Optimization with Convex Constraints II | |
| Week 7 | Conditions for linear constraints Tangent cones for nonconvex sets Necessary conditions for non-convex sets Linearised feasible directions Constraint qualifications LICQ Farkas' Lemma KKT-conditions | N&W, Chapter 12.2–12.4 | Conditions for linear constraints Concave inequality constraints Tangent Cone and Constraint Qualifications Question Session Question Session with Notes |
| Week 8 | Review Sessions | Review Lecture (Covering Lectures 1-5) Review Session by Markus Köbis | |
| Week 9 | Second order necessary and sufficient conditions | N&W, Chapter 12.5 | Second-Order Optimality Conditions for Constrained Optimization |
| Week 10 | Quadratic penalty method Nonsmooth penalty methods | N&W Chapters 17.1–17.2 | Quadratic Penalty Method Nonsmooth penalty methods |
| Week 11 | Augmented Lagrangian method Penalty methods for inequality constraints Logarithmic Barrier Methods | N&W, Chapter 17.3 N&W 17.4 N&W 19.6 | Augmented Lagrangian & Logarithmic Barrier Method Practical Augmented Lagrangian |
| Advanced methods for free optimization | |||
| Week 12 | Quasi-Newton Methods SR1-method DFP Method BFGS Method | N&W, Chapter 6.1,6.2,6.4 | Quasi-Newton Methods |
| Week 13 | Easter Break | ||
| Week 14 | Trust region methods Exact solution of the trust region problem | N&W Chapter 4.1–4.3 | Trust Region Methods Part 1 (updated version with a typo corrected) |
| Week 15 | Cauchy point Convergence of trust region methods | N&W Chapter 4.1–4.3 | Trust Region Methods Part 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 | Linear Programs Part 1 Linear Programming Example Linear Programs Part 2 (updated version with corrections) | |
| Week 16 | Primal-dual interior point method for linear programs Central path Path following methods Quadratic programs Direct solution of equality constrained problems | N&W Chapter 14.1 N&W, Chapters 16.1, 16.2 | Primal-dual Method Example for Quadratic Programming - Portfolio Optimization Quadratic Programs with Equality Constraints |
| Week 17 | Active set methods SQP method (equality and inequality constraints) Newton's method for KKT equations. Merit functions Maratos effect | N&W, Chapters 16.5 N&W, Chapters 18.1, N&W, Chapters 15.4, 15.5 | Quadratic Programs (Direct Methods, cont. and Active Set Methods); SQP Method |
1)
12.2 is particularly relevant here.