近日，kaiyun開云官方網(wǎng)站王承競副教授（通訊作者）與合作者的最新研究成果“An efficient algorithm for the ?p norm based metric nearness problem”（中文譯名：基于?p范數(shù)的度量接近問題的高效算法）被計算數(shù)學(xué)頂級期刊《Mathematics of Computation》接收。該期刊專注于數(shù)學(xué)計算的理論與實踐，由美國數(shù)學(xué)會出版，在中國數(shù)學(xué)會推薦的數(shù)學(xué)期刊分類簡表中被列為T1類刊物。。
度量接近問題是機器學(xué)習(xí)中的一類重要問題，廣泛應(yīng)用于傳感器網(wǎng)絡(luò)、圖像處理、數(shù)據(jù)庫索引、計算機視覺等領(lǐng)域。然而，由于O(n3)的度量約束和通?；诩訖?quán)?p范數(shù)的非光滑目標(biāo)函數(shù)，即使獲得一個中等精度的數(shù)值解也是一個極大的挑戰(zhàn)。為深入研究該問題，該論文提出了一種延遲約束生成方法，針對度量接近問題，每個子問題通過基于半光滑牛頓法的近端增廣拉格朗日方法進行求解。
該算法充分利用與度量約束相關(guān)矩陣的特殊結(jié)構(gòu)，避免了高內(nèi)存存儲的需求。數(shù)值實驗表明，該算法不僅在該領(lǐng)域中具有最高的效率，還可以處理多達10^8個變量和10^13個約束的問題，顯著提升了可處理的度量接近問題的規(guī)模標(biāo)準(zhǔn)。以下表格列出了該文所提算法DCGM_PALM與被廣泛應(yīng)用于學(xué)術(shù)研究和工業(yè)界的高性能軟件Gurobi對比的數(shù)值結(jié)果。
論文鏈接：https://arxiv.org/abs/2211.01245
主頁鏈接：https://faculty.swjtu.edu.cn/wangchengjing/zh_CN/index.htm
