2
$\begingroup$

$a)$ Prove that a convex polytope has finitely many extreme points.

$b)$ Prove that the unit disc $S:=\{x\in\mathbb{R}^2:x_1^2+x_2^2\le1\}$ is not a convex polytope.

Hint : what are the extreme points of $S?$

My thoughts:

"A polytope is a bounded polyhedron", then formalize it we have:

$$\exists a_1^t\dots a_n^t\in\mathbb{R}^n,c_1\dots c_n\in\mathbb{R}, r\in\mathbb{R}\cap(0,\infty),s.t.$$

$$\{x\in\mathbb{R}^n:a_1^tx\le c_1\}\cap\dots\cap\{x\in\mathbb{R}^n:a_n^tx\le c_n\}\subseteq B(0,r)$$

$$\text{iff } \{x\in\mathbb{R}^n:a_1^tx\le c_1\}\cap\dots\cap\{x\in\mathbb{R}^n:a_n^tx\le c_n\}\text{ is a polytope.}$$

Using "Elementary Linear Programming With Application" by Bernard Kolman ⋅ Robert E. Beck

Intuition:

$a)$ Since those extreme points must located on intersections of finitely many half-spaces which implies extreme points are finite

$b)$ This is just a closed $\mathbb{R}^2$ circle, which has infinitely many extreme points, so it can not be formed by finitely many half-spaces, which can be bounded but can't be a polytope, so certainly not a convex polytope.

Intuitively, $a),b)$ are both almost trivial, but how do I write the proof formally$?$

Thanks for your help.


More definitions

$0.$Definition of polyhedron

A polyhedron is the intersection of finitely many halfspaces

$1.$Definition of halfspaces $P$ in $\mathbb{R}^n$ $$P=\{x∈\mathbb{R}^n,a^tx\le(\ge)b\}$$

$2.$A point $x\in\mathbb{R^n}$ is a $\underline{\text{convex combination}}$ of the points $x_1,x_2,\dots,x_r$ in $\mathbb{R}^n$ if for some real numbers $c_1,c_2,\dots,c_r$ which satisfy $$\sum_{i=1}^r c_i=1\text{ and }c_i\ge0,\space1\le i\le r,$$ we have $$x=\sum_{i=1}^rc_ix_i$$

$3.$ The $\underline{\text{convex hull}}$ of a finite point set $S$ is the set of all convex combinations of its points.

$4.$ a $\underline{\text{convex polytope}}$ is the convex hull of a finite set of points

$5.$ A point $u$ in a convex set $S$ is called an $\underline{\text{extreme point}}$ of $S$ if it is not an interior point of any line segment in $S$. That is, $u$ is an extreme point of $S$ if there are no distinct points $x_1$ and $x_2$ in $S$ such that $$u=\lambda x_1+(1-\lambda)x_2,\space0<\lambda<1.$$


Rough work

$a)$Proof.

Do this by contradiction

Assume $S$ is such convex polytope and has infinitely many extreme points, then

$$\forall n\in \mathbb{N},\exists^{\ge n} u\in S, s.t. \forall x_1\neq x_2\in S,\lambda\in(0,1)\cap\mathbb{R},u=\lambda x_1+(1-\lambda)x_2$$

Which contradict with $S$ is a convex hull of a finite set so it's not a convex polytope$ (\Rightarrow\Leftarrow)$ $\tag*{$\square$}$

$b)$ Proof.

Define $B(a;r):=\{x∈\mathbb{R}^n:|x−a|<r\}$ where $a\in\mathbb{R}^n$

Let $\overline{S}:=\{{x∈\mathbb{R}^n:∀ε>0,B(x;ε)∩S≠\varnothing}\}$. then we have:

$$\forall u\in\overline{S},x_1\neq x_2\in S,\lambda\in(0,1)\cap\mathbb{R},u\neq\lambda x_1+(1-\lambda)x_2$$

And also $\overline{S}\subseteq S$

But $\overline{S}$ is not a finite set, which means S has infinitley many extreme points, by contrapositive of $a)$

That implies $S$ is not a convex polytope. $\tag*{$\square$}$


Yet I'm trying to write a proof using def $2,3,4,5$,

Which I think is the correct definition that I suppose to use.

(keep updating$\dots$)

Any help or hint or suggestion would be appreciated.

$\endgroup$
  • 3
    $\begingroup$ What is your book's definition of polytope ? $\endgroup$ – kimchi lover Oct 5 '19 at 16:29
  • $\begingroup$ I do not know how to interpret your various ways to put parentheses into the natural language definition of convex polyhedron. I mean, I do not see how to formalize the statement in any other way than $$ P=\bigcap_{i=1}^n H_i$$ where $n\in\Bbb N$ and for $1\le i\le n$, $H_i$ is a closed half-space. $\endgroup$ – Hagen von Eitzen Oct 5 '19 at 16:29
  • $\begingroup$ @Manx Does that mean your book only defines (convex) polyhedron, not polytope? Does it define extreme point? $\endgroup$ – Hagen von Eitzen Oct 5 '19 at 16:31
  • $\begingroup$ $B(0:r)$ stand for a open ball locate at $0$ with radius $r$, I'm trying to use the def for bounded set on this@Hagen von Eitzen $\endgroup$ – Manx Oct 5 '19 at 16:39
  • $\begingroup$ @Manx I do not see that your book has a definition of polytope that implies boundedness. $\endgroup$ – Hagen von Eitzen Oct 5 '19 at 16:43

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.