求解加權Euclidean單中心問題的SMO-型算法

叢 偉 杰

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

0 引 言

給定點集P={p1,p2,…,pm}?Rn和對應的正權重W=(w1,w2,…,wm}；加權Euclidean單中心(weighted Euclidean one-center,簡記為WEOC)問題就是尋找一個點c∈Rn,最小化P中各點到c加權Euclidean距離的最大值. 給定(P,W)的WEOC問題記為WEOC(P,W),可表示為

WEOC問題[1-3]是計算幾何中的經典問題,在現代工程學和數學領域應用廣泛,尤其在設施選址問題上[4-5]. 當WEOC問題中的所有權重wi=1時,WEOC問題即退化為最小閉包球(minimum enclosing ball,簡記為MEB)問題[6],即尋找一個半徑最小的球包含點集P中的所有點.

序列最小最優化(sequential minimal optimization,簡記為SMO)方法[7]是支持向量機中求解凸二次優化問題的主要工具,與一般傳統優化迭代方法不同,SMO方法在每次迭代過程中只需更新決策變量的兩個分量,節省了計算時間,能加速算法的執行. 本文首先定義了求解WEOC問題的兩個近似最優性條件,然后基于SMO方法的思想,提出一種求解WEOC問題的SMO-型算法. 該算法求解WEOC問題滿足第二個近似最優性條件的(1+ε)-近似解. 數值實驗結果驗證了算法的有效性.

1 優化公式及近似最優性條件

WEOC(P,W)問題可以轉化為如下優化問題:

(1)

其中c=(c1,c2,…,cn)T∈Rn和r∈R是原始變量. 文獻[3]通過平方問題(1)的約束并定義γ=r2,將問題(1)轉化為如下凸優化問題:

(2)

(3)

其中u=(u1,u2,…,um)T∈Rm是對偶變量. 由問題的KKT最優性條件[3]可得

(4)

其中(c*,r*)∈Rn×R和u*∈Rm分別為原規劃(1)和對偶規劃(3)的最優解. 因此,WEOC(P,W)問題能轉化為求解對偶規劃(3).

(5)

下面類似于MVAE問題的近似最優性條件[8],給出WEOC問題的兩個近似最優性條件定義.

定義1給定ε>0,如果

wi‖pi-c‖≤(1+ε)r,i=1,2,…,m,

(6)

定義2給定ε∈(0,1),如果式(6)成立,并且有

ui>0 ?wi‖pi-c‖≥(1-ε)r,i=1,2,…,m,

(7)

則稱對偶規劃(3)的可行解u滿足強ε-近似最優性條件.

由定義2可知,當ui>0時,有(1-ε)r≤wi‖pi-c‖≤(1+ε)r(i=1,2,…,m),表明對于充分小的ε,定義2是比定義1對式(5)更好的近似.

2 SMO-型算法

下面給出求解WEOC(P,W)問題的SMO-型算法.

算法1給定P={p1,p2,…,pm}?Rn,W={w1,w2,…,wm},ε>0.

4) 令

算法1中1)是簡單的初始化過程,與文獻[3]中算法5.1的初始化過程相同. 算法1與算法5.1[3]的主要不同在于主循環部分,在第k次迭代中,由2)和3)可得

wi+‖pi+-ck‖=(1+ε+)rk≤(1+εk)rk,wi-‖pi--ck‖=(1-ε-)rk≥(1-εk)rk,

表明每次迭代算法1總能得到對偶規劃(3)的一個可行解uk滿足強εk-近似最優性條件. 因此,當算法終止(εk≤ε)時,得到的可行解uk滿足強ε-近似最優性條件(6),(7),并且有

由WEOC(P,W)的(1+ε)-近似解定義知,算法1終止時,得到問題的一個(1+ε)-近似解為(ck,r(ck))∶=(ck,(1+εk)rk).

