0
$\begingroup$

Consider $P$ a convex polytope in $\mathbb R^d$, and $x\in P$ a vertex of $P$. Let $N_P(x)$ be the set of "neighboring" points of $x$. A vertex $y\in P, y\neq x$ is a neighbor of $x$ if $(x,y)$ is an edge (1-dimensional face) of $P$. Mathematically, $(x,y)$ is an edge if and only if there exists $c\in\mathbb R^d$, $c\neq 0$, such that $c^\top (y-x)=0$ and $c^\top (z-x)<0$ for all vertices $z$ different from $x,y$.

Question: Now suppose for some non-zero $c\in\mathbb R^d$, $c^\top (y-x) < 0$ for all $y\in N_P(x)$. Prove that $c^\top(z-x)<0$ as well for all other vertices of $P$.

My attempt (partial solution): when the vertex $x$ is not over-specified (i.e., there are exactly $d$ facets intersecting at $x$), it is not difficult to prove that each facet corresponds to an edge, and therefore $c$ must be in the normal cone of $x$. However, I do not know how this argument could be extended to over-specified $x$.

$\endgroup$
11
  • $\begingroup$ By polytope do you mean the convex hull of a finite number of points? $\endgroup$
    – copper.hat
    Mar 5, 2020 at 18:37
  • $\begingroup$ Yes, a convex polytope is a convex hull of a finite number of points in $\mathbb R^d$. $\endgroup$ Mar 5, 2020 at 19:27
  • $\begingroup$ How do you define a vertex? I have only seen them defined for affinely independent sets. An extreme point? $\endgroup$
    – copper.hat
    Mar 6, 2020 at 4:15
  • $\begingroup$ $x\in P$ is a vertex if its normal cone is $d$-dimensional. (The normal cone of $x$ is the set of all $c\in\mathbb R^d$ such that $c^T x\geq \sup_{z\in P}c^\top z$.) $\endgroup$ Mar 6, 2020 at 20:27
  • $\begingroup$ Perhaps I am misunderstanding, but if $P$ has a non empty interior, then every point on the boundary will be a vertex by this definition? I presume by dimension you mean the dimension of the affine hull? $\endgroup$
    – copper.hat
    Mar 6, 2020 at 21:38

1 Answer 1

1
$\begingroup$

General: Given a vertex $x_0\in P$ the simplex algorithm computes an optimal vertex $x^*$ which fulfills $c^Tx^*=\max_{y\in P}c^Ty$. In each step, the algorithm moves from vertex to vertex via the edges of the polytope. This yields a sequence of vertices $x_0,x_1,...,x^*$ such that

$c^Tx_0\leq c^Tx_1\leq ...\leq c^Tx^*$

holds.

In this case: Assume there exist vertices $y\notin N_P(x)$, such that $c^T(y-x)\geq 0$ is satisfied. Take a vertex $x^*\neq x$ which maximises $c^Ty$ of all vertices. Therefore, by the simplex algorithm we have a sequence of vertices $x,y_1,...,y_k,x^*$ with $c^Tx\leq c^Ty_1\leq ...\leq c^Tx^*$. Since $x^*\notin N_P(x)$, we have $y_1\in N_P(x)$ with $c^Tx\leq c^Ty_1$ which contradicts $c^T(y_1-x)<0$.

$\endgroup$
5
  • $\begingroup$ Thank you. This sounds like a very clean proof to the statement and could also be applied to some of my other variants of the statement. I need to do more reading on simplex methods. Is it true that, for any bounded polytope and any starting point, the simplex method always terminates in finite number of edge travels? $\endgroup$ Mar 8, 2020 at 18:14
  • $\begingroup$ Yes, there are special implementations which guarantee finite termination. $\endgroup$
    – sqlman
    Mar 8, 2020 at 18:26
  • $\begingroup$ How do you know that $[x,y_1]$ is an edge as defined in the question. $\endgroup$
    – copper.hat
    Mar 9, 2020 at 13:16
  • $\begingroup$ @copper.hat I can prove rigorously that the edge I defined is equivalent to "1-dimensional faces" of a polytope. So this should not be a problem. $\endgroup$ Mar 9, 2020 at 21:51
  • $\begingroup$ Yes, but the discussion above does not show that $[x,y_1]$ is an edge. $\endgroup$
    – copper.hat
    Mar 9, 2020 at 22:57

You must log in to answer this question.

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