Search All of the Math Forum:
Views expressed in these public forums are not endorsed by
NCTM or The Math Forum.


Math Forum
»
Discussions
»
sci.math.*
»
sci.math
Notice: We are no longer accepting new posts, but the forums will continue to be readable.
Topic:
Is there any algorithm for Caratheodory theorem (convex hull)?
Replies:
5
Last Post:
May 20, 2010 4:45 PM




Re: Is there any algorithm for Caratheodory theorem (convex hull)?
Posted:
May 19, 2010 4:13 PM


On Wed, 19 May 2010, Yihong wrote:
> If we know how P can be written as a convex combination of _finite_ points in A, then we know how to proceed inductively. This is essentially how the proof of the Caratheodory theorem is done. The problem now is I do not know how to do the first step. I only know P, as an expectation, lies in the convex hull of the image.
In this case I might start by taking a random sample of size n+1 from your random variable, and keep increasing the size of the sample until P is in the convex hull of the sample points.
Robert Israel israel@math.MyUniversitysInitials.ca Department of Mathematics http://www.math.ubc.ca/~israel University of British Columbia Vancouver, BC, Canada
>> In article >> <931825785.184920.1274257295244.JavaMail.root@gallium. >> mathforum.org>, >> Yihong <yihongwu@princeton.edu> wrote: >> >>> I have a question about the constructive aspects of >>> Caratheodory theorem, >>> which states that any point P in the convex hull of >>> A \subset R^n can be >>> written as the convex combination of at most n+1 >>> points in A. >>> >>> This is an existence result. I wonder if there is >>> any algorithm that can give >>> these n+1 points. In the problem I have A is the >>> image of some continuous >>> function f: R>R^n, and P = E[f(X)] for some random >>> variable X. >>> >>> Thanks! >>
>> I guess you need to apply induction, together with: >> given k points, >> constructively determine whether the affine span has >> dimension less >> than k1, and if so, constructively write one of the >> points as a convex >> combination of the others. >> >>  >> G. A. Edgar >> >> >> >> >> >> >> >> >> >> >> >> >> >> >> http://www.math.ohiostate.edu/~edgar/ >



