大连理工大学 2021年最优化方法大作业(1)

我们这届的题目如下,下面是一些自己的小想法供大家参考。

大连理工大学 2021年最优化方法大作业(1)

文章目录



一、不精确一维线搜索-采用Wolfe-Powell准则

要求的四个算法中,三个需要用到一维线搜索,实际算法中往往采用不精确搜索,题目要求采用Wolfe-Powell准则,这个准则就是,给定c1,c2两个常数,要求λ满足两个方程(大工的教材有P170)也就是我下面画的框图的两个判断条件,下面的流程图我是采用书上的直接法画的,通过看这个图,就可以开始编写我们的函数了。

大连理工大学 2021年最优化方法大作业(1)

可以看出,输入:初始点,方向,目标函数,目标函数梯度

                  常数: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



二、最速下降法


书上有现成的流程图,我就不画了

大连理工大学 2021年最优化方法大作业(1)

可以看出 输入:精度ε,初始点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

大连理工大学 2021年最优化方法大作业(1)

 后面的方法大同小异,后续更新

上一篇:NC49 最长的括号子串


下一篇:利用System.Net.Mail 发送邮件