Convergence and Descent in the Fermat Location Problem

The Fermat location problem is to find a point whose sum of weighted distances from m given points (vertices) is a minimum. The best known method of solution is an iterative scheme devised by Weiszfeld in 1937, which converges to the unique minimum point unless one of the iterates happens to “land” on a nonoptimal vertex. The convergence proof of this scheme depends on two theorems, one of which (descent theorem) states that the objective function strictly decreases at each step. This paper extends the descent theorem by proving: (1) there is a “ball” whose radius and center depend on the Weiszfeld iteration, such that any algorithm whose iterates are “in the ball” or “on its surface” is a descent algorithm; (2) under certain circumstances, one or more of the vertices may be deleted, although the weight(s) are taken into account, and the Weiszfeld algorithm retains its descent property. In general there are several subsets of vertices which may be deleted, and for each subset, a corresponding iterate; (3) the convex hull of these iterates is such that all points within it have the descent property. Examples of the potential application of these extensions are given, including the construction of a modified Weiszfeld algorithm that without exception converges to the optimum. Beyond that, it is hoped the theorems may in time be useful in proving the descent property of yet to be discovered, very fast, nongradient algorithms.