|
BA
in Mathematics, Section C
|
Hilary Term 2006 Nick Gould |
Introduction
Optimization deals with the problem of minimising or maximising a mathematical model of an objective function such as cost, fuel consumption etc. under a set of side constraints on the domain of definition of this function. Optimization theory is the study of the mathematical properties of optimization problems and the analysis of algorithms for their solution. The aim of this course is to provide an introduction to nonlinear continuous optimization specifically tailored to the background of mathematics students.
The major pre-requisites for the course will be some knowledge of both linear algebra and real analysis, while an appreciation of methods for the numerical solution of linear systems of equations will be helpful.
Who is teaching?
- Lecturer: Nick Gould, Comlab office 217, email
- Class Tutor: Denis Zuev, Maths Institute office DH03, email
- Marker: ??
How is this course organised?
The course consists of lectures and classes, but no practicals. Students hand in solutions to seven problem sheets which will be discussed in classes during weeks 2-8 of the term. Lectures are taking place in weeks 1-8 of HT05 on Mondays and Wednesdays from 2-3pm in Room 147 of the Comlab. Classes take place in Comlab ??, ?? 4-5pm, weeks 2-8. Solutions have to be handed in by noon on Mondays before class. Mark them "for ??" and hand them in at the Comlab reception. See also the course outline slides.
Synopsis
Each lecture is accompanied by a lecture note (written by Raphael Hauser and augmented in places by Nick Gould) that explains the material in further detail. These notes will be posted here and form a self-contained introduction to the subject. They constitute compulsory reading assignments. Suggestions on how to improve the lecture notes are always very welcome!
In addition, I will post transparencies of the actual lectures, problem sheets and sample exams for the revision classes in TT06. All materials are posted in PDF format. In order to display it, you need the Acrobat software, which is installed on almost all PCs and workstations. If you are experiencing problems downloading some of the materials, please contact me via email.
Chapter I: Unconstrained Optimization.
- Lecture 1: introduction and preliminaries. Notes, slides.
- Lecture 2: the descent method and line searches. Notes, slides.
- Lecture 3: steepest descent and Newton methods. Notes, slides.
- Lecture 4: quasi-Newton methods. Notes, slides.
- Lecture 5: conjugate gradients and the Fletcher-Reeves method. Notes, slides.
- Lecture 6: trust region methods. Notes, slides.
- Lecture 7: the dogleg and Steihaug methods. Notes, slides
Chapter II: Constrained Optimization
- Lecture 8: the fundamental theorem of linear inequalities. Notes, slides.
- Lecture 9: first order necessary optimality conditions (KKT). Notes, slides.
- Lecture 10: second order optimality conditions. Notes, slides.
- Lecture 11: the method of Lagrange multipliers, examples. Notes.
- Lecture 12: Lagrangian Duality and Convex Programming. Notes, slides.
- Lecture 13: the penalty function method. Notes, slides.
- Lecture 14: the augmented Lagrangian method. Notes, slides.
- Lecture 15: the barrier method for nonlinear programming. Notes, slides.
- Lecture 16: primal-dual path-following for linear programming. Notes, slides.
Problem sheets
- Problem set 1: on the material of lectures 1&2.
- Problem set 2: on the material of lectures 3&4.
- Problem set 3: on the material of lectures 5&6.
- Problem set 4: on the material of lectures 7&8.
- Problem set 5: on the material of lectures 9&10.
- Problem set 6: on the material of lectures 11&12.
- Problem set 7: on the material of lectures 13&14.
Revision material
Revision classes
- I would like to hold two revision classes to discuss the sample exams 1 and 2. For this purpose I reserved Room 051 (Comlab) from 2-3pm on Tuesdays of weeks 2 and 3 of TT05. Please let me know as soon as possible if you have a conflict with these times.
Reading List
The following books contain useful background material. The first is particularly recommended:
J. Nocedal and S. Wright, Numerical Optimization, Springer Verlag 1999
J. Dennis and R. Schnabel, Numerical Methods for Unconstrained Optimization and Nonlinear Equations, (republished by) SIAM (Classics in Applied Mathematics 16) 1996
P. Gill, W. Murray and M. Wright, Practical Optimization, Academic Press 1981
R. Fletcher, Practical Methods of Optimization, 2nd edition Wiley 1987, (republished in paperback 2000)
A. Conn, N. Gould and Ph. Toint, Trust-Region Methods, SIAM 2000
WWW sites
Optimization, at its best, is featured on the following WWW sites:
- Linear programming frequently-asked questions
- Nonlinear programming frequently-asked questions
- The Optimization Technology Center with its guide to optimization software
- The Network-Enabled Optimization System(NEOS) - solve optimization problems online
- A Decision Tree for Optimization Software, and associated Benchmarks for Optimization Software
- Optimization Online
- INFORMS resouces
- Mathematical Programming Society
- SIAM
Last updated 3 January 2006 at 08:35