离散p-扩散问题的连续化算法

An Efficient Lagrangian Smoothing Heuristic for the p-Dispersion-Sum Problem

摘要: p-扩散问题主要研究在事先定义的n个位置中如何选取p个位置，使得这p个位置之间的距离之和最大，具有很实际的应用价值。本文提出了解决p-扩散问题的一种连续化方法，采用连续的算法解决离散问题策略，通过控制一个参数使得从拉格朗日函数向罚函数过渡迭代求解。这种算法的子问题采用了截断的Frank-Wolfe算法来避免收敛过慢，相比较离散算法，不受结点数量的制约，更具有广泛性。本文建立了有效的迭代终止准则，并且证明了这种算法最终会收敛在一个KKT点。最后，针对这种连续化算法，我们做了大量数值实验，验证了算法的可行性与有效性。

Abstract: In this article, we propose a Lagrangian smoothing algorithm for the p-dispersion-sum problem (PDSP), a problem to locate p facilities at some of n predefined locations by maximizing the distance sum between the p established facilities, where the continuation subproblems are solved by the truncated Frank-Wolfe algorithm. We make the iteration from Lagrangian function to penalty function by controlling a parameter. We establish practical stopping criteria and prove that our algorithm finitely terminates at a KKT point. Compared to the discrete algorithm, the smoothing algorithm is free from the constraints of the number of nodes and more extensive. Numerical results indicate that our approach outperforms good and rapid for solving randomly generated problems in dimensional n ≥ 100.