Date: Mon, 24 Jun 1996 16:52:01 -0400
From: Joao Luis Cardoso Soares <jls55@columbia.edu>
Subject: A convex analysis question
Hi
I am trying to figure out what what would be the convex hull of an infinite union of sets. According to most books in Convex Analysis it should be the set of all the _finite_ convex combinations with points in some of those sets.
I cannot understand why does it have to be finite.
Any help on making this clear is appreciated.
Thanks,
Joao
Date: 25 Jun 1996 10:29:35 -0500
From: hennebry@plains.nodak.edu (Michael J. Hennebry)
Subject: A convex analysis question
If one is attempting constrained optimization, then one usually needs closed sets. The union of a finite set of closed sets is closed, but the union of an infinite set of closed sets might not be. In fact,
every open set, except the empty set, is the union of an infinite
set of distinct non-intersecting closed sets.
By the way, Rockafellar defines the convex hull of a set S to be the intersection of all convex sets containing S. He defines this for the case S subset of R^n, but the definition may well pertain more generally, since the property that the intersection of convex sets is convex seems to be universal.
-- Paul
Date: Thu, 27 Jun 1996 14:59:37
From: JMJ6@pge.com (Jonathan M. Jacobs)
Subject: A convex analysis question
The convex hull of X should be the minimal convex set containing X. Clearly it has to include finite convex combinations of points in X to be convex. That's enough to make it convex so by minimality you're done.
More importantly, infinite convex combinations are not necessary to enforce the convexity property: If P and Q are in a convex set and w in [0, 1], then wP + (1-w)Q is also in that set.
For the N dimensional set R^N, one need only consider convex combinations of up to N+1 points.
Even in Hilbert space, only finite convex combinations need be considered.
Please ignore my previous post. I'd left my head in my other hat.
More importantly, infinite convex combinations are not necessary to enforce the convexity property: If P and Q are in a convex set and w in [0, 1], then wP + (1-w)Q is also in that set.
For the N dimensional set R^N, one need only consider convex combinations of up to N+1 points.
Even in Hilbert space, only finite convex combinations need be considered.
My previous post wasn't as bad as my first post on this subject, but is still worthy of ignore-ance. I'd given a series of weights that didn't sum to one.
Date: 2 Jul 1996 11:07:01 -0500
From: rudi3964@utdallas.edu
Subject: A convex analysis question
Proof by induction:
In 1-space (a line), it's clear that the convex hull is simply the set of
all convex combinations of the lowest and highest points. 2 is clearly finite.
Now consider point X in the convex hull of the infinite union. Bisect the n-space with an n-1 hyperplane. Consider A(n-1) to be the portion of the convex hull in the n-1 hyperplane. Each extreme point of A(n-1) is on a line between two extreme points in the original complex hull. So however many points are needed in n-1 space, only twice as many are needed in n-space.
By induction, then, any point in the convex hull in the plane can be expressed as a linear combination of four points in the infinite sets. (Actually, three is enough, but that proof doesn't lead to an easy induction). Similarly, with eight points you can find any point in the convex hull in 3-space, etc. In finite dimensions, then, any point in the convex hull can be expressed as a linear combination of a finite set of points from the original sets.
The point is not that infinite combinations aren't allowed, but that every point can be represented as a combination of a finite set of points.
I'm reasonably certain that it will never take more than n+1 points to specify any point in the convex hull, but I haven't constructed a proof.
Jay Rudin
University of Texas at Dallas
Date: 2 Jul 1996 21:40:40 GMT
From: rubin@msu.edu (Paul A. Rubin)
Subject: A convex analysis question
It's Caratheodory's Theorem. See, for instance, Rockafellar's _Convex Analysis_, Thm. 17.1, page 155.
Date: 18 Oct 1996 17:33:48 GMT
From: spellucci@mathematik.th-darmstadt.de (Peter Spellucci)
Subject: convex image
hi , you all ,
here comes a nice problem:
obviously a linaer map map's convex sets to convex ones. What about sufficient conditions for a nonlinear map F going from R^n to R^n to map
(Clearly if F(x)=Ax+phi(x) and phi is diagonal and continuous, then a) holds but b) not) Any pointer to the literature will be highly appreciated.
Thanks in advance
peter
Date: 21 Oct 96 18:44:45 GMT
From: chinneck@halley.sce.carleton.ca (John Chinneck)
Subject: convex? concave? both?
If you work with nonlinear functions for optimization or modelling,
you might be interested in MProbe. MProbe is new software for empirically
determining the "shape" of a nonlinear function of many variables in a
specified region. By "shape" is meant whether the function is almost
linear, convex, almost convex, concave, almost concave, or both convex
and concave.
An empirical approach is used because a function whose analytic form appears horribly nonlinear may in fact turn out to be simpler (e.g. almost linear) in a limited region of interest.
MProbe also provides various analyses of function range, a multidimensional analog of "slope", simple model navigation, and the ability to plot a function value along a straight line between any two points in multidimensional space.
For further information on MProbe, or to download a student/demo version of MProbe, please visit the web page at:
http://www.sce.carleton.ca/faculty/chinneck/mprobe.html
If you do not have web access, you can obtain the student/demo version of MProbe via ftp at this address:
Login as "anonymous", then change to the directory pub/MProbe.
I look forward to your feedback on MProbe. If there is sufficient interest in the software, then I intend to continue adding functionality.