2
$\begingroup$

Let's $K\subset\mathbb{R}^n$ compact. If $K$ is convex then who to prove that any point of $K$ is convex combination of one or two extremal points of $K$?

Intuitively, for any closed ball that is true.

  • 3
    It won't be "one or two". Think of a simplex. In ${\mathbb R}^n$ you need $n+1$ points.2012-04-03
  • 0
    Got it. I was thinking implicitly when the boundary of K coincides with its set of extremal point. For the ball in R ^ n this makes sense. But not for the simplex. Thank you.2012-04-03

2 Answers 2

5

The fact that in ${\mathbb R}^n$ each point of a compact convex set is a convex combination of at most $n+1$ extreme points is a theorem of Carathéodory. You can prove this by induction on $n$.

The case $n=0$ is easy. For the induction step, if $K$ is a compact convex set in ${\mathbb R}^{n+1}$ and $x \in K$, choosing some extreme point $y$ of $K$ we have $x = t y + (1-t) z$ where $0 \le t \le 1$ and $z$ is a boundary point of $K$. $K$ has a supporting hyperplane $H$ at $z$, and $H \cap K$ is a compact convex set in the $n$-dimensional space $H$ whose extreme points are extreme points of $K$. So represent $z$ as a convex combination $z = \sum_{i=1}^{n+1} c_i z_i$ of at most $n+1$ of these extreme points, and $x = t y + \sum_{i=1}^{n+1} (1-t) c_i z_i$ is a convex combination of at most $n+2$ extreme points of $K$.

  • 1
    can you please tell me the proof for : The fact that in $R^n$ each point of a compact convex set is a convex combination of at most n+1 extreme points.2017-05-08
  • 1
    I did. Or Look up [Caratheodory's theorem (convex hull)](https://en.wikipedia.org/wiki/Carath%C3%A9odory%27s_theorem_(convex_hull)) in Wikipedia.2017-05-08
1

This is the Krein-Milman Theorem. Just do a search for the proof of this, and you should find the answer you are looking for. The proof can be kind of complicated depending on how much generality you proof it for (it holds in general for locally compact Hausdorff spaces, which can be much nastier than $\mathbb{R}^n$).

Edit: Your claim breaks down even in $\mathbb{R}^2$. Consider the square determined by points (0,0), (0,1), (1,1), (1,0). Note that the extreme points of the square are exactly these corner points. Then consider the point $(1/2,1/3)$. Can you write this point as the convex combination of only one or two points?

  • 0
    I hoped that in the case of $\mathbb{R}^n$ in the proof would be easy. Thank you.2012-04-03
  • 0
    If you want a reference that proves it for the simple case of $\mathbb{R}^n$ here is one that looks decent. It has a fair amount of buildup though, in proving the theorem you always have to go through what extreme points are, some facts about the convex hull, etc. http://www2.isye.gatech.edu/~nemirovs/OPTIII_LectureNotes.pdf2012-04-03
  • 0
    I'm not interested in the existence of convex combination. But in the amount of extremal points of the convex combination.2012-04-03
  • 1
    *locally compact* should be *locally convex*.2012-04-04