1

Let $P=\{x:\;a_i^Tx\leq b_i,\;\forall i\}$ be a Polyhedron in $\mathbb{R}^n$. Let $x$ and $y$ be two distinct basic feasible solutions.
Recall $I_x =\{i:\;a_i^Tx\leq b_i \}$
Suppose that rank $\{ a_i: i \in I_x ∩ I_y \} = n − 1$.
Then the line segment $L_{x,y} = \{ \lambda x + (1 − \lambda)y :\, \lambda \in [0, 1] \}$ is an edge of P. Moreover, if P is a polytope, then every edge arises in this way.

I found this definition online and I have a problem understanding parts of it. If P is defined the way it is, then the inequality holds for all $i$ and for all (basic) feasible solutions. Wouldn't that then mean that $I_x=I_y=I_x\cap I_y$? Because otherwise there are $i$ for which the inequality doesn't hold and therefore the solution isn't an element of the Polyhedron, which is a contradiction. This part is quite confusing to me and I would appreciate anyone helping to clear up the confusion.

user619755
  • 620

1 Answers1

1

The text is wrong. It should be $I_x = \{i : a_i^Tx = b_i\}$. This is exercise 2.15 in Introduction to Linear Optimization by Bertsimas and Tsitsiklis.

LinAlg
  • 19,822
  • 1
    Thank you! Makes sense, the definition threw me off. – user619755 Jun 12 '20 at 21:35
  • Dear @user619755 or LinAlg, could you please tell me what the definition of an edge of a polytope is? – Blue Oct 04 '20 at 03:05
  • @Blue I guess you could say an edge is a 1-dimensional face of a polytope, therefore a line connecting two vertices/corners (do you know the definition of a face?). Also, as you can see in my post, "if P is a Polytope, every edge" takes the form of $L_{x,y}$ above, where $x$ and $y$ are corners. – user619755 Oct 04 '20 at 10:30
  • @user619755 Thanks for your reply. I also don't know the definition of a face, do you have a rigorous definiton for that? About the definition in your post: I think it needs to have some restrictions, because we cannot just take any two vertices $x, y$, connect them with line, and get an edge. For example in a square, if we connect two opposite corners, we get a diagonal, which is not an edge. – Blue Oct 04 '20 at 12:27
  • @Blue Wikipedia defines a face as a polygon on the boundary of a polyhedron. Some textbooks define a face as a set that maximizes $c^Tx$ for some vector $c$. The latter is the correct definition and also gives the (improper) face that is the polyhedron itself. – LinAlg Oct 04 '20 at 13:18
  • @Blue well the restrictions that that you are talking about are in my post as well, check the part about rank${ a_i: i \in I_x ∩ I_y } = n − 1$. As for the definition of a face: $\mathcal{F}$ is a face of $\mathcal{P}$, iff $\mathcal{F}=\mathcal{P}\cap{x\in\Bbb{R}^n\ :\ A_ix=b_i}$ – user619755 Oct 05 '20 at 14:56