共轭梯度法及其matlab程序

  上一篇文章介绍了修正牛顿法,修正牛顿法的缺点是收敛速度一般,所以为了使算法既不使用Hess阵,也要保证它的收敛速度,本文介绍共轭梯度法。共轭梯度法有超线性的收敛速度,算法结构简单,容易编程,并且不用计算Hess阵的优点。下面介绍共轭梯度法的算法步骤。

 步0:确定精度e=(0~1),给定初始点x0,计算g0=共轭梯度法及其matlab程序f(x0),k=0

步1:若||gk||<=e,停止运算,输出xk作为最优解

步2:计算搜索方向dk:

若k=0,dk=-gk

若k>=1,dk= -gk+共轭梯度法及其matlab程序*共轭梯度法及其matlab程序       其中   

 共轭梯度法及其matlab程序

步3:用Armijo精确线搜索技术确定搜索步长,具体步骤上一篇文章已经详细介绍。这里不再赘述。算了,还是写吧:

设置初始参数 ,共轭梯度法及其matlab程序=(0~1),共轭梯度法及其matlab程序=(0~0.5)

步长共轭梯度法及其matlab程序k=共轭梯度法及其matlab程序^mk,m的值从0开始

若满足不等式f(xk+ 共轭梯度法及其matlab程序^m*dk)<=f(xk)+共轭梯度法及其matlab程序*共轭梯度法及其matlab程序^m*gk'dk

则 mk=m,步长 共轭梯度法及其matlab程序k=共轭梯度法及其matlab程序^mk,若不满足上式,则m=m+1,直到满足上述不等式为止

步4:令Xk+1=xk+ 共轭梯度法及其matlab程序k*dk,然后计算gk=共轭梯度法及其matlab程序f(xk+1),k=k+1,转步1

 代码实现:

1.共轭梯度函数

function [x,val,k]=frcg(fun,gfun,x0)
%功能:用共轭梯度法求无约束问题 mini f(x)
%输入:fun,gfun分别是目标函数和梯度,x0是初始点
%输出:x,val分别是近似最优点和最优值,k表示迭代次数
k=0;
maxk=5000;
rho=0.6;
sigma=0.4;
e=1e-5;%精度
n=length(x0);
while(k<maxk)
    g=feval(gfun,x0);%求梯度
    itern=k-(n+1)*floor(k/(n+1));%用于重新开始
     itern=itern+1;
       %计算搜索方向
       if(itern==1)
           d=-g;
       else
           beta=(g'*g)/(g0'*g0);
           d=-g+beta*d0;
           gd=g'*d; %当搜索方向不是下降方向时,插入负梯度方向作为搜索方向
           if(gd>=0.0)
               d=-g;
           end
       end
    if(norm(g)<=e) ,break;end
m=0;
mk=0;
while(m<20)
        if(feval(fun,x0+rho^m*d)<feval(fun,x0)+sigma*rho^m*g'*d);
           mk=m;
           break;
        end
       m=m+1;
end
     x0=x0+d*rho^mk;
    val=feval(fun,x0);
     g0=g;
     d0=d;
     k=k+1;
end
x=x0;
val=feval(fun,x);
end

2.fun函数

function f= fun(x)
%目标函数
f=100*(x(1)^2-x(2))^2+(x(1)-1)^2;
end

3.gfun函数

function  g=gfun(x)
%目标函数的梯度
g=[400*x(1)*(x(1)^2-x(2))+2*(x(1)-1),-200*(x(1)^2-x(2))]';
end

4.主函数

%这个问题的精确值是x=(1,1)',f(x)=0;
clear all
clc
x0=[-1.2 1]';
[x,val,k]=frcg('fun','gfun',x0);
disp('迭代次数:k=')
disp(k)
disp(['最优解:x = '])
disp(x)
disp(['此时: f(x) = ',num2str(val)]) 

上一篇:PTA天体赛 L1-071 前世档案 (20 分) 详解


下一篇:数组上下文规则