基于交替方向法的韦伯问题求解方法

New Numerical Methods for Weber Problem Based on Alternating Direction Method of Multipliers

韦伯问题(Weber problem)是设施选址领域中的重要问题,Weiszfeld算法则是求解韦伯问题最常用的数值方法.应用Weiszfeld算法求解韦伯问题需考虑如下两方面:1)当出现迭代点和顾客点重合(称为奇异情形)时,Weiszfeld算法的全局收敛性无法保证;2)韦伯问题经常需要快速求解,但Weiszfeld算法作为最速下降法其求解效率并不高.本文对lp-范数下的韦伯问题建立基于交替方向法的统一算法框架,并提出求解l1,l2,l∞-范数下韦伯问题新的数值算法.新算法在算法的收敛性和收敛效率两方面都有着显著的优势:即使在奇异情形下新算法仍能保证全局收敛性,且具有比Weiszfeld算法更快的收敛效率.数值实验验证了基于交替方向法的新算法求解韦伯问题的有效性.

Weber problem （WP） is one of important problems in facility location and Weiszfeld algorithm is the well-used numerical method for solving Weber problem. When Weiszfeld algorithm is used to solve Weber problem, the following two aspects should be taken into consideration. Firstly, when the iterate happens to coincide with one customer （which is called as singular case）, the global convergence of Weiszfeld algorithm is not guaranteed. Secondly, Weber problem needs to he solved quickly in many cases, hut as the steepest descent method the efficiency of Weiszfeld algorithm is not high enough. In this paper we consider the Weber problem under lp-norm. Based on the alternating direction method of multipliers （ADMM）, we develop a unified algorithm framework for solving Weber problem under different p and propose new ADMM-based methods for Weber problem under li , l2 , l∞-norms. The ADMM-based method has advantages in both convergence and convergence efficiency in the sense that it ensures the global convergence even in singular case and has faster convergence efficiency than Weiszfeld algorithm. The numerical results verify the efficiency of the proposed ADMM-based methods.