叢偉杰, 孫 繪

(西安郵電大學(xué) 理學(xué)院, 西安 710121)

0 引 言

若給定任意點的集合P={p1,p2,…,pm}?n, 則最小閉包球(minimum enclosing ball, MEB)問題為尋找一個半徑最小的球, 使其包含P中的所有點. MEB問題可寫為如下優(yōu)化問題:

(1)

其中: ‖·‖為Euclid距離;c=(c1,c2,…,cn)T∈n和r∈為決策變量. MEB問題在計算幾何[1-2]和數(shù)據(jù)挖掘[3-5]等領(lǐng)域應(yīng)用廣泛.

在幾何中, 加權(quán)最小閉包球(weighted minimum enclosing ball, WMEB)可視為在MEB的基礎(chǔ)上, 進一步考慮集合P中各點的重要程度不同而對其賦權(quán). 不失一般性, 設(shè)集合P中各點對應(yīng)的權(quán)重為W={w1,w2,…,wm},wi∈(0,1]. 于是, WMEB問題可類似寫為如下優(yōu)化問題:

(2)

在代數(shù)中, WMEB問題也稱為加權(quán)Euclid單中心(weighted Euclidean one-center, WEOC)問題[6-8]. 如問題(2)所述, WEOC問題為尋找一個中心c∈n, 使得P中各點到中心c的加權(quán)Euclid距離的最大值達到最小. 文獻[7]將問題(2)轉(zhuǎn)化為凸優(yōu)化問題, 并給出其對偶規(guī)劃:

(3)

其中u=(u1,u2,…,um)T∈m為Lagrange對偶變量. 因此, 求解WEOC問題轉(zhuǎn)化為求解對偶問題(3). WEOC問題在圖論的設(shè)施選址中應(yīng)用廣泛, 為使WEOC問題像MEB問題一樣應(yīng)用于數(shù)據(jù)挖掘領(lǐng)域, 本文從幾何的角度, 即從上述WEOC問題和MEB問題的關(guān)系上, 將WEOC問題重新定義為WMEB問題. 顯然, 當WMEB問題中的全部權(quán)重wi=1時, WMEB問題即退化為MEB問題. 因此, WMEB問題可視為MEB問題的更一般情形.

本文首先在文獻[8]的基礎(chǔ)上, 結(jié)合文獻[9]中關(guān)于收斂性分析的方法, 建立針對求解WMEB問題的SMO-型算法的線性收斂性. 其次, 為進一步有效提高求解大規(guī)模數(shù)據(jù)集上WMEB問題的計算效率, 將文獻[10]中有效求解MEB問題的列生成方法應(yīng)用于WMEB問題中, 給出求解WMEB問題的列生成算法. 數(shù)值實驗結(jié)果驗證了本文算法的有效性.

1 SMO-型算法的收斂性分析

1.1 SMO-型算法

算法1[8]輸入點集P={p1,p2,…,pm}?n及對應(yīng)的權(quán)重W={w1,w2,…,wm},wi∈(0,1], 精度參數(shù)ε>0.

1) 初始化： 執(zhí)行文獻[6]中初始近似算法, 得初始可行解u0∈m, 令構(gòu)造并置k=0；

如果εk≤ε, 則算法終止, 同時輸出uk,ck,rk； 否則, 轉(zhuǎn)3)；

3) 更新可行解： 令

由文獻[8]可知, 當算法1終止時, 可得WMEB問題的一個(1+ε)-近似解.

引理1算法1每次迭代總使對偶問題(3)的目標函數(shù)值至少有如下增加:

(4)

證明: 由文獻[8]中式(12), 可得

1.2 算法收斂性分析

用文獻[9]方法建立算法1的線性收斂性. 先引入擾動向量z∈m, 并令給出如下與問題(2)等價的凸優(yōu)化問題的一個擾動：

(5)

再給定滿足強εk-近似最優(yōu)性條件[8]的問題(3)的可行解uk, 并定義zk∶=z(uk,εk)∈m為

其中:

(6)

根據(jù)文獻[8]中強ε-近似最優(yōu)性條件的定義可得

表明

(7)

根據(jù)問題(3)和式(6)可得

于是有

(8)

由此可得以下結(jié)論：

引理2若uk滿足強εk-近似最優(yōu)性條件[8], 則(ck,rk)∈m×為問題(5)的最優(yōu)解.

類似文獻[9], 令φ(z(uk,εk))表示問題(5)的最優(yōu)目標值函數(shù). 由引理2和式(8)可得

