第四章 非线性规划4

第四节复合形法复合形法(ComplexMethod)是1965年由博克斯(Box)提出，后经古恩(Gwin)修正的解非线性规划的一种直接搜索法。如同随机方向搜索法一样.在确定搜索方向时，它不需要函数的梯度信息，它是求解非线规划中的一种简单适用的方法。一、基本原理对于约束优化问题minf(X)XgRn<s.t g(X)<0u=1,2,3,ma<x(0)<bi=1,2,nTOC\o"1-5"\h\zl・ ・ • •..i i i使用迭代格式 ...X好1=Xk+AXk=Xk+akSk k=1,2,3,所谓复合形是指在n维设计空间的可行域内由.k(=n+1〜2n)个顶点所构成的多面体。复合形法是一种在可行域内直接的求优方法。利用复合形各顶点处目标函数值的大小关系，判断目标函数值的下降方向，不断丢掉函数值最大的所谓最差点，代之以既使目标函数值有所下降又能满足所有约束条件的一个新点，从而不断地构成新的复合形。如此重复计算，使新的复合形不断地向可行域的最优点移动和收缩，直至得到满足收敛准则的近似解为止。由于对复合形不必保持规则图形，顶点数较多，因此可以求解非线性的约束问题，面且计算稳定可靠。但不能用于解含有等式约束的问题。二、复合形的迭代步骤确定复合形的顶点复合形法是一种在可行域内直接的求优方法，要求第一个复合形的k个顶点都是可行的。对复合形的顶点数一般推荐取k=2n，当n计算问题的维数较多(如n>5)时，可取k=n+1。如果复合形顶点数少了，一旦出现丢失顶点现象就可能会出现降维搜索而找不到真正的最优点。初始复合形的确定方法有如下几种：给定k个初始顶点。由设计者预先选择k个设计方案，即人工构造一个初始复合形。由于k个顶点都必须满足所有的约束条件，因此当设计变量数目较多或约束条件比较复杂时，这样做可能是很不方便的或者是很困难的。给定一个初始顶点，随机产生其他顶点。如果用常规设计方法能取得一个设计方案，此方案虽然不是最优的，但却是一个可行的。则其他k-1个顶点可用随机法产生x(j)=a+rj(b-a)i=1,2,nj=1,2,ki iiii式中a,b—各设计变量的x的上、下界限，一般取边界约束值;

