
最速下降法的本質是一個迭代式: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)」的一種方法——Dogleg 演算法,因此程式碼中只體現了這部分。步長的選取寫得相當粗糙,用的是指數衰減(每次收斂不順就把 a 乘上 0.995),之所以可以這麼草率,是因為被最佳化的目標函數嚴格凸,步長策略並不會對結果造成決定性影響。
採用的是知名的 Rosenbrock 函數:
[x1, x2] = argmin ( 100 * (x2 - x1^2)^2 + (1 - x1)^2 )
它的全域最小值在 (1, 1),但函數形狀狹長平坦,是檢驗最佳化演算法收斂能力的經典難題。
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)
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)。