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: Chip Eastham on 20 May 2010 16:45 On May 19, 11:12 am, Yihong <yihon...(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 <yihon...(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/ > > If you know P is in the convex closure of A, then you know P is a convex combination of finitely many points in A, by definition. Here evidently you define P to be the expected value of a transformed random variable, P = E[f(X)]. The initial wording made it seem that you already have a computed value for P, but perhaps computing P is part of your question? regards, chip |