A Weiszfeld-like algorithm for a Weber location problem constrained to a closed and convex set

arXiv1204.1087MaRDI QIDQ6232099FDOQ6232099

Germán A. Torres

Publication date: 4 April 2012

Abstract: The Weber problem consists of finding a point in $mathbbm{R}^n$ that minimizes the weighted sum of distances from $m$ points in $mathbbm{R}^n$ that are not collinear. An application that motivated this problem is the optimal location of facilities in the 2-dimensional case. A classical method to solve the Weber problem, proposed by Weiszfeld in 1937, is based on a fixed point iteration. In this work a Weber problem constrained to a closed and convex set is considered. A Weiszfeld-like algorithm, well defined even when an iterate is a vertex, is presented. The iteration function $Q$ that defines the proposed algorithm, is based mainly on an orthogonal projection over the feasible set, combined with the iteration function of a modified Weiszfeld algorithm presented by Vardi and Zhang in 2001. It can be seen that the proposed algorithm generates a sequence of feasible iterates that have descent properties. Under certain hypotheses, the limit of this sequence satisfies the KKT optimality conditions, is a fixed point of the iteration function that defines the algorithm, and is the solution of the constrained minimization problem. Numerical experiments confirmed the theoretical results.

Mathematics Subject Classification ID

Convex programming (90C25) Nonlinear programming (90C30) Continuous location (90B85)

This page was built for publication: A Weiszfeld-like algorithm for a Weber location problem constrained to a closed and convex set

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6232099)