A De-singularity Subgradient Approach for the Extended Weber Location Problem

这篇论文研究了扩展Weber定位问题，这是一个经典的优化问题，最近在几个机器学习场景中启发了一些新的工作。然而，当成本函数的幂次为$1\leqslant q<2$时，例如广泛使用的迭代Weiszfeld方法，大多数现有算法可能会因数据点处的奇异性而陷入困境。因此，本文提出了一种去奇异性的次梯度方法，并提供了完整的收敛证明，修正了一些以前的Weiszfeld算法证明中不完整的陈述。此外，我们在一个特殊情况下推导了迭代序列的新的超线性收敛理论结果，即最小点为奇异点的情况。我们在一个真实的机器学习场景中进行了广泛的实验，结果表明，所提出的方法解决了奇异性问题，在非奇异性情况下产生相同的结果，并显示出合理的线性收敛速度。结果还表明，在某些情况下，$q$次方($1<q<2$)比$1$次方和$2$次方更有优势。因此，去奇异性的次梯度方法对推进扩展Weber定位问题的理论和实践都有益处。

解决问题：论文旨在解决扩展Weber位置问题中当代价函数的幂次为1≤q<2时，迭代Weiszfeld算法会因数据点的奇异性而陷入困境的问题。

关键思路：论文提出了一种去奇异性的次梯度方法来解决这个问题，并给出了完整的收敛证明。此外，论文还在特定情况下推导出了迭代序列的超线性收敛理论结果。

其他亮点：论文在真实世界的机器学习场景中进行了大量实验，展示了所提出的方法解决奇异性问题，产生与非奇异性情况相同的结果，并表现出合理的线性收敛速度。此外，研究结果表明，幂次为1

相关研究：最近的相关研究包括Weiszfeld算法的其他变体，如加权Weiszfeld算法和多尺度Weiszfeld算法。