I need some elementary knowledge of polyhedral and I am consulting several books. However, I found the definitions may not be consistent. I am not sure if I understand them right.
The question is about extreme subsets of convex sets. In book "convex analysis and minimization algorithms I", page 112, the authors give a definition of extreme subsets of convex set:
The convex subset $F\subset C$ is extremal if there are no two points $x_1$ and $x_2$ in $C\setminus F$ such that $1/2 (x_1+x_2)\in F$.
Then the authors give an alternative definition. I quote what they said as follows:
"The above statement can be rephrased in reversed logic as: if $x_1$ and $x_2$ in $C$ are such that $\alpha x_1+(1-\alpha)x_2\in F$ for some $\alpha\in(0,1)$, then $x_1$ and $x_2$ are in $F$ as well."
I doubt that, in the alternative definition, they may also need to require that $x_1$ and $x_2$ are in $C\setminus F$. Here is a counterexample I can find:
Consider $\mathbb{R}^2$. Let $C=\{(x,y):-1\leq x\leq 1, -1\leq y\leq 1\}$ and $F=\{(x,y):0\leq x\leq 1, y=1\}$.
According to the original definition, $F$ is extremal. However, according to the alternative definition, $F$ is not, as we can choose $x_1=(-1,1)$ and $x_2=(1,1)$.
Any help is appreciated.
I think I agree with your issue.
However, I don't think the problem is with the latter definition, it is with the former. I think the former definition should have been (note that I am taking $x_1$ from $C$ rather than $C\setminus F$):
The convex subset $F\subset C$ is extremal if there are no two points $x_1\in C$ and $x_2\in C\setminus F$ such that $1/2 (x_1+x_2)\in F$.
What your counterexample shows, is that their current definition allows you to take the intersection of a half-space and an extremal set, and still call it extremal. We could make the second definition agree with this, but that would ruin later results such as: An extreme point of F is an extreme point of C.