MATH46132 - 2007/2008
- Title: Numerical Optimization
- Unit code: MATH46132
- Credits: 15
- Prerequisites: MATH46101 Numerical Linear Algebra or familiarity with numerical linear algebra and MATLAB.
- Co-requisite units:
- School responsible: Mathematics
- Members of staff responsible:
To provide a basic mathematical understanding of modern approaches to numerical optimization, and to discuss practical aspects of implementation and available software.
Brief Description of the unit
This course unit develops the theory and practise of numerical methods for nonlinear optimization with and without constraints, covering methods suitable for both small and large-scale problems and discussing available software. The subject is of considerable importance in scientific, industrial and economic problems, and the ideas and methods of solution have been stimulated by practical applications. The course can be regarded as constructive analysis of functions of n variables, leading to algorithms for numerical solution.
On successful completion of this course unit students will
- understand the mathematical conditions characterizing the solutions of optimization problems;
- have developed their knowledge of matrices, analysis and geometry in $n$ dimensions;
- be familiar with several differing types of optimization problems and some methods of solution;
- appreciate the issues involved in the choice of algorithm for particular optimization problems.
Future topics requiring this course unit
Motivating examples. Continuous vs discrete optimization. Local vs Global optimization. 
- Unconstrained Optimization.
Optimality conditions. Convexity results. Local and Global solutions. 
Line search vs Trust region methods. Line search methods: Armijo and Strong Wolfe Conditions. Convergence of steepest descent algorithm. 
Search directions: nonlinear conjugate gradient method, Newton's method: Quasi-Newton methods.  Sums of squares: Gauss-Newton and Levenberg-Marquardt methods. 
- Constrained Optimization.
Optimality conditions. 
Linear algebra for the KKT system. 
Sequential Quadratic Programming. 
Reduced and full space methods. Interior point methods. 
Trajectory Optimisation. 
Inverse problems and regularization. 
Total Variation regularization in image deblurring/denoising. Solving the Euler Lagrange equations. 
- Global optimization.
Overview of approaches for solving global optimization problems. 
Introduction to state of the art software and algorithms. (Local and global optimization.) [1-2]
- J. T. Betts, Practical Methods for Optimal Control using Nonlinear Programming, SIAM 2001.
- T. F. Chan and J. Shen, Image Processing and Analysis, SIAM, 2006.
- R. Fletcher, Practical Methods of Optimization, Wiley, Chichester, UK, second edition 1987.
- Philip E. Gill, Walter Murray, and Margaret H. Wright, Practical Optimization, Academic Press, London 1981.
- Jorge Nocedal and Stephen J. Wright, Numerical Optimization, Springer-Verlag, New York 1999.
- N. Gould and S. Leyffler, An introduction to algorithms for nonlinear optimization; in Frontiers in Numerical Analysis (Durham, 2002), Springer 2003.
Teaching and learning methods
30 lectures (two or three lectures per week) with a weekly examples class. In addition should expect to spend at least seven hours each week on private study..