Is there any algorithm for Caratheodory theorem (convex hull)?
in [Math]
|
Prev: tried out the prism tonight Chapt10, Fiberglass Experiment #95; ATOM TOTALITY
Next: approximating a 2nd order bezier curve with a 3rd order bezier curve
From: Yihong on 19 May 2010 00:21 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!
From: G. A. Edgar on 19 May 2010 08:45 In article <931825785.184920.1274257295244.JavaMail.root(a)gallium.mathforum.org>, Yihong <yihongwu(a)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 k-1, and if so, constructively write one of the points as a convex combination of the others. -- G. A. Edgar http://www.math.ohio-state.edu/~edgar/
From: Yihong on 19 May 2010 07:12 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 article > <931825785.184920.1274257295244.JavaMail.root(a)gallium. > mathforum.org>, > Yihong <yihongwu(a)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 k-1, and if so, constructively write one of the > points as a convex > combination of the others. > > -- > G. A. Edgar > > > > > > > > > > > > > > > http://www.math.ohio-state.edu/~edgar/
From: Robert Israel on 19 May 2010 16:13 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(a)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(a)gallium. >> mathforum.org>, >> Yihong <yihongwu(a)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 k-1, and if so, constructively write one of the >> points as a convex >> combination of the others. >> >> -- >> G. A. Edgar >> >> >> >> >> >> >> >> >> >> >> >> >> >> >> http://www.math.ohio-state.edu/~edgar/ >
From: G. A. Edgar on 20 May 2010 08:36
In article <1391743100.187422.1274281989232.JavaMail.root(a)gallium.mathforum.org>, Yihong <yihongwu(a)princeton.edu> 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 article > > <931825785.184920.1274257295244.JavaMail.root(a)gallium. > > mathforum.org>, > > Yihong <yihongwu(a)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 k-1, and if so, constructively write one of the > > points as a convex > > combination of the others. > > > > -- > > G. A. Edgar > > > > > Maybe start the induction in dimension 1. Then, assuming you can do the problem in dimension m, show how to do it in dimension m+1. (This is Caratheodory's step.) -- G. A. Edgar http://www.math.ohio-state.edu/~edgar/ |