近日，西南交通大学数学学院王承竞副教授（通讯作者）与合作者的最新研究成果“An efficient algorithm for the ℓp norm based metric nearness problem”（中文译名：基于ℓp范数的度量接近问题的高效算法）被计算数学顶级期刊《Mathematics of Computation》接收。该期刊专注于数学计算的理论与实践，由美国数学会出版，在中国数学会推荐的数学期刊分类简表中被列为T1类刊物。。
度量接近问题是机器学习中的一类重要问题，广泛应用于传感器网络、图像处理、数据库索引、计算机视觉等领域。然而，由于O(n³)的度量约束和通常基于加权ℓp范数的非光滑目标函数，即使获得一个中等精度的数值解也是一个极大的挑战。为深入研究该问题，该论文提出了一种延迟约束生成方法，针对度量接近问题，每个子问题通过基于半光滑牛顿法的近端增广拉格朗日方法进行求解。
该算法充分利用与度量约束相关矩阵的特殊结构，避免了高内存存储的需求。数值实验表明，该算法不仅在该领域中具有最高的效率，还可以处理多达10^8个变量和10^13个约束的问题，显著提升了可处理的度量接近问题的规模标准。以下表格列出了该文所提算法DCGM_PALM与被广泛应用于学术研究和工业界的高性能软件Gurobi对比的数值结果。
论文链接：https://arxiv.org/abs/2211.01245
主页链接：https://faculty.swjtu.edu.cn/wangchengjing/zh_CN/index.htm
