0
$\begingroup$

Consider polytopes in $\mathbb R^n$ defined by

$x_i \ge 0, Ax = b$, for $b > 0$. Assume $A$ is of full rank $r$ and $Ax=b$ has solutions.

The following properties seems to be correct. I would be thankful for confirming my understanding is correct.

  1. All vertices of polytope can be described as points $(x_1\ldots x_n)$ with $n-r$ coordinates equal to zero, other $r$ coordinates can be found solving $Ax=b$. So there are $ (\frac {n}{n-r} )$ vertices.

  2. From each vertex there are $n-r$ outgoing edges (1-dimensional facets). This means that such polytopes are generic, since in general there can be many edges outgoing from each edge.

The edges outgoing some vertex with $n-r$ coordinates equal to zero, can be described by changing any of these coordinates away from zero.


Motivation is coming from simplex-method in linear-programming, where from constraints $Ax \le b$ one passes to constrains $Ax + Id s = b$, adding additional variables $s_i \ge 0$. As far as I understand the geometric meaning of such transform is to get more tractable polytope. Since initial polytope $ Ax \le b, x_i\ge0$ does not have clear description of vertices, neither clear description of edges, which are both crucial for simplex method since the idea of algorithm is to pass from of vertex to another by the edge joining them.


Additional question – consider convex polytope $Ax \le b$ in $R^n$, are there explicit algebraic conditions for $A,b$ such that polytope would be generic i.e. it does not change under small pertrubation, (in particular number of edges outgoing each vertex would be equal $n$ ).

$\endgroup$
1
$\begingroup$

Your point (1) is not correct. There can be at most $C(n,r)$ vertices, but it is easy to formulate LP's in which some basic solutions are infeasible because the corresponding point doesn't have $x \geq 0$. Furthermore, there are degenerate LP's in which a basic variable is 0 in the basic solution. In this situation, different bases can easily correspond to the same vertex.

You should read up on degeneracy in linear programming.

$\endgroup$
4
  • $\begingroup$ Thank you. Yeh, you right. something like (-x = b) is not consistent with x > 0. So there should be at most C(r,n), but not exactly C(r,n). However is it true that all vertices can be described "as points (x1...xn) with n−r coordinates equal to zero," $\endgroup$ Jan 27 '16 at 9:43
  • 1
    $\begingroup$ No, there could be more than $n-r$ components that are 0. Such a vertex and basic feasible solution are called "degenerate." $\endgroup$ Jan 27 '16 at 12:59
  • $\begingroup$ Thank you again, however that differs in tiny (but important) detail from what I am asking. I am asking weaker thing: all vertices have AT LEAST (n-r) zero components (I allow to have more zero components) - is it true ? Well, actually it seems "obvious", but I want to check that my understanding is correct. $\endgroup$ Jan 27 '16 at 13:05
  • 1
    $\begingroup$ Yes, any vertex will have at least $(n-r)$ zero components. However, if a vertex is degenerate then an arbitrarily small change to $A$ or $b$ can result in a change to the topology of polyhedron (e.g. new vertices and edges can appear.) $\endgroup$ Jan 27 '16 at 15:09

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.