2024/12/20 by Lai, Zhao-Rong, Wu, Xiaotian, Fang, Liangda +2
#FOS: Computer and information sciences #FOS: Mathematics #Machine Learning (cs.LG) #Optimization and Control (math.OC)
paper · doi:10.48550/arxiv.2412.15546
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 ℓ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 ℓ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 ℓ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.