Polyhedral Computation

Overview

Polyhedral computation deals with various computational problems associated with convex polyhedra in general dimension. Typical problems include the representation conversion problem (between halfspace and generator representations), the polytope volume computation, the construction of hyperplane arrangements and zonotopes, the Minkowski addition of convex polytopes.

In this lecture, we study basic and advanced techniques for polyhedral computation in general dimension. We review some classical results on convexity and convex polyhedra such as polyhedral duality, Euler's relation, shellability, McMullen's upper bound theorem, the Minkowski-Weyl theorem, face counting formulas for arrangements, Shannon's theorem on simplicial cells. Our main goal is to investigate fundamental problems in polyhedral computation from both the complexity theory and the viewpoint of algorithmic design. Optimization methods, in particular, linear programming algorithms, will be used as essential building blocks of advanced algorithms in polyhedral computation. Various research problems, both theoretical and algorithmic, in polyhedral computation will be presented.

We also study applications of polyhedral computation in combinatorial optimization, integer programming, game theory, parametric linear and quadratic programming.

Prerequisites and Remarks

This course assumes the basic knowledge of linear programming, which is taught in courses such as "Introduction to Optimization" (401-2903-00L) and "Mathematical Optimization" (401-3901-00L), formerly known as "Optimization Techniques".

Evaluation

Solving at least 50% of exercise problems is required for a student to qualify for the exam. In order (for both a masters and doctorate student) to obtain credits, one has to pass the oral exam during an ordinary exam period. The duration is thirty minutes.

Lecture notes

will be available on this page during the course

Schedule