A globally convergent algorithm for the Euclidean multiplicity location problem

The Euclidean single facility location problem (ESFL) and the Euclidean multiplicity location problem (EMFL) are two special nonsmooth convex programming problems which have attracted a large literature. For the ESFL problem, there are algorithms which converge both globally and quadratically. For the EMFL problem, there are some quadratically convergent algorithms, but for global convergence, they all need nontrivial assumptions on the problem.In this paper, we present an algorithm for EMFL. With no assumption on the problem, it is proved that from any initial point, this algorithm generates a sequence of points which converges to the closed convex set of optimal solutions of EMFL.This research is supported in part by the Air Force Office of Scientific Research Grant AFOSR-87-0127, the National Science Foundation Grant DCR-8420935 and University of Minnesota Graduate School Doctoral Dissertation Fellowship awarded to G.L. Xue.