De-singularity Subgradient for the q-th-Powered lₚ-Norm Weber Location Problem
Zhao-Rong Lai, Xiaotian Wu, Liangda Fang, Ziliang Chen, Cheng Li
Abstract
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 l_2-norm case (1<= q<2), which has only finite singular points. In this paper, we further establish the de-singularity subgradient for the q-th-powered l_p-norm case with 1<= q<= p and 1<= 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 l_p-norm Weiszfeld Algorithm without Singularity (qPpNWAWS) for this problem, which ensures convergence and the descent property of the objective function. Extensive experiments on six real-world data sets demonstrate that qPpNWAWS successfully solves the singularity problem and achieves a linear computational convergence rate in practical scenarios.
BibTeX
@article{Lai_Wu_Fang_Chen_Li_2025, title={De-singularity Subgradient for the q-th-Powered lₚ-Norm Weber Location Problem}, volume={39}, url={https://ojs.aaai.org/index.php/AAAI/article/view/33983}, DOI={10.1609/aaai.v39i17.33983}, abstractNote={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 l_2-norm case (1<= q<2), which has only finite singular points. In this paper, we further establish the de-singularity subgradient for the q-th-powered l_p-norm case with 1<= q<= p and 1<= 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 l_p-norm Weiszfeld Algorithm without Singularity (qPpNWAWS) for this problem, which ensures convergence and the descent property of the objective function. Extensive experiments on six real-world data sets demonstrate that qPpNWAWS successfully solves the singularity problem and achieves a linear computational convergence rate in practical scenarios.}, number={17}, journal={Proceedings of the AAAI Conference on Artificial Intelligence}, author={Lai, Zhao-Rong and Wu, Xiaotian and Fang, Liangda and Chen, Ziliang and Li, Cheng}, year={2025}, month={Apr.}, pages={18026-18034} }