## Simple optimization problem regarding distances

Given points in the plane we can study the problem

For the solution is known and for a triangle which has an angle less than is the Toricelli (or Fermat) point, which lies at the intersection of the circumcircles of the equilateral triangles built outside the triangle having the sides of the triangle as support.

For , if we have a convex quadrilateral, then a simple triangle inequality argument proves that the optimal position for is the intersection of the diagonals.

In general, we cannot precisely say what is the position of the solution. Providing a numerical algorithm which computes the optimal position of is not a hard task, and I will do that in the end of this post.

First let’s prove that the problem always has a solution. I note where is a point chosen as the origin of the plane. If then it is easy to see that . One way to see this is to write the triangle inequality .

Therefore the set is compact for every real number . It is closed by the continuity of and bounded from the above remark. Pick some in the plane and very large. Since the function is bounded below by there exists and . We can pick a minimizing sequence such that .

From a point on is in which is compact. Therefore has a limit point and taking the limit we find that . This proves that the problem has a solution for every configuration of points .

Let’s turn to the numerical part. If we want to find numerically the position of then we can use an optimization algorithm like the gradient descent. The objective function is which is easy to calculate.

Let’s find the gradient of . If is a direction in with then the derivative of in is

Denote . Then using the cosine theorem we have

Using this we have

This is according to intuition: if we have a segment and we go from in a direction which points towards the zone of the plane where is then the angle between and is in the interval region where is positive and therefore is negative. This means that going in the direction will decrease the distance between and (at least for a little while…).

If the angle between and is obtuse then is negative and going in that direction will increase the distance between and .

The cosine of an angle of two vectors is connected to their scalar product by

The direction was chosen arbitrary, and to find the gradient we only need the directions corresponding to the canonical base and . Therefore if we consider where are the coordinates of then we have

and

Taking a good look at our results we can see that

which is minus the unit vector in the direction of .

Our function is a sum of functions of the type for different points so

Having calculated the gradient of we can plug it in a gradient descent algorithm and see the results. Usually for optimization algorithms we need to be close to the solution if we want to find the global minimum. But here, since the distance function is strictly convex, we have a unique minimizer, so the algorithm will converge to it whatever starting point we choose.

Here is a matlab code for calculating the distances and the gradient:

function [val,gradt,exit_opts] = cost_steiner(x,opts) P = opts.P; exit_opts = opts; val = sum(sqrt(sum((P-repmat(x,[1 size(P,2)])).^2,1))); gradt = P-repmat(x,[1 size(P,2)]); norms = sqrt(sum(gradt.^2,1)); gradt = gradt*diag(1./norms); gradt = - sum(gradt,2); fill(P(1,:),P(2,:),'go'); plot(x(1),x(2),'rx'); axis equal drawnow

Below you have some examples of some executions of the algorithm. Notice that we find the same solution even if we choose different starting points.