AAAI 2025：韦伯区位难题获解，次梯度法显神威

好的，这是一篇根据您提供的材料撰写的新闻报道，力求达到您所提出的专业性和深度要求：

标题：暨南大学团队突破“奇异性”难题：为韦伯区位问题带来全新解法

引言：

在运筹优化领域，韦伯区位问题如同一个古老的谜题，吸引着无数研究者不断探索。这个问题看似简单，实则蕴含着深刻的数学挑战，并在机器学习、人工智能、金融工程等多个领域有着广泛的应用。近日，暨南大学通用机器学习课题组在这一难题上取得了突破性进展，他们提出了一种名为“去奇异性次梯度方法”的新颖算法，为解决韦伯区位问题中的“奇异性”难题提供了全新的视角和解决方案。这一研究成果不仅在理论上具有重要意义，更在实际应用中展现出巨大的潜力。

主体：

韦伯区位问题：一个跨越世纪的挑战

韦伯区位问题最早可追溯到著名数学家皮耶·德·费马，后经经济学家阿尔弗雷德·韦伯（社会学家马克斯·韦伯之弟）的扩展，成为一个经典的运筹优化问题。其核心在于寻找一个“中心点”，使得该点到多个给定数据点的加权距离之和最小。这个看似简单的目标，在实际应用中却面临着诸多挑战，尤其是在处理非欧几何和非凸优化问题时。

该问题的数学表达如下：

min ∑_i w_i ||x - x_i||_p^q

其中，x是要寻找的中心点，x_i是给定的数据点，w_i是权重，||.||_p表示l_p范数，q是距离的幂次。p和q这两个参数的变化，使得问题更具表达力和适应性，但也带来了求解上的复杂性。

“奇异性”：优化算法的拦路虎

在求解韦伯区位问题时，一个关键的挑战在于“奇异性”。当算法迭代过程中，某些参数组合导致梯度不存在时，就会出现奇异性。具体而言，当 q<p 或 p<2 时，如果迭代点 y 恰好落在特定的奇异集上，梯度就会消失，导致算法无法继续优化。

当 p=2 时，奇异点是有限的，算法可以通过一定的策略脱离奇异集。然而，当 1<=p<2 时，奇异集会变成一个包含无限个点的连续集合，算法可能会反复陷入奇异集，无法收敛到最优解。这种奇异性问题在实际应用中经常发生，并且难以通过简单的随机扰动或重选初始点来解决。

暨南大学团队的创新解法：去奇异性次梯度方法

针对上述难题，暨南大学通用机器学习课题组提出了一种名为“去奇异性次梯度方法”的创新算法。该方法的核心思想是：首先识别出引发奇异性的数据点和维度，然后将相应的分量去除掉，从而避免梯度消失。

具体而言，该方法通过以下步骤实现：

识别奇异性： 使用集合 V_t(y) 和 U_i(y) 来分别表示引发奇异性的数据点和维度。
定义去奇异性次梯度： 基于识别出的奇异性信息，定义去奇异性次梯度 D_{p,q}(y)。
验证次梯度性质： 证明该次梯度具有与普通梯度类似的良好性质，如能够刻画最小值点和下降方向。
构建去奇异性Weiszfeld算法： 基于经典的Weiszfeld算法，构建一种基于q次方p范数的去奇异性Weiszfeld算法（qPpNWAWS）。该算法在非奇异性情形下使用常规Weiszfeld更新迭代，在奇异性情形下使用沿下降方向线性搜索法。

算法优势与未来展望

该算法的优势在于：

解决奇异性问题： 有效解决了韦伯区位问题中的奇异性难题，使得算法能够稳定收敛到最优解。
不增加计算复杂度： 与传统梯度法相比，该方法在不增加计算复杂度的前提下，实现了对奇异性的有效处理。
保证收敛性： 证明了算法的收敛性，尤其在 1<p<2 这一严格凸情形下，能够保证迭代序列收敛到全局最小值点。

该研究成果不仅在理论上具有重要意义，更在实际应用中展现出巨大的潜力。例如，在物流选址、设施布局、资源分配等领域，该算法能够提供更准确、更高效的解决方案。

团队介绍

暨南大学通用机器学习课题组由网络空间安全学院和信息科学技术学院的多名青年教师、博士生、硕士生和本科生共同组成，研究方向包括通用逼近理论、分布外泛化、非凸优化、稀疏学习、深度学习框架的基础模块开发、优化器开发、隐私保护与增强等。自 2024 年 4 月至 12 月，该课题组作为第一单位已获得所有 CCF A 机器学习国际顶级会议 ICML（2 篇）、NeurIPS 和人工智能国际顶级会议 IJCAI、AAAI 录用论文共 5 篇。

结论：

暨南大学通用机器学习课题组的这项研究成果，为解决韦伯区位问题中的“奇异性”难题提供了全新的思路和方法。该团队提出的去奇异性次梯度方法，不仅在理论上具有创新性，更在实际应用中展现出巨大的潜力。随着人工智能和机器学习技术的不断发展，我们有理由相信，这项研究成果将为相关领域带来更深远的影响。

参考文献：

[1] [原始论文引用1]
[2] [原始论文引用2]
[3] [暨南大学团队 IJCAI 2024 论文]
[4] [相关文献引用4]
[5] [Weiszfeld 算法原始文献]

项目地址:

https://github.com/laizhr/qPpNWAWS

论文链接:

http://arxiv.org/abs/2412.15546

（完）

写作说明：