文章目錄

• 一、前言
• 二、Goldstein準則
• • 1. 定義
  • 2. 幾何含義
• 三、代碼實現
• 四、與Armjio準則的對比
• 五、總結

---

一、前言

為了克服 Armijo 準則的缺陷，我們需要引入其他準則來保證每一步的 ${\alpha }^k$ 不會太小。

既然 Armijo 準則只要求點 $(\alpha ,?(\alpha ))$ 必須處在某直線下方，我們也可使用相同的形式使得該點必須處在另一條直線的上方。

這就是 Armijo-Goldstein 準則，簡稱 Goldstein 準則。

---

二、Goldstein準則

1. 定義

設 $d^k$ 是點 $x^k$ 處的下降方向，若

$$\begin{array}{rl}& f(x^k+\alpha d^k)\le f(x^k)+c\alpha ?f(x^k{)}^T{d}^k,\\ & f(x^k+\alpha d^k)\ge f(x^k)+(1?c)\alpha ?f(x^k{)}^T{d}^k\end{array}$$

則稱步長 $\alpha$ 滿足 Goldstein 準則，其中 $c\in (0,\frac{1}{2})$。

2. 幾何含義

與 Armjio 準則相類似，Goldstein 準則也有非常直觀的幾何含義，它指的是點 $(\alpha ,?(\alpha ))$ 必須在兩條直線

$$\begin{array}{rl}& l_1(\alpha )=?(0)+c\alpha ?f(x^k{)}^T{d}^k,\\ & l_2(\alpha )=?(0)+(1?c)\alpha ?f(x^k{)}^T{d}^k\end{array}$$

之間。如下圖所示：

區間 $[{\alpha }_1,{\alpha }_2]$ 中的點均滿足 Goldstein 準則，同時我們也注意到 Goldstein 準則確實去掉了過小的 $\alpha$。

---

三、代碼實現

MATLAB 代碼如下：

function [alpha, xk, f, k] = Goldstein(fun, grid, x0, dk)%% Function [alpha, xk, fx, k] = Goldstein(fun, grid, x0, dk)% 求出函數fun在x0處以dk為下降方向時的步長alpha，同時返回相對應的下% 一個下降點xk以及xk處的函數值fx，k為迭代次數% -----------------------------------------------------------% 輸入: % fun 函數名稱(字符變量）% grid 梯度函數名稱(字符變量)% x0 迭代點(列向量)% dk 函數在迭代點處的下降方向(列向量)%% 輸出:% alpha 函數在x0處以dk為下降方向時的下降步長% xk 函數在x0處以dk為下降方向，以alpha為步長% 求得的下降點% f 函數在下降點xk處的函數值% k 求步長算法迭代次數% -----------------------------------------------------------% by Zhi Qiangfeng %c = 0.3; % 泰勒展開式補足系數，0 < c < 1/2alpha = 1; % 初始步長為 1k = 0; % 統計迭代次數a = 0; b = inf; % 二分法確定 alpha 值gk = feval(grid, x0); % x0處的梯度值fk = feval(fun, x0 + alpha * dk); % 函數在下一個迭代點處的目標函數值l1 = feval(fun, x0) + c * alpha * gk' * dk; % Armjio準則l2 = feval(fun, x0) + (1 - c) * alpha * gk' * dk; % Armjio準則的補全while trueif fk > l1k = k + 1;b = alpha;alpha = (a + b) / 2;fk = feval(fun, x0 + alpha * dk);l1 = feval(fun, x0) + c * alpha * gk' * dk;l2 = feval(fun, x0) + (1 - c) * alpha * gk' * dk;continue;endif fk < l2k = k + 1;a = alpha;alpha = min([2 * alpha, (a + b) / 2]);fk = feval(fun, x0 + alpha * dk);l1 = feval(fun, x0) + c * alpha * gk' * dk;l2 = feval(fun, x0) + (1 - c) * alpha * gk' * dk;continue;endbreak;endxk = x0 + alpha * dk; % 下降點f = feval(fun, xk); % 下降點處函數值 end

---

四、與Armjio準則的對比

以求解 Rosenbrock 函數為例，這是優化領域中一個著名的檢驗函數，函數表達式如下：

$$\begin{array}{rl}& f(x)=100(x_2?x_1^2{)}^2+(1?x_1{)}^2,\\ & g(x)=\left[\begin{array}{r}?400x_1{x}_2+400x_1^3+2x_1?2;\\ 200x_2?200x_1^2\end{array}\right]\end{array}$$

編寫函數文件 fun.m 如下：

function f = fun(x) f = 100 * (x(2) - x(1)^2)^2 + (1 - x(1))^2; end

隨后是梯度函數文件 grid.m 如下：

function g = grid(x) g = [-400 * x(1) * x(2) + 400 * x(1)^3 + 2 * x(1) - 2;200 * x(2) - 200 * x(1)^2]; end

Armjio 準則代碼參考此篇博客：最優化建模算法理論之Armjio準則（數學原理及MATLAB實現）

求解方法采用 BFGS 擬牛頓方法，代碼參考此篇博客：最優化建模算法理論之BFGS/DFP擬牛頓方法（數學原理及MATLAB實現）

編寫求解代碼如下：

x0 = [-10; 10]; [f, xk, k] = BFGS(x0, 'fun', 'grid', 1e-5, 1000)

初始點選為 [-10, 10]，若采用 Armjio 準則求步長，輸出如下：

>> resolve f =8.7712e-17 xk =1.00001.0000 k =70 >>

迭代了 70 次，若采用 Goldstein 準則，輸出如下：

>> resolve f =8.3501e-20 xk =1.00001.0000 k =60 >>

迭代了 60 次即達到了精度要求，并且求解的函數值 f = 8.3501e-20 還要優于 Armjio 準則。

---

五、總結

不喜歡寫總結。

總結

以上是生活随笔為你收集整理的最优化建模算法理论之Goldstein准则（数学原理及MATLAB实现）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。