最速下降法的一次迭代收斂性的一點(diǎn)注記

邱松強(qiáng), 謝海燕

(1.中國(guó)礦業(yè)大學(xué) 數(shù)學(xué)學(xué)院,江蘇 徐州 221116; 2.江蘇師范大學(xué) 數(shù)學(xué)與統(tǒng)計(jì)學(xué)院,江蘇 徐州 221116)

0 引 言

本文考慮如下的嚴(yán)格凸二次規(guī)劃問(wèn)題

(1)

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

最速下降法是求解無(wú)約束優(yōu)化問(wèn)題的最為常見算法之一[1-3].這種算法及其改進(jìn)方法因?yàn)樵砗?jiǎn)單,較好的全局收斂性,計(jì)算量小,易于實(shí)現(xiàn)等特點(diǎn)而得到重視和應(yīng)用, 如文獻(xiàn)[4-7]等.特別值得一提的是近年來(lái)它們?cè)跈C(jī)器學(xué)習(xí)領(lǐng)域的應(yīng)用極為成功,如文獻(xiàn)[8-9]等.

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

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

本文進(jìn)一步討論了最速下降法的一次迭代收斂性,證明最速下降法在某初始點(diǎn)處具有一次迭代收斂性等價(jià)于它從該點(diǎn)出發(fā)可經(jīng)有限次迭代后到達(dá)問(wèn)題點(diǎn)最優(yōu)解.這說(shuō)明在求解 (1) 時(shí),最速下降法或者一次迭代終止,或者無(wú)法在有限次迭代內(nèi)達(dá)到精確解.本文的工作豐富了最速下降法的理論,有助于更好地認(rèn)識(shí)和理解該算法.

1 特征值與特征向量

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

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

性質(zhì)1矩陣A∈n×n的屬于不同特征值的特征向量線性無(wú)關(guān).

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

性質(zhì)2設(shè)G∈n×n是對(duì)稱矩陣,則G的每一個(gè)特征值都是實(shí)數(shù).

性質(zhì)3實(shí)對(duì)稱矩陣G的屬于不同特征值的特征向量是正交的.

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

性質(zhì)5設(shè)G∈n×n是對(duì)稱矩陣,則G有n個(gè)線性無(wú)關(guān)的特征向量.

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

2 最速下降法及其基本性質(zhì)

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

算法1最速下降法

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

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

步3 令xk+1=xk+αkdk,k=k+1,轉(zhuǎn)步1.

根據(jù)步2最優(yōu)步長(zhǎng)αk的計(jì)算公式可知

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

(2)

從而有

(3)

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

定理2[2]設(shè){xk}是最速下降法應(yīng)用于嚴(yán)格凸二次規(guī)劃問(wèn)題 (1) 時(shí)產(chǎn)生的點(diǎn)列,則有

接下來(lái)的定理說(shuō)明當(dāng)初始點(diǎn)滿足一定條件時(shí),最速下降法只需一次迭代即可得到 (1) 的精確解.

3 最速下降法在有限步內(nèi)得到解的充要條件

定理3是一個(gè)比較常見的性質(zhì),經(jīng)常出現(xiàn)在一些最優(yōu)化教材的習(xí)題中.實(shí)際上,可以對(duì)該定理做一些擴(kuò)展,考慮算法在有限次,而非僅一次迭代后得到問(wèn)題的解.

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

先考慮第一次迭代.設(shè)最優(yōu)步長(zhǎng)為α0,則由(3)知,α0≥1/λl>0.因

故

所以有

因此對(duì)任意1≤i≤l, 有

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

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

4 結(jié) 論

本文以矩陣特征值、特征向量及其基本性質(zhì)為基礎(chǔ),討論了最速下降法具備一次迭代收斂性,證明求解嚴(yán)格凸二次規(guī)劃時(shí),最速下降法的一次迭代收斂性等價(jià)于有限次迭代收斂性.本文的結(jié)果豐富了最速下降法的理論,對(duì)于認(rèn)識(shí)、理解最速下降法有一定的理論價(jià)值,對(duì)最速下降法或梯度類算法的教學(xué)有一定的啟發(fā)意義.同時(shí),本文的結(jié)果對(duì)如何提高最速下降法的效率具有一定的啟發(fā)性,這方面的工作正在進(jìn)行之中.

致謝作者非常感謝相關(guān)文獻(xiàn)對(duì)本文的啟發(fā)以及審稿專家提出的寶貴意見.