单纯形法解决无约束优化问题Word格式文档下载.docx
《单纯形法解决无约束优化问题Word格式文档下载.docx》由会员分享，可在线阅读，更多相关《单纯形法解决无约束优化问题Word格式文档下载.docx（8页珍藏版）》请在冰点文库上搜索。
作业三
学生姓名：
学号：
提交时间：
一、问题重述
形如的
问题称为无约束优化问题，常用下降算法来解决这类问题。
下降算法的关键在于步长和搜索方向的选取。
步长的求取可以借助前面作业中提到的一维搜索等方法求取，而搜索方向算法可以分为两大类，解析法和直接法。
解析法借助了目标函数的导数进行搜索，这类算法搜索速度快、效率高，但是对目标函数的要求更为严格。
常用的方法有最速下降法、Newton法、共轭梯度法、拟Newton法等。
直接法不使用导数，也不需要得到目标函数的明确解析式，只需要能够得到某些函数上的点即可。
因此直接法的适用范围更广，但相应的收敛速度会较慢，计算量也会随着问题维数的增加而迅速增大。
常用的方法有单纯形法、Powell方向加速法以及Powell改进算法。
本作业以直接法的Powell法为例，解决具体的无约束优化问题，并对将Powell方向加速法和Powell改进算法解决结果进行对比。
二、算法原理
对于n维正定二次函数
，设
关于G共轭，
与
为任意不同点。
分别从
出发，依次沿
作一维搜索。
如果最后找到两个互不相同的极小点
，则
关于G共轭。
Powell方向加速法正是基于这一原理，每次迭代过程作n+1次一维搜索。
第一次沿给定的n个线性无关的方向
依次作一维搜索，之后沿由这一阶段的起点到第n次搜索所得到的点的方向P再做一次一维搜索，并把这次所得点作为下一阶段的起点，下一阶段的n个搜索方向为
。
以此直到找到最优解。
此算法是在迭代中逐次生成共轭方向，而共轭方向又是较好的搜索方向，所以称之为方向加速法。
但是，此算法产生的n个向量可能线性或近似线性相关，这时张不成n维空间，可能得不到真正的极小点。
因此，Powell原始算法存在一定的缺陷。
Powell改进算法虽然不再具有二次终止性，但克服了搜索方向的线性相关的不利情形，是解决无约束优化问题较有效的直接法之一。
本次作业一维搜索的过程是利用函数求导，求得最小值。
经过试验发现，α是允许为负数的。
否则最终寻优得到的极值点与实际结果存在很大的偏差，而且寻优的效率特别低下。
三、算法流程
Powell算法流程图：
图1Powell算法流程图
Powell改进算法流程图：
图2Powell改进算法流程图
四、实验验证
1、设目标函数
，收敛精度为0.001，初始点（-2,2）。
利用Matlab自带的函数求二元函数极值点函数fminsearch，求得极值点为（-0.630,-1.500），最小值为-1.722。
以此为标准，检验Powell方向加速法和Powell改进算法的寻优结果。
Powell方向加速法经过2次迭代，求得极值点（-0.630,-1.500），对应的最小值-1.722；
Powell改进方向加速法经过2次迭代，求得极值点（-0.630,-1.500），对应的最小值1.722。
2、设目标函数
利用Matlab自带的函数求二元函数极值点函数fminsearch，求得极值点为（0.5827,-1.7913），最小值为-1.5109。
Powell方向加速法经过4次迭代，求得极值点（0.5827,-1.7912），对应的最小值-1.5109；
两种方法对应的寻优过程如下图所示。
图3Powell直接与改进法寻优过程
四、算法程序
1、Powell方向加速关键部分算法：
error=0.001;
x_process=[-2,2];
dimensions=2;
P=[eye（dimensions）;
zeros（1,dimensions）];
%初始搜索方向
symsaerfa;
while
（1）
x_zero=x_process;
fori=1:
dimensions%沿着P（i,:
）方向进行一维搜索
f=F_Object（x_process+aerfa*P（i,:
））;
aerfa_process_all=double（real（solve（diff（f））））;
F_process_j=[];
forj=1:
length（aerfa_process_all）
aerfa_process=aerfa_process_all（j）;
x_process_j=x_process+aerfa_process*P（i,:
）;
F_process_j=[F_process_jF_Object（x_process_j）];
end
[~,j]=min（F_process_j）;
x_process=x_process+aerfa_process*P（i,:
ifnorm（x_process-x_zero）<
=error
break;
%可以避免之后分母中的（x_process-x_zero）过小而影响算法的进行
P（dimensions+1,:
）=（x_process-x_zero）/norm（x_process-x_zero）;
dimensions
P（i,:
）=P（i+1,:
f=F_Object（x_process+aerfa*P（dimensions+1,:
aerfa_process_all=double（real（solve（diff（f））））;
%一维搜索
x_process=x_process+aerfa_process*P（end,:
ifnorm（x_process-x_zero）<
end
2、Powell改进法关键部分算法：
symsaerfa;
dimensions=length（x_zero）;
F_process=zeros（dimensions+1,1）;
P=eye（dimensions）;
x_zero=x_process;
F_process
（1）=F_Object（x_zero）;
F_process（i+1）=F_Object（x_process）;
=errorbreak;
[F_Object_data,m]=max（F_process（1:
dimensions）-F_process（2:
dimensions+1））;
F_Object_xing=F_Object（2*x_process-x_zero）;
if（F_Object_xing>
=F_process
（1））||（（F_process
（1）2*F_process（dimensions+1）+F_Object_xing）*（F_process
（1）-F_process（dimensions+1）-F_Object_data）^2>
0.5*（F_process
（1）-F_Object_xing）^2*F_Object_data）
else
fori=m:
dimensions-1P（i,:
P（dimensions,:
f=F_Object（x_process+aerfa*P（dimensions,:
%一维搜索
升级会员 