Convexity of a non linear optimization problem

Question

I have a non linear optimization problem, namely:

$$\min {\sqrt{(x-u)^2 + (y-v)^2 + (z-w)^2)}}$$

How can i show that the above function is convex. Doing via Hessian is a difficult task.

Answer 1

You can use directly the definition of a convex function: $f(tx+(1-t)y)\leq tf(x)+(1-t)f(y),\,\forall t\in [0,1]$. So you have to prove that $$f(x,y,z,u,v,w)=\sqrt{(x-u)^2+(y-v)^2+(z-w)^2}$$ is convex.

The whole idea is to see that your function is the second Euclidean norm in $\mathbb R^3$ of the vector $(x-u,y-v,z-w)$ and to use the convexity of the Euclidean norm, which is proved by using the triangle inequality.

Take $t\in[0,1]$ and two vectors $\vec a=(x_1,y_1,z_1,u_1,v_1,w_1)$ and $\vec b=(x_2,y_2,z_2,u_2,v_2,w_2)$. Then $$f(t\vec a+(1-t)\vec b)\\ = f(tx_1+(1-t)x_2,ty_1+(1-t)y_2,tz_1+(1-t)z_2,tu_1+(1-t)u_2,tv_1+(1-t)v_2,tw_1+(1-t)w_2)\\ =\sqrt{(tx_1+(1-t)x_2-(tu_1+(1-t)u_2))^2+(ty_1+(1-t)y_2-(tv_1+(1-t)v_2))^2+(tz_1+(1-t)z_2-(tw_1+(1-t)w_2))^2}$$ $$=\sqrt{(t(x_1-u_1)+(1-t)(x_2-u_2))^2+...}$$ $$=\|t(x_1-u_1,y_1-v_1,z_1-w_1)+(1-t)(x_2-u_2,y_2-v_2,z_2-w_2)\|$$ $$\leq t\|(x_1-u_1,y_1-v_1,z_1-w_1)\|+(1-t)\|(x_2-u_2,y_2-v_2,z_2-w_2)\|$$ $$=t\sqrt{(x_1-u_1)^2+(y_1-v_1)^2+(z_1-w_1)^2}+(1-t)\sqrt{(x_2-u_2)^2+(y_2-v_2)^2+(z_2-w_2)^2}$$ In the last but one line we used triangle inequality for the second Euclidean norm.

Answer 2

The locus of $(x,y,z)$ is a sphere of radius $\sqrt{5}$

The locus of $(u,v,w)$ is a cylinder of radius $1$ , height $4$ and having it's center at $(4,0,6)$

Now consider all the cross sections of the figures which are parallel to the $xz$ plane.The 2 points which minimize this distance is suppose to be in one of these planes.We get the largest cross sectional areas of both the figures if the plane is $y=0$. Hence the points which are the closest to each other - one belonging to the sphere and the other to the cylinder lie on this plane.

The two cross sections are a circle and a rectangle. The point on the rectangle lying closest to the origin is $(3,0,4)$. This is also a point on the circle. Hence the minimum distance is $0$ for the point $(3,0,4)$.

Answer 3

Is my simple minded argument allowed?

The problem of finding $(y,x,z)$ (or $(x,y,z,u,v,w)$) that minimizes $$ \min \sqrt{(x-u)^2 +(y-v)^2 + (z-w)^2 } $$ is the same as: $$ \min \> (x-u)^2 +(y-v)^2 + (z-w)^2 $$ as the square root is a monotonic function.

Sum of squares is convex (and $x-u$ etc. is linear). So we are done.