8
$\begingroup$

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

$\endgroup$
1
  • 1
    $\begingroup$ 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 $\endgroup$
    – Mark Reid
    Dec 15 '09 at 2:46
7
$\begingroup$

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.

$\endgroup$
3
  • $\begingroup$ 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. $\endgroup$
    – Mark Reid
    Nov 19 '09 at 5:02
  • $\begingroup$ @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. $\endgroup$ Nov 19 '09 at 5:04
  • $\begingroup$ 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. $\endgroup$
    – Mark Reid
    Nov 19 '09 at 5:04
3
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ I'd also considered these as candidates. Does your argument show that they constitute all of ext C? $\endgroup$
    – Mark Reid
    Nov 19 '09 at 5:07
  • $\begingroup$ David's candidates are a subset of mine – just take a singleton set and follow my construction. $\endgroup$ Nov 19 '09 at 5:28

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.