拟牛顿方法测试

测试函数

Watson 函数

$$
min \sum_{i=1}^{m}r_i^2(x) \\
r_i(x) = \sum_{j=2}^n(j-1)x_jt_i^{j-2} - (\sum_{j=1}^nx_jt_i^{j-1})^2 - 1
$$

其中,$t_i=i/29,~ 1 \le i \le 29,~ r_{30}=x_1,~ r_{31} = x_2 - x_1^2 -1,~ 2 \le n \le 31,~ m = 31$ . 初始点选为 $x^{(0)} = (0, \dots ,)^T$.

根据文章[1], $watson$ 函数的最小值为:
$$
f=2.28767 \cdots 10^{-3} ~~if~n=6\\
f=1.39976 \cdots 10^{-6} ~
~if~n=9\\
f=4.72238 \cdots 10^{-10} ~~~~if~n=12
$$

函数形式比较复杂,求一阶导的过程比较繁琐,写出来也麻烦,直接给出 $watson$ 函数和它的导数的matlab 代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
%% Watson function, fix m = 31, n can be modified
function w = fwatson(x)
% x is n dim vector, w is 1 dim value
m = 31; n = length(x);
w = 0;
for ii = 1:29
tmp_i1 = 0;
tmp_i2 = 0;
ti = ii/29;
for jj = 1:n
tmp_j1 = (jj-1)*x(jj)*ti^(jj-2);
tmp_j2 = x(jj)*ti^(jj-1);
tmp_i1 = tmp_i1 + tmp_j1;
tmp_i2 = tmp_i2 + tmp_j2;
end
w = w + (tmp_i1 - tmp_i2^2 - 1)^2;
end
% add r30 and r31
w = w + x(1)^2 + (x(2) - x(1)^2 -1)^2;
end
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
%% gwatson: gradient of watson function
function [grad] = gwatson(x)
% x is n dim vector, grad is n dim value
n = length(x);
grad = zeros(n, 1);
% compute sum in the square
insum = zeros(29, 1);
for ii = 1:29
ti = ii/29;
for jj = 1:n
insum(ii) = insum(ii) + x(jj)*ti^(jj-1);
end
end
% Compute r_i
r = zeros(31, 1);
for ii = 1:29
r(ii) = r_i(ii, x, n);
end
r(30) = x(1); r(31) = x(2) - x(1)^2 - 1;
for jj = 1:n
dfdxj = 0;
for ii = 1:29
ti = ii/29;
dridxj = ((jj-1)*ti^(jj-2) - 2*insum(ii)*ti^(jj-1))*2*r(ii);
dfdxj = dfdxj + dridxj;
end
grad(jj) = dfdxj + 2*r(30);
end
grad(1) = grad(1) - 2*x(1)*2*r(31);
grad(2) = grad(2) + 2*r(31);
end
function ri = r_i(i, x, n)
% compute r_i(x)
ti = i/29;
tmp_i1 = 0; tmp_i2 = 0;
for jj = 1:n
tmp_i1 = tmp_i1 + (jj-1)*x(jj)*ti^(jj-2);
tmp_i2 = tmp_i2 + x(jj)*ti^(jj-1);
end
ri = tmp_i1 - tmp_i2^2 -1;
end
Discrete boundary value function

$$
min \sum_{i=1}^n r_i^2(x) \\
r_i(x) = 2x_i - x_{i-1} - x_{i+1} + h^2(x_i + t_i + 1)^3/2
$$

其中 $h = 1/(n+1),~ t_i = ih,~ x_0 = x_{n+1} = 0,~ m=n$, 初始点选为 $x^{(0)} = (t_1(t_1-1), \cdots, t_n(t_n-1))^T$.

同样根据[1], 该函数的最小值为 $f = 0$.