算法5.1[3]給出的可行解迭代更新公式為uk+1=(1-λk)uk+λkei+=uk+λk(ei+-uk)或uk+1=(1+λk)uk-λkei-=uk+λk(uk-ei-),其中ei表示第i個分量為1的單位向量. 它們使用了兩個不同的搜索方向dk∶=ei+-uk或uk-ei-,導致算法5.1[3]計算非常復雜的步長λk. 基于SMO方法的思想,每次迭代僅更新可行解的兩個分量,算法1中4)給出的可行解迭代更新公式為

uk+1=uk+λk(ei+-ei-),

(8)

其中搜索方向為dk∶=ei+-ei-,使得算法1能夠計算一個相對簡單的步長λk.

(9)

ck+1=(1-(σ+-σ-))ck+σ+pi+-σ-pi-.

(10)

對于任意的x,y,z∈Rm和σ1,σ2∈R ,易驗證下式成立:

下面計算算法1中的步長λk. 由前面的計算可得Φ(uk+1)=Φ(uk)+Δk(λk),其中

(12)

對式(12)中關于λ的函數Δk(λ)分別求一、 二階導數,得

3 數值實驗

為了驗證本文提出SMO-型算法的有效性,對于相同的數據集,在Matlab中同時執行文獻[3]中的算法5.1和本文的算法1. 實驗中用到的數據集是由函數randn(n,m)隨機產生的正態分布數據,對應的權重是由函數rand(1,m)隨機產生的均勻分布數據,其中(n,m)=(10,10 000)～(100,100 000). 對于每對固定的(n,m),隨機產生10組不同的數據執行算法,得到的結果以其算術平均值形式給出.

表1列出了當精度ε=10-7時,兩個算法執行的迭代次數和CPU時間的比較結果. 由表1可見: 算法1總比算法5.1[3]運行速度快,一般在迭代次數和CPU時間上比算法5.1減少41%～56%;對于n=100,m=100 000的大規模數據,算法1僅需要執行約90 s,表明算法1能有效求解高精度的大規模計算問題.

表1 算法5.1[3]和算法1在高精度ε=10-7下的數值結果比較Table 1 Comparisons of numerical results by virtue of algorithms 5.1[3] and 1 with ε=10-7

[1] Megiddo N. The Weighted Euclidean 1-Center Problem [J]. Mathematics of Operations Research,1983,8(4): 498-504.

[2] Megiddo N,Zemel E. AnO(nlogn) Randomizing Algorithm for the Weighted Euclidean 1-Center Problem [J]. Journal of Algorithms,1986,7(3): 358-368.

[3] Kumar P,Yildirim E A. An Algorithm and a Core Set Result for the Weighted Euclidean One-Center Problem [J]. Informs Journal on Computing,2009,21(4): 614-629.

[4] Drezner Z,Gavish B.ε-Approximations for Multidimensional Weighted Location Problems [J]. Operations Research,1985,33(4): 772-783.

[5] Drezner Z. The Weighted Minimax Location Problem with Set-up Costs and Extensions [J]. Operations Research,1991,25(1): 55-64.

[6] CONG Wei-jie,LIU Hong-wei. An SMO-Type Method for Solving the MEB Problem [J]. Journal of Northwest University: Natural Science Edition,2010,40(6): 965-969. (叢偉杰,劉紅衛. 求解MEB問題的一種SMO-型方法 [J]. 西北大學學報: 自然科學版,2010,40(6): 965-969.)

[7] Chen P H,Fan R E,Lin C J. A Study on SMO-Type Decomposition Methods for Support Vector Machines [J]. IEEE Transactions on Neural Networks,2006,17(4): 893-908.

[8] CONG Wei-jie,LIU Hong-wei. Linearly Convergent Algorithm for Solving the Minimum Volume Axis-Aligned Ellipsoid Problem [J]. Journal of Jilin University: Science Edition,2011,49(2): 173-178. (叢偉杰,劉紅衛. 求解最小體積軸向橢球問題的線性收斂算法 [J]. 吉林大學學報: 理學版,2011,49(2): 173-178.)