2
$\begingroup$

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?

Improve this question
$\endgroup$
3
  • 1
    $\begingroup$ Perhaps the vertex enumeration problem is of interest to you. $\endgroup$
    – Rodrigo de Azevedo
    Commented 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$
    – Davide Papapicco
    Commented 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
    Commented Feb 1, 2020 at 15:16

1 Answer 1

Reset to default
3
$\begingroup$

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

Improve this answer
$\endgroup$
0

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .