I am going through some linear programming lecture notes. I can't understand what is $\bar{X}$ in the proof, possibly because $\bar{X}$ is a typo. How to fix that typo?
My interpretation of the proof is in the bullet points.
Page 65:
Theorem 4.44. Let $P$ be a non-empty, unbounded polyhedral set defined by: $$P = \lbrace \vec{x} \in \mathbb{R}^{n}: \mathcal{A}\vec{x} \le \vec{b}, \vec{x} \ge \vec{0} \rbrace $$ (where we assume $\mathcal{A}$ is not an empty matrix). Suppose $P$ has extreme points $\vec{x}_1, \ldots, \vec{x}_k$ and extreme directions $\vec{d}_1, \ldots, \vec{d}_{l}$. If $\vec{x} \in P$, then there exists constants $\lambda_{1},\ldots,\lambda_{k}$ and $\mu_{1},\ldots,\mu_{k}$ such that:
\begin{align}\tag{4.30}\label{4.30} \vec{x} = &\sum_{i = 1}^{k} \lambda_{i} \vec{x}_{i} + \sum_{j = 1}^{l} \mu_{j}\vec{d}_{j} \\ &\sum_{i=1}^{k}\lambda_{i} = 1\\ &\lambda_{i}\ge 0\quad i = 1,\ldots,k\\ &\mu_{j}\ge 0\quad j = 1,\ldots,l\\ \end{align}
Proof. Let $\vec{x}\in P$. We will show that we can identify $\lambda_{1},\ldots,\lambda_{k}$ and $\mu_{1},\ldots,\mu_{k}$ making Expression 4.30 true. Define the set:
$$\tag{4.31}\label{4.31}\bar{P} = P \cap \lbrace \vec{x} \in \mathbb{R}^{n}: \vec{1}^{\intercal} \vec{x} \le M \rbrace $$
where $M$ is a large constant so that $\vec{1}^{\intercal}\vec{x}_{i} < M$ for $i = 1,\ldots,k$ and $\vec{1}^{\intercal}\vec{x} < M$. That is $M$ is large enough so that the sum of the components of any extreme point is less than M and the sum of the components of $\vec{x}$ is less than $M$.
- We are adding an extra half-plane $\vec{1}^{\intercal} \vec{x} \le M$. This plane acts like a lid to make the polyhedral set bounded. The $\bar{P}$ set contains all the extremal points of $P$. Since the components of any $\vec{\alpha}\in \bar{P}$ are non-negative and sum to something less than $M$, the point $\vec{\alpha}$ is between a simplex with finite size and the planes defined by $\vec{x} \ge \vec{0}$. Therefore $\bar{P}$ is bounded.
It is clear that $\bar{P}$ is bounded. In fact, if $P$ is bounded, then $\bar{P}=P$. Furthermore, $\bar{P}$ is a polyhedral set contained in $P$ and therefore the extreme points of $P$ are also the extreme points of $\bar{P}$. Define $$\bar{E}_{p} = \lbrace \vec{x}_{1},\ldots,\vec{x}_{k},\ldots,\vec{x}_{k+u}\rbrace$$ as the extreme points of $\bar{P}$. By Lemma 4.41 we know that $0 \le u < \infty$. If $\vec{x} \in \bar{E}_{p}$, then $\vec{x}$ can be written as a convex combination of the elements of $\bar{E}_{p}$. Therefore, assume that $\vec{x} \notin \bar{E}_{p}$. Now, suppose that the system of equations $\mathcal{G}\vec{y} = \vec{g}$ represents the binding hyperplanes (constraints) of $\bar{P}$ that are active at $\vec{x}$. Clearly $\mathrm{rank}(\mathcal{G}) < n$ (otherwise, $\vec{x}$ would be an extreme point of $\bar{E}_p$).
- if $P$ is bounded, $\bar{P} = P$
- If $P$ is bounded, since $M$ is large enough to make all extreme points of $P$ to satisfy the constraint $\vec{1}^{\intercal} \le M$, all these extreme points of $P$ are part of $\bar{P}$. All points in $P$ are convex combinations of the extreme points of $P$, which are within $\bar{P}$. Therefore $P$ is a subset of $\bar{P}$. Recall that $\bar{P}$ is the intersection of $P$ with another set \eqref{4.31}. Therefore, if $P$ is bounded, $\bar{P} = P$.
- $\bar{P}$ is a polyhedral set contained in $P$ and therefore the extreme points of $P$ are also the extreme points of $\bar{P}$
- $\bar{P}$ is a polyhedra set formed by intersecting the polyhedral set $P$ with a half plane.
- The extreme points of $P$ are in $\bar{P}$ because $M$ is large enough \eqref{4.31}.
- For each extreme point $\vec{\beta}$ of $P$, according to the definition of extreme point, we have: no two points $\vec{p} \in P$ and $\vec{q} \in P$ that are not both $\vec{\beta}$ can satisfy $\lambda\vec{p} + (1 - \lambda)\vec{q} = \vec{\beta}$ for any $\lambda \in (0, 1)$.
- Since $\bar{P}$ is the intersection of $P$ with another set, $\bar{P} \subseteq P$. Therefore, no such points $\vec{p}$, $\vec{q}$ in $P$ implies no such points in $\bar{P}$. Therefore, each extreme point $\beta$ of $P$ is also an extreme point of $\bar{P}$
- By Theorem 4.41 we know that $0 \le u < \infty$.
- According to the definition of polyhedral set, $\bar{P}$ is a polyhedral set because it is the intersection of a polyhedral set (intersection of half-planes) with another half-plane. Since $\bar{P}$ is a polyhedral set, $\bar{P}$ has a finite number of extreme points, according to Theorem 4.41.
- If $\vec{x} \in \bar{E}_{p}$, then $\vec{x}$ can be written as a convex combination of the elements of $\bar{E}_{p}$.
- If $\vec{x} \in \bar{E}_{p}$, $\vec{x}$ is one of the extreme points of $\bar{P}$. Therefore, $\vec{x}$ is a linear combination of that extreme point ($\vec{x}$) and the other elements of $\bar{E}_{p}$, which are the other extreme points of $\bar{P}$.
- Therefore, assume that $\vec{x} \notin \bar{E}_{p}$. Now, suppose that the system of equations $\mathcal{G}\vec{y} = \vec{g}$ represents the binding hyperplanes (constraints) of $\bar{P}$ that are active at $\vec{x}$.
- In the definition of $P$, $\mathcal{A}\vec{z} \le \vec{b}$ is a system of half-planes: $\forall i: \vec{a}^{\intercal}\vec{z} = b_{i}$, where the $i^{\mathrm{th}}$ row of $\mathcal{A}$ is $\vec{a}_{i}$, and $b_{i}$ is the $i^{\mathrm{th}}$ element of $\vec{b}$. Let's say the $i^{\mathrm{th}}$ half-plane is active at $\vec{x}$, that means for the corresponding row in $\mathcal{A}$, we can define a hyperplane $\vec{a}_{i}^{\intercal}\vec{z} = b_{i}$ that contains $\vec{x}$. In other words, $\vec{a}_{i}^{\intercal}\vec{x} = b_{i}$. Collecting all the rows of $\mathcal{A}$ and elements of $\vec{b}$ that corresponds to half-plains that are active at $\vec{x}$, we can form $\mathcal{G}$ and $\vec{b}$ and a system of hypeplaines that binds $\vec{x}$: $\mathcal{G}\vec{y} = \vec{g}$.
Let $\vec{d} \ne \vec{0}$ be a solution to the problem $\mathcal{G}\vec{d} = 0$ and compute $\gamma_{1} = \max \lbrace \gamma: \vec{x} + \gamma \vec{d} \in \bar{X}\rbrace$.
After following the steps of the proof for a few hours, I am stuck because I don't know what is $\bar{X}$. Is that a typo? How to fix the typo in the proof?
It should be $$\gamma_1 = \max\{ \gamma: \vec{x}+\gamma \vec{d} \in \bar{P}\}$$
We are trying to trying to travel as far as we can along direction $\vec{d}$ and remains inside $\bar{P}$.