基本牛顿法测试

基本牛顿方法

基本牛顿方法, 迭代方向为 $d_k = -G_k^{-1}g_k$, 步长取1. 迭代公式为 $x_k = x_k + d_k$. 因为不能保证 hesse 矩阵正定, 导致无法保证 $d_k$ 为下降方向. 其具有局部收敛性, 即初始点距离最优点必须足够小, 否则迭代序列 $x{k}$ 就会收敛到鞍点或极大点.

下面用两个不同初始点测试函数
$$
f(x) = \frac{x_1^4}{12} + \frac{x_1^2}{2} + x_2arctanx_2 - \frac{ln(x_2^2 + 1)}{2}
$$

它的一阶导和 hesse 阵分别为
$$
g(x) = [x_1^2/3 + x_1 ~, ~ arctanx_2 ]’
$$

$$
G(x) = \begin{bmatrix}
x_1^2+1 & 0\\
0 & \frac{1}{x_2^2+1}
\end{bmatrix}
$$

基本牛顿法代码:

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
47
function [x, val, k] = newton_basic(f, g, hesse, x0, ifplot)
%% Basic newton's method
% x: result point val: result value k: total iterations
% f: function to be optimized g: gradient of f x0: start point, column vector
% ifplot: 1, plot figure hesse: Hesse matrix of f
maxiter = 500;
epsilon = 1e-5;
xs = x0;
ys = feval(f, x0);
for iter = 1:maxiter
f_x0 = feval(f, x0);
grad_x0 = feval(g, x0);
% Record optimization
if(iter >= 1)
xs = [xs; x0'];
ys = [ys; f_x0];
end
disp(['iteration ' num2str(iter-1) ' current f: ' num2str(f_x0)]);
if(norm(grad_x0) < epsilon)
disp('Optimization done!')
break;
else
h_x0 = feval(hesse, x0);
d = -inv(h_x0)*grad_x0;
x0 = x0 + d;
end
end
x = x0;
val = f_x0;
k = iter;
if(ifplot & length(x0)==2) % Can only plot 2 dimension x variable figures
x1 = [x0(1)-2 : 0.1 : x0(1)+2]';
x2 = [x0(2)-2 : 0.1 : x0(2)+2]';
y = zeros(length(x1), length(x2));
for ii = 1:length(x1)
for jj = 1:length(x2)
y(ii, jj) = feval(f, [x1(ii), x2(jj)]);
end
end
surfc(x1, x2, y); hold on;
p = plot3(xs(1,:), xs(2,:), ys, 'r');
p.Marker = '*';
end
end

运行代码.

初始点选取 $x^{(0)} = [1, 0.7]’$ 时运行结果:

Iter $x$ $f(x)$
1 [1, 0.7]’ 0.8115
2 [0.33, -0.21]’ 0.0785
3 [0.02, 0.0061]’ 0.0003
4 [0, 0] 0

很快收敛到极小值点. 二维变量可以画图,下面画出优化时经过的路径:

Basic newton

初始点选取 $x^{(1)} = [1, 2]’$ 时运行结果:

Iter $x$ $f(x)$
1 [1,2]’ 1.9929
2 [0.33, -3.54]’ 3.3346
3 [0.02, 13.95]’ 18.2780
4 [7e-6, -279.34]’ 432.1602
…… …… ……

函数值随迭代增大, 方法失效.