Weber-Fermat Problem, degenerate cases

[iorfus]

Homework Statement

I have to prove some things on the Weber-Ferma problem. Here is the assignment :

We want to find a point $$x$$ in the plane whose sum of weighted
distances from a given set of fixed points $$y_1, ...,y_m$$ is minimized.

1-Show that there exist a global mimimum to the problem.
2-Is the minimum always unique?

3-Considering that there are actually ropes connected to weights for each of the fixed point, prove that the minimum is the point where the resultant force is zero.
My problem is that I want to prove the las point by observing that the gradient is just the resulting force on the minimum. Therefore, being the gradient zero for a minimum, the point is proven.
However, I have two questions which I am not able to answer:

1-If the points are not collinear, can the minimum be one of them?
2-If the mimimum is one of them, how can I prove that the resulting force is null?

Forum-related question : $x$ does not work, is it normal?

Thanks

Homework Equations

The function to minimize is
$$f(x)= \sum_{i=1}^m w_i|| x-y_i || $$

with no constraints.

The Attempt at a Solution

1-Done, the function is continuous and I can define it on a compact ball of arbitrary radius, so for Weierstrass's Theorem it has a minimum.

2-The minimum is unique if the points are not collinear. Indeed, the function f(x), which is convex, can be shown to be strictly convex if the points are not collinear (if someone is interested, I will report my proof).

3-It should be easy, the gradient is null in the minimum and the gradient is just the resultant force.
My problem is : what do I do if the minimum coincides with one of the fixed point? I cannot differentiate, the gradient is not defined.

 

[iorfus]

Anyone?
Any hint?

 

[Ray Vickson]

Anyone?
Any hint?

Google Varignon Frame, which is an analogue device that can be used to find the optimal point.

For a Varignon Frame the objective $f(\vec{x}) = \sum_i w_i || \vec{x} - \vec{y}_i ||$ is the potential energy of the weights hung on the strings under the holes at point $\vec{y}_i, i=1,2,\ldots, n$. As you say, at a non-degenerate point we have $\nabla f(\vec{x}) = \vec{0}$, which means that the gradient of the potential energy equals zero. What would that tell you about the "force"?

If (as sometimes happens) the optimal point $\vec{x*}$ lies on one of the points $\vec{y}_i$, the gradient is not well-defined precisely at the point where the solution happens to occur. Suppose, for example, that $\vec{x*} = \vec{y}_n$. At that point, $w_n || \vec{x*} - \vec{y}_n|| = 0$, so point $n$ does not actually contribute to $f$. So, if you eliminated point $\vec{y}_n$ entirely, how would that affect the solution? What could you say about the "force" in the modified problem? What then happens if you put back point $\vec{y}_n$?

 

[iorfus]

First of all, thanks for the answer and for the didactic questions.

What would that tell you about the "force"?

It precisely tells me that the resultant force is zero, because the two components of the gradient are the horizontal and vertical component of the resultant force acting on the optimal point.

So, if you eliminated point ⃗yny→n\vec{y}_n entirely, how would that affect the solution?

I had thought about eliminating one of the points if the minimum coincides with one of them, but I have two main doubts:
Doubt 1-Removing one point, the original function would be different, therefore the minimum would change.
Doubt 2-Moreover, if the minimum concides with one of the fixed point, is the resultant force on the minimmum null?

For example, imagine to have equal weights and the three points :
$$A(-\sqrt{3}, 0); \hspace{0.3cm} B(\sqrt{3}, 0); \hspace{0.3cm} C(0,1) $$

It is not difficult to prove that the minimum coincides with C. Indeed, this was one of the cases which was geometrically proven back in Torricelli's time (more or less).
Now, it seems to me that the resultat force on the poinc C is not zero (doubt 2).
Imagine I remove the point C ... the minimum would then be any point on the AB segment (doubt1).

I am very confused by these degenerate cases ... any further hint would help.
Thanks

 

[Ray Vickson]

First of all, thanks for the answer and for the didactic questions.It precisely tells me that the resultant force is zero, because the two components of the gradient are the horizontal and vertical component of the resultant force acting on the optimal point.I had thought about eliminating one of the points if the minimum coincides with one of them, but I have two main doubts:
Doubt 1-Removing one point, the original function would be different, therefore the minimum would change.
Doubt 2-Moreover, if the minimum concides with one of the fixed point, is the resultant force on the minimmum null?

For example, imagine to have equal weights and the three points :
$$A(-\sqrt{3}, 0); \hspace{0.3cm} B(\sqrt{3}, 0); \hspace{0.3cm} C(0,1) $$

It is not difficult to prove that the minimum coincides with C. Indeed, this was one of the cases which was geometrically proven back in Torricelli's time (more or less).
Now, it seems to me that the resultat force on the poinc C is not zero (doubt 2).
Imagine I remove the point C ... the minimum would then be any point on the AB segment (doubt1).

I am very confused by these degenerate cases ... any further hint would help.
Thanks

