MATH46132 - 2009/2010

 

Specification

Aims

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 practice 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.

Learning Outcomes

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

None.

Syllabus

1. Introduction.
   Motivating examples. Continuous vs discrete optimization. Local vs Global optimization. [1]
2. Unconstrained Optimization.
   Optimality conditions. Convexity results. Local and Global solutions. [2]
   Line search vs Trust region methods. Line search methods: Armijo and Strong Wolfe Conditions. Convergence of steepest descent algorithm. [3]
   Search directions: nonlinear conjugate gradient method, Newton's method; Quasi-Newton methods. [6]
   Sums of squares problems: Gauss-Newton and Levenberg-Marquardt methods. [2]
3. Constrained Optimization.
   Optimality conditions. [3]
   Linear algebra for solving KKT systems. [2]
   Linear constraints. Active Set Methods. [2]
   Non-linear constraints, Sequential Quadratic Programming. [2]
   Penalty and barrier methods. Interior point methods. [3]
4. Applications.
   Inverse problems and regularization. Image Processing; Total Variation regularization in image deblurring/denoising. Solving the Euler Lagrange equations. [3]
5. Global optimization.
   Overview of approaches for solving global optimization problems. [1]

Textbooks

The course closely follows the text [4] which is available as an e-book from the Joule library.

1. J. T. Betts, Practical Methods for Optimal Control using Nonlinear Programming, SIAM 2001.
2. R. Fletcher, Practical Methods of Optimization, Wiley, Chichester, UK, second edition 1987.
3. Philip E. Gill, Walter Murray, and Margaret H. Wright, Practical Optimization, Academic Press, London 1981.
4. Jorge Nocedal and Stephen J. Wright, Numerical Optimization, Springer-Verlag, New York 1999.
5. 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 fortnightly examples class. In addition should expect to spend at least seven hours each week on private study.

Assessment

Mid-semester coursework: 25%

End of semester examination: three hours weighting 75%

to the top

Arrangements