3
$\begingroup$

I'm having difficulty following a proof in the book Nonlinear Programming Theory and Algorithms, Third Edition by Bazaraa, Sherali, and Shetty on page 68 section 2.6.4. The proof is reproduced below, up to the part of the proof I'm confused about.

My question concerns the author's statement:

But this implies that $x_{11} = x_{21} = B^{-1}b$.

I don't see how the author makes that connection.

Theorem (Existence of Extreme Points)

Let $S = \{ x : Ax = b, x \geq 0\}$, where $A$ is an m x n matrix and $b$ is an m-vector. A point $x$ is an extreme point of $S$ if and only if $A$ can be decomposed into $[B, N]$ such that

$x = \begin{bmatrix} x_B \\ x_N \end{bmatrix} = \begin{bmatrix} B^{-1}b \\ 0 \end{bmatrix}$

Proof:

Suppose that $A$ can be decomposed into $[B, N]$ with $x = \begin{bmatrix} B^{-1}b \\ 0 \end{bmatrix}$ and $B^{-1}b \geq 0$. It is obvious that $x \in S$. Now suppose that $x = \lambda x_1 + (1 - \lambda)x_2$ with $x_1$, $x_2 \in S$ for some $\lambda \in (0,1)$. In particular, let $x^{t}_{1} = (x^{t}_{11}, x^{t}_{12})$ and $x^{t}_{2} = (x^{t}_{21}, x^{t}_{22})$. Then

$\begin{bmatrix} B^{-1}b \\ 0 \end{bmatrix} = \lambda \begin{bmatrix} x_{11} \\ x_{12} \end{bmatrix} + (1 - \lambda) \begin{bmatrix} x_{21} \\ x_{22} \end{bmatrix}$

Since $x_{12}, x_{22} \geq 0$ and $\lambda \in (0,1)$, it follows that $x_{12} = x_{22} = 0$. But this implies that $x_{11} = x_{21} = B^{-1}b$ and hence $x = x_1 = x_2$. This shows that $x$ is an extreme point of $S$.

  • 0
    @Amy: Thanks Amy, I edited the post to include the author, title, and page number. You are correct in assuming it was only half the proof as I wasn't able to get past that sentence.2011-05-21

1 Answers 1

4

Note that $x_1,x_2 \in S$ and hence $Ax_1 = b$ and $Ax_2 = b$. Hence, you get $x_{11} = x_{21} = B^{-1}b$ and hence $x_1 = x_2$.

To elaborate a bit, since $x_{1},x_{2} \geq 0$ and $\lambda \in (0,1)$, we have $x_{12} = 0 = x_{22}$.

Now, $Ax_1 = b \implies Bx_{11} + Nx_{12} = b \implies B x_{11} = b \implies x_{11} = B^{-1}b$.

Similarly, $Ax_2 = b \implies Bx_{21} + Nx_{22} = b \implies B x_{21} = b \implies x_{21} = B^{-1}b$.

Hence, $x_1 = x_2$ and both equals $x$.

  • 0
    @Theo: Thanks, it was a typo but I did what you said and then went through the proo$f$ and I have a better understanding of it. It was a lot easier when I worked out examples, I should have done that from the beginning. Thank you for the help.2011-05-23