一种改进的牛顿法及其在欧式距离选址模型中的应用

段 琼，戴 璟，乔 慧

（1.昆明理工大学 经济与管理学院，云南 昆明 650093；2.河南理工大学 数学与信息科学学院，河南 焦作 454003）

一种改进的牛顿法及其在欧式距离选址模型中的应用

段 琼1，戴 璟1，乔 慧2

（1.昆明理工大学 经济与管理学院，云南 昆明 650093；2.河南理工大学 数学与信息科学学院，河南 焦作 454003）

设施选址决策在物流网络的设计中具有重大作用，距离选址模型实际上是一个无约束条件的最优化问题，可采用无约束优化算法求解。首先提出一种求解退化问题的牛顿-梯度耦合算法，数值算例表明，该算法是可行的，并且具有更好的计算效果，在此基础上进一步将提出的算法应用于欧氏距离选址模型，通过实例分析证明提出的牛顿-梯度耦合算法对解决欧氏距离选址模型是有效的。

牛顿法；梯度法；退化问题；欧式距离选址模型

近年来，关于物流设施选址的理论发展迅速[1]，国内外学者在该领域已取得了许多研究成果。代表性的方法有交叉中值模型(Cross Media Model)和重心法(Cen-

1 引言

设施选址决策在物流网络设计中作用重大，决定了整个物流系统的模式、结构和形状。选址决策就是用模型化的方法来确定物流相关设施的数量、具体位置和分配方案，从而保证物流系统各功能活动的有机结合,达到降低整个系统运营成本的目的。不管是单个企业troid Method)。选址因素一般多只考虑运输费率和该点的货物运输量,所以这两个方法都较为简单。然而使用上述两种方法仅能获得粗略的最优解，无法得到精确的解。金鑫和王胜囡[2]应用交叉中值模型研究了新建城镇物流服务设施选址问题。Hobi等[3]应用重心法对吉林省物流配送中心选址问题进行了研究。丁浩等[4]通过对影响物流配送中心选址因素分析，确立了影响物流配送中心选址的主要因素和原则，并以获得最佳经济效益为目标，建立了物流配送中心选址模型；吕海峰等[5]基于网络分析方法对物流配送中心选址问题进行了研究，建立了配送中心选址的网络优化模型，并通过总费用最小化确定配送中心的数量、位置以及生产商与配送中心、配送中心与销售商之间的供需关系，即最优供货方案。选址模型认为可以考察一个连续空间内所有可能的点，待选区域是一个平面，可能的选址位置的数量是无限的,从中选择其中最优的一个，而且通常也可以对其进行相当有效的分析。因此距离选址模型实际上是一个最优化问题，可采用优化算法求解。

牛顿法主要利用Hessian矩阵提供的曲率信息，具有二次收敛性，是求解中小规模无约束最优化问题最有效的算法之一。然而，当第k个迭代点xk处的Hessian矩阵不正定时，不能保证算法产生的方向是目标函数f在xk处的下降方向。特别地，当Hessian矩阵奇异时，牛顿方向可能不存在，从而影响算法全局收敛性。Li等[6]研究了求解无约束凸规划问题的正则化牛顿法，并证明了算法的超线性收敛性/二次收敛性。在不假设Hessian矩阵正定的前提下得到了正则化牛顿的全局收敛性和二次收敛性，Han等[7]通过修正牛顿方向，给出了一种求解该病态问题的新的修正牛顿法。万中等[8]充分利用迭代点处目标函数的一阶、二阶信息，合适选取搜索方向，提出了一种精细修正牛顿法。有关求解退化问题的优化算法研究还可参看文献[9-11]等。

本文针对无约束优化问题，提出了一种牛顿法和梯度法的耦合算法。和传统牛顿-梯度法不同的地方在于, 该方法即使在目标函数的Hessian矩阵半正定时，也能充分利用迭代点处目标函数的二阶信息，合理选取迭代点处的搜索方向。数值实验表明该方法是有效的，且具有较好的计算效率。本文进一步将提出的算法应用于欧氏距离选址模型，通过实例分析证明提出的牛顿-梯度耦合算法可有效解决欧氏距离选址模型。

2 牛顿-梯度耦合算法

