Explicitly describing extreme points of infinite dimensional convex sets - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-25T16:11:41Z http://mathoverflow.net/feeds/question/6061 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/6061/explicitly-describing-extreme-points-of-infinite-dimensional-convex-sets Explicitly describing extreme points of infinite dimensional convex sets Mark Reid 2009-11-19T04:00:50Z 2009-11-19T05:02:43Z <p>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 &isin; C : C - { x } is convex }.</p> <p>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.</p> <p>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.</p> <p>Does anyone know of any techniques for identifying extreme points of convex sets? </p> <p>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".</p> http://mathoverflow.net/questions/6061/explicitly-describing-extreme-points-of-infinite-dimensional-convex-sets/6062#6062 Answer by David Eppstein for Explicitly describing extreme points of infinite dimensional convex sets David Eppstein 2009-11-19T04:35:02Z 2009-11-19T04:35:02Z <p>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.</p> http://mathoverflow.net/questions/6061/explicitly-describing-extreme-points-of-infinite-dimensional-convex-sets/6063#6063 Answer by Harald Hanche-Olsen for Explicitly describing extreme points of infinite dimensional convex sets Harald Hanche-Olsen 2009-11-19T04:45:47Z 2009-11-19T05:02:43Z <p>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.</p> <p>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.</p> <p>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.</p> <p><strong>Edit:</strong> I realized that you wanted a proof. Let <em>S</em> be the simplex, let <em>K</em> be a closed convex subset (not containing a corner of <em>S</em>), and let <em>f</em> be the inf of all affine functions ≥ 0 on <em>S</em> and ≥ 1 on <em>K</em>. Assume \$2f=g+h\$. Then <em>g</em> and <em>h</em> are both equal to 1 on <em>K</em>, 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 <em>f</em>.</p>