The fundamental theorem of Linear Programming: extensions and applications

The fundamental theorem of linear programming (LP) states that every feasible linear program that is bounded below has an optimal solution in a zero-dimensional face (a vertex) of the feasible polyhedron. We extend this result in two directions. We find a larger class of objective functions for which vertex optimality holds, and we give conditions guaranteeing the existence of an optimal solution in a larger family of faces of the feasible polyhedron. Our results also extend, with a very simple proof, the Frank-Wolfe theorem on the existence of an optimal solution to a Quadratic Program that is bounded below. We then apply our results to build up a general framework for obtaining upper and lower bounds and constant factor approximation algorithms for optimization problems. Furthermore, we show that several known results providing continuous formulations for discrete optimization problems can be easily derived and generalized with our extension of the fundamental theorem of Linear Programming. Finally, by exploiting the equivalence between continuous and discrete formulations of the problem of minimizing a function on a polyhedron, we prove polynomial-time solvability and present efficient algorithms for several new classes of continuous optimization problems. © 2011 Fabio Tardella.