# Pensum (Curriculum)

Final pensum in the course for spring 2020:

First of all, the pensum includes all the material and all the results and approaches that were discussed in the lectures.

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**. - Convergence of descent methods with backtracking, in particular, the main idea for the proof of the
**convergence of backtracking methods**. - Optimisation with convex constraints, sections 1-3, in particular, the
**necessary and sufficient conditions**for optimisation with convex constraints and the idea of**projections**.

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.
- Theorem 5.1.
- Linear CG method.
- 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:
- Theorems 5.2 and 5.3.
- Details of the convergence rates, in particular Theorems 5.4 and 5.5.

- Please ignore:
- Everything concerning preconditioning.
- Explicit forms of the algorithms (linear CG, different non-linear CG methods).
- Proofs of the convergence results.

**Quasi-Newton Methods:**Chap. 6.1,6.2, 6.4.- Most important notions/results:
- Idea of Quasi-Newton methods.
- Necessity of Wolfe conditions.
- Main convergence results (Theorems 6.5 and 6.6).

- Less important results:
- Proof of the convergence results.
- SR1 method.
- Limited-memory BFGS.

- Please ignore:
- Definitions of the DFP and BFGS updates.

**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
- 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, results concerning 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 optimization problem.****Tangent cone and cone of linearized feasible directions.****Linear independence constraint qualification (LICQ).****KKT-conditions.**- Farkas' Lemma.
**Second order sufficient and necessary conditions.****Dual of a constrained optimization problem.****Weak duality.**

- Less important results:
- Nothing.

- Please ignore:
- Projected Hessians.
- Wolfe dual.

**Linear Programming:**Chap. 13.1-13.2, 14.1.- Most important notions/results:
- Standard form of linear programs.
**Optimality conditions for linear programs.****Dual problems and strong duality (Theorem 13.1).**

- Less important results:
- 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).
- 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.5, 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).
- Idea of active set methods for quadratic programmes.

- Please ignore:
- Gradient projection method.
- Subspace minimization.
- Implementation details for the active set method.
- Everything containing reduced Hessians.

**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.**- Merit functions for enforcing convergence.
- Properties of the l
^{1}-merit function (mainly Theorem 18.2). - Problems caused by the Maratos effect.

- Please ignore:
- Construction of the SQP-method for inequality-constrained problems.
- 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 course has already been covered by the project.