4
$\begingroup$

Consider the following definition

Definition: Let $\Omega \subset R^n$ a bounded convex set. A point $x \in \partial \Omega$ is called an extremal point if $x$ cannot be written as linear combination of the form $x = tx_1 + (1-t)x_2$ ,$t \in (0,1)$ , $x_1,x_2 \in \partial \Omega$. The set formed by this elements will be denoted by $E_{\Omega}$.

I am reading an article, and the author writed this:

Let $\Omega \subset R^n$ a bounded convex set.If the point $x \in\partial \Omega$ is not an extremal point then $x$ can be written as a linear combination as above

$$ x = \displaystyle\sum_{i=1}^{n}t_i x_i \ \ where \ \ \displaystyle\sum_{i=1}^{n}t_i =1, x_i \in \overline{E_{\Omega}}$$

I have no idea to prove this . I searched how but i dont find anything. someone can give me a reference or a proof, please? I am an ignorant on theorems involving convex sets =\

Thanks in advance

$\endgroup$
1
$\begingroup$

$$ \partial\Omega \subseteq \overline{\Omega} = \overline{\text{conv}(E_\Omega)} = \text{conv}(\overline{E_\Omega}) $$ The first equality is the finite-dimensional case (due to Minkowski) of the Krein-Milman theorem, that a compact convex set is the closed convex hull of its extreme points (together, I suppose, with the theorem that the closure of a convex set is convex). The second equality, that closure commutes with convex hull, holds for bounded sets in $\mathbb{R}^n$ and is a standard application of Carathéodory's theorem.

Since you asked for references:

  • In Schneider's Convex Bodies: The Brunn-Minkowski Theory, the first equality is Corollary 1.4.5, the fact that the closure of a convex set is convex is part of Theorem 1.1.9 (whose proof Schneider omits as an "easy exercise"), and the second equality is Theorem 1.1.10.
  • In Lay's Convex Sets and their Applications, the first equality is Theorem 5.6, the fact that the closure of a convex set is convex is Theorem 2.11, and the second equality is... actually, I don't see it, but the hard direction ($\subseteq$) follows from Theorem 2.30.
$\endgroup$
2
$\begingroup$

The linear combination you wrote is called a "convex combination" and usually you insist that all coefficients $t_i$ are non-negative (otherwise it's an "affine combination"). The statement should be that every point can be written as a convex combination of $n+1$ extremal points, not $n$. (Think of a triangle in two dimensions: you need all 3 vertices to form convex combinations in the interior of the triangle.)

Perhaps the easiest way to see that the statement is true is to first note that the set of all convex combinations of extremal points forms a convex set, and it is the smallest convex set that contains the extremal points. So this gives you an alternate definition for your convex set. (Technically you also need to prove that any larger convex set has more extremal points, but this is not too hard.) Then you need to prove that a convex combination of more than $n+1$ extremal points can be reduced to a convex combination of $n+1$ extremal points. To do this, take your extremal points and lift into one dimension higher by appending $1$ as the last coordinate of each point. If you have more than $n+1$ points, then these lifted points will be linearly dependent as vectors and so you will get a linear combination that equals zero. This means that there are coefficients for the original points such that the coefficients add up to zero and the linear combination of points gives the zero vector. So you can add a multiple of these coefficients to your original convex combination and make at least one coefficient $t_i$ equal to zero while preserving $\sum_i t_i = 1$ and all $t_i \geq 0$. So this removes one extremal point from your convex combination. You can repeat this process until you have $n+1$ extremal points in the convex combination.

$\endgroup$
  • 2
    $\begingroup$ I guess the $n$ (rather than $n+1$) is because the point in question is in the boundary of $\Omega$. $\endgroup$ – user21467 Jun 6 '14 at 22:58
  • 1
    $\begingroup$ Whoops, I missed that. Working with the boundary makes it more complicated, I'll leave my answer because it might contain some clues for the proof but currently I don't know how to prove $n$ for the boundary. I mean, it basically boils down to showing that the maximal solutions to a linear functional over a convex body is convex and can only have dimension at most $n-1$, and that this characterizes the entire boundary as the linear functional varies, but I don't know how to show all that off the top of my head. $\endgroup$ – user2566092 Jun 6 '14 at 23:04
  • 1
    $\begingroup$ I think you can just let $H$ be a supporting hyperplane at $x$ and do everything in $H$. (Replace $\overline\Omega$ with $H\cap\overline\Omega$, etc.) $\endgroup$ – user21467 Jun 6 '14 at 23:35

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.