最速下降法的一次迭代收斂性的一點注記

邱松強, 謝海燕

(1.中國礦業大學 數學學院,江蘇 徐州 221116; 2.江蘇師范大學 數學與統計學院,江蘇 徐州 221116)

0 引 言

本文考慮如下的嚴格凸二次規劃問題

(1)

其中G∈n×n是正定矩陣,b∈n,c∈.

最速下降法是求解無約束優化問題的最為常見算法之一[1-3].這種算法及其改進方法因為原理簡單,較好的全局收斂性,計算量小,易于實現等特點而得到重視和應用, 如文獻[4-7]等.特別值得一提的是近年來它們在機器學習領域的應用極為成功,如文獻[8-9]等.

但是最速下降法的缺點和它的優點一樣明顯:收斂速度較慢. 在較為一般的條件下,它具有線性收斂速度,并且迭代過程中會產生著名的“鋸齒 (Zigzag) 現象”[1-3]. 而相比之下,共軛梯度法、擬牛頓法等算法有更快的收斂速度[1-3,10],特別地,它們都具有二次終止性,即當算法被應用于嚴格凸二次規劃 (1) 時,從任何初始點出發,最多經過n次迭代就可以得到問題的精確解[1-2]. 這樣的對比使得學生容易把最速下降法當成一種十分“低效”的算法,并因此忽視其價值.

最速下降法并不具備二次終止性,但是當初始點x0滿足一定條件時,算法將在一次迭代后得到 (1)的精確解[11].本文中,稱一個算法在點x0處具有一次迭代終止性,如果以該點為初始點,算法將在一次迭代后得到 (1) 的精確解.按定義,二次終止性蘊含了一次迭代收斂性,反之不然.

本文進一步討論了最速下降法的一次迭代收斂性,證明最速下降法在某初始點處具有一次迭代收斂性等價于它從該點出發可經有限次迭代后到達問題點最優解.這說明在求解 (1) 時,最速下降法或者一次迭代終止,或者無法在有限次迭代內達到精確解.本文的工作豐富了最速下降法的理論,有助于更好地認識和理解該算法.

1 特征值與特征向量

特征值和特征向量是線性代數中最具特色的內容之一.關于這部分的詳細論述可參考線性代數教材或相關文獻[12-14].這里只介紹其定義和幾個在本文后續的討論中將會被用到的性質.

定義1設A∈n×n,如果存在數λ∈和非零向量α∈n,使得Aα=λα,則稱λ為A的特征值,稱α為A的屬于特征值λ的特征向量.

性質1矩陣A∈n×n的屬于不同特征值的特征向量線性無關.

推論1設α1,α2∈n是方陣A的兩個屬于不同特征值的特征向量,則α1+α2必不是A的特征向量.

性質2設G∈n×n是對稱矩陣,則G的每一個特征值都是實數.

性質3實對稱矩陣G的屬于不同特征值的特征向量是正交的.

性質4若G∈n×n是對稱正定矩陣, 則G的特征值均大于零.

性質5設G∈n×n是對稱矩陣,則G有n個線性無關的特征向量.

推論2設G∈n×n是對稱矩陣,則對任意w∈n,存在G的屬于不同特征值的特征向量v1,v2,…,vl,(l≤n),使得w=v1+v2+…+vl.

2 最速下降法及其基本性質

在任意x∈n處,若梯度?f(x)≠0,則沿負梯度方向函數值下降最快,因此負梯度方向常被稱為最速下降方向.1847年,Cauchy提出了一個基于最速下降方向的算法,即著名的最速下降法.

算法1最速下降法

步0 給定控制誤差ε>0.取初始點x0.令k=0;

步1 計算?fk=?f(xk).若‖?fk‖≤ε,則令x*=xk,算法終止;

步3 令xk+1=xk+αkdk,k=k+1,轉步1.

根據步2最優步長αk的計算公式可知

?f(xk-αk?f(xk))T?f(xk)=0.

(2)

從而有

(3)

以下定理給出了最速下降法的收斂速度.

定理2[2]設{xk}是最速下降法應用于嚴格凸二次規劃問題 (1) 時產生的點列,則有

接下來的定理說明當初始點滿足一定條件時,最速下降法只需一次迭代即可得到 (1) 的精確解.

3 最速下降法在有限步內得到解的充要條件

定理3是一個比較常見的性質,經常出現在一些最優化教材的習題中.實際上,可以對該定理做一些擴展,考慮算法在有限次,而非僅一次迭代后得到問題的解.

證由推論2,向量w可以表示成為G的幾個屬于不同特征值的特征向量之和,即存在分別屬于特征值0<λ1<λ2<…<λl的特征向量v1,v2,…,vl, 使得w=v1+v2+…+vl.由于w不是G的特征向量故而l≥2.

先考慮第一次迭代.設最優步長為α0,則由(3)知,α0≥1/λl>0.因

故

所以有

因此對任意1≤i≤l, 有

特別地,由λ1<λ2<…<λl知

推論4設用最速下降法求解(1).從初始點x0出發,算法能經有限次迭代得到解的充要條件是算法經一次迭代得到解.

4 結 論

本文以矩陣特征值、特征向量及其基本性質為基礎,討論了最速下降法具備一次迭代收斂性,證明求解嚴格凸二次規劃時,最速下降法的一次迭代收斂性等價于有限次迭代收斂性.本文的結果豐富了最速下降法的理論,對于認識、理解最速下降法有一定的理論價值,對最速下降法或梯度類算法的教學有一定的啟發意義.同時,本文的結果對如何提高最速下降法的效率具有一定的啟發性,這方面的工作正在進行之中.

致謝作者非常感謝相關文獻對本文的啟發以及審稿專家提出的寶貴意見.