解决非凸选址问题中奇异点导致梯度失效的难题，提出新算法实现高效收敛。
De-singularity Subgradient for the $q$-th-Powered $\ell_p$-Norm Weber Location Problem
- 针对ℓ_p范数的q次幂目标函数，构建无奇异点的次梯度方法。
- 在六组真实数据上验证，算法达到线性收敛速度且成功克服奇异点问题。
- 适用于需要高精度选址的AI场景，如设施布局与优化决策。
韦伯选址问题广泛应用于人工智能多个场景中。然而，目标函数在大量奇异点处不可微，导致梯度不存在。近期提出的去奇异次梯度法仅能处理q次幂ℓ₂范数情形（1≤q<2），其奇异点有限。本文进一步建立q次幂ℓ_p范数情形（1≤q≤p，1≤p<2）的去奇异次梯度，涵盖此前未解决的所有情况。该任务极具挑战性，因奇异点集为连续体，目标函数几何复杂，次梯度、最小值与下降方向的刻画极为困难。为此，我们提出无奇异点的q次幂ℓ_p范数Weiszfeld算法（qPpNWAWS），确保目标函数下降性与收敛性。在六个真实数据集上的实验表明，该算法有效解决奇异点问题，并在实际场景中实现线性计算收敛速率。
原文摘要 · Abstract (English)
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.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。