有约束优化问题

分数:___________任课教师签字：___________课程作业学年学期：2017——2018学年第二学期课程名称：优化理论作业名称：作业四学生姓名：学号：提交时间：一、问题重述形如下式的寻优问题称为无约束最优化问题，这类问题的最优解称为约束最优解。minf(x)..(x)0,i1,...ph(x)0,j1,...q0,0ijstgpq约束优化问题的最优性条件是，在满足灯饰和不等式约束条件下，其目标函数值最小的点所必须满足的条件。约束优化设计问题求解方式有两种，间接法和直接法。直接法是在满足不等式约束的可行设计区域内直接搜索问题的最优解和最小值，常用的方法有随机方向法、复合形法。间接法是将优化问题转化为一系列无约束优化问题来求解，常用的方法有内惩罚函数法、外惩罚函数法以及混合惩罚函数法。本次作业以为例，介绍无约束最优化问题的寻优方法。二、算法原理复合形法是求解约束非线性寻优问题的一种重要的直接方法。复合形法的核心在于可行域内构造的不断逼近最优点的复合形。每次迭代，计算各顶点的目标函数值，找到目标函数值最大的顶点(称最坏点)，然后按相应的原则求出目标函数可行的下降点，以此代替最坏点，构成新的复合形。复合形每改变一次，各个顶点就向最优点移动一步，直至满足终止条件，找到最优点。复合形法的顶点数K通常取12nKn，其中n表示搜索环境的维度。初始图形的顶点是由设计者确定或者随机产生的，但一定要保证在可行域内。如果随机产生的初始点没有在可行域内，可以通过以下步骤将其调入可行域内。（1）计算在可行域内点的初始点集中心X(s);（2）将可行域外的点向X(s)靠拢，每次前进间距的一半，直至进入可行域内。复合行法的终止条件可以有以下几种形式，满足终止条件后，可将最后复合形的好点及其函数值作为最优解输出。（1）各顶点与好点函数值之差的均方根小于误差限；（2）各顶点与好点的函数之差平和小于误差限；（3）各顶点与好点函数值差的绝对值之和小于误差限。另外，需要注意的是复合形法只能求解仅含不等式约束的问题。三、算法流程复合形算法的流程图：开始顶点数K产生K个随机点将非可行点调入可行域构造复合形计算各顶点的函数值，选出好点、坏点计算坏点外的其余各顶点的中心点计算映射点，并将映射点调入可行域内映射点代替坏点不满足终止条件映射点优于坏点多次调整系数映射点优于坏点改变映射方向最优点最小值开始最后的好点作为最优点YNYNNY图1复合形法算法流程四、实验验证用Matlab自带的fmincon函数求得的约束最优解作为标准值，以此检验复合形算法的准确度。用复合形法求解下列问题的约束最优解2212121211223142512min(x)6010x4..(x)x0(x)x10(x)6x0(x)8x0(x)x110fxxxxxstgggggx表1结果对比标准值复合形法最小值点（6,4.999）最小值点（6,4.992）最小值11.000011.0000可见编写的复合形法准确度还是蛮高的。四、算法程序复合形法关键算法：clc;clearall;closeall;%%%%%%%%%%%%%%部分参数初始值area=1.3;error=0.0000000000001;%误差限k=4;%复合形顶点数dimensions=2;%搜索空间的维度a=[-10,-10];%初始点1b=[10,10];%初始点2c=zeros(1,2);x_in=[];%%%%%%%%%%%%%产生初始随机点，保证至少有一个点在可行域内whileisempty(x_in)x_in=[];x_out=[];fori=1:k%产生初始随机点c(1)=a(1)+rand*(b(1)-a(1));c(2)=a(2)+rand*(b(2)-a(2));ifInequal(c)=0x_in=[x_in;c];elsex_out=[x_out;c];endendend%%%%%%%%%%%%%%将不在可行域内的随机点调入可行域内while~isempty(x_out)x_in_mean=mean(x_in,1);x_out(1,:)=x_in_mean+0.5*(x_out(1,:)-x_in_mean);ifInequal(x_out(1,:))0x_in=[x_in;x_out(1,:)];x_out(1,:)=[];endend都在可行域内的随机点x_zero=x_in;%%%%%%%%%%%%迭代复合形算法F=zeros(1,k);while(1)fori=1:kF(i)=Fmin(x_zero(i,:));end[F_L,x_L_i]=min(F);%好点[F_H,x_H_i]=max(F);%坏点J=(F-F_L)*(F-F_L)';%各顶点与好点的函数值之差的平方和ifJerror%终止条件break;endflag=1;x_SH_i=x_H_i;while(flag==1)%需要改变映射方向,即改变x_SH_iflag=0;j=1;%表示次最大点x_SH=x_zero(x_SH_i,:);x_0=(sum(x_zero,1)-x_SH)/(k-1);%除坏点外的其余各项中心点x_R=x_0+area*(x_0-x_SH);%映射点area_part=area*0.5;%求在可行域内的映射点while(Inequal(x_R)0)%不在可行域内x_R=x_0+area_part*(x_0-x_SH);%映射点调入可行域area_part=area_part*0.5;endwhile(Fmin(x_R)=F_H)x_R=x_0+area_part*(x_0-x_SH);%认为映射过远，减半映射area_part=area_part*0.5;ifarea_part0.0000001%经过多次映射，仍无法满足flag=1;%需要改变映射方向,即改变x_SH_i[~,x_Fdescend_i]=sort(F,'descend');j=j+1;x_SH_i=x_Fdescend_i(j);%表示次j最大点break;endendend%此时映射点优于坏点x_zero(x_H_i,:)=x_R;%映射点代替坏点endx_zero(x_L_i,:)%最优点F_L%最小值%%%%%%%%%%%%%%%%%Matlab自带的求约束条件的极小值点A_Limit=[-10;0-1;10;01;11];%约束条件矩阵b_Upper=[0;-1;6;8;11];[xmin,fmin]=fmincon(@Fmin,c,A_Limit,b_Upper,[],[],[],[],[])目标函数%寻优目标函数functionoutput=Fmin(x)x1=x(1);x2=x(2);output=60-10*x1-4*x2+x1*x1+x2*x2-x1*x2;约束条件%不等式约束条件functionoutput=Inequal(x)x1=x(1);x2=x(2);g(1)=-x1;g(2)=-x2+1;g(3)=-6+x1;g(4)=-8+x2;g(5)=x1+x2-11;ifisempty(g(g0))output=1;%满足约束条件elseoutput=-1;%不满足约束条件end