Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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".

share|improve this question
1  
I've since found a paper that more or less answers my question. In case anyone else is interested it is "Extremal Convex Functions", Bronshtein, E.M., Sibirskii Matematicheskii Zhurnal, Vol. 19, No 1., 1978 springerlink.com/content/k89m467j865uw7x2 –  Mark Reid Dec 15 '09 at 2:46
add comment

2 Answers 2

up vote 6 down vote accepted

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.

share|improve this answer
    
If I understand your candidates in the case of the 1-simplex, these would be functions over [0,1] that are trapeziums with a flat top over [a,b]? I don't think these are extreme though - an appropriately weighted sum of "tents" plus some proportion of the 0 function (also extreme) would show these are a convex combination of other points in C. –  Mark Reid Nov 19 '09 at 5:02
    
@mark: No, a proper convex combination of a tent with anything else in your set will be less than 1 wherever the tent is less than 1. –  Harald Hanche-Olsen Nov 19 '09 at 5:04
    
Regarding compactness, I think you may have a point. Those function would converge to a point that is non-zero over a vertex and thus not in C. I may have to rethink my construction. –  Mark Reid Nov 19 '09 at 5:04
add comment

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.

share|improve this answer
    
I'd also considered these as candidates. Does your argument show that they constitute all of ext C? –  Mark Reid Nov 19 '09 at 5:07
    
David's candidates are a subset of mine – just take a singleton set and follow my construction. –  Harald Hanche-Olsen Nov 19 '09 at 5:28
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.