ACS6408 Optimisation: Theory, algorithms and applications

Module Description

This unit aims to provide detailed presentations to the use of numerical optimisation and search methods for a wide range of engineering problems. Traditional approaches drawn from Operations Research will be enhanced by topics based on recent developments in heuristic methods, such as evolutionary computing, e.g. genetic algorithms and swarm intelligence.

Credits: 15 (Autumn semester)

Module Leader

Dr Leon WeiDr Leon Wei
Room D06, Amy Johnson Building

If you have any questions about the module please talk to me during the lectures or the labs in the first instance. It is likely that other students will learn from any questions you ask as well, so don’t be afraid to ask.

Outside of lectures please contact me via email, or drop in to see me.

Learning Outcomes

Learning Outcomes

At the end of the module, the student should be able to:

  1. List and describe the main methods of optimisation; evaluate and appraise their performance; propose an appropriate method for a typical specific optimisation problem; extend, adapt and integrate the theory and methods of optimisation to solve unfamiliar problems. [SM1m, SM2m, SM4m, EA3m, EA4m, EA6m, D3m, D4m, D6m, D7m, EP9m]
  2. Formulate, solve and interpret linear programming (LP) problems by graphical and simplex methods. [SM5m, EA4m, D3m, EP10m]
  3. Develop an in-depth understanding of the theory of unconstrained and constrained optimisation; apply the results to solve typical problems both analytically and numerically (e.g. using Matlab); appraise and evaluate the performance and limits of these methods, and adapt them to new problems. [SM1m, SM2m, SM4m, SM5m, EA3m, EA4m, EA5m, EA6m, D3m, D4m, D6m, EP1m, EP4m, EP9m]
  4. Design and apply evolutionary algorithms by selecting appropriate techniques for specific problems. [SM2m, SM4m, SM5m, EA3m, EA4m, EA5m, EA6m, D2m, D7m, EP1m, EP9m]
  5. Extend knowledge of single objective optimisation to the multi-objective case. [SM6m, EA3m, EA4m, EA5m, EA6m, D2m, D4m, EP1m, EP9m]

This module satisfies the AHEP3 (Accreditation of Higher Education Programmes, Third Edition) Learning Outcomes that are listed in brackets after each learning outcome above. For further details on AHEP3 Learning Outcomes, see the downloads section of our accreditation webpage.

Syllabus

Syllabus 

This module includes two themes:

  • Classical optimisation methods/algorithms (e.g. gradient or steepest descent search method, Newton’s method etc), and
  • Heuristic search algorithms (e,g, evolutionary algorithms, genetic algorithms etc).
  1. Overview of optimisation and operations research. Optimisation and operations research problems and their classification.
  2. Linear programming. LP problems (equality, inequality, canonical problems). Graphical method. Simplex method. Duality theory.
  3. Applications of linear programming. Transportation problems. Network problems (minimum cost flow, maximal flow). Game theory (zero-sum two person games).
  4. Non-linear unconstrained optimisation. Necessary and sufficient conditions. Line search methods (golden section, quadratic interpolation). Gradient methods. Newton methods. Quasi-Newton methods. Step size rules (minimisation, Armijo, constant, vanishing step size rules).
  5. Non-linear constrained optimisation. Lagrangian function. Necessary and sufficient conditions. Feasible direction methods. Penalty methods. Barrier methods. Lagrange methods. Interior point methods. Applications to real-world problems.
  6. Heuristic Search. Understanding basic features of search methods. Modelling the problem, constraints, representation, evaluation, neighbourhoods and local optima. Exhaustive search, local search. Greedy algorithms, divide and conquer, dynamic programming, branch-and-bound. Simulated annealing.
  7. Evolutionary Algorithms. Designing evolutionary algorithms. Representation, evaluation, variation operators, selection, initialization. Other types of evolutionary algorithms. Genetic programming. Multiobjective optimization.
Teaching Methods

Learning and Teaching Methods

Lectures: 24 hours
Example classes: 6 hours
Lab Classes: 12 hours
Independent Study: 106 hours

Teaching Materials

Learning and Teaching Materials

All teaching materials will be available via MOLE.

Assessment

Assessment

30% Coursework (3 assignments)

70% Exam (2 hour written examination)

No resit examination is available for this module.

Feedback

Feedback

This module includes two themes:

Students will receive feedback through tutorials and question and answer sessions. They will also have the opportunity to undertake informal formative examinations e.g. laboratory exercises, for which they will receive feedback.

Student Evaluation

Student Evaluation

Students are encouraged to provide feedback during the module direct to the lecturer. Students will also have the opportunity to provide formal feedback via the Faculty of Engineering Student Evaluation Survey at the end of the module.

Recommended Reading

Recommended Reading

  • S.S. Rao, Engineering Optimization - Theory and Practice (4th Ed),
    John Wiley & Sons Inc., 2009
  • S. Boyd and L. Vandenberghe, Convex Optimization, Cambridge University Press, 2004.
    Free available at
    https://web.stanford.edu/~boyd/cvxbook/
  • F. S. Hillier, and G. J. Lieberman, Introduction to Operations Research, McGraw Hill, 2005 (8th ed.), [available in Western Bank Library, Q658.4034 (H)]
  • D. G. Luenberger, and Y. Ye, Linear and Nonlinear Programming, Springer, 2008 (3rd ed.)
  • Z. Michalewicz and D.B. Fogel, How To Solve It: Modern Heuristics, Springer 2000.
  • M. S. Bazaraa, H. D. Sherali, and C. M. Shetty, Nonlinear Programming, John Wiley & Blackwell, 2006(3rd ed.).