函数和它的导数的代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
%% fdbv: Discrete boundary value
function [fx] = fdbv(x)
m = length(x);
fx = 0;
for iter = 1:m
fx = fx + r_i(iter, x)^2;
end
end
function ri = r_i(ii, x)
n = length(x);
x(n+1) = 0;
h = 1/(n+1);
ti = ii*h;
if(ii == 1) % x(0)=0
ri = 2*x(ii) - x(ii+1) + h^2*(x(ii)+ti+1)^3/2;
else
ri = 2*x(ii) - x(ii-1) - x(ii+1) + h^2*(x(ii)+ti+1)^3/2;
end
end
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
%% gdbv: Gradient of discrete boundary value
function [grad] = gdbv(x)
n = length(x);
h = 1/(n+1);
t1 = 1*h; tn = n*h;
grad = zeros(n, 1);
grad(1) = (2+3*h^2*(x(1)+t1+1)/2)*2*r_i(1, x) + (-1)*2*r_i(2, x);
for iter = 2:n-1
ti = iter*h;
grad(iter) = (-1)*2*(r_i(iter+1, x) + r_i(iter-1, x)) +...
(2+3*h^2*(x(iter)+ti+1)/2)*2*r_i(iter, x);
end
grad(n) = (2+3*h^2*(x(n)+tn+1)/2)*2*r_i(n, x) + (-1)*2*r_i(n-1, x);
end
function ri = r_i(ii, x)
n = length(x);
x(n+1) = 0;
h = 1/(n+1);
ti = ii*h;
if(ii == 1) % x(0)=0
ri = 2*x(ii) - x(ii+1) + h^2*(x(ii)+ti+1)^3/2;
else
ri = 2*x(ii) - x(ii-1) - x(ii+1) + h^2*(x(ii)+ti+1)^3/2;
end
end

SR1,DFP和BFGS方法效果比较

