Geometric Aspects of Linear Programming : Shadow Paths, Central Paths, and a Cutting Plane Method

Abstract

Most everyday algorithms are well-understood; predictions made theoretically about them closely match what we observe in practice. This is not the case for all algorithms, and some algorithms are still poorly understood on a theoretical level. This is the case for many algorithms used for solving optimization problems from operations reserach. Solving such optimization problems is essential in many industries and is done every day.

One important example of such optimization problems are Linear Programming problems. There are a couple of different algorithms that are popular in practice, among which is one which has been in use for almost 80 years. Nonetheless, our theoretical understanding of these algorithms is limited.

This thesis makes progress towards a better understanding of these key algorithms for lineair programming, among which are the simplex method, interior point methods, and cutting plane methods.