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?

  • 1
    $\begingroup$ Perhaps the vertex enumeration problem is of interest to you. $\endgroup$ Feb 1, 2020 at 12:10
  • $\begingroup$ So does that mean it is an open problem and I can't find the vertices of a convex polytope in general? $\endgroup$ Feb 1, 2020 at 13:02
  • $\begingroup$ 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. $\endgroup$
    – usul
    Feb 1, 2020 at 15:16

1 Answer 1


Here is a link for software and references: https://rdrr.io/cran/volesti/man/sample_points.html


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.