Gilbert算法研究及其改進*

汪衛兵，劉秉瀚

（福州大學 數學與計算機科學學院，福建 福州350108）

Gilbert算法[1]是一種求解最接近點對算法，即求解凸包外指定點到一群點集組成的凸包的距離，廣泛應用于機器人領域。Gilbert算法是一種迭代算法，屬于梯度下降算法，具有很好的全局收斂性，易被計算機實現，而且適用幾何的觀點來分析。但是，Gilbert算法的缺點也很明顯，特別是接近最優解時收斂過慢。

針對Gilbert算法的改進算法有MDM算法[2]、NPA算法[3]以及CHANG L[4]等人提出的改進算法。MDM算法利用具有消極影響的訓練樣本點改進更新策略，在迭代過程中，一旦發現迭代點的組合中具有消極影響的訓練樣本點，就直接在迭代點的線性組合中刪除或是降低該點對目標函數的影響，并同時使得目標函數邊緣下降。MDM算法解決了Gilbert算法接近最優解時收斂過慢的問題，但仍需要多次迭代完成計算。NPA算法結合了Gilbert算法和MDM算法的特點，選取三角形區域作為迭代點的搜索范圍，擴大了迭代點的搜索范圍，實驗結果顯示，它比MDM算法收斂更快，但NPA算法仍存在計算量很大的不足。參考文獻[4]的研究證明了最接近點對問題的最優解一定出現在凸包頂點中兩點組成的邊上或者幾點確定的面上，根據此結論，最優解一定落在凸包邊界上。CHANG L等人據此提出了一種改進的Gilbert算法(下文簡稱CQW)，當算法迭代到一定次數時，如果發現算法重復選取幾個凸包頂點作為算法迭代選取的頂點，就直接計算凸包外指定點到這幾點組成的平面或兩點組成的線段的距離，它加快了Gilbert的收斂，但需要人工設置迭代次數，迭代次數的選取是一個難點。

針對上述算法計算量大的問題，本文分析了Gilbert收斂慢的原因，當新的迭代點越來越趨近于最優解時，它一直在最優解附近徘徊，不能快速到達凸包邊界。本文通過實驗發現，在迭代的過程中，一旦迭代點出現在凸包的邊界上，Gilbert算法會快速收斂。據此，本文在Gilbert算法的基礎上提出一種新的迭代策略，迭代過程中將Gilbert算法原有的梯度方向上的候選點與凸包邊界上的候選點進行比對，選取離凸包外指定點更近的候選點作為新的迭代點，這樣的迭代機制一有機會即將迭代點拉到凸包的邊界上，有效避免了在凸包內部最優解附近不停徘徊迭代的情況發生，減少迭代次數，加快收斂速度。實驗結果表明，本文改進后的算法與NPA算法相比，計算量小，問題的求解速度更快，與CQW算法相比，不需要人工設置迭代次數，更容易求出最優解。

1 Gilbert算法

1.1 最接近點對問題

最接近點對問題（NPP問題）的目標就是找到兩個凸包間的最接近點對，即：

Z=U-V表示凸包U和V的明可夫斯基差，凸包Z有s1×s2個頂點，最接近點對問題轉化為在凸包Z上找到離凸包外指定點（為方便闡述，凸包外指定點默認為坐標軸原點）最近的點（MNP問題），即：

1.2 算法步驟

Gilbert算法原本解決的是MNP問題，在凸包U上找到離原點最近的點。下面給出一些相關的數學定義[5]：

定義1：設U為Rm的一個凸包，y∈U，稱

為U上的支持函數。表示求向量x和向量y的內積運算。

定義2：設S(y)是Rm上的一個函數，稱

為Rm上的關聯函數。S(y)為U的一個頂點。

Gilbert算法具體步驟如下：

(1)初始化。取t=1，在凸包U上任取一點z1，z1∈U，設定停止精度ε。

(2)按式(7)進行梯度下降局部優化迭代更新。

其中zt+1為zt和S(-zt)組成的線段上離原點最近的點，更新力度：

(3)如果滿足條件||zt||2-||zt+1||2<ε，則算法停止，否則令t=t+1，轉步驟(2)。

