Explicitly describing extreme points of infinite dimensional convex sets - MathOverflow

Explicitly describing extreme points of infinite dimensional convex sets

2009-11-19T04:00:50Z

I am currently trying to apply some results from Choquet theory - i.e., the generalisation of results by Minkowski and Krein-Milman for representing points in a compact, convex set C by probability measures over its extreme points, ext C = { x ∈ C : C - { x } is convex }.

My main problem is with explicitly describing the set of extreme points for a particular convex set, namely the set C of concave functions over the k-simplex that vanish at the vertices of the simplex and have sup-norm at most 1. I've convinced myself that this set of functions in compact and convex and so the Choquet's theorem applies. However, apart from the case of the 1-simplex I am struggling to say anything about what the extreme functions might be.

In the case of the 1-simplex, the functions in ext C are "tents" with height 1, that is, functions f that are zero on the boundaries and rise linearly to a single point x where f(x)=1. I suspect that in the case of the 2-simplex the extreme functions are also piece-wise linear concave functions with height 1. I have considered a number of candidates (the functions formed by the taking the minimum of 3 affine functions, each zero on a different vertex) but am having trouble showing that the candidates are actually extreme.

Does anyone know of any techniques for identifying extreme points of convex sets?

Pointers to applications of Choquet's theorem that explicitly construct ext C and the probability measure for a given point in C would also be much appreciated. My reading in this area has only got me as far as Phelps' monograph "Lectures on Choquet Theory" and a survey article by Nina Roy titled "Extreme Points of Convex Sets in Infinite Dimensional Spaces".

Answer by David Eppstein for Explicitly describing extreme points of infinite dimensional convex sets

2009-11-19T04:35:02Z

The obvious candidates are the functions that have height 1 at some single point x other than a vertex, vanish on the boundary cells of the simplex that do not contain x, and are linear along any line segment from x to the boundary. They obviously belong to C, and no function with height 1 at x can have a smaller value than one of these functions at any other point without destroying concavity.

Answer by Harald Hanche-Olsen for Explicitly describing extreme points of infinite dimensional convex sets

2009-11-19T04:45:47Z

There are more candidates for the extreme points. Take any compact convex subset of the simplex, then take the infimum of all affine functions that are ≥ the characteristic function of the subset. You could start with more arbitrary subsets, but the result is the same.

As far as general techniques go, I don't have any, except when the set is given by inequalities, try to make as many of them equalities as you can. In this case, make your functions equal to 1 or to 0 as much as possible, and as affine as you can make them.

By the way, don't you have a problem with compactness? Take tents on points $x_n$ and let $x_n$ converge to a vertex of the simplex.

Edit: I realized that you wanted a proof. Let S be the simplex, let K be a closed convex subset (not containing a corner of S), and let f be the inf of all affine functions ≥ 0 on S and ≥ 1 on K. Assume $2f=g+h$. Then g and h are both equal to 1 on K, and since they are concave they are infimums of affine functions, and so both are $\ge f$. But then they must both be equal to f.