Exercise 2.12

Question

Consider a nonempty polyhedron $P$ and suppose that for each variable $x_i$ we have either the constraint $x_i \geq 0$ or $x_i \leq 0$. Is it true that $P$ has at least one basic feasible solution?

Elu Thingol · Accepted Answer

extbf{Yes.} This is practically a baby version of Theorem 2.6 (Existence of extreme points). We demonstrate that $P$ cannot contain a line, i.e., for any vector $\mathbf{x} \in P$ and any nonzero vector $\mathbf{d} \in \mathfrak{R}^n$ we can find some $\lambda \in \mathfrak{R}$ such that $\mathbf{x} + \lambda \mathbf{d} 
ot\in P$. To do so, we make use of the fact that the negativity-positivity constraints are linearly independent, i.e., assuming without loss of generality the following order of constraints, we have
$$\begin{bmatrix}
\pm1   &\ldots  & 0\
\vdots & \ddots & \vdots\
0      &\ldots  & \pm 1\
a_{1,n+1}& \ldots & a_{n,n+1} \ 
\vdots & \ddots & \vdots\
a_{1,m}& \ldots & a_{n,m}
\end{bmatrix}
\begin{bmatrix} x_1 \ \vdots\ x_n \end{bmatrix} \geq
\begin{bmatrix} 0 \ \vdots \ 0 \ b_{n+1} \ \vdots \ b_{m} \end{bmatrix}.
$$
\begin{proof}
Let $\mathbf{x}$ be an element of $P$ and let $I = \{i \mid \ x_i = 0\}$. If $n$ of the standard vectors $\pm\mathbf{e}_i$, $1 \leq i \leq n$, corresponding to the active negativity-positivity constraints are contained in $I$, then $\mathbf{x}$ is, by definition, a basic feasible solution and, therefore, a basic feasible solution exists. If this is not the case, then we can find at least one $1 \leq j \leq n$ such that $x_j 
eq 0$, i.e., either $x_j > 0$ or $x_j < 0$. But then it is obvious that
$$\forall \mathbf{d}\in\mathfrak{R}^n \quad 	ext{for } \lambda:=- 2\frac{x_j}{d_j}: \quad \mathbf{x} - 2\frac{x_j}{d_j} \mathbf{d} 
ot\in P$$
since the $j$th component of this vector $x_j - 2\frac{x_j}{d_j}d_j = -x_j$  is the opposite of $x_j$ and thus violates the $j$-th constraint. Thus, $P$ cannot contain a line and must therefore, by Theorem 2.6, possess an extreme point.
\end{proof}

Exercise 2.12

Answers

Comments

Exercise 2.12

Answers

Comments

Add answer