Given a system of

$$(\text{P})\ \begin{cases} Ax=b \\ x \ge 0\end{cases}$$

where $A \in \Bbb{R}^{m \times n}, m \le n, \ \text{rank}(A) = m, b \in \Bbb{R}^m, x \in \Bbb{R}^n$. By $x \ge 0$, we mean termwise, each term is nonnegative.

By definition, the Polyhedron of the Allowed Solutions are:

$$P = \{x \in \Bbb{R}^n | Ax = b, x \ge 0\}$$

This is a polyhedron since each row of matrix $A$ gives a restriction to the solutionspace, and cuts off a halfspace from it. And a polyhedron is by definition the intersection of halfspaces.

Def. $\overline{x} \in P$ is called a basis solution if $\ \overline{x} =(x_1, \dots, x_n),\ J_+ = \{j\in \{1,\dots,n\}| x_j > 0\},\ A = [a_j]_{j \in \{1,\dots n\}}$ are the columvectors of $A$, and the set of vectors $\{a_j\}_{j \in J_+}$ are linearly independent. (These are the columns of $A$ such that their indicies are exactly those indicies where $\overline{x}$ is positive.)

Def. $\overline{x} \in P$ is called the extreme point of $P$, if $\ \forall x_1,x_2 \in P$ and $0 < \lambda < 1$: $$\overline{x} = \lambda x_1 + (1- \lambda) x_2 \ \Rightarrow\ \overline{x} = x_1 = x_2$$ (These are the "edges" of the $P$ polyhedron.)

Question: Why do these two definitions match up exactly? Why is the following theorem true?

Theorem: $\overline{x}$ is a basis solution $\Longleftrightarrow$ $\overline{x}$ is a emtreme point of $P$.

I'd like to understand both directions of the proof ($\Leftarrow, \Rightarrow$), and haven't found anything that explains this in a great detail. Thank you in advance!


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.