0
$\begingroup$

Is the distance between two points $(x,y)$, $(a,b)$ convex? $f(x,y) = \sqrt{(x-a)^2 + (y-b)^2} + \sqrt{(x-c)^2 + (y-d)^2}$ Where $(a,b)$ & $(c,d)$ are fixed points and we want to pick $(x,y)$ that minimizes the total distance. Thanks!

$\endgroup$
  • $\begingroup$ welcome to MSE, have you tried proving it? $\endgroup$ – Siong Thye Goh Aug 28 '18 at 0:47
  • $\begingroup$ Thanks! I tried to prove it using the Hessian matrix but the formula gets messy when I took the derivatives... $\endgroup$ – Juan Aug 28 '18 at 3:46
  • $\begingroup$ it is always encouraged to include your working on MSE when a question is posted. welcome to MSE. $\endgroup$ – Siong Thye Goh Aug 28 '18 at 3:49
  • $\begingroup$ The $\ell_p$ norm is convex ior all $p \in [1,\infty]$ math.stackexchange.com/questions/2280341/… $\endgroup$ – dohmatob Aug 29 '18 at 0:35
0
$\begingroup$

Let $X=(x,y), \ A=(a,b).\ C=(c,d)$. Triangle inequality $||A-C||=||A-X+X-C||\le ||A-X||+||X-C||$. Equality (which is the minimum) when $X$ is in between $A$ and $C$ and on the straight line connecting $A$ and $C$.

Note: $||A-C||=\sqrt{(a-c)^2+(b-d)^2}$, etc.

$\endgroup$
  • $\begingroup$ The first sentence is a little confusing. My answer was to minimize $f(x,y)$. $\endgroup$ – herb steinberg Aug 28 '18 at 1:26
  • $\begingroup$ Sorry for the confusion and thanks for the answer! $\endgroup$ – Juan Aug 28 '18 at 3:46
  • $\begingroup$ Yes, I was trying to minimize f(x,y) $\endgroup$ – Juan Aug 28 '18 at 3:47
0
$\begingroup$

First, prove that $g(x,y) = \sqrt{x^2+y^2}$ is convex.

Norms are convex because of triangle inequality, since $\lambda \in [0,1]$,

$$\left\|\lambda \begin{bmatrix}x_1\\y_1\end{bmatrix}+ (1-\lambda)\begin{bmatrix}x_2\\y_2 \end{bmatrix}\right\|\le \lambda\left\| \begin{bmatrix}x_1\\y_1\end{bmatrix}\right\|+ (1-\lambda)\left\| \begin{bmatrix}x_2\\y_2 \end{bmatrix}\right\| $$

and note that $g(x-a, y-b)$ is convex, it is just a translation.

Finally, we just have to use the fact that sum of convex functions are convex.

$\endgroup$
  • $\begingroup$ Thank you so much for the answer! $\endgroup$ – Juan Aug 28 '18 at 4:04

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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