Convexity and Optimisation

10 credits

Syllabus, Bachelor's level, 1MA023

This course has been discontinued.

A revised version of the syllabus is available.

Code: 1MA023
Education cycle: First cycle
Main field(s) of study and in-depth level: Mathematics G1F
Grading system: Pass with distinction (5), Pass with credit (4), Pass (3), Fail (U)
Finalised by: The Faculty Board of Science and Technology, 15 March 2007
Responsible department: Department of Mathematics

What is a course syllabus?

Entry requirements

Several Variable Calculus, Linear Algebra II

Learning outcomes

In order to pass the course (grade 3) the student should be able to

give an account of important concepts and definitions in convexity theory;

give an account of the duality concept in linear programming;

outline some variant of the simplex algorithm and of some inner point method for linear programs;

explain the role of the Lagrange function and the Kuhn–Tucker theorem in non-linear programming;

formulate important results and theorems covered by the course and describe the main features of their proofs;

express optimisation problems from various areas of applications in a mathematical form suitable for further analysis;

use the theory, methods and techniques of the course to solve mathematical problems;

present mathematical arguments to others.

Content

Convex sets: separation theorems, supporting hyperplanes and extremal points. Cones: finitely generated cones, dual cones, extremal rays. Polyhedra: Motzkin's theorem. Solvability of systems of linear inequalities: Farkas' lemma. Convex functions: characterisation in terms of subdifferentials and the Hessian. Linear programming: duality, the simplex algorithm, inner point methods, Karmarkar's algorithm and briefly about complexity. Non-linear and convex optimisation: the Lagrange function, Kuhn–Tucker theorems. Examples from production planning, economy and game theory.

Instruction

Lectures and problem solving sessions.

Assessment

Written and, possibly, oral examination at the end of the course. Moreover, compulsory assignments may be given during the course.