Pensum (Curriculum)

Final pensum in the course:

Lecture notes:

Minimisers of Optimisation Problems, in particular the results concerning the existence of minimisers.
Basic Properties of Convex Functions, in particular, the different characterisations of convexity.

All the exercises.

This includes the brief introduction to duality of optimisation problems on exercise sheet 9.

The following chapters in Nocedal & Wright, Numerical Optimization, Second Edition, 2006 (most important points in boldface):

Basics of optimization: Chap. 1, 2.
- Most important notions/results:
  - Notions of (strict) global/local solutions of optimisation problems.
  - First order necessary conditions.
  - Second order sufficient and necessary conditions.
  - Basic idea of trust region/line search.
Line Search Methods: Chap. 3.1-3.3.
- Most important notions/results:
  - Definitions of Wolfe conditions.
  - "Well-posedness" of Wolfe conditions (Lemma 3.1).
  - Zoutendijk's result (Theorem 3.2).
  - Idea of backtracking line search.
  - Linear convergence of the gradient descent method, importance of the condition of the Hessian.
  - Quadratic convergence of Newton's method.
- Less important results:
  - Superlinear convergence of Quasi-Newton methods
Trust-Region Methods: Chap. 4.1-4.3.
- Most important notions/results:
  - Basic trust-region algorithm (Algorithm 4.1).
  - Characterisation of trust-region steps (Theorem 4.1).
  - Cauchy point and dogleg method.
  - Proof of Theorem 4.1.
- Less important results:
  - All the details about the convergence results in Section 4.2.
  - Details of the numerical solution of the trust-region subproblem in 4.3.
Conjugate Gradient Methods: Chap. 5.
- Most important notions/results:
  - Idea of linear CG, conjugacy.
  - Theorems 5.1 and 5.2.
  - Linear CG-algorithm (Algorithms 5.1 or 5.2) and Theorem 5.3.
  - Convergence rate in (5.36) and comparison to (3.29).
  - Fletcher-Reeves and Polak-Ribière method.
  - Requirements for the line-search (Lemma 5.6), convergence results (Theorems 5.7 and 5.8).
- Less important results:
  - Details of the convergence rates, in particular Theorems 5.4 and 5.5.
  - Proofs of the convergence results.
- Please ignore:
  - Everything concerning preconditioning.
Quasi-Newton Methods: Chap. 6.1, 6.4.
- Most important notions/results:
  - Idea of Quasi-Newton methods and definition of DFP/BFGS updates.
  - Necessity of Wolfe conditions.
  - Main convergence results (Theorems 6.5 and 6.6).
- Less important results:
  - Proof of the convergence results.
  - SR1 method.
Least-Squares Problems: Chap. 10.1-10.3.
- Most important notions/results:
  - Linear least squares and normal equations (10.14).
  - Idea of the Gauss-Newton method and relation to trust-region methods (Levenberg-Marquardt method).
  - Convergence of Gauss-Newton (Theorem 10.1).
- Less important results:
  - Methods for the solution of linear least-squares problems (most of Section 10.2).
- Please ignore:
  - Implementation details, convergence of Levenberg-Marquardt, methods for large residual problems.
  - Proof of Theorem 10.1.
Constrained Optimization: Chap. 12.1-12.5, 12.9.
- Most important notions/results:
  - Notions of local and global solutions.
  - Active set.
  - Lagrangian of a constrained optimisation problem.
  - Tangent cone and cone of linearised feasible directions.
  - Linear independence constraint qualification (LICQ).
  - KKT-conditions.
  - Farkas' Lemma.
  - Second order sufficient and necessary conditions.
  - Dual of a constrained optimisation problem
  - Weak duality
- Less important results:
  - Nothing, really.
- Please ignore:
  - Projected Hessians.
  - Wolfe dual.
Linear Programming: Chap. 13.1-13.2, 14.1.
- Most important notions/results:
  - Standard form of linear programmes.
  - Optimality conditions for linear programmes.
  - Dual problems and strong duality (Theorem 13.1).
  - Basic feasible points and solutions of linear programmes in standard form (Theorem 13.2).
  - Idea of interior point methods.
  - Primal-dual path-following and the central path.
  - Long-step path-following (Algorithm 14.2).
  - Convergence of Algorithm 14.2 (Theorem 14.4).
- Less important results:
  - Details of the proofs in Section 13.2.
  - All the details necessary for the derivation of Theorem 14.4.
- Please ignore:
  - The simplex method.
Quadratic Programming: Chap. 16.1, 16.4, 16.6, 16.7.
- Most important notions/results:
  - KKT-conditions for quadratic programmes (equations (16.5) and (16.37)).
  - Differences between linear programmes and quadratic programmes (in particular Figures 16.1, 16.2).
  - Application of interior point methods to quadratic programmes.
  - Gradient projection method.
- Less important results:
  - Step length selection for interior point methods.
  - Subspace minimization.
- Please ignore:
  - Everything containing reduces Hessians.
  - The practical primal-dual method.
Penalty Methods: Chap. 17.1-17.3.
- Most important notions/results:
  - Quadratic penalty method and Framework 17.1.
  - Convergence of the quadratic penalty method (Theorem 17.1).
  - Accuracy of the quadratic penalty method and asymptotic ill-conditioning (Theorem 17.2 and p. 505).
  - Idea of non-smooth penalty functions.
  - Augmented Lagrangian method (Framework 17.3).
  - Exactness and convergence of the Augmented Lagrangian method (Theorems 17.5 and 17.6).
- Less important results:
  - Well-conditioned reformulation of the quadratic penalty method (p. 506).
  - All details in section 17.2.
  - Details of the proofs concerning the Augmented Lagrangian method.
Sequential Quadratic Programming: Chap. 18.1-18.3 (and 15.5).
- Most important notions/results:
  - SQP for equality-constrained problems and Newton's method for the KKT-conditions.
  - Construction of the SQP-method for inequality-constrained problems.
  - Merit functions for enforcing convergence.
  - Properties of the l¹-merit function (mainly Theorem 18.2).
  - Problems caused by the Maratos effect.
- Please ignore:
  - Quasi-Newton methods for SQP.
  - Reduced-Hessian Quasi-Newton methods.
Interior-Point Methods for Nonlinear Programming: Chap. 19.1, 19.6.
- Most important notions/results:
  - Logarithmic barrier problem (equation (19.4)).
- Please ignore:
  - Everything else.

Note: Programming is not part of the exam; this part of the lecture has already been covered by the project.