# 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 |

^{1)}

There was an error in the old version of this, leading to drastically reduced performance for the Newton method

^{2)}

12.2 is particularly relevant here.