求解加權最小閉包球問題的列生成算法

叢偉杰, 孫 繪

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

0 引 言

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

(1)

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

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

(2)

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

(3)

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

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

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

1.1 SMO-型算法

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

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

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

3) 更新可行解： 令

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

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

(4)

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

1.2 算法收斂性分析

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

(5)

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

其中:

(6)

根據文獻[8]中強ε-近似最優性條件的定義可得

表明

(7)

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

于是有

(8)

由此可得以下結論：

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

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

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

其中

(10)

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

于是有

(11)

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

(12)

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

(13)

(14)

于是可構造不等式:

再結合式(14)可得

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

2 列生成算法

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

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

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

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

3 數值實驗

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

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

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

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