A course on Continuous Optimization

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.

How is this course organised?

The course consists of lectures and classes, but no practicals. Students hand in solutions to six problem sheets which will be discussed in classes during the term.
Synopsis

Copies of the key points for each lecture, along with notes giving details of proofs of results, will be made available in advance:

1. A gentle introduction. [key poimts: 1, 2, 4 slides per page]
2-3. Optimality conditions and why they are important. [key poimts: 1, 2, 4 slides per page] [notes: 1, 2 sides per page]

4-6. Line-search methods for unconstrained minimization. [key points: 1, 2, 4 slides per page] [notes: 1, 2 sides per page]

7-9. Trust-region methods for unconstrained minimization. [key points: 1, 2, 4 slides per page] [notes: 1, 2 sides per page]

10-11. Active-set methods for linearly-constrained minimization. [key points: 1, 2, 4 slides per page] [notes: 1, 2 sides per page]
12. Penalty and augmented Lagrangian methods for constrained minimization. [key points: 1, 2, 4 slides per page] [notes: 1, 2 sides per page]

13-14. Interior-point methods for constrained minimization. [key points: 1, 2, 4 slides per page] [notes: 1, 2 sides per page]

15-16. Sequential quadratic programming (SQP) methods for constrained minimization. [key points: 1, 2, 4 slides per page] [notes: 1, 2 sides per page]

Full lecture notes are available as an accompanying paper.
These notes form a self-contained introduction to the subject, and constitute compulsory reading assignments. Suggestions on how to improve the lecture notes are always very welcome!
In addition, I provide problem sheets and sample exams in PDF format (you will need the Acrobat software to read it).
Problem sheets

Problem set 1: on the material of lectures 1-3.

Problem set 2: on the material of lectures 4-6.

Problem set 3: on the material of lectures 7-9.

Problem set 4: on the material of lectures 10-12.

Problem set 5: on the material of lectures 13-14.

Problem set 6: on the material of lectures 15-16.

Revision material

Revision sheet

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 21st February 2006 at 14:35 GMT

1.	A gentle introduction. [key poimts: 1, 2, 4 slides per page]
2-3.	Optimality conditions and why they are important. [key poimts: 1, 2, 4 slides per page] [notes: 1, 2 sides per page]
4-6.	Line-search methods for unconstrained minimization. [key points: 1, 2, 4 slides per page] [notes: 1, 2 sides per page]
7-9.	Trust-region methods for unconstrained minimization. [key points: 1, 2, 4 slides per page] [notes: 1, 2 sides per page]
10-11.	Active-set methods for linearly-constrained minimization. [key points: 1, 2, 4 slides per page] [notes: 1, 2 sides per page]
12.	Penalty and augmented Lagrangian methods for constrained minimization. [key points: 1, 2, 4 slides per page] [notes: 1, 2 sides per page]
13-14.	Interior-point methods for constrained minimization. [key points: 1, 2, 4 slides per page] [notes: 1, 2 sides per page]
15-16.	Sequential quadratic programming (SQP) methods for constrained minimization. [key points: 1, 2, 4 slides per page] [notes: 1, 2 sides per page]