Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Someone told me that the the following problem is elementary. Given three points $a=(-5,0)$, $b=(0,5)$ and $c=(5,0)$ in $\mathbb R^2$ with Euclidean norm:

$$\mbox{minimize}\;\; \; f(x)=\|x-a\| + \|x-b\|-2\|x-c\|,\;\; x\in \mathbb R^2.$$

I will highly appreciate for your answers. Thanks in advance.

share|improve this question
    
I'll give you 2 hints: - first, minimizing $(x-a)^2$ is equivalent to minimizing $\sqrt{(x-a)^2}$. Of course the minimum value will be different, but the location will be the same. - Now just think, how would you find the minimum to a generic function $f_{(x)}$? And if it were $f_{(x,y)}$? –  lifesayko Mar 31 at 13:15
    
@lifesayko: I don't know how to use your hints at all! Hic, please make it more clearly. –  Richkent Mar 31 at 14:21
    
Richkent, it is not my job to solve your your probelms for you. Please show at least what you've tried. What specifically are you having trouble with? Show how you would set up the problem. If you really have no idea, try to find the minimum to a generic problem $f_{(x)}$, such as $f_{(x)}=x^2+4$. Then reason how to transfer this to what you have. –  lifesayko Apr 1 at 11:38
    
Fist of all, I want to verify that whether the problem has a global minimum or not? I have showed that $f(x)$ is bounded but the existence of a minimum point have been not determined yet. –  Richkent Apr 1 at 12:38
    
I have no solution, but the - not elementary - problem seems to be the "Fermat Weber Problem with positive and negative weights". Your constellation looks asymptotically bounded at $f(x)=-\sqrt{250}$ for $x=(t, -t/3) \text{ for } t \to -\infty$. –  Axel Kemper Apr 1 at 21:41

1 Answer 1

up vote 1 down vote accepted
+50

You seem to be serious about solving this problem. What I would try is this: Choose any $r$ such that $$ \|a-b\| \le r < \infty. $$ Consider the ellipse $$ \|x-a\|+\|x-b\|=r, $$ for which you can get an equation by the standard trick of expanding: $$ \|x-a\|^{2}=r^{2}-2\|x-b\|+\|x-b\|^{2} \\ \|x-a\|^{2}-\|x-b\|^{2}-r^{2}=-2\|x-b\| \\ (2(b\cdot x)-2(a\cdot x)+\|a\|^{2}-\|b\|^{2}-r^{2})^{2}=4\|x-b\|^{2}. $$ ("$\cdot$" represents vector dot product in the last expression.) Now, minimize $f$ on this ellipse. This comes down to considering $f(x)=r-2\|x-c\|$ for $x$ on the ellipse. Finally, look at the minimum value of $f$ as a function of $r$, and see what you can do with that.
Note: Try finding the location of the minimum for $f(x)=r-2\|x-c\|$ on the ellipse by finding the location of the maximum for $\|x-c\|^{2}=\|x\|^{2}-2(x\cdot x)+\|c\|^{2}$ on the ellipse, which can be done by first replacing $\|x\|^{2}=x_{1}^{2}+x_{2}^{2}$ with terms from the equation for the ellipse.

No guarantee that this will lead to enough reduction in complexity, but I don't see any other reasonable suggestions. It might be worthwhile to first rotate the configuration until $a$ and $b$ are on one horizontal or on one vertical line.

share|improve this answer
    
@ T.A.E, here is my attempt, but there is a trouble I need to verify: math.stackexchange.com/questions/739262/… –  Richkent Apr 4 at 7:09

Your Answer

 
discard

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.