运筹与模糊学

Vol.4 No.1 (February 2014)

离散p-扩散问题的连续化算法
An Efficient Lagrangian Smoothing Heuristic for the p-Dispersion-Sum Problem

 

作者:

龚玉君 , 邹慧敏 :北京航空航天大学,数学与系统科学学院,北京

 

关键词:

二次规划问题拉格朗日光滑算法启发式连续算法Quadratic Program Lagrangian Smoothing Frank-Wolfe Algorithm Heuristic

 

摘要:

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

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.

文章引用:

龚玉君 , 邹慧敏 (2014) 离散p-扩散问题的连续化算法。 运筹与模糊学, 4, 7-14. doi: 10.12677/ORF.2014.41002

 

参考文献

分享
Top