牛顿型方法和非精确搜索

牛顿型方法(不包括拟牛顿法)

基本牛顿法的收敛性是局部的,计算效果受初值点选取影响很大。一方面初始点选取不当可能会导致 $hesse$矩阵不正定,从而无法下降;另一方面即使海赛矩阵正定了,因为它的收敛性只在局部成立,同样不能保证函数值下降。为解决这些问题,可以使用阻尼牛顿法和修正牛顿法。

1.最速下降法

最速下降法似乎应该不算牛顿型方法,但是它的思想很重要: 找到函数下降最快的方向,然后按照这个方向迭代就能找到极小值点。后面的牛顿型方法都可以看成变度量意义下的最速下降法,即它们依然是沿着下降最快的方向迭代,只是各自对’下降最快’的定义不同,导致具体下降方法不同。

最速下降法的下降方向直接取负梯度方向: $d_k = -g_k$,这种取迭代方向为负梯度方向的算法称为负梯度方法,当搜索步长 $\alpha$ 采用精确线搜索时,就称其为最速下降法。最速下降法对初始点选取不敏感,即使从一个不太靠近最优解的点出发,它也能产生接近最优点的迭代序列,后面拟牛顿法的第一次迭代就是利用最速下降法先快速靠近最优解。同时该方法只需要计算一阶导信息,实现简单且计算量小。虽然最速下降法在每一步迭代都取当前能采取的最优策略,但贪心的未必是最好的: 它的收敛速度是线性收敛,随着迭代的进行,最速下降法靠近最优点的速度会很慢。

采用精确线搜索时,最速下降法的最优步长为 $\alpha = \frac{g_k^{T}g_k}{g_k^{T}Gg_k}$ .

下面是负梯度方法的代码(步长确定使用的是非精确搜索amijo准则而非精确搜索)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
function [x, val, k, plotinfo] = steepest_descent(f, g, x0)
%% steepest descent method, line search based on Armijo
% x: result point val: result value k: iterations used
% f: function to be optimized g: gradient of f x0: start point
% define them in other function file
maxiter = 5000;
epsilon = 1e-3; % accuracy
rho = 0.5; sigma = 0.4; % paras for Armijo
x1s = 0; x2s = 0; ys = 0;
for iter = 1:maxiter
f_x0 = feval(f, x0);
disp(['Iteration ' num2str(iter-1) '. f_value: ' num2str(f_x0) ', current point:']);
disp(x0');
% record optimize path
x1s = [x1s; x0(1)]; x2s = [x2s; x0(2)]; ys = [ys; f_x0];
grad = feval(g, x0);
% fval = feval(f, x0);
if(norm(grad) < epsilon)
disp('Optimization done!')
x = x0; val = feval(f, x0); k = iter;
break;
else
m = 0; mk = 0;
while(m < 20) % Amijo search
if(feval(f, x0 + (rho^m)*(-grad)) < feval(f, x0) + (rho^m)*sigma*grad'*(-grad))
mk = m; break;
end
m = m + 1;
end
if(m >= 20)
disp('Amijo did not find a satisfied answer!')
% mk = m;
end
x0 = x0 + (rho^mk)*(-grad);
end
end
if(iter >= 5000)
disp('Optimization stop early, accuracy not satisfied for 5000 iterations!')
x = x0; val = feval(f, x0); k = iter;
end
plotinfo = [x1s(2:end), x2s(2:end), ys(2:end)];
end

2.阻尼牛顿法

阻尼牛顿法可以改善基本牛顿法的局部收敛性,它可以保证在 hesse 矩阵正定时,${f_k}$ 单调下降,即使 $k$ 点离最优点较远。可以证明对严格凸函数,采用 Wolfe 准则的阻尼牛顿方法具有全局收敛性。

阻尼牛顿法实现很简单,只是在基本牛顿法方向确定的基础上加上步长 $\alpha$ 的一维线搜索,即迭代公式为 $x_{k+1} = x_k + \alpha_kd_k$ .

代码里只要加上一句非精确搜索就好了:

1
[mk, x0] = amijo(f, g, x0, d);

amijo 搜索的介绍在本文后面给出。

3.修正牛顿方法

修正牛顿方法针对可能出现的 hesse 矩阵非正定的情况做出修正。一种方法就是在 hesse 阵 $G_k$ 非正定时将基本牛顿法的方向 $d_k $ 换成负梯度方向;另一种则是修改 $G_k$ 使其正定: $(G_k+v_kI)d = -g_k$ , 即取新的方向为 $d = -(G_k+v_kI)^{-1}g_k$ , 其中 $v_k>0$ , $I$ 是单位阵,确定合适的 $v_k$ 使 $G_k+v_kI$ 正定即可。

下面给出修改海赛阵的代码,代码来自参考[1]书

1
2
3
4
% revised part
muk = norm(grad_x0)^(1+tau);
Ak = h_x0 + muk*eye(length(startp));
d = -Ak\grad_x0;

非精确搜索

下面给出两个非精确搜索的代码。分别是 wolfe 准则和 amijo 准则,代码同样非原创。

1.Wolfe

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
function [alpha, x] = wolfe(f, g, x0, d)
%% Weak wolf
% Code from internet
rho = 0.25; sigma = 0.75;
alpha = 1; a = 0; b = Inf;
k = 0;
while(1)
k = k + 1;
if (k > 300)
break;
end
if (~mod(k,100))
disp([' Wolf iter' num2str(k)]);
end
if ~(feval(f, x0+alpha*d) <= feval(f, x0) + rho*alpha*feval(g, x0)'*d)
b = alpha;
alpha = (alpha+a)/2;
continue;
end
if ~(feval(g, x0+alpha*d)'*d >= sigma*feval(g, x0)'*d)
a = alpha;
alpha = min([2*alpha, (b+alpha)/2]);
end
break;
end
x = x0 + alpha*d;
end

2.Amijo

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
function [mk, x] = amijo(f, g, x0, d)
%% Amijo condition
% code from book
beta = 0.5; sigma = 0.4;
m = 0; maxiter = 20;
while(m < maxiter)
if(feval(f, x0+beta^m*d) <= feval(f, x0) + sigma*beta^m*feval(g, x0)'*d)
mk = m; x = x0 + beta^mk*d;
break;
end
m = m + 1;
end
disp('Amijo can not find a satisfied step length in 20 iterations!')
mk = m; x = x0 + beta^mk*d;
end

[1]: 最优化方法及其 Matlab 程序设计 马昌凤