我们这届的题目如下,下面是一些自己的小想法供大家参考。
文章目录
一、不精确一维线搜索-采用Wolfe-Powell准则
要求的四个算法中,三个需要用到一维线搜索,实际算法中往往采用不精确搜索,题目要求采用Wolfe-Powell准则,这个准则就是,给定c1,c2两个常数,要求λ满足两个方程(大工的教材有P170)也就是我下面画的框图的两个判断条件,下面的流程图我是采用书上的直接法画的,通过看这个图,就可以开始编写我们的函数了。
可以看出,输入:初始点,方向,目标函数,目标函数梯度
常数:c1,c2,β1,β2,a,b
输出:λ
所以我们就可以写出采用Wolfe-Powell准则搜素λ的代码,用MATLAB实现
%这是题目的目标函数
function f = fun(x)
f = 10*(x(1)-1)^2 + (x(2)+1)^4;
end
%这是题目目标函数的梯度,手算比计算机求导运行速度要快
function g = gradient(x)
g = zeros(1,2);
g(1)=20*(x(1)-1);
g(2) = 4*(x(2)+1)^3;
end
%wolfe-powell实现函数
%xk为起始点坐标,dk为搜索方向
function lamda = wolfe_powell(xk,dk)
%对基本常数进行设置
c1 = 0.1;c2=0.5;
a = 0; b =Inf;
beita1 = 2;
beita2 = 1/2;
lamda = 1;
%进入循环体
while(1)
%判断是否符合条件1
if ~(fun(xk+lamda*dk)-fun(xk) <= c1*lamda*gradient(xk)*dk)
b = lamda;
lamda = (lamda + a)*beita2
continue;
end
%判断是否符合条件2
if ~(gradient(xk+lamda*dk)*dk >= c2*gradient(xk)*dk)
a = lamda;
lamda = min([beita1*lamda,(b+lamda)*beita2]);
continue;
end
break;
end
end
二、最速下降法
书上有现成的流程图,我就不画了
可以看出 输入:精度ε,初始点x0
输出:最优解xk
写出代码如下
function start_zuisu(x0,eps)
gk = gradient(x0);%目标函数梯度
res = norm(gk);%梯度模长
k = 0;
while (res > eps && k < 2000) %循环条件&&防止死循环,最多算2000次
fprintf('The %d-th iteration, the residual is %f\n',k,res); %记录迭代次数
fprintf('x=[%f,%f],min(f):%f\n',x0(1),x0(2),fun(x0));
fprintf('**********************************************\n');
dk = (-gk).'; %需要转置
lamda1 = wolfe_powell(x0,dk);%调用上面的一维搜索函数
x0 = x0 + lamda1*dk;
gk = gradient(x0);
res = norm(gk);
k = k+1;
end
fprintf('The %d-th iteration, the residual is %f\n',k,res);
fprintf('x=[%f,%f],min(f):%f\n',x0(1),x0(2),fun(x0));
end
三、实现展示
将上面代码写在一起,并且加上题目起始点与误差,即可得到结果,附上整体代码
x = [0;0];%起始点
eps = 0.0001;%精度
start_zuisu(x,eps);
function f = fun(x)
f = 10*(x(1)-1)^2 + (x(2)+1)^4;
end
function g = gradient(x)
g = zeros(1,2);
g(1)=20*(x(1)-1);
g(2) = 4*(x(2)+1)^3;
end
function lamda = wolfe_powell(xk,dk)
c1 = 0.1;c2=0.5;
a = 0; b =Inf;
beita1 = 2;
beita2 = 1/2;
lamda = 1;
while(1)
if ~(fun(xk+lamda*dk)-fun(xk) <= c1*lamda*gradient(xk)*dk)
b = lamda;
lamda = (lamda + a)*beita2;
continue;
end
if ~(gradient(xk+lamda*dk)*dk >= c2*gradient(xk)*dk)
a = lamda;
lamda = min([beita1*lamda,(b+lamda)*beita2]);
continue;
end
break;
end
end
function start_zuisu(x0,eps)
gk = gradient(x0);
res = norm(gk);
k = 0;
while (res > eps && k <=2000)
fprintf('The %d-th iteration, the residual is %f\n',k,res);
fprintf('x=[%f,%f],min(f):%f\n',x0(1),x0(2),fun(x0));
fprintf('**********************************************\n');
dk = (-gk).';
lamda1 = wolfe_powell(x0,dk);
x0 = x0 + lamda1*dk;
gk = gradient(x0);
res = norm(gk);
k = k+1;
end
fprintf('The %d-th iteration, the residual is %f\n',k,res);
fprintf('x=[%f,%f],min(f):%f\n',x0(1),x0(2),fun(x0));
end
后面的方法大同小异,后续更新