Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

Suppose I am minimizing the Euclidean distance in $\mathbb{R}^{n}$ between a point $y$ and compact convex set $U$ (where $y\notin U$):

$\min_{x\in U}\|x-y\|$.

I believe the minimizer $x_{U}^{*}$ is unique and my question is about the continuity properties of the argmin mapping with respect to the choice of set $U$. That is, if I have two minimization problems, one with minimizing over set $U$ and one with minimizing over a set $V$, what is the distance between the minimizers $x_{U}^{*}$ and $x_{V}^{*}$? In other words, what is the distance between the minimizers of:

$\min_{x\in U}\|x-y\|$

and

$\min_{x\in V}\|x-y\|$

for the fixed $y\notin U \cup V$?

One paper, "on the stability of minimizers in convex programming" http://www.sciencedirect.com/science/article/pii/S0362546X11001635

seems to be related to the solution, but I was hoping there would be a stronger result possibly for the special case of the Euclidean norm.

In summary my questions are:

1) (Qualitative). If $V\to U$ in the Hausdorff distance, does this imply $x_{V}^{*}\to x_{U}^{*}$ in the Euclidean norm?

2) (Quantitative). Is there some Lipschitz constant or geometric argument that gives a bound on the distance between $x_{V}^{*}$ and $x_{U}^{*}$ given a fixed $U$ and $V$ in terms of the Hausdorff distance between them (or some other metric between sets)?

3')I am also looking to see if the distance between the minimizers in the sets $U$ and $V$ are ``independent'' of the choice of point $y$. Imagine two circles of radius 1 at (2,0) and (-2,0), if the point y travels along (0,y), the minimizers on the circles have a maximum separation distance regardless of how far $y$ goes up the $y$ axis.

4') Any help in where I might start looking (alternate names for the problem) would be a great help. Or, in the case when there is a negative answer to the above questions, if there are more assumptions I can make to get the desired convergence, it would be great!

share|improve this question
1  
Yes to Q1, because the $x^*_V$ are at almost the same distance to $y$ as $x^*_U$, and if they were somewhere else (not close to $x^*_U$), then by convexity of $U$ and definition of Hausdorff distance, you could do better than $x^*_U$. –  Christian Remling Jun 10 at 21:47
    
Thanks Christian! What about the case of taking the supremum over all $y$? So $\sup_{y\in \mathbb{R}^{n}}\|x_{V}^{*}(y)-x_{U}^{*}(y)\|$? Do you think the same convergence holds? –  Pallen Jun 10 at 21:51
    
No, this won't work for (say) $U$ a square and $V$ a slightly rotated version and then consider $y$ at a huge distance of $U,V$. (So that's a "no" to Q2 if you wanted to do this uniformly in $y$.) –  Christian Remling Jun 10 at 22:08
    
About the answer to Q1, I don't know if the proof is as direct as that, because that kind of proof works only if $x_{V}^{*}$ and $x_{U}^{*}$ are close but not the same distance to $y$, but otherwise, if they are exactly the same distance to $y$, the proof might be more subtle. –  Pallen Jun 11 at 15:04
    
I think it works fine. In the situation you describe, $x^*_U$, $x^*_V$ are on a circle about $y$, so the connecting line segment contains points closer to $y$. Almost the same line segment will be contained in $U$ because (by definition of Hausdorff distance), there are points in $U$ very close to $x^*_V$. –  Christian Remling Jun 11 at 18:47

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.