MATH66132 - 2012/2013

 

Specification

Aims

To provide a mathematical understanding of modern numerical optimization, and to discuss practical aspects of implementation and available software. To introduce inverse and ill-posed problems and their application to industrial, geophysical and medical imaging problems.

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.

Optimization problems as discussed in this course are encountered by many practicians working in financial mathematics, industrial mathematics or in mathematical economics. For example, one often needs to infer the material properties of an object from some physical measurement. Often the measurements are taken exterior to the object and we wish to identify variable material properties on the inside: in industrial and medical imaging, one applies ultra sound, X-rays or an electromagnetic field to an object, makes measurements on the outside and then attempts to form an image of the inside. These problems are examples of so-called 'inverse problems' and are typically ill-posed in the sense that the mapping taking data to images is discontinuous, and numerically reconstruction algorithms tend to be unstable unless one makes sufficient assumptions, such as smoothness, about the image. As discretized inverse problems are ill-conditioned, we have to constrain the solution using extra (a priori) information and the usual compromise results in an optimization problem that trades off fitting the data against satisfying the constraints given by the a priori information. Numerical optimisation techniques are often used to solve such problems.

The course will be illustrated by practical examples including visits to experimental groups in the University, and will include numerical examples illustrated by MATLAB programs.

Learning Outcomes

On successful completion of this course unit students will

• be able to understand the nature and setup of optimization problems in typical practical applications;
• understand the mathematical conditions characterizing the solutions of these 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 their numerical solution;
• appreciate the issues involved in the choice of algorithm for particular optimization problems.
• understand the basic theory of regularization for ill-posed problems, and its application to a number of medical, geophysical and industrial problems.

Future topics requiring this course unit

None.

Syllabus

1. Introduction. [2]
   Motivating examples. Continuous vs discrete optimization. Local vs Global optimization.
2. Unconstrained Optimization. [10]
   Optimality conditions. Convexity results. Local and Global solutions. Convergence of steepest descent algorithm. Search directions: nonlinear conjugate gradient method, Newton's method; Quasi-Newton methods. Sums of squares problems: Gauss-Newton and Levenberg-Marquardt methods.
3. Constrained Optimization. [6]
   Optimality conditions. Linear algebra for solving KKT systems. Overview of methods for constrained optimisation.
4. Inverse Problems [12] Introduction to inverse problems. Tikhonov regularization of linear ill-posed problems. Total Variation regularization in image deblurring/denoising. Solving the Euler Lagrange equations. Adjoint formulation and seismic imaging. The Radon Transform and X-Ray computerized Tomography.

Textbooks

1. J. T. Betts, Practical Methods for Optimal Control using Nonlinear Programming, SIAM 2001.
2. R. Fletcher, Practical Methods of Optimization, Wiley, 1987.
3. Philip E. Gill, Walter Murray, and Margaret H. Wright, Practical Optimization, Academic Press, 1981.
4. Jorge Nocedal and Stephen J. Wright, Numerical Optimization, Springer-Verlag, 1999.
5. N. Gould and S. Leyffler, An introduction to algorithms for nonlinear optimization; in Frontiers in Numerical Analysis (Durham, 2002), Springer, 2003.
6. M. Bertero and P. Boccacci, Introduction to Inverse Problems in Imaging, Taylor & Francis, 1998.
7. P. C. Hansen, Rank-deficient and Discrete Ill-posed Problems, SIAM, 1987.
8. R. Aster, B. Borchers and C. Thurber, Parameter Estimation and Inverse Problems. Academic Press, 2012.
9. A. Tarantola, Inverse Problem Theory, SIAM, 2005.

A more comprehensive list of textbooks will be distributed at the beginning of the course.

Teaching and learning methods

30 lectures (two or three lectures per week) with a fortnightly examples class. In addition you 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