Optimisation is the art of getting (at least close to) the best solution of a given problem within physical, economic or other constraints. It has a host of applications, for example business planning, industrial process control, data fitting, design of structures, and game strategies.
This course will cover the essential theory needed to understand what computational methods do, and why; explain the fundamental algorithms such as Quasi-Newton methods for non-linear optimisation and the Simplex method for linear programming; and explore these algorithms in action using simple example programs.
The course is intended for practising scientists and engineers who require an overview of the various branches of optimisation with an emphasis on available techniques and their application to real-life problems. There are no rigid entry requirements, but it is expected that participants will be educated to degree level with knowledge of mathematics of at least 'A' level standard, including a familiarity with vector and matrix notation. The material in our course Introduction to Numerical Methods provides more than an adequate background.
The course includes:
Introduction:
The nature of
optimisation problems and their solutions. Global and local optima. A review
of vector and matrix notation and algebra. The significance of
differentiability of functions.
Unconstrained problems in one dimension:
Line search algorithms: bisection, regula falsi,
Newton, secant, golden section,
Fletcher and Powell.
Unconstrained problems in many dimensions:
Elementary methods: the Simplex method; Hooke and Jeeves method;
conjugate directions. Newton and quasi-Newton methods. Choleski
decomposition. Approximating
the Hessian Matrix. The DFP method. The BFGS method. Application to non-linear
regression and data fitting.
Linear Programming:
Basic ideas. The Simplex
Algorithm. The two-phase method. Duality theory. The dual simplex
method. Sensitivity
analysis.
Integer Linear Programming:
Integer valued variables.
The dangers of rounding. Uses of binary variables. Alternative constraints and
non-convex feasible regions. Branch and Bound technique. Cutting plane
algorithms. Special ordered sets.
Dynamic Programming:
The nature of problems
suitable for solution by DP. Separable functions. Terminology: stages and state
variables. Solution method. Mathematical formulation.
Constrained non-linear optimisation:
Equality constraints. Substitution. Penalty functions. The Lagrangian
function and
Lagrange multipliers. The Augmented Lagrangian method.
Inequality constraints:
Feasible directions. The Khun-Tucker
conditions. Solution methods: penalty functions, multiplier penalty functions,
quadratic programming, active set methods.
Review of Software:
An overview of the types of
software available for solution of optimisation problems, both general purpose
and specialist.
Practicals:
Computer practicals will be used to motivate
and illustrate many of the methods discussed. Software used will include
specialised mathematical programming packages and the MATLAB Optimisation
Toolbox.
The course lectures will be given by the teaching and research staff of the Applied Mathematics and Operational Research Group. External speakers may give lectures on advanced topics.