# ACS6408 Optimisation: Theory, algorithms and applications

## Module Description (subject to change)

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)

Dr Leon Wei

Email: w.hualiang@sheffield.ac.uk
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.

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

NOTE: This summary of teaching methods is representative of a normal Semester. Owing to the ongoing disruption from Covid-19, the exact method of delivery will be different in 2020/21.

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 Blackboard (MOLE).

Assessment

### Assessment

Coursework (Asynchronous, Limited Window) - 100%

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.

You can view the latest Department response to the survey feedback here.