一種改進(jìn)的自適應(yīng)信賴域算法

胡夢(mèng)英

北京郵電大學(xué)理學(xué)院

一種改進(jìn)的自適應(yīng)信賴域算法

胡夢(mèng)英

北京郵電大學(xué)理學(xué)院

胡夢(mèng)英，女，碩士在讀，北京郵電大學(xué)理學(xué)院，主要研究方向?yàn)樽顑?yōu)化算法。

考慮無(wú)約束極小化問(wèn)題

其中f:Rn→R 二次連續(xù)可微。

求解上述無(wú)約束問(wèn)題主要有信賴域法和線搜索法。線性搜索先確定方向再確定步長(zhǎng)，信賴域法則是先確定步長(zhǎng)再確定方向。信賴域方法的主要思想是圍繞當(dāng)前迭代點(diǎn)xk定義一個(gè)區(qū)域，即信賴域，使二次模型在信賴域內(nèi)能充分近似目標(biāo)函數(shù)，之后求解信賴域子問(wèn)題得到試探步長(zhǎng)，然后用某一評(píng)價(jià)函數(shù)來(lái)決定是否接受該試探步長(zhǎng)以及決定下一次迭代的信賴域。信賴域法具有很強(qiáng)的全局收斂性，但是算法效率會(huì)受到子問(wèn)題中信賴域半徑大小的影響。

對(duì)于無(wú)約束優(yōu)化問(wèn)題的信賴域算法，子問(wèn)題中二次模型的信賴域半徑大小的選擇是關(guān)鍵。本文的改進(jìn)自適應(yīng)信賴域算法，利用BB算法得到的步長(zhǎng)作為子問(wèn)題的信賴域半徑，隨著迭代的進(jìn)行自動(dòng)調(diào)節(jié)信賴域半徑，提高運(yùn)算效率。

自適應(yīng)信賴域算法

信賴域半徑大小的選擇是影響每一步迭代效率的關(guān)鍵。如果信賴域太小，則算法就可能得不到目標(biāo)函數(shù)的最優(yōu)點(diǎn)，影響迭代速度。反之如果信賴域太大，則二次模型與目標(biāo)函數(shù)近似程度不高，因而不得不減少信賴域并重新計(jì)算。自適應(yīng)信賴域算法中信賴域半徑隨每一次迭代的進(jìn)行而自動(dòng)改變，是對(duì)傳統(tǒng)信賴域算法的一個(gè)改進(jìn)。

自適應(yīng)信賴域法的信賴域子問(wèn)題：

BB算法

BB算法是Barzilai和Borwein提出的Two－Point Step Size Gradient Methods。BB算法的基本思路是用當(dāng)前迭代點(diǎn)以及前一點(diǎn)的信息來(lái)確定步長(zhǎng)因子。迭代公式可以看成是

因此計(jì)算得出，

改進(jìn)的自適應(yīng)信賴域算法

改進(jìn)思路

自適應(yīng)信賴域算法中信賴域半徑自動(dòng)調(diào)節(jié)，本文提出的新算法利用BB算法得到的步長(zhǎng)的倍數(shù)作為信賴域子問(wèn)題的信賴域半徑，這其實(shí)是一種自適應(yīng)信賴域算法。

新得到的信賴域的子問(wèn)題為：

表1　三種算法的運(yùn)行結(jié)果

算法步驟

Step1 給定初始點(diǎn)x0，初始信賴域半徑α0，給定θ的值，參數(shù)0<μ<η<1，置k=1。

Step2 計(jì)算gk，若則停止，否則轉(zhuǎn)Step3。

Step3 求解子問(wèn)題（3.1），得到近似解dk。

Step6 令k=k+1，返回Step2。

數(shù)值實(shí)驗(yàn)

本次數(shù)值實(shí)驗(yàn)，我們選用的編程環(huán)境為Mathematics8.0。用Mathematics語(yǔ)言分別編寫了傳統(tǒng)信賴域算法、自適應(yīng)信賴域算法和改進(jìn)自適應(yīng)信賴域算法的算法程序。

選用的測(cè)試函數(shù)

測(cè)試算法

1.傳統(tǒng)信賴域算法

傳統(tǒng)信賴域算法的信賴域子問(wèn)題：

其中?k是信賴域半徑。

2.自適應(yīng)信賴域算法

自適應(yīng)信賴域法的信賴域子問(wèn)題：

3.改進(jìn)的自適應(yīng)信賴域算法

改進(jìn)的自適應(yīng)信賴域法的信賴域子問(wèn)題：

數(shù)值結(jié)果

實(shí)驗(yàn)一：Rosenbrock函數(shù)，

實(shí)驗(yàn)二：

實(shí)驗(yàn)三：

從表中結(jié)果分析：無(wú)論對(duì)于一些維數(shù)較高的測(cè)試問(wèn)題，還是次數(shù)較高的函數(shù)來(lái)說(shuō)，改進(jìn)的自適應(yīng)信賴域算法具有良好的計(jì)算效能。改進(jìn)算法迭代次數(shù)少，效率高，誤差小。

表2　三種算法的運(yùn)行結(jié)果

表3　三種算法的運(yùn)行結(jié)果

結(jié)語(yǔ)

對(duì)于求解無(wú)約束優(yōu)化問(wèn)題最優(yōu)解的信賴域算法，子問(wèn)題二次模型的信賴域半徑的大小的選擇是影響算法收斂速度的關(guān)鍵。本文提出改進(jìn)自適應(yīng)信賴域算法，利用BB算法得到的步長(zhǎng)作為子問(wèn)題的信賴域半徑，用BB步長(zhǎng)自動(dòng)調(diào)節(jié)信賴域半徑。數(shù)值實(shí)驗(yàn)結(jié)果顯示改進(jìn)算法具有良好的計(jì)算效能，不管是迭代步數(shù)還是精度，本文的改進(jìn)算法都有較好的計(jì)算性能。