第四章_约束优化方法.ppt

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,第四章 约束问题的最优化方法,4.1,引言,4.2,内点惩罚函数法,4.3,外点惩罚函数法,4.4,混合惩罚函数法,4.5,随机方向搜索法,4.6,复合形法,4.7,可行方向法,4.8,约束坐标轮换法,4.9,拉格朗日乘子法,4.1,引言,直接解法：随机方向搜索法、复合形法、可行方向法,间接解法：内点惩罚函数法、外点惩罚函数法、混合惩罚函数法,一,.,有约束问题解法分类：,二,.,直接解法的基本思想：,合理选择初始点，确定搜索方向，以迭代公式,x,(k+1),=x,(k),+,(k),S,(k),在可行域中寻优，经过若干次迭代，收敛至最优点。,收敛条件：,边界点的收敛条件应该符合,K-T,条件；,内点的收敛条件为：,4.1,引言,特点：,在可行域内进行；,若可行域是凸集，目标函数是定义在凸集上的凸函数，则收敛到全局最优点；否则，结果与初始点有关。,4.1,引言,目的,：将有约束优化问题转化为无约束优化问题来解决。,方法,：以原目标函数和加权的约束函数共同构成一个新的目标函数,(x,r,1,r,2,),，成为无约束优化问题。通过不断调整加权因子，产生一系列,函数的极小点序列,x,(k),*,(r,1,(k),r,2,(k),)k=0,1,2,，逐渐收敛到,原目标函数的约束最优解,。,三,.,间接解法的基本思想：,有解的条件：,f(x),和,g(x),都连续可微；,存在一个有界的可行域；,可行域为非空集；,迭代要有目标函数的下降性和设计变量的可行性。,4.1,引言,新目标函数：,其中：惩罚项：,加权因子，即惩罚因子,：,r,1,r,2,函数的极小点序列,x,(k),*(r,1,(k),r,2,(k),)k=0,1,2,其收敛必须满足：,无约束优化问题：,4.1,引言,不等式约束优化问题,三,.,约束优化问题的类型：,等式约束优化问题,一般约束优化问题,4.2,内点惩罚函数法,一,.,惩罚函数法简介,：,惩罚函数法是一种求解约束优化问题的间接解法，它将约束优化问题转化为一系列无约束优化问题来求解，又称为序列无约束极小化技术（,Sequential Unconstrained Minimization Technique,），即,SUMT,法。,惩罚函数的值一般总是大于原目标函数的值，表示它对目标函数的惩罚作用。为了使惩罚函数最后能够收敛到目标函数的同一最优解，应该做到：,一方面要恰当地构造关于约束函数的复合函数，在求解惩罚函数极小化的过程中，当迭代点不满足约束条件时，两个惩罚项的函数值增大，使目标函数得到“惩罚”；另一方面，随着迭代次数的增大，惩罚因子的数值不断调整（递增或递减），惩罚项对惩罚函数的惩罚作用越来越小并趋于消失，无约束最优点序列不断逼近约束目标函数的最优点。,42,内点惩罚函数法（障碍函数法）,二,.,内点惩罚函数法基本思想：,内点法将新目标函数,(x,r),构筑在,可行域,D,内,，随着惩罚因子,r,(k),的不断,递减,，生成一系列新目标函数,(x,k,r,(k),),，在可行域,内,逐步迭代，产生的极值点,x,k,*(r,(k),),序列从可行域,内,部趋向原目标函数的约束最优点,x*,。,例,4-1,：求下述约束优化问题最优点。,min.f(x)=x x R,1,s.t g(x)=1-x 0,X,1,*,X,2,*,X,*,4.2,内点惩罚函数法,三,.,内点惩罚函数的形式,：,其中：惩罚（加权）因子,降低系数,c,：,0 c 1,4.2,内点惩罚函数法,四,.,步骤：,选取合适的初始点,x,(0),，以及,r,(0),、,c,、计算精度,1,、,2,，令,k=0,；,2.,构造惩罚（新目标）函数；,3.,调用无约束优化方法，求新目标函数的最优解,x,k,*,和,(x,k,r,(k),),；,4.,判断是否收敛：运用终止准则,若均满足，停止迭代，有约束优化问题的最优点为,x*=x,k,*,；,若有一个准则不满足，则令,并转入第,3,步，继续计算。,4.2,内点惩罚函数法,五,.,几个参数的选择：,惩罚因子初始值,r,(0),的选择：,过大、过小均不好，,建议考虑选择：,2.,降低系数,c,的选择：,c,的典型值为,0.1,0.002,。建议先试算。,3.,初始点,x,(0),的选择,：,要求：,在可行域内；,不要离约束边界太近。,方法：,人工估算，需要校核可行性；,计算机随机产生，也需校核可行性。,4.2,内点惩罚函数法,方法：,搜索方法：,任意给出一个初始点；,判断其可行性，若违反了,S,个约束，求出不满足约束中的最大值：,应用优化方法减少违反约束：,以求得的设计点作为新初始点，继续其判断可行性，若仍有不满足的约束，则重复上述过程，直至初始点可行。,4.2,内点惩罚函数法,六,.,方法评价：,用于目标函数比较复杂，或在可行域外无定义的场合下：,由于优化过程是在可行域内逐步改进设计方案，故在解决工程问题时，只要满足工程要求，即使未达最优解，接近的过程解也是可行的；,初始点和序列极值点均需严格满足所有约束条件；,不能解决等式约束问题。,4.2,内点惩罚函数法,例,4-2,：,盖板问题,b,h,t,s,t,f,设计一个箱形截面的盖板。,已知：长度,l,0,=600cm,，宽度,b=60cm,，侧板厚度,t,s,=0.5cm,，翼板厚度为,t,f,(cm),，高度为,h(cm),，承受最大的单位载荷,q=0.01Mpa,。,要求：在满足强度、刚度和稳定性等条件下，设计一个最轻结构。,设计分析,：,（略）,数学模型：,4.2,内点惩罚函数法,优化方法,：,选用内点惩罚法，惩罚函数形式为：,调用,Powell,法求序列无约束优化极值，以逐渐逼近原问题的极值点。,4.2,内点惩罚函数法,4.,求解过程分析：,4.3,外点惩罚函数法,(,衰减函数法）,一,.,基本思想：,外点法将新目标函数,(x,r),构筑在,可行域,D,外,，随着惩罚因子,r,(k),的不断,递增,，生成一系列新目标函数,(x,k,r,(k),),，在可行域,外,逐步迭代，产生的极值点,x,k,*(r,(k),),序列从可行域,外,部趋向原目标函数的约束最优点,x*,。,例,4-3,：求下述约束优化问题最优点,min.f(x)=x x R,1,s.t g(x)=1-x 0,新目标函数：,4,4.3,外点惩罚函数法,二,.,惩罚函数的形式：Z,一般取,2,。,因为在约束面处,f(x),与,(x),当,Z=0,时，函数不连续；,当,0Z1,时，一阶、二阶导数不连续；,当,Z=1,时，一阶导数连续，二阶导数不连续。,0Z1,4.3,外点惩罚函数法,说明：,4.3,外点惩罚函数法,三,.,几个参数的选择：,r,(0),的选择,:,r,(0),过大，会使惩罚函数的等值线变形或偏心，求极值困难。,r,(0),过小，迭代次数太多。,x,(0),的选择：,基本上可以在可行域内外，任意选择。,递增系数,a,的选择,：,通常选择,5,10,，可根据具体题目，进行试算调整。,4.3,外点惩罚函数法,终止准则和约束裕量：,终止准则：,约束裕量：当必须严格满足约束条件时，选用约束裕量,。,g=g+,g,0,0,4.3,外点惩罚函数法,四,.,步骤：,2.,构造惩罚（新目标）函数，调用无约束优化方法，求新目标函数 的最优解,x,k,*,和,(x,k,r,(k),),；,3.,4.,判断是否收敛：运用终止准则,若均满足，停止迭代，有约束优化问题的最优点为,x*=x,k,*,；,若有一个准则不满足，则令,并转入第,2,步，继续计算。,1.,选择合适的初始点,x,(0),，并选择,r,(0),a,1,2,0,，令,k=0,；,4.3,外点惩罚函数法,五,.,方法评价：,初始点原则上可任意选择,;,能解决等式约束问题,;,由于优化过程是在可行域外进行，故在解决工程问题时，过程解均不可行。,4.4,混合惩罚函数法,一,.,基本思想,：,采用内点法和外点法相结合的混合惩罚函数法，以发挥内点法和外点法的特点，处理既有等式约束，又有不等式约束的优化设计问题。,二,.,惩罚函数的形式：,一般既包括障碍项，也包括衰减项。,4.4,混合惩罚函数法,其中：,4.5,随机方向搜索法,一,.,基本思想：,随机产生初始点，随机产生搜索方向,S,(k),，进行搜索。,但要确保：新迭代点在可行域中；目标函数值的下降性。,二,.,随机数的产生：,1.,伪随机数,：,用数学模型，从计算机（的随机数发生器）中产生的随机数。,随机数的特性,有较好的概率统计特性,抽样的随机性；,分布的均匀性；,前后数之间的独立性；,周期性长。,4.5,随机方向搜索法,给出,随机数,t,0,=2z 1;,用递推公式：,t,i,=t,i-1,(mod M),，产生,随机数列,t,0,t,1,t,2,其中：,乘,子；,mod M,整除,M,取,余,数；,t,i,=t,i-1,乘以,后除以,M,所得的余数。,3.,乘同余法：,4.5,随机方向搜索法,4.,产生任意区间内的伪随机数列,：,三,.,随机产生初始点：,估计设计变量的上、下限：,x,i,l,x,i,x,i,u,，,i=1,2,n,；,在区间,0,1,中产生伪随机数列,r,i,，,x,i,(0),=x,i,l,+r,i,(x,i,u,-x,i,l,),；,判断是否,g,u,(x,i,(0),)0,；若满足，则,x,(0),=x,i,(0),若不满足，则转向。,4.5,随机方向搜索法,四,.,随机产生搜索方向：,x,(0),x,(m),x,(1),x,(2),x,(j),x,(,l,),H,(0),4.5,随机方向搜索法,五,.,步骤：,X,(k+1),均是，转判,2,随机方向法流程图,随机方向法搜索过程,4.5,随机方向搜索法,六,.,方法评价：,优点：,对目标函数无性态要求；,收敛快（当,m,足够大时）；,不受维数影响，维数愈高，愈体现优点。,缺点：,对于严重非线性函数，只能得近似解；,当,m,不够大时，解的近似程度大；,对于非凸函数，有可能收敛于局部解。,例,4-4,二维约束优化问题,试用两个随机数 构成第,K,次搜索的随机方向 ，,由当前点 出发，按照该方向取步长 计算各个迭代,点，确定该方向的终点,解：随机方向和新点：,适用性检验：,新点函数值小于旧点函数值，该点适用,可行性检验：,该点可行。因此，新点 是成功点,令 ，按照原来的步长和方向继续迭代，得到新点：,适用性检验：,可行性检验：,该点不可行。因此，该方向的极小点是：,新点函数值小于旧点函数值，该点适用,其函数值：,4.6,复合形法,一,.,单纯形法：,定义,：,基本思想,：,以一个目标函数值较小的新点，代替原单纯形中目标函数值最大的顶点组成新的单纯形，这样不断地迭代，单纯形逐渐逼近最优点。,以二维空间中的映射法为例,：,X,(1),=X,(H),X,(2),X,(3),X,(S),X,(R),=X,(4),X,(5),X,(6),在,n,维空间中，由,n+1,个点组成的图形称单纯形。,X*,4.6,复合形法,二,.,复合形法：,定义,：,在,n,维空间中，由,kn+1,个点组成的多面体称为复合形。,基本思想,：,以一个较好的新点，代替原复合形中的最坏点，组成新的复合形，以不断的迭代，使新复合形逐渐逼近最优点。,说明：,单纯形是无约束优化方法，而复合形可用于约束优化的方法。,因为顶点数较多，所以比单纯形更灵活易变。,复合形只能解决不等式约束问题。,因为迭代过程始终在可行域内进行，运行结果可靠。,4.6,复合形法,三,.,迭代方法,：,1.,映射法,：,例：二维空间中，,k=4,，复合形是四面体,x,(1),x,(2),x,(3),x,(4),，计算得：,f(x,(1),)f(x,(2),)f(x,(3),)1,，建议先取,1.3,。,映射迭代公式,：,x,(R),=x,(S),+(x,(S),x,(H),),若求得的,x,(R),在可行域内，且,f(x,(R),)5,时，,k,的取值可小些。,初始复合形的三个顶点为：,例,4-5,用复合形法求二维约束优化问题的最优解,解：,1.,检验初始复合形各个顶点的可行性，经过检验（略），全部,顶点都在可行域内。,2.,计算初始复合形各个顶点的目标函数值：,得到坏点：好点：,3.,去掉坏点的其他各顶点的几何中心：,取映射系数 ，计算映射点：,用映射点 取代坏点 ，构成一个新的复合形，它的三个顶点是：,满足约束条件，是可行点,4.,计算：,5.,第二个复合形的迭代计算（略）,4.7,可行方向法,一,.,基本思想：,在第,k+1,次迭代时，从,x,(k),点出发，寻找一个可行的搜索方向和合适的步长因子，从而得到一个可行、目标函数值下降的新点,x,(k+1),，再以此点出发，寻找新点，直至满足收敛条件，得到最优点,x*,。,(k),的选择原则：,使新点,x,(k+1),在可行域内。,S,(k),的选择原则：,必须是可行方向，即必须与所有适时约束的梯度方向成钝角。,必须是目标函数值下降的方向，即必须与目标函数的负梯度方向成锐角。,同时满足以上两个条件的方向，称为,适用可行方向,。,4.7,可行方向法,二,.,搜索策略：,可根据目标函数和约束函数的不同性态，选择不同的搜索策略。,边界反弹法,：,第一次搜索为负梯度方向，终止于边界。以后各次搜索方向均为适用可行方向，以最大步长从一个边界反弹到另一个边界，直至满足,K-T,条件。,最优步长法：,第一次搜索为负梯度方向，终止于边界。第二次搜索沿适用可行方向作一维搜索以最优步长因子求得最优点。反复以上两步，直至得到最优点x*,。,4.7,可行方向法,贴边搜索法,：,第一次搜索为负梯度方向，终止于边界。以后各次搜索贴边（约束面）进行。,若适时约束面是切面，每次搜索到约束面的交集时，移至另一个约束面，直至收敛到最优点。,若可行域是凸集，约束面是非线性时，从,x,(k),点沿切线（面）方向,s,(k),搜索，会进入非可行域。,容差带,：,建立约束面的容差带,+,，从,x,(k),出发，沿,s,(k),方向搜索到,s,(k),方向与,g(x)+=0,的交点,x,后，再沿适时约束的负梯度方向返回约束面的,x,(k+1),点。,4.7,可行方向法,调整步长因子,1,：,4.7,可行方向法,三,.,适用可行方向产生的方法梯度投影法,：,A,u,B,uA,S,(k),S,(k),4.7,可行方向法,简化计算法：,有关步长因子和步骤，请自学。,4.8,约束坐标轮换法,一,.,基本思想：,对,n,维约束优化问题，依次沿着相应的,n,个坐标轴方向进行一维搜索优化，并且对获得的每一个迭代点都进行可行性条件和适用性条件的检查。,约束坐标轮换法的基本思 想与无约束坐标轮换法基本相同，其主要区别如下：,1,、沿坐标方向搜索的迭代步长采用加速步长，而不是采用最优步长。因为按照最优步长所得到的迭代点往往超出了可行域。,2,、对于每一个迭代点，不仅要检查目标函数值是否下降，而且必须检查是否在可行域内，即进行适用性和可行性的检查二,.,与无约束坐标轮换法区别：,x,2,x,1,x,0,x,1,1,x,2,1,x,3,1,x,1,2,x,2,2,x,3,2,x,A,x,C,x,D,x,B,当迭代点到达,x,1,3,点，无论沿,e,1,或,e,2,方向搜索，所得到的四个邻近点都不能同时满足可行性与适用性的要求时，取,x,1,3,作为最优解，,但显然它就是一个伪最优点。,x,1,3,约束坐标轮换法算法明了、,迭代简单、便于掌握和运用。,但其收敛速度较慢，而且在某些情况下，会出现“死点”。,4.8,约束坐标轮换法,三,.,伪最优点：,四,.,方法评价：,等式约束时极值存在的必要条件：,称为拉格朗日乘子,4.9,拉格朗日乘子法,一,.,基本思想：,对于目标函数为,f,(,x,1,x,2,),，等式约束为,g,(,x,1,x,2,)=0,，极值点存在的必要条件是：,由上式可得：,4.9,拉格朗日乘子法,由上式可得：,上式相当于求解一个无约束的函数：,的极值点，,L,称为拉格朗日函数，此函数极值点存在的必要条件为：,4.9,拉格朗日乘子法,二,.,求解等式约束问题的步骤：,目标函数为,f,(,X,),，为,n,维变量，有,m,个等式约束条件：,函数,L,为极小的必要条件为：,则拉格朗日函数为：,三,.,求解不等式约束问题的步骤：,不等式约束条件为：,引入松弛变量,x,3,，,使上式变成如下等式约束：,例,4-6,二维函数 ，等式约束为,，试用拉格朗日乘子法求其极小值。,解：构造拉格朗日函数：,拉格朗日函数为极小的必要条件：,例,4-7,二维函数 ，试用拉格朗日乘子,法求其极小值。等式约束为,解：引入松弛变量,x,3,，,x,4,：,构造拉格朗日函数：,上式可以用等式约束中的直接寻优法求解。,