1
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.