牛顿法的搜索方向是根据目标函数的负梯度方法和二阶偏导数矩阵来构造的，其迭代格式为：

其中f是目标函数，xk是当前迭代点，xk+1是下一步迭代点，Hk是xk点的Hessian矩阵。当Hk正定时，目标函数在xk附近邻域内是严格凸函数，牛顿法具有二次收敛性。然而当Hk是半正定时，目标函数在xk附近邻域内是凹函数，牛顿法可能失效。这时，可使用修正牛顿法或者转为梯度法求解。本文采用一种修正的矩阵取代Hk，使之正定。

牛顿法的Hk半正定时，其秩rank(Hk)＜n，其中n是求解问题的维数。此时，可以通过引入梯度法来使Hk的修正形式满秩。首先将牛顿-梯度法转化为如下形式：

其中I是单位矩阵。变换后，xk点的下降方向dk的求解方程组是一个超定方程组。因而，可以采用下述方法求解：

至此，可以描述本文牛顿-梯度耦合算法的计算步骤。

具体算法如下:

步骤1：(初始步)给定初始点x0，收敛精度ε＞0，设k=0。

步骤2：(计算步)计算函数在xk点的梯度和海森矩阵。

步骤4：(方向确定步)构造正定矩阵Ak，向量gk，其中

令dk=-A-k1gk，转入下一步。

步骤5：(更新步)令xk+1=xk+dk,k=k+1转步骤2。

本文选取文献[7]中的测试函数进行数值实验，比较本文算法和文献[7]中算法的数值效果。测试函数如下：

该函数可视为某个无约束优化问题目标函数的梯度函数。其真值为x*=(0,1)。若取初值为x0=(1,0), 原始牛顿法失效，其收敛点为(-1,2)。采用本文的算法，则有下面的计算结果（见表1）。文献[7]需要5步找到真值，收敛精度1.0e-10。而本文的方法仅需要2步，该对比表明了本文方法的优越性。

表1 本文耦合算法的计算结果

3 欧式距离选址模型求解

对于选址问题，目标函数一般是寻求总成本的最小化。在选址模型中，最基本的参数是各个节点之间的距离。当节点间的运输多为直线运输时，多用欧式距离选址模型。欧式距离可以用下面的公式表达。

其中(ai,bi)是第i个现有设施节点坐标，(xj,yj)是第j个新建设施节点坐标。

对于在计划区域内设置一个物流中心的简单情况，假设在计划区域内有m个现有设施节点，各点的需求运输量ω（ii=1,...,m），各自的坐标为(ai,bi)。需设置一个新的节点，该新建设施节点为(x1,x2)。第i个现有设施节点到新建设施节点的单位运输费率为ri。其欧氏距离选址问题的最优化模型的目标函数可以表达如下[12]：

其中λ是实际距离和欧式距离的转化系数。从上面可以看出，如果不考虑其它约束条件，欧式距离选址模型实际上就是一个无约束最优化问题。在该模型中，通常取初始迭代点为其几何重心，即：

如果视该初始点为物流中心的选取地方，则该方法就是重心法。重心法是一种模拟方法，该方法将物流系统的需求点和资源点都看作是分布在某一平面范围内的物流系统，各点的需求量和资源量分别看成是物体的重量，物流系统的重心作为物流系统的最佳设置点，从而利用重心点确定物流中心的位置。然而，重心法并不能准确地确定最佳物流中心的位置，因为这一方法将纵向和横向的距离视为相互独立的量，与实际不符合，因此只能作为一个参考解。一般情况下，可采用某种优化算法，通过选取该重心点为初始迭代点，可以较快地获得最优解。在此可采用本文提出的算法求解此类模型，具体实例如下：

某制造企业发现两个资源点所生产的产品都需要向3个需求点进行供应，而两个资源点所用运输工具的运输效率都很低，汽车空驶率很高。为了合理配置资源，制造企业决定在两个资源点和三个需求点之间建立一个配送中心，提高效率。已有设施的地理坐标如图1所示，根据搜集的数据(见表2)，用欧氏距离选址模型来确定配送中心的最佳位置，假设λ=1.5，取迭代精度ε=0.1。

图1 现有设施节点坐标

表2 现有设施已知条件