Gilbert算法首先任取一個樣本點z1，通過式(6)確定與z1反向量內積最大的凸包頂點S(-z1)，判斷S(-z1)是否與z1靠得很近，如果是，則停止；否則，按式(7)進行局部更新，即在S(-z1)和z1連線上求取離原點最近的點(這個更新操作可以保證zt+1的范數嚴格小于zt的范數)，如此反復，最終獲得凸集U的最小范數點。

1.3 Gilbert算法的收斂問題

如圖1所示，三角形ABC為一個平面凸包，O為原點（即凸包外指定點），選取P1作為算法的初始點，迭代點依次沿著P2、P3、P4更新，最終到達離O點的最近點Pn。在Pi(i=1，2，…，n)迭代的過程中，與向量Pi內積最小的頂點一直是B點或者C點，最終問題的解落在線段BC上。Gilbert算法計算O點到三角形ABC的求解迭代過程如圖2所示，Gilbert算法迭代到一定次數后，迭代點一直在最優解附近徘徊，算法收斂速度非常慢，當設定停止精度ε=10-6時，算法迭代了489次。

圖3 迭代搜索范圍

算法迭代搜索范圍如圖3所示，AA′和CC′相交于P1點，P1D平行于AC，OE與BC垂直。在第 一次迭代過程中，線段P1C是Gilbert算法迭代點的搜索范圍，Gilbert算法只計算與向量P1內積最小的頂點C，而MDM算法還計算了與向量P1內積最大的頂點A，P1D平行于AC，讓P1點沿著P1D方向偏移，線段P1D是MDM算法迭代點的搜索范圍。NPA算法結合了Gilbert算法和MDM算法的優點，考慮了4種搜索范圍：(1)三角形P1DC；(2)三角形P1A′C；(3)四邊形ACA′C′；(4)三角形ABC。這4種情況都包含了Gilbert算法和MDM算法的搜索范圍，NPA算法認為(1)和(2)兩種情況優于Gilbert算法和MDM算法，(3)和(4)兩種情況搜索范圍太廣，比MDM算法的效果差。第(1)種情況收斂速度比MDM算法快，第(2)種情況比第(1)種情況收斂速度更快。因此，NPA算法選取三角形P1A′C作為迭代點的搜索區域，擴大了迭代點的搜索范圍，有利于找到更優的迭代點，同時加快了收斂速度。CQW算法依然采用Gilbert算法的更新策略，當迭代K次(K的選取是人為設置的）后,發現算法重復選取幾個凸包頂點作為算法迭代時選取的頂點，就直接計算O點到這幾點組成的平面或兩點組成的線段的距離，減少了迭代次數。

1.4 Gilbert算法收斂慢的原因分析

如圖4所示，矩形ABCD是一個平面凸包，O為原點。利用Gilbert算法求解點O到凸包的最短距離時，選取初始點P1進行第一次迭代后，與P1點內積最小的頂點為D點，然后求出O點到線段P1D上的最近點P2，并將其作為新的迭代點。圖4中若∠P1DO>90°，則P2點就是D點，而D屬于凸包的邊界，算法很快收斂，找到最優解。若∠P1DO<90°(如圖5所示)，則迭代點P2出現在凸包的內部，Gilbert算法會在凸包內部不停地選取迭代點，很難到達凸包的邊界，算法收斂速度非常緩慢。

圖4 迭代點出現在凸包邊界

圖5 迭代點在凸包內部

凸包邊界由邊和面組成，根據CHANG L[4]等人的結論，最優解一定落在凸包邊界上。本文通過多次實驗發現，算法迭代點到達凸包邊界之后就會快速收斂。因此，本文考慮每次選取迭代點時都與離O點最近的凸包邊界線段上的點作比較，盡可能將迭代點拉至凸包邊界上，這樣可避免算法在凸包內部最優解附近徘徊迭代，以此來改進Gilbert算法的收斂速度。

2 本文方法

2.1 算法思路

本文基于1.4節的分析，在算法第一次迭代確定頂點D之后(見圖5)，考慮包含D的凸包邊界線段AD和CD，選擇離O點最近的邊界線段AD，同時將P1D和AD這兩條邊作為迭代點的搜索范圍，分別計算O點到這兩條線段的最近點，選取兩者中較近的點作為新的迭代點：如果O點到AD邊更近，則選取O點到AD邊上最近點作為新的迭代點；如果O點到Gilbert算法原來的迭代點更近，則選取原來的迭代點作為新的迭代點。這樣每次迭代都有機會將迭代點拉到凸包邊界，可避免Gilbert算法不停地在凸包內部最優解附近選取迭代點，使得算法快速收斂。

2.2 算法步驟

本文改進后的算法步驟如下：

(1)初始化。取t=1，在凸包U上任取初始迭代點z1，z1∈U，設定停止精度ε。

(2)按式(7)得到迭代候選點z′。如果z′∈X（X為凸包U的頂點集合），則zt+1=z′，令t=t+1，轉步驟(3)繼續執行；如果z′?X，按式(8)求S(-z′)和S(-zt)組成的線段上離O點最近的點z″。

令t=t+1，轉步驟(3)繼續執行。

(3)檢驗停止條件。如果滿足條件||zt||2-||zt+1||2<ε，則算法停止，否則轉步驟(2)。

如圖6所示，z1是算法選取的初始點，在迭代過程中，先計算出與向量z1內積最小的頂點C，即S(-z1)，計算O到線段z1C的最近點z′。

圖6 本文算法迭代過程

如果z′∈X，則表示新的迭代點是凸包的頂點，按照Gilbert原算法執行迭代。如果z′?X，計算與向量z′內積最小的頂點B，即S(-z′)，計算O到BC的最近點z″。

比較z′和z″，取兩個距離中較小的垂足作為新一輪的迭代點。這樣可以保證每次選取的迭代點到O點的距離小于或者等于Gilbert算法中的迭代點到O點的距離，Gilbert算法已被證明是收斂的，這樣可以保證本文算法的收斂性。

本文算法每次選取迭代點時都與離O點近的邊界線段上的點作比較，有效避免了在凸包內部最優解附近不停地選取迭代點這種情況的發生，可以減少算法的迭代次數，加快收斂速度，提高計算效率。

3 實驗結果及分析

為了證明本文算法迭代策略的有效性，將本文算法與CQW算法、NPA算法進行實驗對比。設X=100×rand(50，3)，這是一個50乘以3的隨機數矩陣，它表示50個點，每個點的各個坐標值均介于0～100，U是由這50個頂點構成的凸包，利用上述3種算法求解坐標軸原點O到凸包的最短距離，設置算法停止精度為10-10，由于精度較高，Gilbert算法很難求出最優解，CQW算法需要人為設定迭代次數，這里設定為100次，3種算法執行時間和迭代次數的比對結果如表1所示。求解的最終結果均為32.813 134 341 830 660。

表1 實驗結果比對

實驗證明，本文算法與CQW算法相比，減少了迭代次數，加快了收斂速度；與NPA算法相比，提高了計算效率和計算速度。

本文針對Gilbert算法的缺點對其進行了改進，解決了Gilbert算法收斂過慢的問題，可以非常高效地求解MNP問題，改進后的Gilbert算法與Gilbert算法一樣，可用于NPP問題，將具有更強的普適性。實驗證明，本算法與其他算法相比具有以下優點：(1)算法的迭代次數不需要人為控制，依然可以快速收斂；(2)算法的執行速度較快，最優解的搜索范圍比NPA算法更優；(3)算法非常有效地避免了迭代點在凸包內部不停迭代的情況。改進后的Gilbert算法可以用于支持向量機的數據分類、碰撞檢測、機器人路徑規劃等領域。同時，它可以用作支持向量機的訓練算法，這是下一步將要展開的工作。

[1]GILBERT E G.An iterative procedure for computing the minimum of a quadratic form on a convex set[J].SIAM Journal of Control，1966，4(1)：61-79.

[2]MITCHELL B F，DEM'YANOV V F，MALOZEMOV V N.Finding the point of a polyhedron closest to the origin[J].SIAM J.Contr.，1974，12：19-26.

[3]KEERTHI S S，SHEVADE S K，BHATTACHARYYA C，et al.A fast iterative nearest point algorithm for support vector machine classifier design[J].IEEE-NN，2000，11(1)：124.

[4]CHANG L，QIAO H，WAN A，et al.An improved Gilbert algorithm with rapid convergence[C].Proceedings of the IEEE/RSJ International Conference on Intelligent Robots and Systems，Beijing：2006：3861-3866.

[5]周志華.機器學習及其應用2007[M].北京：清華大學出版社，2007：62-63.