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