6
$\begingroup$

In Section 2.3.3 "Polytopes and LP" of the book "Combinatorial Optimization: Algorithms and Complexity" by Christos H. Papadimitriou, Theorem 2.4 establishes the relation between bfs's (basic feasible solutions) of LP and vertices in polytope (for developing the simplex algorithm). However, I have difficulty in understanding its proof.


Consider an LP instance $Ax = b, x \ge 0$ where, $A$ is an $m \times n$ matrix, $x = (x_1, \ldots, x_n)$ is an $n$ (column) vector, and $b = (b_1, \ldots, b_m)$ is an $m$ (column) vector.

By convention (if I understand it correctly; Page 38 for the discussion), we can assume that the left hand sides of the LP instance is of the form with $A = [H|I]$ in the figure.

LP-form

Let $P \subseteq R^{n-m}$ be the convex polytope corresponding to the feasible set of the LP instance: $$x_j \ge 0, \quad j = 1, \ldots, n-m$$ $$b_i - \sum_{j=1}^{n-m} h_{ij} x_j \ge 0, \quad i = n-m+1, \ldots, n$$


Theorem 2.4 (Page 39) states that

$(c) \Rightarrow (a):$ If $y = (y_1, \ldots, y_n)$ is a bfs (basic feasible solution) of $Ax = b, x \ge 0$, then $\hat{y} = (y_1, \ldots, y_{n-m})$ is a vertex of $P$.


The proof (Page 40) goes as follows:

$y = (y_1, \ldots, y_n)$ is a bfs

$\Rightarrow^{1}$ there exists a cost vector $c$ such that $y$ is the unique vector $x \in R^{n}$ satisfying $c'x \le c'y; \quad Ax = b; \quad x \ge 0$ ($c'$ is the transpose of $c$).

$\Rightarrow^{2}$ $\hat{y} = (y_1, \ldots, y_{n-m})$ is the unique point in $R^{n-m}$ satisfying $d' \hat{x} \le d' \hat{y}, \hat{x} \in P$, where $$d_i = c_i - \sum_{j=1}^{m} h_{n-m+j,i}c_{n-m+j} \qquad i = 1, \ldots, n-m$$

$\Rightarrow^{3}$ $\hat{y}$ is a vertex of $P$, with supporting hyperplane defined by $d' \hat{x} = d' \hat{y}$


Questions:

  1. In step $\Rightarrow^{2}$: How $d' \hat{x} \le d' \hat{y}, \hat{x} \in P$ (in particular, the $d_i$ values) is obtained?
  2. In step $\Rightarrow^{3}$: Why does $d' \hat{x} \le d' \hat{y}, \hat{x} \in P$ imply that $\hat{y}$ is a vertex of $P$? Should a vertex in $P \subseteq R^{n-m}$ be defined by at least $n-m$ hyperplanes?
  3. Consider the following LP instance in Example 2.4 (Page 40; note that $A$ is of the form of $[H|I]$): $A = \begin{bmatrix} 1 &1 &1 &1 &0 &0 &0 \\ 1 &0 &0 &0 &1 &0 &0 \\ 0 &0 &1 &0 &0 &1 &0 \\ 0 &3 &1 &0 &0 &0 &1 \end{bmatrix}$ , $x \in R^{7} \ge 0, b = (4,2,3,6)$.
    Consider the base $\mathcal{B} = \{ A_1, A_2, A_4, A_6 \}$ ($A_i$ denotes the $i$-th column of $A$), its corresponding bfs is $y = \mathcal{B}^{-1}b = (2,2,0,0,0,3,0)$. According to Theorem 2.4, $\hat{y} = (2,2,0)$ is a vertex of the polytope $P$ corresponding to the feasible set of LP.
    How to obtain this result following the steps in the proof above?
$\endgroup$
  • 1
    $\begingroup$ Since you didn't get an answer here, you may want to repost on Mathematics. $\endgroup$ – Raphael May 24 '16 at 9:43

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.