一種改進的自適應信賴域算法

胡夢英

北京郵電大學理學院

一種改進的自適應信賴域算法

胡夢英

北京郵電大學理學院

胡夢英，女，碩士在讀，北京郵電大學理學院，主要研究方向為最優化算法。

考慮無約束極小化問題

其中f:Rn→R 二次連續可微。

求解上述無約束問題主要有信賴域法和線搜索法。線性搜索先確定方向再確定步長，信賴域法則是先確定步長再確定方向。信賴域方法的主要思想是圍繞當前迭代點xk定義一個區域，即信賴域，使二次模型在信賴域內能充分近似目標函數，之后求解信賴域子問題得到試探步長，然后用某一評價函數來決定是否接受該試探步長以及決定下一次迭代的信賴域。信賴域法具有很強的全局收斂性，但是算法效率會受到子問題中信賴域半徑大小的影響。

對于無約束優化問題的信賴域算法，子問題中二次模型的信賴域半徑大小的選擇是關鍵。本文的改進自適應信賴域算法，利用BB算法得到的步長作為子問題的信賴域半徑，隨著迭代的進行自動調節信賴域半徑，提高運算效率。

自適應信賴域算法

信賴域半徑大小的選擇是影響每一步迭代效率的關鍵。如果信賴域太小，則算法就可能得不到目標函數的最優點，影響迭代速度。反之如果信賴域太大，則二次模型與目標函數近似程度不高，因而不得不減少信賴域并重新計算。自適應信賴域算法中信賴域半徑隨每一次迭代的進行而自動改變，是對傳統信賴域算法的一個改進。

自適應信賴域法的信賴域子問題：

BB算法

BB算法是Barzilai和Borwein提出的Two－Point Step Size Gradient Methods。BB算法的基本思路是用當前迭代點以及前一點的信息來確定步長因子。迭代公式可以看成是

因此計算得出，

改進的自適應信賴域算法

改進思路

自適應信賴域算法中信賴域半徑自動調節，本文提出的新算法利用BB算法得到的步長的倍數作為信賴域子問題的信賴域半徑，這其實是一種自適應信賴域算法。

新得到的信賴域的子問題為：

表1　三種算法的運行結果

算法步驟

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

Step2 計算gk，若則停止，否則轉Step3。

Step3 求解子問題（3.1），得到近似解dk。

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

數值實驗

本次數值實驗，我們選用的編程環境為Mathematics8.0。用Mathematics語言分別編寫了傳統信賴域算法、自適應信賴域算法和改進自適應信賴域算法的算法程序。

選用的測試函數

測試算法

1.傳統信賴域算法

傳統信賴域算法的信賴域子問題：

其中?k是信賴域半徑。

2.自適應信賴域算法

自適應信賴域法的信賴域子問題：

3.改進的自適應信賴域算法

改進的自適應信賴域法的信賴域子問題：

數值結果

實驗一：Rosenbrock函數，

實驗二：

實驗三：

從表中結果分析：無論對于一些維數較高的測試問題，還是次數較高的函數來說，改進的自適應信賴域算法具有良好的計算效能。改進算法迭代次數少，效率高，誤差小。

表2　三種算法的運行結果

表3　三種算法的運行結果

結語

對于求解無約束優化問題最優解的信賴域算法，子問題二次模型的信賴域半徑的大小的選擇是影響算法收斂速度的關鍵。本文提出改進自適應信賴域算法，利用BB算法得到的步長作為子問題的信賴域半徑，用BB步長自動調節信賴域半徑。數值實驗結果顯示改進算法具有良好的計算效能，不管是迭代步數還是精度，本文的改進算法都有較好的計算性能。