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

GERMÁN ARIEL TORRES

Córdoba

Congreso; IV CONGRESO LATINOAMERICANO DE MATEMATICOS; 2012

Unión Matemática de América Latina y el Caribe - Facultad de Matemática, Astronomía y Física (UNC)

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 proved that $x^*$ is a fixed point of the iteration function $Q$ if and only if $x^*$ is the solution of the constrained Weber problem. Besides that, under certain hypotheses, $x^*$ satisfies the KKT optimality conditions. The algorithm generates a sequence of feasible points having descending properties. The limit of this sequence is a fixed point of the iteration function $Q$, and therefore it is the solution of the constrained Weber problem. Numerical experiments confirmed the theoretical results.