一种超松弛的最优传输近似点算法  

An Overrelaxed Proximal Point Method for Optimal Transport

作　　者：吴凡 刘向阳[1] WU Fan;LIU Xiangyang(Schoolof Science,Hehai University,Nanjing 211106,China)

机构地区：[1]河海大学理学院,南京211106

出　　处：《重庆师范大学学报（自然科学版）》2022年第6期20-27,共8页Journal of Chongqing Normal University:Natural Science

基　　金：国家自然科学基金(No.61773152)。

摘　　要：【目的】最优传输在实际应用中通常使用Sinkhorn算法求解熵正则化形式得到近似解,考虑Sinkhorn算法的效果容易受熵正则化参数影响,且难以收敛到最终精确解,提出了一种超松弛形式的近似点算法。【方法】针对原最优传输的近似点算法,为其中传输计划的迭代计算引入超松弛算子,并给出了超松弛参数计算方法。【结果】在保持算法对正则化参数具有鲁棒性及可收敛至精确解的优点的同时,所提算法能更快地收敛至精确解。【结论】数值实验表明,相较于原近似点算法,所提算法进一步提升了收敛速度,在有限的迭代步骤下能够达到更高精度,算法可更好地应用于机器学习。[Purposes]In practical applications, Sinkhorn algorithm is usually used to solve the entropy regularization form of the optimal transport to obtain its approximate solution. Considering that the Sinkhorn algorithm is easily affected by the entropy regularization parameter, and it is difficult to converge to the final accurate solution, an overrelaxed form of proximal point method is proposed. [Methods]The overrelaxed operator is introduced to the iterative calculation of the transport plan in the original proximal point method of optimal transport, and the calculation strategy of the overrelaxed parameter is given. [Findings]While maintaining the robustness to the regularization parameter and the advantages of converging to the accurate solution, the proposed method can converge towards the accurate solution faster. Through theoretical and experimental analysis, the method is not only robust to the selection of entropy regularization parameter, but can also converge to an accurate optimal transport plan. [Conclusions]Compared with the original form of the proximal point method, the proposed method further improves its convergence speed, it can achieve higher accuracy within limited iteration, and the method can be better applied to machine learning.

关 键 词：最优传输 超松弛 近似点算法 熵正则化 矩阵缩放算法 

分 类 号：O224[理学—运筹学与控制论] O29[理学—数学]