# 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
^{1}-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.