Pensum

Final pensum in the course:

Lecture notes:

All the exercises.

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.
- Please ignore:
  - 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).
  - Proof of Theorem 10.1.
- Please ignore:
  - Implementation details, convergence of Levenberg-Marquardt, methods for large residual problems.
Constrained Optimization: Chap. 12.1-12.5.
- 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.
- Less important results:
  - Nothing, really.
- Please ignore:
  - Projected Hessians.
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.
- 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.
- Less important results:
  - Step length selection for interior point methods.
- 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.

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