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
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
Farkas' Lemma
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
(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
There was an error in the old version of this, leading to drastically reduced performance for the Newton method
12.2 is particularly relevant here.
2020-03-18, Geir Bogfjellmo