胡夢(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)算效率。
信賴域半徑大小的選擇是影響每一步迭代效率的關(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算法是Barzilai和Borwein提出的Two-Point Step Size Gradient Methods。BB算法的基本思路是用當(dāng)前迭代點(diǎn)以及前一點(diǎn)的信息來(lái)確定步長(zhǎng)因子。迭代公式可以看成是
因此計(jì)算得出,
改進(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),我們選用的編程環(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é)果
對(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ì)算性能。