Unit information: Optimisation 2 in 2013/14

Unit name	Optimisation 2
Unit code	MATH20600
Credit points	20
Level of study	I/5
Teaching block(s)	Teaching Block 1 (weeks 1 - 12)
Unit director	Dr. Misha Rudnev
Open unit status	Not open
Pre-requisites	MATH11002 and MATH11003
Co-requisites	None
School/department	School of Mathematics
Faculty	Faculty of Science

Description including Unit Aims

Methods for finding (local or global) maxima or minima of functions of 1 or more variables, particularly when subject to constraint. Linear programming and non- linear minimisation, including results where convexity is relevant, such as the Kuhn-Tucker theorems. Applications in industry and economics. The emphasis is on practical techniques for solution of specific problems, but enough theory is given to provide a solid foundation for them. Some numerical work is included.

Aims:

To introduce students to mathematical foundations of linear and nonlinear optimisation.

Syllabus

The number of lectures shown is approximate. Some miscellaneous items may be added/removed throughout the course.

Introduction (2). Linear programming: the Simplex Method (7), sensitivity, duality, convexity and Farkas alternative (8). Applications in Game theory (2, if time allows).

Non-linear problems: unconstrained maxima and minima for functions of n variables, the Hessian and convexity, Jensen's inequality and corollares (5); problems with equality constraints; Lagrange multipliers (3); problems with inequality constraints; the Kuhn-Tucker conditions (6).

Note: There are 33 hours listed here. The remaining hours (out 36 available) will be devoted to additional topics, worked examples, discussions of difficult points, etc.

Approximately one week before the exam, a review session will be held.

Relation to Other Units

Related material is in the Engineering Mathematics unit Optimisation Theory and Applications. Students may not take both units.

Intended Learning Outcomes

At the end of the unit students should be able to:

• understand basic concepts of optimisation;
• formulate practical linear problems mathematically, starting from the verbal description;
• understand the theory underlying the simplex method, including the theory of convex sets;
• solve "small" linear problems by the simplex method;
• prove correct the solution obtained to a "small" problem, without appealing to the simplex method;
• exploit duality in linear problems, understand the concept of sensitivity;
• find local optima of explicitly given functions of several variables, with or without constraints;
• identify convex and concave functions, understand their maths and relevance to optimisation;
• understand how the Kuhn-Tucker conditions wrap up the theoretical basis for the unit;
• interpret the results of an optimisation calculation in terms of the original practical problem.

Transferable Skills:

This is an eclectic course with relevance to a wide spectrum of Maths. Intelligence and imagination; mathematical formulation of complex "real-world" problems that are presented in continuous prose; communication to non-mathematicians of the results of a mathematical investigation.

Teaching Information

Lectures; discussions in Problems classes. Homework will be of critical importance and an average student is expected to invest some 5 hours a week into it. There is a lot of software, designed for optimisation, some being available online, yet using it is not part of the course. Students are expected to do independent study and reading.

Assessment Information

The final assessment mark for the unit is calculated 100% from a standard rubric examination in April. This means a 2½-hour written exam consisting of FIVE questions; your best FOUR will be counted towards the exam mark. Candidates may bring one A4 double-sided sheet of notes into the exam. Calculators of an approved type (non-programmable, no text facility) are permitted in the examination.

Reading and References

There will be no regular printed notes distributed, yet the course is accompanied by a series of handouts which address the majority of the difficult issues involved.

The unit is not based on a single book, and there is no mandatory text. However, the following books are highly recommended. There are many other texts covering various parts of the unit: try browsing in the shelves QA402 and T57 in Queen's Building Library. They can be used to get different perspectives on the material covered.

• J.N. Franklin, Methods of Mathematical Economics: Linear and Nonlinear Programming, Fixed-Point Theorems (recently published as SIAM Classics in Applied Mathematics 37). Excellent book, though sometimes quite advanced. Best for theory. However, the simplex method per se within the unit's limits would be more accessible elsewhere.
• W. L. Winston, Introduction to Mathematical Programming (on reserve in the Library). Parts of chapters 3, 4, 5, 6, 12 are relevant to this unit. An antipode to Franklin's book, designed for MBA's. Much of this book is at the easy level for the theory, and it has many examples.
• H.P. Williams, Model Solving in Mathematical Programming (on reserve in the Library). Clearly written, covers in detail the "linear" part of the course and goes on to more advanced material.
• E.M.L. Beale, Introduction to Optimization (Wiley). Brief, clear, covers a good deal of the course.
• R. Hartley, Linear and Nonlinear Programming. More detailed than Beale, but does not cover so many topics.
• G.R. Walsh, An Intorduction to Linear Programming. The title is self-explanatory, the book has a good level of detail and complexity. Among other things, it contains a good exposition of the Ellipsoid algorithm, which however is beyond the unit's scope.