Convergence and Descent in the Fermat Location Problem

Lawrence M. Ostresh
Additional contact information
Lawrence M. Ostresh: The University of Wyoming, Laramie

Transportation Science, 1978, vol. 12, issue 2, 153-164

Abstract: 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.

Date: 1978
References: Add references at CitEc
Citations: View citations in EconPapers (1)

Downloads: (external link)
http://dx.doi.org/10.1287/trsc.12.2.153 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:ortrsc:v:12:y:1978:i:2:p:153-164

Access Statistics for this article

More articles in Transportation Science from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().