Geometry of Optimisation

Overview

• Functionals on R^n, linear equations and inequalities; hyperplanes; half-spaces
• Convex polytopes; faces
• Specific examples: e.g., traveling salesman polytope, matching polytopes
• Linear optimisation problems; geometric interpretation; graphical solutions
• Simplex algorithm
• LP duality
• Further topics in optimisation, e.g., integer programming, ellipsoid method

Learning Objectives

It is intended that students shall, on successful completion of the module, be able to:
• demonstrate understanding of the foundational geometry of convex polytopes;
• demonstrate understand of the geometric ideas behind linear optimisation;
• solve simple optimisation problems graphically;
• apply the simplex algorithm to concrete optimisation problems.

Skills

Knowing and applying basic techniques of polytope theory and optimisation.

Assessment

None