A projected newton method forl p norm location problems

This paper is concerned with the numerical solution of continuous minisum multifacility location problems involving thel _p norm, where 1<p<x. This class of problems is potentially difficult to solve because the objective function is not everywhere diflerentiable. After developing conditions that characterize the minimum of the problems under consideration, a second-order algorithm is presented. This algorithm is based on the solution of a finite sequence of linearly constrained subproblems. Descent directions for these subproblems are obtained by projecting the Newton direction onto the corresponding constraint manifold. Univariate minimization is achieved via a specialized linesearch which recognizes the possibility of first derivative discontinuity (and second derivative unboundedness) at points along the search direction. The algorithm, motivated by earlier works of Calamai and Conn, and related to methods recently described by Overton and Dax, is shown to possess both global and quadratic convergence properties. Degeneracy can complicate the numerical solution of the subproblems. This degeneracy is identified, and a method for handling it is outlined. An implementation of the algorithm, that exploits the intrinsic structure of the location problem formulation, is then described along with a discussion of numerical results. The research was supported in part by Natural Sciences and Engineering Research Council of Canada grants A-5671 and A-8639 and by the Applied Mathematical Sciences Research Program (KC-04-02) of the Office of Energy Research of the U.S. Department of Energy under Contract W-31-109-Eng-38. This paper was typeset using software developed at Bell Laboratories and the University of California at Berkeley.