解：首先，将图1中各点坐标和表2中数据带入公式(8)，可得初始点为x0=(5.160，5.180)。然后，应用本文的算法求解，结果见表3，迭代2步后，可以得到最优解为x*=(4.910，5.058)，最小成本为32 137.7元。值得注意的是，若设置初始点为(1，0)，由于在计算过程中，Hessian矩阵出现近似奇异的情况，原始牛顿法失效，而本文的算法依然可以迭代到最优解。

表3 本文耦合算法的计算结果

4 结语

本文充分利用迭代点处目标函数的一阶、二阶导数信息，提出了一种求解退化无约束优化问题的牛顿法。数值实验表明该方法的正确性，和同类方法对比表明本文方法具有较好的数值实验效果。同时，将该方法应用于求解欧式距离选址模型，实例证明它在解决欧氏距离选址模型时是非常有效的。

[1]蔡临宁.物流系统规划—建模及实例分析[M].北京:机械工业出版社,2003.

[2]金鑫,王胜囡.交叉中值模型在物流设施选址中的应用研究[J].物流科技,2014,(4):98-99.

[3]Hobi A,Bihl T,Fellay B,et.al.Study on Logistics Center Site Selection of Jilin Province[J].Journal of Software,2012,7(8):35-39．

[4]丁浩,李电生.城市物流配送中心选址方法的研究[J].华中科技大学学报,2004,21(1):51-54．

[5]吕海峰,马维忠,王衍华.基于网络分析方法的物流配送中心选址的研究[J].运筹与管理,2004,13(6):81-85．

[6]Lid H,Fukushima M,Qi L,et.al.Regularized Newton Methods for Convex Minimization Problems with Singular Solutions[J]. Computational Optimization and Applications,2004,28:131-147.

[7]Han B,Zhang D,Liu J.A new class of methods for solving nonlinear equations[J].JournalofComputationaland Applied Mathematics,1994,51(1):107-111.

[8]万中,冯冬冬.无约束优化问题的精细修正牛顿算法[J].高校应用数学学报,2011,26(2):179-186.

[9]王现辉.拟牛顿法超线性收敛性定理[D].长沙:湖南大学, 2009.

[10]Yamashita N,Fukushima M.On the rate of convergence of the Levenberg-Marquardt method[J].Computing Supplementa, 2001,15:239-249.

[11]Li D,F ukushima M.Aglobally and supperlinearly convergent Gauss-Newton-based BFGS methods for symmetric nonlinear equation[J].SIAM Journal on Numerical Analysis,2000,37 (1):152-172.

[12]田森平,罗婷婷.梯度法在欧氏距离选址模型中的应用[J].工业工程,2006,9(3):112-115.

An Improved Newton Method and Its Application in Euclidean Distance Based Location Model

Duan Qiong1,Dai Jing1,Qiao Hui2
(1.School of Economics&Management,Kunming University of Science&Technology,Kunming 650093;
2.School of Mathematics&Information Science,Henan Polytechnic University,Jiaozuo 454003,China)

In this paper,we first proposed a Newton-gradient coupling algorithm for the degenerate problem which through a numerical example was shown to be valid and capable of yielding better outcome than the traditional method,then on such basis,further applied the algorithm to the Euclidean distance based location model,and again through an empirical analysis,demonstrated the effectiveness of the Newton-gradient coupling algorithm in this respect.

Newton method;gradient method;degenerate problem;Euclidean distance based location model还是供应链系统的设施选址决策，都受到外部因素和内部因素的影响。外部因素主要指政治和经济因素、基础设施以及环境、竞争对手情况等；而内因往往是最重要的，即设施的选址要符合企业的目标及发展战略。

F224;F252

A

1005-152X(2017)08-0079-04

2017-06-11

云南省科技厅重点项目(2016FA028)；云南省省级项目(人培)(KKSY201408093)

段琼（1982-），女，河南周口人，昆明理工大学经济与管理学院硕士研究生，主要研究方向：人力资源管理；戴璟（1979-），女，云南昆明人，博士，昆明理工大学经济与管理学院讲师，主要研究方向：公共卫生管理，物流管理。

doi∶10.3969/j.issn.1005-152X.2017.08.019