I am interested in the following question:
1) Is given a continuous set-valued mapping M : R^n => R^m ;
2) I have a fixed vector z in R^m and am interested in D := {x in R^n : z \in int co M(x) },
where int = the interior, co the convex hull.
Now the question is : can we conclude that for a given x1, x2 in D that there exist points
z1, ..., zk in M(x1) \cap M(x2) and weights \lambda_1, ..., \lambda_k such that z = \sum_{i=1}^k \lambda_i z_i.
If so any reference to a work where this could be shown (or disproven)?
This is a good and interesting question.
In the detailed explanation of the question, I assume that "weights" refers to edge weights.
A good place to start in answering this question (for an overview of convex hulls) is
Joseph S. B. Mitchel, Subhash Suri, A Survey of Computational Geometry:
http://www.ams.sunysb.edu/~jsbm/papers/survey-OR.pdf
More to the point, you may find it helpful to consider the invariance of convex hull weights in terms of the diameters of elipses in the interior of a convex hull. This is the basic approach in
Peter Richtarik, SOME ALGORITHMS FOR LARGE-SCALE LINEAR AND CONVEX MINIMIZATION IN RELATIVE SCALE, Ph.D. thesis, Cornell University, 2007:
http://www.maths.ed.ac.uk/~richtarik/papers/thesis.pdf
See Lemma 3.2.12 and Lemma 3.2.13, starting on page 93. For the geometry of these Lemmas, see the attached image.
This is a good and interesting question.
In the detailed explanation of the question, I assume that "weights" refers to edge weights.
A good place to start in answering this question (for an overview of convex hulls) is
Joseph S. B. Mitchel, Subhash Suri, A Survey of Computational Geometry:
http://www.ams.sunysb.edu/~jsbm/papers/survey-OR.pdf
More to the point, you may find it helpful to consider the invariance of convex hull weights in terms of the diameters of elipses in the interior of a convex hull. This is the basic approach in
Peter Richtarik, SOME ALGORITHMS FOR LARGE-SCALE LINEAR AND CONVEX MINIMIZATION IN RELATIVE SCALE, Ph.D. thesis, Cornell University, 2007:
http://www.maths.ed.ac.uk/~richtarik/papers/thesis.pdf
See Lemma 3.2.12 and Lemma 3.2.13, starting on page 93. For the geometry of these Lemmas, see the attached image.
Yes indeed, weights means, elements of the unitary simplex in dimension k. Thank you for those references, I will check them out.
I just answered negatively the question.
Think of two opposite crescent moons around a point z, so that they do not overlap. Then indeed the point z is in both convex hulls (even in its interior). Yet M(x1) \cap M(x2) is empty.
- Badges
- Science topic
- Similar topics
- Mathematics
- Applied Mathematics