最优化DFP算法 姓名：施 政 学号：1010010125 班级：1 班 专业：通信与信息系统 目 录 1 算法流程图..............................................................................................................1 1.1 DFP算法的流程图.......................................................................................1 1.2 黄金分割法流程图.......................................................................................1 1.3 回退法计算初始区间的算法.......................................................................2 2 测试函数..................................................................................................................3 2.1 二维、二次函数...........................................................................................3 2.2 二维、高次函数...........................................................................................3 2.3 高维、二次函数...........................................................................................4 2.4 高维、高次函数...........................................................................................4 3 运行结果及分析......................................................................................................5 4 Matlab源程序........................................................................................................6 4.1 主函数...........................................................................................................6 4.2 DFP算法函数................................................................................................8 4.3 黄金分割法函数...........................................................................................9 4.4 回退法求解初始区间.................................................................................10 4.5 计算测试函数的值.....................................................................................11 4.6 计算测试函数的梯度.................................................................................12 5 参考文献................................................................................................................12 南京邮电大学2010级通信与信息系统专业 2010-11-8
11 算法流程图 对于DFP算法主要涉及到3个主要的算法，分别是：利用回退法计算初始区间、利用黄金分割法进行一维搜索、然后利用DFP算法计算最小点对应的自变量的值。 下面分别画出了这三个算法流程图。
1.1 DFP算法的流程图
设定控制误差为ε；输入的初始点坐标是0x；0E是与0x同维的单位阵。
图 1 1.2 黄金分割法流程图 给定精确度ε>0;当区间长度小于等于ε时，即停止运行，同时取x=(a+b)/2作为最小点坐标。 在给定初始区间[a,b]内，求最小点时对应的α值，要保证α是大于等于零的，否则函
数值就不是朝下降方向递降的了。在本算法中保证初始区间的端点是大于等于零的，就可以满足这一条件了。 算法如下图所示：
N Y Start DFP_algorithm x1=x0; H1=H0=E0;计算 x0对应的梯度g1=g0
g1的范数大于
ε
Optimal_x=x0
END function
p0=-H0* g0;把x0和 g0;作
为参数传给黄金分割法的函数；求出最优的α；
求出100*xapα=+；求出g1；利用DFP修正公
式更新H1；
k=k+1 南京邮电大学2010级通信与信息系统专业 2010-11-8
2 图 2 1.3 回退法计算初始区间的算法 针对这个算法,参考文献[1]上面利用的回退法不能保证a，b两个端点的值大于零，因为利用黄金分割法求α时，α肯定是大于等于零的，所以可以对书上的算法适当的改进。初
始的点是0x；步长是xΔ；算法如下：
图 3 注意：上面的算法是针对一维的情况，所以在计算0x；1x；2x时，应该注意使
Y N N Y
Start initial_interval x0，f(x0) x1= x0+Δx;f(x1)
f(x0)<= f(x1) Δx=2 Δx; x2= x1+Δx; f(x2) a= x0; b= x1 End function f(x0)<= f(x2)
a= x0; b= x2
x0=x1;x1=x2;f(X0)=f(X1);f(X0)= f(X1)
Y N N Y N Y x1=a+0.382*(b-a);f(x1) x2=a+0.618*(b-a); f(x2)
|b-a|<=ε α=(a+b)/2
End function
Start golden_section_method f(x1)< f(x2) f(x1)> f(x2) b= x2; x2 = x1; f(x2)=f(x1) x1=a+0.382*(b-a);f(x1) a= x1; x1 = x2; f(x1)= f(x2) x2=a+0.618*(b-a); f(x2)
a = x1 ; b = x2 南京邮电大学2010级通信与信息系统专业 2010-11-8
3用0000*xatp=+；0a代表的是对应DFP算法上次迭代的自变量的坐标值，0p代表的是0
a
点的梯度，0t开始的值是0；同样有1010*xatp=+；2020*xatp=+；10ttt=+Δ；21ttt=+Δ。注意tΔ的变化，算法中已显示其变化规律。
2 测试函数 2.1 二维、二次函数 对于二维、二次的测试函数，算法中应用的是First De Jong function(sphere) [3]。
221212(,)fxxxx=+
…………………………………………..（式2.1）
下面就是函数对应的3维图形，从图4可以看出其最小点，在(x1,x2)=(0,0),该点对应的
函数值是0。也是该函数全局极小点。
-1-0.500.51-1-0.500.5100.511.52
图 4 2.2 二维、高次函数 对于二维、高次的测试函数，算法中应用的是Goldstein-Price's function[3]。 2222121211212(,)(1(1))(191431463))Goldfxxxxxxxxxx=+++•−+−++•
2212112122(30(23)2)(1832483627))xxxxxxxx+−•−++−+
………..（式2.2）
其中，22,1,2ixi−≤≤= 下面就是该函数对应的三维图形，该函数的全局极小点是(x1,x2)=(0,-1)，f(x1,x2)=3。