# Sampling algorithms on convex polytopes

Let $$f=\mathbf{c}\cdot\mathbf{x}$$ be the optimization objective function whose parameter vector $$\mathbf{x}\in\mathbb{R}^n$$ is subject to the following constraints in the very well-known linear-programming problem $$\mathbf{A}\mathbf{x}=\mathbf{b}\in\mathbb{R}^m\;,\quad \mathbf{0}\leq\mathbf{x}\leq\mathbf{v}$$ Suppose that the space of feasible solutions of the above linear system is a convex polytope; my questions are the following:

1. How are the vertices of said polytope found in linear programming? Kindly reference the theoretical argument for that.

2. What are the MCMC algorithms to sample points from the polytope s.t. it eventually finds the optimal point for the object function?

• Perhaps the vertex enumeration problem is of interest to you. – Rodrigo de Azevedo Feb 1 at 12:10
• So does that mean it is an open problem and I can't find the vertices of a convex polytope in general? – Davide Papapicco Feb 1 at 13:02
• For one thing, there can be exponentially many vertices, e.g. the hypercube. So more needs to be said about what it means to "find" the vertices. – usul Feb 1 at 15:16