Breadcrumb

Optimisation 2 (MATH 20600)

Academic Year:

Contents of this document:

Administrative Information

  1. Unit number and title: MATH 20600 Optimisation 2
  2. Level: I/5
  3. Credit point value: 20 credit points
  4. Year: 12/13
  5. First Given in this form: 1989
  6. Unit Organiser: Vladislav Tadic
  7. Lecturer: V. Tadic
  8. Teaching block: 1
  9. Prerequisites: MATH 11007 Calculus 1 and MATH 11005 Linear Algebra & Geometry. Cannot be taken with the Engineering Mathematics unit Optimisation Theory and Applications (EMAT 30670).

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.

Teaching Methods

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.

Learning Objectives

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.

Assessment Methods

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.

Award of Credit Points

Credit points are gained by:

  • either passing the unit, i.e getting a final assessment mark of at least 40,
  • or gaining a final assessment mark of at least 30 and performing satisfactorily on the homework.

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.

Texts

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, inexpensive, 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.

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.

Optimisation 2

All the course information will be available on

Unit Home Page: http://www.maths.bris.ac.uk/~maxmr/opt2.html