SR1, DFP 和 BFGS 都是拟牛顿方法,计算步骤相同,只是计算近似矩阵 $H$ 时有不同,故代码写在一处:

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
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
function [x, vals, k] = quasi_newton(f, g, xk, method)
%% Quasi-newton's method
% x: result point val: result value k: total iterations
% f: function to be optimized g: gradient of f xk: start point, column vector
% hesse: Hesse matrix of f
% method 'SR1', 'DFP', 'BFGS'
maxiter = 200;
epsilon = 1e-5;
x = xk';
vals = feval(f, xk);
% Iteration 1, steepest descent
H = eye(length(xk));
grad_k = feval(g, xk); % gk, gradient at xk
d = -H*grad_k; % d1
[alpha, xk1] = wolfe(f, g, xk, d);
grad_k1 = feval(g, xk1);
delta_x = xk1 - xk; % s1
delta_g = grad_k1 - grad_k; % y1
for iter = 1:maxiter
% Record results
disp(['Quasi_newton iteration ' num2str(iter)])
x = [x; xk1'];
vals = [vals; feval(f, xk1)];
if(norm(grad_k1) < epsilon)
disp('Optimization done!')
break;
else
if (strcmp(method, 'SR1'))
delt_H = (delta_x - H*delta_g)*(delta_x - H*delta_g)'/((delta_x - H*delta_g)'*delta_g);
H = H + delt_H;
elseif (strcmp(method, 'DFP'))
delt_H = delta_x*delta_x'/(delta_x'*delta_g) - H*(delta_g*delta_g')*H/(delta_g'*H*delta_g);
H = H + delt_H;
elseif (strcmp(method, 'BFGS'))
delt_H = (1 + delta_g'*H*delta_g/(delta_g'*delta_x))*(delta_x*delta_x')/(delta_g'*delta_x) - ...
(delta_x*delta_g'*H + H*delta_g*delta_x')/(delta_g'*delta_x);
H = H + delt_H;
else
error('Invalid method!');
end
d = -H*grad_k1;
xk = xk1;
[alpha, xk1] = wolfe(f, g, xk1, d);
% Prepare for next iteration
grad_k = grad_k1;
grad_k1 = feval(g, xk1);
delta_x = xk1 - xk;
delta_g = grad_k1 - grad_k;
end
end
if(iter > maxiter)
disp(['Can not find answer in ' num2str(maxiter) ' iterations!'])
else
k = iter;
end
end

实验终止条件都是使用梯度条件: $|g(x_k)| < 1e-5$ ,最大迭代次数400 .

  • $watson$ 函数上测试的测试情况(feval 为函数及其导数函数的调用次数)

    | $n = 6$ | feval | 迭代次数 | 最终结果 | 备注 |
    | ———– | —– | —- | —— | ————————————- |
    | SR1(Wolfe) | | | NaN | wolfe准则搜不到满意步长, iter 12步长太小,出现NaN,无法解 |
    | SR1(Amijo) | 803 | 400 | 0.0060 | amijo准则无法搜索到满意步长,迭代到maxiter,没有满足终止条件 |
    | DFP(Wolfe) | 671 | 335 | 0.0024 | wolfe准则在满足终止条件前无法找到步长 |
    | DFP(Amijo) | 803 | 400 | 0.0026 | amijo准则迭代到maxiter,没有满足终止条件 |
    | BFGS(Wolfe) | 601 | 300 | 0.0024 | wolfe准则300次后出现NaN,无法解 |
    | BFGS(Amijo) | 803 | 400 | 0.0024 | amijo准则无法搜索到满意步长,迭代到maxiter,没有满足终止条件 |

    | $n = 9$ | feval | 迭代次数 | 最终结果 | 备注 |
    | ———– | —– | —- | ——— | ———————————— |
    | SR1(Wolfe) | 260 | 129 | 1.3999e-6 | |
    | SR1(Amijo) | 803 | 400 | 0.0111 | amijo准则无法搜索到满意步长,迭代到maxiter,没有满足终止条件 |
    | DFP(Wolfe) | 803 | 400 | 4.1172e-5 | wolfe迭代到maxiter,没有满足终止条件 |
    | DFP(Amijo) | 803 | 400 | 4.9962e-5 | amijo准则无法搜索到满意步长,迭代到maxiter,没有满足终止条件 |
    | BFGS(Wolfe) | 98 | 48 | 6.6841e-6 | |
    | BFGS(Amijo) | 803 | 400 | 0.0080 | amijo准则无法搜索到满意步长,迭代到maxiter,没有满足终止条件 |

    | $n = 12$ | feval | 迭代次数 | 最终结果 | 备注 |
    | ———– | —– | —- | ——— | ———————————— |
    | SR1(Wolfe) | | | NaN | wolfe准则搜不到满意步长,iter 18步长太小,出现NaN,无法解 |
    | SR1(Amijo) | 803 | 400 | 0.0116 | amijo准则无法搜索到满意步长,迭代到maxiter,没有满足终止条件 |
    | DFP(Wolfe) | 803 | 400 | 5.6117e-6 | wolfe迭代到maxiter,没有满足终止条件 |
    | DFP(Amijo) | 803 | 400 | 4.2964e-6 | amijo准则无法搜索到满意步长,迭代到maxiter,没有满足终止条件 |
    | BFGS(Wolfe) | 84 | 41 | 1.5767e-7 | |
    | BFGS(Amijo) | 803 | 400 | 0.0019 | amijo准则无法搜索到满意步长,迭代到maxiter,没有满足终止条件 |

    结果似乎都不太理想,似乎n=6时终止条件太苛刻,n=12时终止条件又太宽松了。

  • $Discrete ~boundary ~value$ 函数上的计算情况

    | $n =m= 15$ | feval | 迭代次数 | 最终结果 | 备注 |
    | ———– | —– | —- | ———- | ————————————– |
    | SR1(Wolfe) | | | NaN | wolfe准则搜不到满意步长, iter 13时步长太小,出现NaN,无法解 |
    | SR1(Amijo) | 38 | 18 | 3.0620e-10 | amijo准则无法搜索到满意步长,但迭代到 iter 18 就满足终止条件 |
    | DFP(Wolfe) | 574 | 286 | 1.1134e-11 | |
    | DFP(Amijo) | 566 | 282 | 7.5798e-12 | amijo准则无法搜索到满意步长,但迭代到 iter 282 就满足终止条件 |
    | BFGS(Wolfe) | 54 | 26 | 5.0347e-12 | |
    | BFGS(Amijo) | 54 | 26 | 4.5023e-11 | amijo准则无法搜索到满意步长,但迭代到 iter 26 就满足终止条件 |

    ​

[1] Testing Unconstrained Optimization Software