您现在的位置: IOS教程網 >> IOS系統 >  >> iOS 訊息 >> iOS 相關資訊

Dogleg Method:「狗腿」演算法實作筆記

編輯:iOS 相關資訊

問題背景

最速下降法的本質是一個迭代式:x(k+1) = x(k) + a(k) * d(k)。其中 x(k) 是定義域上的點,a(k) 是前進的步長(純量),d(k) 是前進的方向;在高維情形下 d(k) 是個列向量。最常見的取法是令 d(k) 為 x(k) 處的負梯度方向,當然也可以帶入海森矩陣,那也就是牛頓法那一系列做法。

所以非線性最佳化的核心問題就在於:如何挑選合適的 a(k) 與 d(k)。

為什麼只談 d(k)

參考資料的順序是先講步長、再講方向。但這次作業只要求實作「選取方向 d(k)」的一種方法——Dogleg 演算法,因此程式碼中只體現了這部分。步長的選取寫得相當粗糙,用的是指數衰減(每次收斂不順就把 a 乘上 0.995),之所以可以這麼草率,是因為被最佳化的目標函數嚴格凸,步長策略並不會對結果造成決定性影響。

測試目標函數

採用的是知名的 Rosenbrock 函數:

[x1, x2] = argmin ( 100 * (x2 - x1^2)^2 + (1 - x1)^2 )

它的全域最小值在 (1, 1),但函數形狀狹長平坦,是檢驗最佳化演算法收斂能力的經典難題。

dogleg.m

clear; clc

x1 = 0:0.005:1; x2 = 0:0.008:2;
ff = zeros(length(x1), length(x2));
for i = 1 : length(x1)
    ff(i, :) = 100 * (x2 - x1(i)^2).^2 + (1 - x1(i))^2;
end

x = [min(x1) + (max(x1) - min(x1)) * rand(1), ...
     min(x2) + (max(x2) - min(x2)) * rand(1)]';

a = 2;                        % 折線參數,決定落在狗腿的哪一側
d = -B(x)^-1 * g(x);
maxiter = 1000; iter = 1;
rey = []; rex1 = []; rex2 = [];

while iter < maxiter
    rey  = [rey,  f(x)];
    rex1 = [rex1, x(1)];
    rex2 = [rex2, x(2)];

    if sum(abs(g(x))) < 0.00001
        break
    end

    iter = iter + 1;

    du = -g(x)' * g(x) * g(x) / (g(x)' * B(x) * g(x));   % 沿負梯度到「狗腿拐點」的距離
    dB = -B(x)^-1 * g(x);                                % 牛頓方向

    if a < 1
        d = a * du;                                      % 落在半徑內,用梯度方向
    else
        d = du + (a - 1) * (dB - du);                    % 沿 dogleg 折線往牛頓方向延伸
    end

    if f(x) > f(x + d)
        x = x + d;        % 有改善就前進
    else
        a = a * 0.995;    % 否則縮小步長再試
    end
end

hold on
mesh(x2, x1, ff);
plot3(rex2, rex1, rey, 'r', 'linewidth', 4)

輔助 m 檔

f.m —— 目標函數

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

g.m —— 梯度向量

function y = g(x)
y = [400 * (x(1)^2 - x(2)) * x(1) + 2 * (x(1) - 1), ...
     200 * (x(2) - x(1)^2)]';
end

B.m —— 海森矩陣

function y = B(x)
y = [400 * (3*x(1)^2 - x(2)) + 2, -400 * x(1); ...
                -400 * x(1),        200];
end

演算法的圖形直覺

Dogleg 之所以叫「狗腿」,是因為可信賴域內的最短路徑形狀像狗腿一樣有個折角:從當前點出發,先沿最陡下降方向走到與可信賴域邊界相交的點(圖中的 du),再沿直線走向牛頓解的無約束最佳點(dB)。參數 a 就是控制這條折線上落點位置的伸縮因子——a 小於 1 時落在折角之前,只用到梯度資訊;a 大於 1 時則沿第二段直線往牛頓方向靠攏。

程式最後把收斂軌跡以紅色線條疊畫在曲面網格上,可以很直觀地看到迭代點如何沿著狹長的山谷一步步走向 (1, 1)。

  1. 上一篇文章:
  2. 下一篇文章:
蘋果刷機越獄教程| IOS教程問題解答| IOS技巧綜合| IOS7技巧| IOS8教程
Copyright © IOS教程網 All Rights Reserved