一種改進的牛頓法及其在歐式距離選址模型中的應用

段 瓊，戴 璟，喬 慧

（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