II.1.3.3: Generalized Weiszfeld Methods

We discuss Weiszfeld's algorithm for the single facility location problem, or equivalently for the spatial median problem, in section 7.3.2. But, in an important early article, Voß and Eckhardt [1980] pointed out that Weiszfeld's algorithm is a member of a much more general class of algorithms, whch they called Generalized Weiszfeld Methods.

The problem Voß and Eckhardt consider is to minimize a twice continuously differentiable $f$ over a polyhedron $\mathcal{X}\subseteq\mathbb{R}^n$, defined by a number of linear inequalities. They assume that $f$ is bounded from below on $\mathcal{X}$ and that the sublevel sets $\{x\mid f(x)\leq\gamma\}$ have a empty of bounded intersection with $\mathcal{X}$. They define the quadratic approximation $$g(x,y)=f(y)+(x-y)'\mathcal{D}f(y)+\frac12(x-y)'A(y)(x-y)$$ for which they assume that $g(x,y)\geq f(x)$ for all $x\in\mathcal{X}.$ In addition the spectral norm $\|A(y)\|$ is must be bounded from above on $\mathcal{X}$ by $A_\infty$, and the smallest eigenvalue of $A(y)$ must be bounded from below on $\mathcal{X}$ by a positive number $\gamma_0$. Their algorithm is $$x^{(k+1)}=\mathop{\mathbf{argmin}}\limits_{x\in\mathcal{X}} g(x,x^{(k)}).$$

This, of course, is a majorization algorithm. In fact, it is an example of the quadratic mjaorization algorithms we discuss in detail in chapter 10. Voß and Eckhardt proceed to prove global convergence, which actually follows directly from Zangwill's theory, and local linear convergence, which follows from Ostrowski's theorem.