| Unit name | Optimisation 2 |
|---|---|
| Unit code | MATH20600 |
| Credit points | 20 |
| Level of study | I/5 |
| Teaching block(s) |
Teaching Block 2 (weeks 13 - 24) |
| Unit director | Dr. Tadic |
| Open unit status | Not open |
| Pre-requisites |
MATH 11007 Calculus 1 and MATH 11005 Linear Algebra & Geometry. Cannot be taken with the Engineering Mathematics unit Optimisation Theory and Applications (EMAT 30670). |
| Co-requisites |
None |
| School/department | School of Mathematics |
| Faculty | Faculty of Science |
Unit aims
To introduce students to mathematical foundations of linear and nonlinear optimisation.
General Description of the Unit
Optimisation targets finding the functions' maxima and minima. This subject is very important in "real life" as one always wants to maximize the gain and minimize the effort. Optimisation essentially means being able to choose the best, or optimal strategy, or solution out of the large pool of feasible ones.
In elementary calculus of one variable one learns the simple rule for characterising the functions' extrema: df/dx = 0. But the scope of this rule is very limited. Even in one dimension things get more complicated if the domain of f, alias the feasible set is not the whole real line, but a subset of it, say one or several closed intervals. Already in this case, one has to evaluate the function at the endpoints, or the boundary of the feasible set. That is, the feasible set has non-trivial geometry. The geometry of R and for that matter Rn is trivial: one can go in any direction starting from any point, and it will all look the same.
Mathematically, a single possible strategy for an optimisation problem is described by a point x in Rn, where n can be pretty large. The complexity of the problem then depends on how the set of all feasible strategies looks like. The greater n, the more exotic it can get. To deal with such situations, a rich and subtle mathematical theory has developed, much of it over the last 60 years; the basics of these developments will be covered in the unit. These methods require nothing but a solid knowledge of differential calculus of several variables and linear algebra, namely the ability to solve systems of linear equations and manipulate with matrices and vectors. However, they provide a marvelous application thereof, with striking consequences. The other thing the unit requires is imagination, but this is true of all mathematics.
As the key [linear] optimisation tool (apart from differential calculus) the unit will introduce an algorithm, called the Simplex method, invented by G. Danzig in early 1950's, and presently underlying the area of so-called Linear programming (a historical term giving an irrelevant and misleading link towards Computer science). One needs a fair bit of theory, concerning so-called basic solutions to bring the method in, and still more theory to take full advantage of the number of quantities, which are being computed throughout the algorithm. The latter will peak in the duality theorem, with many corollaries. Interestingly enough, the duality theorem is a corollary of a theorem of Julius Farkas, that has been around since the early 1900s and is known as the Farkas alternative. Generally speaking, duality is an extremely useful basic principle of modern analysis, whose importance was first emphasised by Newton. If time allows, applications of the duality principle in game theory and mathematical finance will be addressed.
For nonlinear theory, the unit will treat (i) unconstrained (local and global) optimization and convexity; (ii) optimization under equality constraints, and the Lagrange method, and (iii) optimization under inequality constraints, and the Kuhn-Tucker conditions. The latter may appear unwieldy, but they represent the apogee of the whole theoretical matter, implying in particular the duality theorem. In essence though, they once again restate the Farkas alternative.
Relation to Other Units
Related material is in the Engineering Mathematics unit Optimisation Theory and Applications. Students may not take both units.
Additional unit information can be found at http://www.maths.bristol.ac.uk/study/undergrad/current_units/index.html
Learning Objectives
At the end of the unit students should be able to:
formulate practical linear problems mathematically, starting from the verbal description;
prove correct the solution obtained to a "small" problem, without appealing to the simplex method;
find local optima of explicitly given functions of several variables, with or without constraints;
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.
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.
100% Examination
Raw scores on the examinations will be determined according to the marking scheme written on the examination paper. The marking scheme, indicating the maximum score per question, is a guide to the relative weighting of the questions. Raw scores are moderated as described in the Undergraduate Handbook.
If you fail this unit and are required to resit, reassessment is by a written examination in the August/September Resit and Supplementary exam period.
Reading and references are available at http://www.maths.bristol.ac.uk/study/undergrad/current_units/index.html
