目录
一.前沿
DFP算法是由Davidon提出的，经过Fletccher和powell改进，故称之为DFP算法。DFP算法也是拟牛顿矫正的一种，目前，它是求解无约束问题最有效的算法之一。其实吧，就是给定一个初始点，根据矫正矩阵和梯度求出下一步的搜索方向，再由Armijo搜索准则求出步长（Armijo准则前面已经简述，现在不再赘述），得到步长和搜索方向之后重新计算新的初始点，若在这个新的点的梯度足够小（就是下降的足够小，一般精度都会给出）时，我们就可以停止运算，输出这个点的值做为近似最优解。
二.矫正公式
三.算法步骤
步0：确定终止误差e=（0~1），设初始点x0，参数
=(0~1)，
=（0,0.5），初始对称正定阵H0=I（单位阵），令k=0
步1：计算gk=
f(xk).若||gk||<=e,停算，输出xk作为最优解。否则，转步2
步2：计算搜索方向dk=-Hk*gk
步3：根据Armijo准则计算搜索步长：
用Armjio搜索技术求步长
k=
^mk，m的值从0开始，
若f(xk+
^m*dk)<=f(xk)+
*
^m*gk’dk
则令 mk=m，步长
k=
^mk，若不满足上式，则m=m+1，直到满足上述不等式为止
其实就是用那个不等式求出m的值，然后用公式求出步长。
步4：令Xk+1=xk+
k*dk，即通过搜索方向和步长确定新的点
步5：根据上面的矫正公式求出新的Hk+1，转步1.
四.matlab程序实现
1.DFP算法封装函数
function [x,val,k]=dfp(x0,fun,gfun)
%功能：用DFP算法求解无约束问题
%输出：x，val，k分别表示近似最优解，近似最优值和迭代次数
%输入:x0,fun,gfun分别表示初始点，目标函数和目标函数的梯度
k=0;
maxk=5000;
rho=0.55;
sigma=0.4;
e=1e-5;%精度
n=length(x0);
Hk=eye(n);
while(k<maxk)
gk=feval(gfun,x0);%求梯度
if(norm(gk)<=e),break;end %判断是否满足停止迭代
dk=-Hk*gk;%确定搜索方向，这个公式课本有
mk=0;
m=0;
%用Armijo准则确定步长
while(m<20)
if(feval(fun,x0+rho^m*dk)<feval(fun,x0)+sigma*rho^m*gk'*dk)
mk=m;
break;
end
m=m+1;
end
x=x0+dk*rho^mk;%根据初始点，搜索方向和步长求出新的搜索点
g=feval(gfun,x);%这个就是新的初始点的梯度
sk=x-x0;%新的点减去原来的点
yk=g-gk;%新的点的梯度
%更新Hk
if(sk'*yk>0)
Hk=Hk-(Hk*yk*yk'*Hk)/(yk'*Hk*yk)+(sk*sk')/(sk'*yk);%公式
end
x0=x;
k=k+1;
end
x=x0;%break跳出后输出x
val=feval(fun,x);
end
2.目标函数
function f=fun(x)
%需要求解最优值的目标函数
f=100*(x(1)^2-x(2))^2+(x(1)-1)^2;
end
3.目标函数梯度
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.主函数
clear all
x0=[-1.2,1]';%设置的搜索初始点
[x,val,k]=dfp(x0,'fun','gfun');%调用函数
disp('迭代的次数k为:')
disp(k)
disp('近似最优解x为:')
disp(x)
disp('此时f(x)的值为：')
disp(val)
5.运行结果与分析
多试几个初始点后，就可以看到DFP算法的计算效率比不上BFGS算法。