机械优化设计方法第六章约束最优化方法.ppt

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,第六章 约束最优化方法,6-1,概 述,约束最优化问题是：求,n,维设计变量,X=,x,1,x,2,x,n,T,，受约束于,g,u,(,X,)0(,u,=1,2,m,),，,h,v,(,X,)=0(,v,=1,2,pn,),，使目标函数为,min,f,(,X,)=,f,(,X,*,),，则称,X*,为最优点，,f,(,X,*,),为最优值。,机械优化设计问题和一般工程实际优化问题绝大多数属于约束非线性规划问题。,约束最优化问题的解法很多，归纳起来可分为两大类。,一类是直接方法，即直接用原来的目标函数限定在可行域内进行搜索，且在搜索过程中一步一步地降低目标函数值，直到求出在可行域内的一个最优解，属于直接方法的有约束变量轮换法、随机试验法、随机方向搜索法、复合形法、可行方向法等。,另一类是间接方法，即将约束最优化问题，通过变换转成为无约束最优化问题然后采用无约束最优化方法得出最优解属于间接方法的有消元法、拉格朗日乘子法、惩罚函数法等。,约束最优化问题算法收效速率的判断比无约束最优化问题困难，约束最优化问题的研究和进展情况远不如无约束优化问题。,6-2,约束随机方向搜索法,一、基本原理,基本原理可用图,6-1,所示二维最优化问题进行说明。,在约束可行区域,D,内，任意选择一个初始点,X,(0),，以给定的初始步长,=,0,沿着随机方向,S,(1),取得探索点,X=X,(0),+,S,(1),若该点同时符合,下降性,(,即,f,(,X,),f,(,X,(0),),和可行性,(,即,XD,),要求，则表示,X,点探索成功。,并以它作为新的起始点，即,X,X,(0),，继续按上面的迭代公式在,S,(1),方向上获取新的探索成功点。,重复上述步骤，迭代点可沿,S,(1),方向前进，直至到达某搜索点不能同时符合下降性和可行性要求时停止。,此时废弃该搜索点并退回到前一个搜索成功点作为,S,(1),方向搜索中的最终成功点，记作,X,(1),。,此后，将,X,(1),点置为新的始点,X,(1),X,(0),，再产生另一随机方向,S,(2),，以步长,重复以上过程，得到沿,S,(2),方向的最终成功点,X,(2),。,经若干循环，点列,X,(,k,),(,k,=1,2,),必最后逼近约束最优点,X*,。,若在初始点,X,(0),或某个换向转折点处,(,如图中的,X,(1),点,),，沿某随机方向的探索点目标函数值增大,(,如图中的,A,点、,C,点,),或者越出可行域,(,如图中的,B,点、,D,点,),则应相应弃去该随机方向,重新产生另一随机方向进行探索。探索成功继续前进,探索失败再重新产生随机方向。,当在某个转折点处,(,如图中的,X,(2),点,),，沿,N,max,(,预先限定在某个转折点处产生随机方向所允许的最大数目,),个随机方向以步长,进行探索均失败，可以反映以此点为中心、,为半径的圆周上各点均难同时符合下降性和可行性条件。,此时可将步长,缩半后继续试探，直到,已缩减到预定精度,以下,(,即,),，且沿,N,max,个随机方向都探索失败时，则以最后一个成功点,(,如图中的,X,(3),点,),作为达到预定精度要求的约束最优点，结束迭代。,N,max,一般可在,50500,范围内选取，对目标函数性态不好的应取较大的值，以提高解题成功率。,二、初始点的选择,随机方向搜索法的初始点,X,(0),必须是一个可行点，即必须满足全部约束条件,g,u,(,X,)0(,u,=1,2,m,),通常有两种方法：,(,一,),人为给定,：即在设计的可行区域,D,内人为地确定一个可行的初始点。,(,二,),随机选定,：即利用电子计算机产生的伪随机数来选择一个可行的初始点,X,(0),。,此时需要送入设计变量估计的上限和下限，以图,6-2,所示二维情况为例，,X,=,x,1,x,2,T,，,a,1,x,1,b,1,，,a,2,x,2,b,2,。,在,0,，,1,区间内产生两个随机数,r,1,和,r,2,，,0,r,1,1,，,0,r,2,1,，,以,x,1,(0),=,a,1,+,r,1,(,b,1,a,1,),x,2,(0),=,a,2,+,r,2,(,b,2,a,2,),作分量获得随机初始点,X,=,x,1,(0),x,2,(0),T,。,同理，若对,n,维变量估计其上限和下限：,a,i,x,i,b,i,(,i,=1,2,n,)(6-1),在,0,，,1,区间内产生,n,个随机数,r,i,，,0,r,i,1(,i,=1,2,n,),这样随机产生的初始点,X,(0),的各分量为,x,i,(0),=,a,i,+,r,i,(,b,i,a,i,)(,i,=1,2,n,)(6-2),r,i,0,1,区间内服从均匀分布的伪随机数列。许多计算机本身就有发生随机数的功能，可直接调用。,需要指出，这样产生的初始点,X,(0),=,x,1,(0),x,2,(0),x,n,(0),T,虽能满足设计变量的边界条件，但不一定能满足所有约束条件,(,如点,),。,因此这样产生的初始点还须经过可行性条件的检验，如能满足，才可作为一个可行的初始点。否则，应重新随机选初始点，直到满足所有的约束条件。,三、随机搜索方向的产生,以图,6-3,所示二维情况说明随机向量的产生。,设,y,1,，,y,2,是在区间,(-1,，,+1),上的两个随机数。将它们分别作为,x,1,，,x,2,坐标轴上的分量所构成的向量即为相应的二维随机向量。,其单位向量,如,y,1,y,2,区间,(-1,，,+1),上的另外两个随机数，同样相应构成另一个二维随机向量，其单位向量为,S,。这些二维随机单位向量的端点分布于半径为单位长的圆周上。,同理类推，对于一个,n,维优化问题，随机方向单位向量可按下式计算：,y,i,(,i,=1,2,n,),是在,n,个坐标轴上随机向量的分量，它由规定在,(-1,，,+1),区间的随机数取得。,有些计算机具有直接调用的功能，但有些计算机则无此功能，需要另编程序。如可获得,(0,，,1),区间内服从均匀分布的随机数数列,r,i,(,i,=1,2,n,),，则可通过下式,y,i,=,a,i,+,r,i,(,b,i,-,a,i,)(,i,=1,2,n,),转化成在,(,a,i,，,b,i,),区间内服从均匀分布的随机数数列。,以,a,i,-1,，,b,i,1,代入上式，可得,(-1,，,+1),区间内服从均匀分布的随机数数列,y,i,=,2,r,i,-1,由于,y,i,在区间,(-1,，,+1),内产生，因此所构成的随机方向单位向量端点一定位于,n,维的超球面上。,四、迭代过程及算法框图,(1),给定设计变量数目,n,初始变量估计的上下限,a,i,b,i,(,i,=1,2,n,),，初始步长,0,，步长收敛精度,，产生随机方向最大次数,N,max,。,(2),随机产生初始点。,(3),X,(0),X,，,f,(,X,),f,0,，,0,。,(4),置,1,k,，,0,jj,。,(5),在,(-1,+1),区间产生随机数,y,i,(,i,=1,2,n,),，获得单位随机向量，沿,S,方向迭代得迭代新点,X=X,(0),+,S,。,(6),检验新点,X,的可行性。若满足,g,u,(,X,),0,(,u,=1,2,m,),，则进行第,(7),步；否则转向第,(9),步。,(7),检验新点,X,的下降性。计算,f,(,X,),f,，若,f,N,max,，则进行第,(11),步；否则返回第,(5),步。,(11),若,，则输出最优解：,X,X*,，,f,(,X,),f,(,X,*,),，可终止迭代；否则,将步长减半,即,0.5,返回第,(4),步，继续迭代。,随机方向搜索法的算法框图如图,6-4,所示。,6-3,复合形法,一、基本原理,复合形法的,基本思路,在,n,维空间的可行域中选取,K,个设计点,(,通常取,n,+1,K,2,n,),作为初始复合形,(,多面体,),的顶点。,然后比较复合形各顶点目标函数值的大小，其中目标函数值最大的点为坏点,以坏点之外其余各点的中心为映射中心，寻找坏点的映射点，一般说来此映射点的目标函数值总是小于坏点的，也就是说映射点优于坏点。,这时，以映射点替换坏点与原复合形除坏点之外其余各点构成,K,个顶点的新的复合形。,如此反复迭代计算，在可行域中不断以目标函数值低的新点代替目标函数值最大的坏点从而构成新复合形，使复合形个断向最优点移动和收缩，直至收缩到复合形的各顶点与其形心非常接近、满足迭代精度要求时为止。,输出复合形各顶点中的目标函数值最小的顶点作为近似最优点。,现以图,6-5,所示二维不等式约束优化问题来作进,步说明。,其数学模型为,D,：,g,1,(,X,),0,g,2,(,X,),0,a,1,x,1,b,1,a,2,x,2,b,2,其中，,g,1,(,X,),0,，,g,2,(,X,),0,可称为隐式约束条件，而边界约束,a,1,x,1,b,1,，,a,2,x,2,b,2,可称为显式约束条件。,在可行域内先选定,X,(1),、,X,(2),、,X,(3),、,X,(4),四个点,(,这里取,K=,2,n=,22=4),作为初始复合形的顶点，计算这四个点的目标函数值，并作比较，得出坏点,X,(,H,),和好点,X,(,L,),：,X,(,H,),：,f,(,X,(,H,),)=max,f,(,X,(,j,),),j,=1,2,K,（,6-7,）,X,(,L,),：,f,(,X,(,L,),)=min,f,(,X,(,j,),),j,=1,2,K,（,6-8,）,由图,6-5,，可以看出点,X,(4),为好点，点,X,(1),为坏点，即,X,(4),X,(,L,),，,X,(1),X,(,H,),。以,X,(2),、,X,(3),、,X,(4),三点的中心,X,(,C,),为映射中心，寻找坏点,X,(,H,),的映射点,X,(,R,),：,X,(,R,),X,(,C,),+(,X,(,C,),-,X,(,H,),)(6-9),为映射系数，通常取,1.3,。,计算映射点,X,(,R,),处目标函数,f,(,X,(,R,),),与坏点目标函数值,f,(,X,(,H,),),相比是否下降。并同时检查,X,(,R,),是否在可行域内。,如果下降性、可行性这两方面都得到满足，则以,X,(,R,),点替换,X,(,H,),点，由,X,(,R,),与,X,(2),、,X,(3),、,X,(4),共四个点构成一个新复合形,如图,6-5,出虚线所示,),，这个新复合形肯定优于原复合形；,如果上述两个条件不能同时满足，则可将映射系数缩半，即,0.5,，仍按式,(6-9),迭代。重新取得新的映射点,X,(,R,),，使其同时满足下降性、可行性条件。有时甚至要经过多次缩减映射系数才能使回缩的映射点,X,(,R,),最后满足这两个条件。这时以回缩成功的映射点,X,(,R,),和,X,(2),、,X,(3),、,X,(4),构成新复合形。构成新复合形就完成了一轮迭代。,再按上述方法进行迭代搜索，不断地使复合形向着目标函数减小的方向移动和收缩，直到逼近最优解。,通过以上说明，复合形寻优可以归为两大步骤：第一步是在可行域内构成初始复合形，第二步是通过复合形的收缩和移动不断调优，逐步逼近最优点。,二、初始复合形的产生,初始复合形的全部,K,个顶点都必须在可行域内。对于维数较低、不很复杂的优化问题，可以人为地预先按实际情况决定,K,个可行设计点作为初始复合形的顶点；,对于维数较高的优化问题则多采用随机方法产生初始复合形。,现将随机方法产生初始复合形的过程阐述如下：,(,一,),确定一个可行点,X,(1),作为初始复合形的第一个顶点,在,(,a,i,，,b,i,),区间给定一点,X,(1),=,x,1,(1),x,2,(1),x,n,(1),T,或调用,(0,，,1),区间内服从均匀分布的随机数列,r,i,(,j,),在,(,a,i,，,b,i,),区间产生第一个随机点,X,(1),，的分量：,x,i,(,j,),a,i,+,r,i,(,j,),(,b,i,-,a,i,)(,j=,1,；,i=,1,2,n,)(6-10),检验,X,(1),是否可行。若非可行点，则调用随机数，重新产生随机点,X,(1),，直到,X,(1),为可行点。,(,二,),产生其他,(,K-,1),个随机点,继续调用随机数,r,i,(,j,),，在,(,a,i,，,b,i,),区间产生其他,(,K-,1),个随机点：,X,(2),=,x,1,(2),x,2,(2),x,n,(2),T,，,X,(3),=,x,1,(3),x,2,(3),x,n,(3),T,，,，,X,(,K,),=,x,1,(,K,),x,2,(,K,),x,n,(,K,),T,其分量为,x,i,(,j,),a,i,+,r,i,(,j,),(,b,i,-,a,i,)(,j=,2,3,K,；,i=,1,2,n,)(6-11),(,三,),将非可行点调入可行域构成初始复合形,用上述方法产生的,K,个点，除第一点,X,(1),已在可行域内，其他,(,K-,1),个随机点未必都在可行域内。因此应设法将不在可行域的所有随机点逐一调入可行域。这就需要依次检查,X,(2),，,X,(3),，,，,X,(,K,),是否在可行域内。检查过程中如,X,(2),，,X,(3),，,，,X,(,q,),依次都在可行域内，它们均作为初始复合形的顶点；至第,X,(,q,+1),点不在可行域内，则应首先将,X,(,q,+1,),点调入可行域。其步骤为：,1,求出已在可行域的,q,个点的点集的中心,X,(,D,),2,将点,X,(,q,+1),向,X,(,D,),点的方向推进，移至,X,(,q,+1),与,X,(,D,),的中点，即按下式产生新的,X,(,q,+1),点,X,(,q,+1),X,(,D,),+0.5(,X,(,q,+1),-,X,(,D,),)(6-13),如果推移后的,X,(,q,+1),点已进入可行域，如图,(a),所示，即 点，则此点可作为初始复合形的第,q,+1,个顶点；,如果仍不满足可行性条件，如图,(b),所示，则仍按上式再次推移产生新的,X,(,q,+1),点，即 点，使之更向,X,(,D,),推移。如此重复迭代推移，直到新点,X,(,q,+1),成为可行点为止。,3,继续依次检查,X,(,q,+2),，,，,X,(,K,),，一旦遇到可行点，即作为初始复合形的顶点；一遇到不可行点则按上述方法处理，使之调入可行域。直到全部成为可行点，从而构成了可行域内的初始复合形。,三、迭代过程及算法框图,对于,n,个设计变量、仅有不等式约束的非线性最优化问题，采用复合形法的具体迭代步骤如下：,(1),给定设计变量数目,n,，变量界限范围,a,i,，,b,i,(,i=,1,2,n,),复合形顶点数目,K,，精度要求,、,。,(2),产生初始复合形。如前所述得初始复合形,K,个顶点,X,(,j,),(,j,=1,2,K,),。,(3),计算复合形各顶点的目标函数值,f,(,X,(,j,),),，,j,=1,2,K,。,在各顶点中找出最坏点,X,(,H,),和最好点,X,(,L,),X,(,H,),：,f,(,X,(,H,),)=max,f,(,X,(,j,),),j,=1,2,K,X,(,L,),：,f,(,X,(,L,),)=min,f,(,X,(,j,),),j,=1,2,K,转入第,(8),步。,(4),计算除坏点,X,(,H,),外其余各顶点的中心,X,(,C,),(5),检查,X,(,C,),点的可行性。若,X,(,C,),不在可行域,D,内，则,D,域可能是一个非凸集，如图,6-7,所示。,这时可在以,X,(,L,),点为起点、,X,(,C,),点为端点的超立方体中,(,二维则为长方形,),利用随机数产生新复合形的各个顶点，即以,x,i,(,L,),a,i,，,x,i,(,C,),b,i,，,i,=1,2,n,，,然后转回第,(2),步；若,X,(,C,),在可行域，则进行下一步。,(6),寻求映射点,X,(,R,),X,(,R,),X,(,C,),+(,X,(,C,),-,X,(,H,),),映射系数,通常取,1.3,。亦须检查,X,(,R,),点是否在可行域内。,若在可行域内，则进行第,(7),步；否则将映射系数,减半，即,0.5,，再按上式计算新的映射点使其向可行域方向靠拢；若新的映射点仍在可行域外，则将,再次减半继续重复迭代直到映射点,X,(,R,),进入可行域为止。而后进行下一步。,(7),比较映射点,X,(,R,),与最坏点的目标函数值，构成新复合形。,计算映射点的目标函数值,f,(,X,(,R,),),并与最坏点的目标函数值,f,(,X,(,H,),),相比较。,若,f,(,X,(,R,),),f,(,X,(,H,),),，则用,X,(,R,),替换,X,(,H,),点，即,X,(,R,),X,(,H,),，构成一个新复合形，返回第,(3),步；否则将步长减半，即,0.5,，返回第,(6),步，重新计算新的回缩的映射点,X,(,R,),，循环迭代，直至,f,(,X,(,R,),),f,(,X,(,H,),),，则以新的,X,(,R,),替换,X,(,H,),构成新复合形，返回第,(3),步。如果经过若干次的减半映射系数,，直到,值小于一个预先给定的很小正数,，仍不能使映射点优于最坏点，这说明该映射方向不利。改变映射方向，找出复合形各顶点中的次坏点,X,(,SH,),，即,X,(,SH,),：,X,(,SH,),max,f,(,X,(,j,),)(,j,=1,2,K,；,jH,)(6-15),次坏点,X,(,SH,),替换最坏点,X,(,H,),，即,X,(,SH,),X,(,H,),，返回第,(4),步。,(8),检验是否满足迭代终止条件,反复执行上述过程，复合形随之收缩。,在每一个新复合形构成之时，均应检验终止条件以判别是否结束迭代。,当复合形缩得很小时，各顶点的目标函数值必然近于相等。,常用各顶点与好点的目标函数值之差的均方根值小于误差限作为终止迭代条件。即,满足迭代终止条件，可将最后复合形的好点,X,(,L,),X*,，,f,(,X,(,L,),),f,(,X,*,),，输出最优解，结束迭代；否则返回步骤,(3),，继续进行下一次选代。,复合形法的算法框图,6-4,惩罚函数法,一、基本原理,将约束问题转化成无约束问题，用无约束方法进行求优的途径就是约束问题求优的间接方法。,惩罚函数法是将约束最优化问题通过变换，转换成为系列无约束最优化问题来处理的一种间接解法。,它是在原无约束最优化问题的目标函数中，引进约束影响的附加项，从而构成一个新的无约束最优化问题的目标函数。,通过合理选择这些附加项，可以使这个新目标函数的无约束最优点的序列收敛到原问题的最优点。现将惩罚函数法的基本原理阐述如下：,将一个约束最优化问题,D,：,gu,(,X,),0 (,u,=1,2,m,),hv,(,X,)=0 (,v,=1,2,pn,),转化成形如,的无约束最优化问题。,(,X,r,1,(,k,),r,2,(,k,),),是一个人为构造的参数型的新目标函数，称为增广目标函数或惩罚函数,(,简称罚函数,),；,f,(,X,),为原目标函数,G,g,u,(,X,),、,H,h,v,(,X,),分别为不等式约束函数,g,u,(,X,),和等式约束函数,h,v,(,X,),以某种方式构成的复合函数，或称为关于,g,u,(,X,),、,h,v,(,X,),的泛函，,G,g,u,(,X,),、,H,h,v,(,X,),在全域内定义为非负；,r,1,(,k,),、,r,2,(,k,),为在优化过程中随迭代次数,k,的增大不断进行调整的参数，称为罚因子或罚参数，定义为一个正实数。根据不同情况，它可以是一个递降或递增的数列。,这样就在新目标函数,(,X,r,1,(,k,),r,2,(,k,),),中即包含了原目标函数又引入了约束条件的影响。和 称为惩罚项，惩罚项的值恒为非负。,由此可见，惩罚函数,(,X,r,1,(,k,),r,2,(,k,),),的值在一般情况下总是大于原目标函数,f,(,X,),的值，亦即,(,X,r,1,(,k,),r,2,(,k,),),f,(,X,)(6-18),这就是所谓惩罚项对新目标函数的“惩罚作用”。显然要求随着迭代次数,k,的增大，惩罚项的影响越来越小和趋于消失。,随着,k,的增大，,(,X,r,1,(,k,),r,2,(,k,),),和,f,(,X,),的差值越来越小最后趋于相等。此时所得的,X*,既是无约束目标函数,(,X,r,1,(,k,),r,2,(,k,),),的最优点，又是约束目标函数,f,(,X,),的最优点。,为了使新目标函数最后总能收敛到原目标函数的同一最优解上去，惩罚项必须具有以下的极限性质：,从而有,(6-21),这样就保证了罚函数收敛到原函数的同一最优解上去。由此表明罚函数法是用罚函数,(,X,r,1,(,k,),r,2,(,k,),),去逼近原目标函数,f,(,X,),的一种函数逼近过程。,其总体求解过程为：确定,G,g,u,(,X,),和,H,h,v,(,X,),的形式选择不同的罚因子,r,1,(,k,),和,r,2,(,k,),的值，每调整一次罚因子值，即对式,(6-17),作一次无约束优化，可得一个无约束最优点,X*,(,k,),，随着罚因子不断调整，无约束最优点序列,X*,(,k,),(,k,1,，,2,，,),不断逼近有约束的原目标函数,f,(,X,),最优点,X*,。,惩罚函数法又称序列无约束最小化方法,(,sequential Unconstrained Minimization Technique,),，简称为,SUMT,法。,根据惩罚项的函数形式不同，惩罚函数法又分为外点惩罚函数法、内点惩罚函数法和混合型惩罚函数法三种,。,二、外点惩罚函数法,(,一,),基本原理,设原目标函数为,f,(,X,),，在不等式约束,g,u,(,X,),0(,u,=1,2,m,),条件下用外点惩罚函数法求极小。外点法常采用如下形式的泛函：,G,g,u,(,X,)=min0,g,u,(,X,),2,（,6-22,）,由此，外点法所构造的相应的惩罚函数形式为,（,6-23,）,式中，惩罚因子,r,(,k,),是一个递增的正值数列，即,0,r,(1),r,(2),r,(,k,),，,惩罚项中：,当迭代点,X,位于可行域内满足约束条件时，惩罚项为零，这时不管,r,(,k,),取多大，新目标函数就是原目标函数，亦即满足约束条件时不受“惩罚”，此时求式,(6-23),的无约束极小，等价于求原目标函数,f,(,X,),在已满足全部约束条件下的极小；而当点,X,位于可行域外不满足约束条件时，惩罚项为正值，惩罚函数的值较原目标函数的值增大了，这就构成对不满足约束条件时的一种“惩罚”。,由式,(6-23),可知，每一次对罚函数,(,X,r,(,k,),),求无约束的极值，其结果将随该次所给定的罚因子,r,(,k,),值而异。,在可行域外，离约束边界越近的地方，约束函数,g,u,(,X,),的值越大，,G,g,u,(,X,),的值也就越小，惩罚项的作用也就越弱，随着罚因子,r,(,k,),逐次调整增大，有增大惩罚项的趋势，但一般说来泛函值下降得更快一些。,此时尽管,r,(,k,),r,(,k,),值增大，但泛函值亦趋于零，满足式,(6-19),。最后当,k,，,r,(,k,),，泛函值惩罚项值均趋近于零。,外点法在寻优过程中，随着罚因子的逐次调整增大，即取,0,r,(1),r,(2),r,(,k,),，所得的最优点序列,X*,(1),，,X*,(2),，,，,X*,(,k,),可以看作是以,r,(,k,),为参数的一条轨迹，当时，最优点点列,X*,(,k,),(,k,1,，,2,，,),从可行域的外部一步一步地沿着这条轨迹接近可行域，所得的最优点列,X*,(,k,),逼近原问题的约束最优点,X*,。,这样，将原约束最优化问题转换成为序列无约束最优化问题。外点法就是因从可行域的外部逼近最优解而得名。,例题,6-2,用外点法求解 ，,D,：,g,(,X,)=,x,-1,0,的约束最优化问题。,解：如图,6-9,所示，约束最优解不难看出是,X*,1,，,f,(,X,*,),1,。,若用外点法求解此约束最优化问题，由式,(6-23),知惩罚函数为,(,X,r,(,k,),),x,+,r,(,k,),min0,(,x,-1),2,式中，,r,(,k,),为递增正值数列的外点法罚因子。这样把原约束最优化问题变为,min(,X,r,(,k,),),的序列无约束极小化问题。,将写,(,X,r,(,k,),),成如下形式,用一阶导数为零的必要条件来代替计算机无约束搜索求优。,将函数,(,X,r,(,k,),),对,x,求导，得,令 ，解得,(,X,r,(,k,),),无约束极小值的点列为,(,X,r,(,k,),),无约束极小值点列相应的惩罚函数值为,在表,6-1,中列出了本例当惩罚因子赋予不同值时迭代的点,X*,(,k,),、泛函,G,g,(,X,*,(,k,),),、惩罚项,r,(,k,),G,g,(,X,*,(,k,),),和函数值,(,X,*,(,k,),),、,f,(,X,*,(,k,),),。,f,(,X,),和,(,X,r,(,k,),),的图形绘于图,6-9,。,由于外点惩罚函数法具有这种搜索特点，所以也很适用于求解如下等式约束条件下的最优化问题。,D,：,h,v,(,X,)=0 (,v,=,1,2,p1,）,若不满足，则进行第（,4),步；否则转第,(5),步。,(4),令,cr,(,k,),r,(,k,+1),，置,k,+1,k,，返回进行第,(2),步。,(5),输出最优解：,X,(,k,),X,*,，,f,(,X,(,k,),),f,(,X,*,),，停止迭代。,外点惩罚函数法的算法框图,(,三,),几点说明,(1),外点惩罚函数法的初始点,X,(0),R,n,，可以在可行域内也可以在可行域外任意选取，对实际计算是很方便的。,(2),初始罚因子,r,(1),和递增系数,c,的选择是否恰当，对方法的有效性与收敛速度都有影响。,若,r,(1),与,c,取值过小，则序列求解函数,(,X,r,(,k,),),的无约束最优化次数增多，计算时间增加。,若,r,(,k,),与,c,取值过大，惩罚函数,(,X,r,(,k,),),的性态变环，导致求解无约束优化问题的困难。,J,Weisman,建议按下公式求每个约束的初始罚因子,r,(1),罚因子递增系数,c,一般取,510,。,图,6-11,反映引例,1-2,人架杆优化当,r,10,-10,，,10,-9,，,10,-8,，,10,-7,时罚函数,(,X,r,(,k,),),的等值线。,(3),外点惩罚函数法通常求到的最优点,X*,是无限接近约束边界的一个位于非可行域的外点，这就不能严格满足约束条件。,为了解决这个问题，可对那些必须严格满足的曲约束,(,如强度、刚度等性能约束,),引入约束裕量,，如图所示，即将这些约束边界向可行城内紧缩移动一个微量，也就是新定义的约束条件为,g,u,(,X,)=,g,u,(,X,)-,u,0 (,u,=1,2,m,),（,6-29,）,这样可以用新定义的约束函数构成的惩罚函数来求它的极小化，取得最优设计方案,X*,。,它虽在紧缩后的约束边界之外，,但已在原来的约束边界之内，,这就可以使原不等式约束条件,能够严格的满足,g,u,(,X,),0,。当,然，,u,值不宜选取过大，以避,免所得结果与最优点相差过远，,一般取,u,10,-3,10,-4,。,三、内点惩罚函数法,(,一,),基本原理,内点法是从可行域内某一初始内点出发，在可行域内进行迭代的序列极小化方法。它仅用于求解不等式约束优化问题。,设原目标函数为,f,(,X,),，在不等式约束,g,u,(,X,),0(,u,=1,2,m,),条件下用内点惩罚函数法求极小。,内点法常采用如下形式的泛函：,（,6-30,）,内点法所构造的相应的惩罚函数形式为,（,6-31,）,惩罚因子,r,(,k,),是一个递减的正值数列，即,r,(1),r,(2),r,(,k,),0,，,式,(6-30),所示的泛函具有如下的,性质,：,当迭代点,X,在可行域内离约束边界较远的地方，泛函是不大的正值；,X,可行域内靠近任一约束边界时，泛函具有很大的正值；,越靠近边界，其值趋向于正无穷大。,它像围墙一样阻止迭代点越出约束边界，所以又称围墙函数。围场函数不一定只限于上述形式，下式所示的函数亦具围墙函数的性质。计算不复杂，亦可用作内点罚函数法的泛函。,G,g,u,(,X,)=,-,ln,g,u,(,X,),罚因子的作用,则为：由于内点法只能在可行域内迭代，而最优点很可能在可行域内靠近边界之处或就在边界上，此时尽管泛函的值很大，但罚因子是不断递减的正值，经多次迭代，,X*,(,k,),向,X*,靠近时，惩罚项 已是很小的正值，因而仍能满足式,(6-19),的要求。,(6-19),由式,(6-31),可知，每一次对罚函数,(,X,r,(,k,),),求无约束的极值，其结果将随该次所给定的罚因子,r,(,k,),值而异。,内点法在寻优过程中，随着罚因子的逐次调整减小，即取,r,(1),r,(2),r,(,k,),0,，所得的最优点序列,X*,(1),，,X*,(2),，,，,X*,(,k,),可以看作是以,r,(,k,),为参数的一条轨迹，在可行域内部一步一步地沿着这条轨迹向原问题约束最优点,X*,逼近；,当 时，所得的最优点,X*,(,k,),逼近原问题的约束最优点,X*,。,这样，将原约束最优化问题转换成为序列无约束最优化问题。,内点法就是因从可行域的内部逼近最优解而得名。,(6-31),例题,6-3,用内点法求解,D,：,g,(,X,)=,x,-,1,0,的约束最优化问题。,惩罚函数为,解得,(,X,r,(,k,),),无约束极小值的点列为：,(,X,r,(,k,),),无约束极小值点列相应的惩罚函数值为：,例题,6-2,内点法迭代的点及其相应的泛函、惩罚项、函数值,当惩罚因子为一递减正值数列时，其极值点,X,*,(,k,),离约束最优点,X,*,愈来愈近，,(,X*,(,k,),r,(,k,),),与,f,(,X,*,(,k,),),的差值愈来愈小，当,r,(,k,),0,时，,X,*,(,k,),X,*=1,，,(,X,*,(,k,),r,(,k,),),f,(,X,*,(,k,),)=1,，亦即逼近于真正的约束最优解。,本例,(,X,r,(,k,),),无约束极值点列,X,*,(,k,),随,r,(,k,),值递减而沿直线,(,X,*,(,k,),r,(,k,),),2,X,*,(,k,),-1,从可行域内部向最优点,X*,收敛。,(,二,),迭代过程及算法框图,内点惩罚函数法具体迭代步骤如下：,(1),给定初始罚因子,r,(1),0,，迭代精度,，递减系数,e,，,0,e,1,，维数,n,。,(2),求约束集,D,的一个内点,X,(0),D,(0),，,D,(0),=,X,gu,0(,u,=1,2,m,，置,1,k,。,(3),以,X,(k-1),D,(0),为初始点，对于惩罚函数,(,X,r,(,k,),),在保证可行性的情况下，使用无约束最优化方法求解惩罚函数,(,X,r,(,k,),),的极小点,X,(,k,),，即,(,X,(,k,),r,(,k,),),min(,X,r,(,k,),),(4),检验是否满足迭代终止条件。终止条件与外点法相同。若不满足，则进行第,(5),步；否则转第,(6),步。,(5),令,er,(,k,),r,(,k,+1),，置,k,+1,k,，返回进行第,(3),步。,(6),输出最优解：,X,(,k,),X*,，,f,(,X,(,k,),),f,(,X,*,),，停止迭代。,(,三,),初始内点的求法,内点惩罚函数法的初始内点,X,(0),必须是约束可行域,D,中的内点，即,X,(0),D,0,。,在机械设计中，只要以增加目标函数,f,(,X,),的值为代价就不难找到可行城内的设计点。,例，在,齿轮传动啮合参数,的优化设计中，若以,中心距最小,作为追求的目标，那么为了满足强度条件，设计人员在选择初始点时，只要有意识地选取较大的模数、齿宽和较多的齿数等等，强度约束肯定就能得到满足。,又如对某,机械产品进行改进设计,，那么原设计虽然不是最优方案，但极大多数是可行的。总之，比较有经验的机械设计人员在进行一项优化设计时，直接地找到一个可行内点，并不会存在过大的困难。,有些设计问题由于相互制约关系很复杂，难以直接观察可行设计内点，此时可按随机选一初始点,X,(0),，检验严格满足,g,u,(,X,)0,来获得初始内点,还可用下述对约束不满足程度逐次调整的搜索方法求初始内点：,任选一个设计点,X,(0),R,n,，计算该点的诸约束函数值,g,u,(,X,(0),)(,u,=1,2,m,),。,若在,m,个约束条件中有,q,个约束条件得到严格满足，余下,(,m,-,q,),个约束条件未得严格满足，即,g,u,(,X,(0),)0(,u,=1,2,q,),g,u,(,X,(0),),0 (,u,=,q,+1,q,+2,m,),以,X,(0),为初始点，暂时将没有被严格满足的那些约束条件的负值作为目标函数，将它在已被严格满足的那些约束条件所构成的可行域中极小化，这时仍可采用内点惩罚函数法进行迭代，最终就可求得一个满足所有约束条件的可行点。,这种用搜索方法求初始内点的迭代步骤如下：,(1),任取,X,(0),R,n,及初始惩罚因子,r,(1),0(,例如,r,(1),1),，递减系数,e,，,0,e,1,，置,0,k,。,(2),定出内点与非内点,(,包括边界点,),的下标集合,T,(,k,),和,S,(,k,),(3),检验集合,S,(,k,),是否为空集,，若,S,(,k,),，则,X,(,k,),D,0,取作初始内点，停止迭代；否则进行第,(4),步。,(4),以,X,(,k,),为初始点，求,的极小点,X,(,k,+1),，其中 ，,r,(,k,+1),0,。,(5),令,er,(,k,+1),r,(,k,+2),，置,k,+1,k,，返回第,(2),步按上述步骤继续搜索迭代，经有限步迭代后，必可求得在可行域内的点,X,(,k,),D,0,。,(,四,),惩罚因子初值和递减系数的选择,惩罚因子初值,r,(1),选择得是否合适，对内点法的收敛速度有显著影响。,一般说来，若初始值,r,(1),选择得过小，则惩罚函数,(,X,r,(,k,),),的性态就会变坏，如在约束边界附近出现深沟谷地，使迭代发生困难甚至得不到正确的最优解。,若,r,(1),择过大，虽然函数,(,X,r,(1),),容易极小化，但函数,(,X,r,(1),),的最优点离函数,f,(,X,),的约束最优点很远，甚至有可能使取得的一些无约束最优点，比初始点,X,(0),更远离约束最优点，这将使计算效率降低。,因此,r,(1),的取值应按函数,(,X,r,(1),),最小化不发生困难的前提下尽可能取得小一些。,在实际计算中，,r,(1),值范围大约为,150,。不少情况是取,r,(1),1,。如果初始点,X,(0),是一个远离边界的内点，推荐,r,(1),值按下式近似求出,当初始点,X,(0),与任何一个或几个约束边界接近时，按上式求出的,r,(1),值一般总是太小，此时必须另选一个适当大的,r,(1),值。考虑到,r,(1),取值过大时，会发生函数,(,X,r,(1),),的最优点比初始点,X,(0),离约束最优点更远的弊病，在选择相当大的,r,(1),值时，可在所求的约束最优化问题中，