De-singularity Subgradient for the $q$-th-Powered $\ell_p$-Norm Weber Location Problem
This work addresses a technical bottleneck in AI applications involving location optimization, but it is incremental as it extends an existing method to more general cases.
The paper tackles the Weber location problem by extending a de-singularity subgradient method to handle the q-th-powered ℓp-norm case with 1≤q≤p and 1≤p<2, where the singular set is a continuum, and demonstrates that the proposed algorithm successfully solves the singularity problem and achieves a linear computational convergence rate in experiments on six real-world datasets.
The Weber location problem is widely used in several artificial intelligence scenarios. However, the gradient of the objective does not exist at a considerable set of singular points. Recently, a de-singularity subgradient method has been proposed to fix this problem, but it can only handle the $q$-th-powered $\ell_2$-norm case ($1\leqslant q<2$), which has only finite singular points. In this paper, we further establish the de-singularity subgradient for the $q$-th-powered $\ell_p$-norm case with $1\leqslant q\leqslant p$ and $1\leqslant p<2$, which includes all the rest unsolved situations in this problem. This is a challenging task because the singular set is a continuum. The geometry of the objective function is also complicated so that the characterizations of the subgradients, minimum and descent direction are very difficult. We develop a $q$-th-powered $\ell_p$-norm Weiszfeld Algorithm without Singularity ($q$P$p$NWAWS) for this problem, which ensures convergence and the descent property of the objective function. Extensive experiments on six real-world data sets demonstrate that $q$P$p$NWAWS successfully solves the singularity problem and achieves a linear computational convergence rate in practical scenarios.