設(shè)點集P中任意兩點間的最大距離, 即點集P的直徑為Δ. 對于MEB問題, 由文獻[1]顯然有Δ/2≤rMEB≤Δ. 由問題(2)與問題(1)的關(guān)系, 易得rWMEB≤rMEB≤Δ,rMEB≤rWMEB/wmin, 其中rMEB和rWMEB分別表示MEB問題和WMEB問題的最優(yōu)半徑,wmin為權(quán)重wi∈(0,1](i=1,2,…,m)中的最小值. 于是, 對于WMEB問題, 總有

其中

(10)

由式(7)和式(10)可得

于是有

(11)

結(jié)合式(11)及文獻[1]可知, 存在最優(yōu)解u*及一個Lipschitz常數(shù)L, 使得

(12)

將式(11),(12)代入式(9)并化簡得

(13)

(14)

于是可構(gòu)造不等式:

再結(jié)合式(14)可得

從而建立了SMO-型算法的線性收斂性. 由式(15)可見, 所建立的WMEB問題的線性收斂性與給定點集的權(quán)重、 大小和直徑有關(guān), 因此是局部線性收斂的.

2 列生成算法

列生成算法[10-11]是求解約束條件數(shù)遠少于變量個數(shù)的大規(guī)模線性規(guī)劃的有效算法. 文獻[10]在二階錐規(guī)劃的基礎(chǔ)上, 結(jié)合列生成的思想給出了有效求解MEB問題的列生成算法. 本文在算法1的基礎(chǔ)上, 結(jié)合列生成的思想給出求解大規(guī)模數(shù)據(jù)集上WMEB問題的列生成算法. 算法思想是每次迭代計算與當前球心加權(quán)距離最遠的點列, 將其加入到核心集中生成新的子集, 再調(diào)用SMO-型算法求解, 直到迭代終止. 下面給出求解WMEB問題的列生成算法.

算法2輸入點集P={p1,p2,…,pm}?n及對應(yīng)的權(quán)重W={w1,w2,…,wm},wi∈(0,1], 精度參數(shù)ε> 0.

1) 執(zhí)行文獻[6]中初始近似算法, 得初始核心集X0={pj,pj*}和初始可行解u0∈m, 令構(gòu)造并置k=0；

3) 更新核心集Xk+1=Xk∪{pi+}, 置k=k+1, 調(diào)用算法1計算WMEB(Xk)的一個(1+ε)-近似解(ck,rk), 轉(zhuǎn)2).

3 數(shù)值實驗

為驗證算法2在求解大規(guī)模數(shù)據(jù)集時的有效性, 在高精度ε=10-7下, 在MATLAB中同時執(zhí)行文獻[7]中算法5.1、 算法1和算法2. 實驗中使用的數(shù)據(jù)集大小列于表1, 其生成方法同文獻[8]. 除與文獻[8]中相同的前五組數(shù)據(jù)集外, 還增加了后兩組更大規(guī)模的數(shù)據(jù)集. 實驗所用計算機配置為Inter Core i7 4.2 GHz處理器, 16 GB內(nèi)存.

表1列出了文獻[7]中算法5.1、 算法1和算法2的迭代次數(shù)以及CPU執(zhí)行時間數(shù)值結(jié)果的比較. 由表1可見, 本文算法2與文獻[7]中算法5.1及算法1相比運行速度有明顯提升, 尤其是隨著數(shù)據(jù)集規(guī)模的增大效果更顯著. 由表1中不同算法的執(zhí)行時間可見, 算法2比算法1在計算效率上提高了3.6～7.5倍, 尤其對于提速達7.5倍的n=100,m=1 000 000大規(guī)模數(shù)據(jù)集, 算法2平均只需執(zhí)行約2.5 min, 表明了算法2使用的列生成技術(shù)在處理高精度、 大規(guī)模數(shù)據(jù)集時的優(yōu)良性能. 由表1中迭代次數(shù)的數(shù)值結(jié)果可見, 列生成技術(shù)在處理大規(guī)模數(shù)據(jù)集上的WMEB問題時效果較好. 算法2每次迭代調(diào)用的SMO-型算法也具有良好的收斂性, 從而使列生成技術(shù)能更好地發(fā)揮其性能.

表1 算法5.1[7]、 算法1和算法2在高精度ε=10-7下的數(shù)值結(jié)果比較Table 1 Comparison of numerical results for algorithm 5.1[7], algorithm 1 and algorithm 2 under high precision ε=10-7

綜上所述, 本文在建立WMEB問題SMO-型算法線性收斂性的基礎(chǔ)上, 使用列生成技術(shù)處理大規(guī)模數(shù)據(jù)集上的計算問題. 數(shù)值實驗結(jié)果表明了列生成算法在處理高精度、 大規(guī)模數(shù)據(jù)集上WMEB問題的優(yōu)越性.