13.6 Convex Book
Definition 13.6.1 (Polytope and Polyhedron).label Polytope is the convex hull of a finite set of points in $\R^{d}$. Let $\curl{c_i}_{1}^{m}\suf\R^{d}$ and $\curl{\be_i}_{1}^{m}\in\R$ then the set
is called a polyhedron
Definition 13.6.2 (Algebraically Open).label Let $V$ be a vector space and $A\suf V$ be convex. $A$ is called algebraically open if for each $v,u\in V$, $A\cap \curl{v+\tau u:\tau\in \R}$ is an open interval (possibly empty).
Theorem 13.6.3 (Isolation).label Let $V$ be a vector space, $A\suf V$ an algebraically open convex set and let $u\nin A$. Then there exists an affine hyperplane $H$ which contains $u$ and strictly isolates $A$.
Lemma 13.6.4.label Let $\curl{v_i}_{1}^{d+1}\suf\R^{d}$ be affinely independent points in $\R^{d}$. The polytope $\la=Conv(\curl{v_i}_{1}^{d+1})$ is called a d-dimensional simplex and $\la$ has nonempty interior.
Theorem 13.6.5.label Let $A\suf\R^{d}$ be a convex set with $int(A)=\emp$ then there exists an affine subspace $L\suf\R^{d}$ such that $A\suf L$ and $\dim L<d$.
Proof. Let $k$ be the maximum number of affinely independent points in $A$. By Lemma 13.6.4, $k<d+1$. Let $\curl{v_i }_{1}^{k}$ be affinely independent points then for each $v\in A$ there exists a solution $\gam\neq 0$ to
Then $v\in A$ can be expressed as an affine combination
Showing $A$ is contained in the affine subspace $L\define aff(\curl{v_i}_{1}^{k})$ so $\dim L=k-1<d$.$\square$
Theorem 13.6.6 (Minkowski/Krein-Milman).label Let $K\suf\R^{d}$ be a compact convex set. Then $K=Conv(Ext(K))$
Proof. We proceed by induction with base case $d=0$ is trivial since $K$ is a point. If $int(K)=\emp$ then by Theorem 13.6.5 $K$ lies in an affine subspace of dimension $<d$ hence the result follows by induction hypothesis. Suppose $int(K)\neq\emp$.$\square$
Post a Comment