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 '20 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$
    – papadeiv
    Feb 1 '20 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 '20 at 15:16

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, privacy policy and cookie policy

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