Optimisation

11-15 February 2008

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.