This paper is concerned with the numerical solution of continuous minisum multifacility location problems involving the \(\ell_ p\) norm, where \(1<p<\infty\). This class of problems is potentially difficult to solve because the objective function is not everywhere differentiable. 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 line search 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 the authors [SIAM J. Sci. Stat. Comput. 1, 512-526 (1980;Zbl 0469.65040); Springer Lect. Notes Math. 912, 1-25 (1982;Zbl 0485.65013)], and related to methods recently described byM. L. Overton [Computing Methods in Appl. Sci. and Engineering VI, Proc. 6th Int. Symp., Versailles 1983, 421-437 (1984;Zbl 0585.73060)] andA. Dax [Math. Program. 36, 72-80 (1986;Zbl 0614.90033)], 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.