y—[0,1]区间内服从均匀分布的伪随机数。i=1,2,n这样随机产生的k-1个顶点，虽然可以满足边界约束条件，但不一定能满足性能约束条件，还必须逐个进行检查，把不满足约束条件的顶点移到可行域内。设已有qi=1,2,ni=1,2,n然后将不满足约束条件的点X(q+1)向中心点X(t)靠拢，即X(q+1)=X(t)一0.5(X(t)-X(q+1)) (复合形的收缩运算)若还不满足约束条件，则可以重复用上式计算。(即以新的X(q+1)进行收缩)只要中心点X(t)是可行点，X(q+1)点经逐步向X(t)靠拢，最终总能成为一个可行顶点。对随机产生的各个顶点进行这种处理后，最后可取得k个初始可行顶点，从而构成初始复合形。事实上，只要可行域是凸集，其中心点必为可行点，因而用上述方法可以成功地在可行域内构成初始复合形。如果可行域为非凸集那就有失败的可能，当中心点处于可行域之外时，就应该缩小随机选点的边界域，重新产生各顶点。随机产牛全部顶点。计算各顶点函数值X(H)一最差点(函数值最大的点)f(X(h))=max{f(X(k))}X0)一最好点(函数值最小的点)f(X(L))=min{f(X(k))}X(C)一复合形的几何中心X。)=1工X(j)即x.(c)=1乙ji=1,2,nj=1 j=1复合形法运算，构造新的复合形复合形不断地向可行域的最优点移动和收缩，是通过反射、收缩、扩展和重构复台形等四种运算来实现的。1.反射运算去掉最坏点后所有点的几何中心点X(。)X（o）=——交Xjk-1j=1j力H反射就是沿最坏点X(H)和X(。)的连线方向上取映射点X(R)，即X(R)=X(o)+a(X(o)-X(H))(a)二维空间三角形的反射;(b)三维空间四面体的收谿式中a称为反射系数.一般a>1，例如可取a=1.3(Box建议)。如果X(R)满足所有约束条件，且f(X(R))<f(X(h))，即可用X(R)代替X(h)组成新复合形，完成一次迭代。如果X(R)不满足约束条件，或不满足f(X(R))<f(X(h))，则将反射系数a减半重新计算X(R)，若仍不满足要求，可继续将a减半，直到a减到很小(例如小于10-5)还不满足要求时，那就只能放弃这一方向，改用次坏点X(G)的映射方向，重新寻求满足条件的映像点。2.扩展运算若初次确定的反射点X(R)，其目标函数值比最好点X(L)的还小，即f(X(R))<f(X(L))时，说明沿此方向映射的效果显著，有进一步扩张的必要，以探求更好的点。即按下式计算新点X(E)=X(o)+P(X(R)-X(o)) (扩展运算)式中，P称为扩展系数，一般多6>1。如果f(X(E))<f(X(R))，则说明扩展成功，用X(E)替换X(R)组成新复合形，完成本次迭代。如果f(X(E))>f(X(R))，则扩展失败，仍取原反射点X(R)替换X(H)组成新复合形。收缩运算若已找不到好的反射点，还可以从X(h)到中心点X(。)连线以内收缩寻找。按下式计算收缩点X(M)X(M)=Xow(Xo(-)XH)式中，y称为收缩系数，一般0<y<1。与扩展同样，如果f(x(m))<f(x(h))则收缩成功，用X(M)替换X(H)，否则失败。重构若采取上述措施均元效，还可以采取向最好点X⑥靠拢的措施，即：X(G)=X(L)-0.5(X(L)-X(G))X(H)=X(L)-0.5(X(L)-X(H))各顶点向最好点靠拢后再重新寻求新顶点。检查停机准则在迭代计算中，由于复合形不断向最好点移动和缩小，因此当复合形的k个顶点X(k)的目标函数值的与中心点X(C)均方差很小时，则停止迭代1{丁寸[f(X(C))-f(X(力)]2}2<£kj=i或max(X(j)-X(c)||)<e1<j<k获取最优解满足停机准则后取函数值最小的顶点作为最优解。三、算法框图

选定一个初始顼点m我出机产生其泰AI*阻点/a-j：-/ixj,L随机产生初始口点选定一个初始顼点m我出机产生其泰AI*阻点/a-j：-/ixj,L随机产生初始口点x严”=1加■算答哽点戏菌数宣只不[_.尤，点的函数值〃私■•：=机、.=（（,=j*2.,用X,代X**,:=思，+心品、X.可近四、 讨论由于复合形法在迭代过程中不必计算目标函数的一、二阶导数，也无需进行一维最优化探索，因此对目标函数和约束函数的性质无特别要求，程序较简单，但随着设计变量和约束条件的增多，其计算效率显著降低。当维数nW5个时，复合形的顶点数k可取2n个，当n>5时，可适当减少顶点数，但不能少于n+1个五、 算例例题试用复合形法求解yOT-容的极小值*己知约束条件为：■—一50《。」O.OOOM1%—0.<J01w02<习<4、Q,5冬互<1解取复合形的顶点数k=2n~^＞用随机法产生初始复合形的顶点:按式：＜5-26).T.j-''=冬"小切—叫)取伪随机数?■(]—0.1＜ —0J2+r"j|—0" 3—G.4r.2=0;1.r£20.2.r3Z-D.3rtL—(L4则初始复合形的4个顶点的工i坐标分量为工计)一2+Q.1(4-3)=2.2h罪—2+0.2(4—2)=2.4工器'=2十0.3(4一£)=2.6坦=2+0.4(4-2)=2.84个顶点的氏坐标分量为5+0.1(1—0.5)=0.55遛=0.5+0.2(1—0.5)=0.6建』巳5十0,3(1—0.5)=0.65卫亨一0.5+0.4(1-0.5)=0.7则初始复合形4个顶点的坐标为22_'2.4-26-~2.8"船皿=，招w=，玲）=刈=-D.55--0,6--0.65-.0,7.椅验各顶点是否可行：将各顶点的坐标值代入等约束方程，均满足约束要求。所以初始复合形选择成功。然后依下列步骤进行迭代计算：（1）计算各顶点的函数值并比较它们的大小，以便确定最差点帝吧最好点X六欢〉=切扁=旺球浓向=第。观一可⑵求除最差点外其除三点的形心X笋［见式（5-29）1；0>=厂羿+X猝+XJ0>)= 1；0>=厂羿+X猝+XJ0>)= 1&—124~4-1lLo.fi-26'

q65--2.8LO.7」I「7.8一一3L1.9技（3〉求最差点的反射点，按式（5*21），取玄=L3：.幻6_-0,65-26]

-0.65」必s=y（o>+心舛一欢）代入约束条件证明在可行域内。2.60,652,20.55代入约束条件，证明*乎代入约束条件，证明*乎在可行域内，Lo.78-(4)计算/(XiwW与f(X^>比较：'0*)=厂亍278’=16+8850</(Xr)=f(X^)-68.3013故可用新点X/替换X]叭构成;新的复合形：■ --rr--- ri—V-b 1 yrql『 ju-'■312”+26312”+26'|+28]]『阡]*0*78--0.65--0.7J)Lo.71-（5）计算新复合形中除最差点X?'外各顶点的形心X卬,代入约束方3.12「34=y(J)— .•A芝—AgL・0.6--0.78-「2.6-■船1)=*妙=2厂■Os-65」07-招口=X/程证明了尚点在可行域内’（6）计算X狄= 的反射点,取a=L（6）计算X狄= 的反射点,取a=L3；'2.84--0+71-xy）=於）+一X?））-「3.412一-0.853-代入约束条件检验,1.32.84]_「0.71」L「2.4]]

q6」l占明不满足第二个约束条件,故应将女减半，即取&=0.65,重算反射点无"，284一-0*71-+0.65_ 「2