My suggestion to remove point n and then put it back was erroneous; I had been thinking of the situation where you solve an (n-1)-point problem, then afterwards add a new point n at the location of the old solution. In that specific case the new point will not affect the solution, but in general the two problems would have different solutions.

All I can do is suggest you Google "Weber problem" and look at the many articles relating to aspects of the problem. Location-theorists have worked for years developing robust algorithms that can work despite the possible presence of degenerate solutions. There is a huge literature out there on the subject, and I have not been keeping up with it for a long time.

 

[iorfus]

Okay, I see ... I had thought about it too (adding a new point afterward) and it did not help me.

You are right, there is a lot of stuff out there. I read some papers and took a look at many\ others. None of them helped me, because I just need
to prove that
1-The solution exists (I did it appealing to Weierstrass theorem)
2-A solution is a point on which the resultant force is null (I just observe that the gradient is null, and the gradient is the resultant force in this case)
And some other things to prove, that I managed to do.

I have seen all the sophisticated algorthms to actually calculate the point, proof that they converge etc.
Interesting, of course. but for my assigment to be complete I only need to extend the proof of point 2 to the case in which the minimum coincides with one of the point. I find no hint on the web ...
If you, Ray, come up with any idea to help me compete this homework, I will be glad to know ... similarly, if anyone has any hint, please let me know!

In the meantime, thanks Ray!

 

[Ray Vickson]

Okay, I see ... I had thought about it too (adding a new point afterward) and it did not help me.

You are right, there is a lot of stuff out there. I read some papers and took a look at many\ others. None of them helped me, because I just need
to prove that
1-The solution exists (I did it appealing to Weierstrass theorem)
2-A solution is a point on which the resultant force is null (I just observe that the gradient is null, and the gradient is the resultant force in this case)
And some other things to prove, that I managed to do.

I have seen all the sophisticated algorthms to actually calculate the point, proof that they converge etc.
Interesting, of course. but for my assigment to be complete I only need to extend the proof of point 2 to the case in which the minimum coincides with one of the point. I find no hint on the web ...
If you, Ray, come up with any idea to help me compete this homework, I will be glad to know ... similarly, if anyone has any hint, please let me know!

In the meantime, thanks Ray!

At a non-degenerate solution, the gradient exists and equals the 0 vector. At a degenerate point there is no gradient, so you cannot say that the gradient = 0 there. However, there is a so-called subgradient, and a subdifferential (which is a set of subgradients), and the optimality condition is that the zero vector is a member of the subdifferential set. Alternatively, the function is increasing along any directional derivative at the solution point.

For existence and uniqueness, it is enough to know that the function is strictly convex and that the minimum value inside some large circle of radius $r$ around the origin is smaller than any value outside the circle (so that if there is a minimum at all, it is inside the circle). Existence of a minimum inside the circle follows form Weierstrass, and uniqueness follows from strict convexity.

As for the "forces" business, I don't see the point, but if you were told to do it I guess you have no choice.

The issue is really what happens if the solution is degenerate, say at point $\vec{y_n}$. In a Varignon frame (where forces are real and are responsible for the solution), the knot comes to rest on the top of the hole at $\vec{y_n}$; it is too large to be sucked down through the hole, so it stops there. If you force the knot to move away from $\vec{y_n}$ a distance $\Delta r$ along a horizontal unit vector $\vec{p}$, that raises the weight $w_n$ below $\vec{y_n}$ by $\Delta r$ and needs work input $w_n \Delta r$. At the same time, some other distances are increased or decreased a bit, so some other weights are lowered or raised a bit. That means that some of the other work inputs may be positive and some may be negative. However, the net work input must be > 0 because the objective is minimized at $\vec{x} = \vec{y_n}$. You could have a positive work input for any direction $\vec{p}$, so the forces would not be balanced.

The forces acting on the knot are (i) those due to the other (n-1) strings, which act horizontally; (ii) the force $w_n$ acting straight down under $\vec{y_n}$; and (iii) the reaction force of the hole's rim, which prevents the knot from slipping down the hole. The total of all three types of forces must = 0, because the knot does not move; however, there is no reason to assume that the sum of forces (i) and (ii) alonegive zero. (Note that the reaction force must have a horizontal component to cancel the horizontal total of the first (n-1) forces; and, of course, its vertical component is $+w_n$ to cancel the force $-w_n$ due to the hanging weight.)

 

[iorfus]

Sorry for the late answer.
Actually, I now think that all the reasoning should be done in ideal conditions, without friction and reaction force.
Indeed, in the example gave

$$A(-\sqrt{3}, 0); \hspace{0.3cm} B(\sqrt{3}, 0); \hspace{0.3cm} C(0,1),$$

the resultant force on the minimum, coinciding with $C$ in this case, is zero.

I would like to prove in general that the resultant force is zero at the minimum,
even when the minimum is one of the fixed points, but I am probably going to give it up.

Thanks in any case.