0

My Optimization book defines a polyhedron as an intersection of finitely many half-spaces, and a polytope $P$ is defined as a bounded polyhedron. The book then goes on to talk about the edges and the non-degenerate vertices, but it does not define these terms (altough it does define a vertex as a point of $P$ which is not the convex combination of any two points in $P$). Could you please enlighten me to the definition of these two terms?

My Idea:

In $\mathbb{R}^2$, an edge of the polytope is a one of the actual hyperplanes defining the polytope. In $\mathbb{R}^3$, an edge of the polytope is the intersection of any two of the hyperplanes defining the polytope. My idea is that in $\mathbb{R}^n$, an edge of the polytope is the intersection of any $n-1$ hyperplanes defining the polytope.

As far as degenrate vertex, I really don't know. Based on the context, I think the following is an example of a degenerate vertex: consider a polytope in $\mathbb{R}^2$ which is just a line segment. Then its endpoints are degenerate vertices.

Blue
  • 492
  • 1
    As the definitions in optimization differ from the more common definitions (in particular, in general a "polyhedron" is 3-dimensional, bounded, and need not be convex), I may be wrong, but I would expect that "edge" would refer only to the portion of the intersection of $n-1$ hyperplanes that lies within the polytope. – Paul Sinclair Oct 04 '20 at 13:27
  • I just answered this question in the comments of this answer, where you conveniently posted the same question – LinAlg Oct 04 '20 at 14:09

1 Answers1

1

I'm a little late but I'm currently studying for an exam in Optimization and we actually have a definition given for degeneracy! It reads as follows:

If you have given a matrix $\text{A} \in \mathbb{R}^{\text{mxn}}$, $\text{A}$ has full row rank $m$ and a Polyhedron $\text{P}^{=}(A,b)$ with a corresponding feasible basis $B$ and a feasible basic solution $x^{*} = (x^{*}_B, x^{*}_N)$.

Then $x^*$ is $non-degenerate$, if $x^*_B > 0$ holds, and otherwise degenerate (i.e. if for some indices $i \in B$ we have $x_i = 0$).

This means that non-degenerate basic solutions only have one unique basis, and when a solution is degenerate we have multiple bases for it.

moldbellchains
  • 79