約束優(yōu)化方法

關(guān)于約束優(yōu)化方法

第五章約束優(yōu)化方法根據(jù)求解方式的不同，可分為直接解法和間接解法兩類。

機(jī)械優(yōu)化設(shè)計(jì)的問(wèn)題，大多屬于約束優(yōu)化設(shè)計(jì)問(wèn)題，其數(shù)學(xué)模型為：

直接解法是在滿足不等式約束的可行設(shè)計(jì)區(qū)域內(nèi)直接求出問(wèn)題的約束最優(yōu)解。間接解法是將約束優(yōu)化問(wèn)題轉(zhuǎn)化為一系列無(wú)約束優(yōu)化問(wèn)題來(lái)解的一種方法。第2頁(yè),共77頁(yè)，2024年2月25日，星期天

第五章約束優(yōu)化方法

直接解法是在滿足不等式約束的可行設(shè)計(jì)區(qū)域內(nèi)直接求出問(wèn)題的約束最優(yōu)解。

屬于直接解法的有：隨機(jī)實(shí)驗(yàn)法、隨機(jī)方向搜索法、復(fù)合形法、可行方向法等。間接解法是將約束優(yōu)化問(wèn)題轉(zhuǎn)化為一系列無(wú)約束優(yōu)化問(wèn)題來(lái)解的一種方法。

由于間接解法可以選用已研究比較成熟的無(wú)約束優(yōu)化方法，并且容易處理同時(shí)具有不等式約束和等式約束的問(wèn)題。因而在機(jī)械優(yōu)化設(shè)計(jì)得到廣泛的應(yīng)用。間接解法中具有代表性的是懲罰函數(shù)法。第3頁(yè),共77頁(yè)，2024年2月25日，星期天直接解法的基本思想：

在由m個(gè)不等式約束條件gu(x)≤0所確定的可行域φ內(nèi)，選擇一個(gè)初始點(diǎn)x(0)，然后確定一個(gè)可行搜索方向S，且以適當(dāng)?shù)牟介L(zhǎng)沿S方向進(jìn)行搜索，取得一個(gè)目標(biāo)函數(shù)有所改善的可行的新點(diǎn)x(1)，即完成了一次迭代。以新點(diǎn)為起始點(diǎn)重復(fù)上述搜索過(guò)程，每次均按如下的基本迭代格式進(jìn)行計(jì)算：x(k+1)＝x(k)+α(k)S(k)(k=0,1,2,…)逐步趨向最優(yōu)解，直到滿足終止準(zhǔn)則才停止迭代。第4頁(yè),共77頁(yè)，2024年2月25日，星期天直接解法的原理簡(jiǎn)單，方法實(shí)用，其特點(diǎn)是：1）由于整個(gè)過(guò)程在可行域內(nèi)進(jìn)行，因此，迭代計(jì)算不論何時(shí)終止，都可以獲得比初始點(diǎn)好的設(shè)計(jì)點(diǎn)。2）若目標(biāo)函數(shù)為凸函數(shù)，可行域?yàn)橥辜?，則可獲得全域最優(yōu)解，否則，可能存在多個(gè)局部最優(yōu)解，當(dāng)選擇的初始點(diǎn)不同，而搜索到不同的局部最優(yōu)解。3）要求可行域有界的非空集。直接解法的特點(diǎn)：第5頁(yè),共77頁(yè)，2024年2月25日，星期天a)可行域是凸集；b)可行域是非凸集第6頁(yè),共77頁(yè)，2024年2月25日，星期天間接解法的基本思路：將約束函數(shù)進(jìn)行特殊的加權(quán)處理后，和目標(biāo)函數(shù)結(jié)合起來(lái)，構(gòu)成一個(gè)新的目標(biāo)函數(shù)，即將原約束優(yōu)化問(wèn)題轉(zhuǎn)化為一個(gè)或一系列的無(wú)約束優(yōu)化問(wèn)題。新目標(biāo)函數(shù)加權(quán)因子然后對(duì)新目標(biāo)函數(shù)進(jìn)行無(wú)約束極小化計(jì)算。第7頁(yè),共77頁(yè)，2024年2月25日，星期天間接解法的基本思路第8頁(yè),共77頁(yè)，2024年2月25日，星期天2.1隨機(jī)方向法的基本思路1、在可行域內(nèi)選擇一個(gè)初始點(diǎn)；2、利用隨機(jī)數(shù)的概率特性，產(chǎn)生若干個(gè)隨機(jī)方向；3、從中選一個(gè)能使目標(biāo)函數(shù)值下降最快的方向作為搜索方向d；4、從初始點(diǎn)x0出發(fā)，沿d方向以一定步長(zhǎng)進(jìn)行搜索，得到新點(diǎn)X，新點(diǎn)X應(yīng)滿足約束條件且f(x)<f(x0)，至此完成一次迭代?；舅悸啡鐖D所示。隨機(jī)方向法程序設(shè)計(jì)簡(jiǎn)單，搜索速度快，是解決小型機(jī)械優(yōu)化問(wèn)題的十分有效的算法。第二節(jié)約束隨機(jī)方向法第9頁(yè),共77頁(yè)，2024年2月25日，星期天隨機(jī)方向法的基本思路第10頁(yè),共77頁(yè)，2024年2月25日，星期天2.2隨機(jī)方向的構(gòu)成1.用RND(X)產(chǎn)生n個(gè)隨機(jī)數(shù)2.將(0,1)中的隨機(jī)數(shù)

變換到(-1,1)中去(歸一化);3.構(gòu)成隨機(jī)方向變換得:于是例:對(duì)于三維問(wèn)題第二節(jié)約束隨機(jī)方向法第11頁(yè),共77頁(yè)，2024年2月25日，星期天從k個(gè)隨機(jī)方向中，選取一個(gè)較好的方向。2.3可行搜索方向的產(chǎn)生第二節(jié)約束隨機(jī)方向法1.檢驗(yàn)k個(gè)隨機(jī)點(diǎn)是否為可行點(diǎn)，除去非可行點(diǎn)，計(jì)算余下的可行點(diǎn)的目標(biāo)函數(shù)值，比較其大小，選出目標(biāo)函數(shù)最小的點(diǎn)XL

。2.比較XL

和X0兩點(diǎn)的目標(biāo)函數(shù)值，若f(XL)<f(X0)，則取XL

和X0連線方向?yàn)榭尚兴阉鞣较颍蝗鬴(XL)>f(X0)，則步長(zhǎng)α0

縮小，轉(zhuǎn)步驟1）重新計(jì)算，直至f(XL)<f(X0)為止。如果α0

縮小到很小，仍然找不到一個(gè)XL，使f(XL)<f(X0)則說(shuō)明X0是一個(gè)局部極小點(diǎn)，此時(shí)可更換初始點(diǎn)，轉(zhuǎn)步驟1）。第12頁(yè),共77頁(yè)，2024年2月25日，星期天產(chǎn)生可行搜索方向的條件為：則可行搜索方向?yàn)椋?.3可行搜索方向的產(chǎn)生第二節(jié)約束隨機(jī)方向法第13頁(yè),共77頁(yè)，2024年2月25日，星期天2.4初始點(diǎn)的選擇

隨機(jī)方向法的初始點(diǎn)x0必須是一個(gè)可行點(diǎn)，既滿足全部不等式約束條件。初始點(diǎn)可以通過(guò)隨機(jī)選擇的方法產(chǎn)生。1）輸入設(shè)計(jì)變量的下限值和上限值，即2）在區(qū)間（0，1）內(nèi)產(chǎn)生n個(gè)偽隨機(jī)數(shù)3）計(jì)算隨機(jī)點(diǎn)x的各分量第二節(jié)約束隨機(jī)方向法4）判別隨機(jī)點(diǎn)x是否可行，若隨機(jī)點(diǎn)可行，用x代替x0為初始點(diǎn)；若非可行點(diǎn)，轉(zhuǎn)到步驟2）重新產(chǎn)生隨機(jī)點(diǎn)，只到可行為止。第14頁(yè),共77頁(yè)，2024年2月25日，星期天2.5.迭代過(guò)程①在初始點(diǎn)處產(chǎn)生一隨機(jī)方向，若該方向適用、可行，則以定步長(zhǎng)前進(jìn)；②若該方向不適用、可行，則產(chǎn)生另一方向；③若在某處產(chǎn)生的方向足夠多(50-100)，仍無(wú)一適用、可行，則采用收縮步長(zhǎng)；④若步長(zhǎng)小于預(yù)先給定的誤差限則終止迭代。第二節(jié)約束隨機(jī)方向法第15頁(yè),共77頁(yè)，2024年2月25日，星期天2.6.流程圖X0=X,F0=F給定內(nèi)點(diǎn)X0,α0,m,ε

α=α0,F0=F(X0)F=F（X）j=1K=K+1是K=0,j=0產(chǎn)生隨機(jī)方向α=0.5α否F<F0j=0K<mα≤ε結(jié)束X*=X0,F*=F0是否是否是否X∈D是否第16頁(yè),共77頁(yè)，2024年2月25日，星期天function[x1,fx1,gx]=opt_random2(f,g_cons,xl,xu,TolX,TolFun)N=length(xl);M=size(g_cons);M=length(M(:,1));gx=ones(M,1);whilemax(gx)>=0dir0=rand(N,1);x0=xl+dir0.*xu;gx=feval(g_cons,x0);%feval()執(zhí)行由串指定的函數(shù)end%========================================================fx0=feval(f,x0);xk=x0+1;fxk=feval(f,xk);xmin=x0;alpha=1.3;k1=0;flag1=1;whilenorm(xk-x0)>TolX|abs(fxk-fx0)>TolFunk1=k1+1;x0=xmin;fx0=feval(f,x0);2.7隨機(jī)方向法的Matlab程序第17頁(yè),共77頁(yè)，2024年2月25日，星期天dir0=rand(N,1)*2-1;dir0=dir0/norm(dir0);xk=x0+alpha*dir0;gx=feval(g_cons,xk);ifmax(gx)>0alpha=alpha*0.7;elsefxk=feval(f,xk);iffxk<fx0ifnorm(xk-x0)<TolX&abs(fxk-fx0)<TolFunbreakelsexmin=xk;alpha=1.3;endx0,xk,fx0,fxkelsealpha=-alpha;endendendx1=x0;fx1=feval(f,x1);gx=feval(g_cons,x1);k1end第18頁(yè),共77頁(yè)，2024年2月25日，星期天例:求2.7隨機(jī)方向法的Matlab程序functionopt_random1_test1%opt_random1_test1.mclc;clearall;f=inline('x(1)^2+x(2)','x');xl=[-3-3]';xu=[33]';TolX=1e-8;TolFun=1e-8;[x1,fx1,g]=opt_random1(f,@fun_cons,xl,xu,TolX,TolFun)functiong=fun_cons(x)g=[x(1)^2+x(2)^2-9x(1)+x(2)-1];計(jì)算結(jié)果：x1=[-0.0076-3.0000],f=-2.9999,g=[-0.0000-4.0076]第19頁(yè),共77頁(yè)，2024年2月25日，星期天第三節(jié)復(fù)合形法復(fù)合形法是求解約束優(yōu)化問(wèn)題的一種重要的直接解法?；舅悸罚?/p>

1、在可行域內(nèi)構(gòu)造一個(gè)具有k個(gè)頂點(diǎn)的初始復(fù)合形；2、對(duì)該復(fù)合形各頂點(diǎn)的目標(biāo)函數(shù)值進(jìn)行比較，找到目標(biāo)函數(shù)最大的頂點(diǎn)（最壞點(diǎn)）；3、然后按一定的法則求出目標(biāo)函數(shù)值有所下降的可行的新點(diǎn)，并用此點(diǎn)代替最壞點(diǎn)，構(gòu)成新的復(fù)合形，復(fù)合形的形狀每改變一次，就向最優(yōu)點(diǎn)移動(dòng)一步，直至逼近最優(yōu)點(diǎn)。

由于復(fù)合形的形狀不必保持規(guī)則的圖形，對(duì)目標(biāo)函數(shù)和約束函數(shù)無(wú)特殊要求，因此這種方法適應(yīng)性強(qiáng)，在機(jī)械優(yōu)化設(shè)計(jì)中應(yīng)用廣泛。第20頁(yè),共77頁(yè)，2024年2月25日，星期天

3.1基本思路

在可行域內(nèi)選取若干初始點(diǎn)并以之為頂點(diǎn)構(gòu)成一個(gè)多面體(復(fù)合形),然后比較各頂點(diǎn)的函數(shù)值,去掉最壞點(diǎn),代之以好的新點(diǎn),并構(gòu)成新的復(fù)合形,以逼近最優(yōu)點(diǎn).第三節(jié)復(fù)合形法第21頁(yè),共77頁(yè)，2024年2月25日，星期天3.2初始復(fù)合形生成的方法：（1）由設(shè)計(jì)者決定k個(gè)可行點(diǎn)，構(gòu)成初始復(fù)合形。設(shè)計(jì)變量少時(shí)適用。（2）由設(shè)計(jì)者選定一個(gè)可行點(diǎn)，其余的k-1個(gè)可形點(diǎn)用隨機(jī)法產(chǎn)生。（3）由計(jì)算機(jī)自動(dòng)生成初始復(fù)合形的所有頂點(diǎn)。第三節(jié)復(fù)合形法*初始復(fù)合形的構(gòu)成*復(fù)合形的移動(dòng)和收縮第22頁(yè),共77頁(yè)，2024年2月25日，星期天第23頁(yè),共77頁(yè)，2024年2月25日，星期天3.2.1初始復(fù)合形的構(gòu)成(1)復(fù)合形頂點(diǎn)數(shù)K的選擇建議:

小取大值,大取小值(2)初始復(fù)合形頂點(diǎn)的確定★用試湊方法產(chǎn)生---適于低維情況;★用隨機(jī)方法產(chǎn)生3.2初始復(fù)合形生成的方法：第三節(jié)復(fù)合形法第24頁(yè),共77頁(yè)，2024年2月25日，星期天②將非可行點(diǎn)調(diào)入可行域內(nèi)★K個(gè)頂點(diǎn)中要求無(wú)一在可行域內(nèi)。重新產(chǎn)生。★K個(gè)頂點(diǎn)中有可行點(diǎn)，重新排列，將可行點(diǎn)依次排在前面，如有q個(gè)頂點(diǎn)X(1)、X(2)、……X(q)是可行點(diǎn)，其它K-q個(gè)為非可行點(diǎn)。對(duì)X(q+1)，將其調(diào)入可行域的步驟是：

先用隨機(jī)函數(shù)產(chǎn)生

個(gè)隨機(jī)數(shù)

,然后變換到預(yù)定的區(qū)間

中去.①用隨機(jī)方法產(chǎn)生K個(gè)頂點(diǎn)第25頁(yè),共77頁(yè)，2024年2月25日，星期天(1)計(jì)算q個(gè)點(diǎn)集的中心X(s)；(2)將第q+1點(diǎn)朝著點(diǎn)X(s)的方向移動(dòng)，按下式產(chǎn)生新的X(q+1)，即

若仍不可行，則重復(fù)此步驟，直至進(jìn)入可行域?yàn)橹埂?/p>

按照這個(gè)方法，同樣使X(q+2)、X(q+3)、……X(K)都變?yōu)榭尚悬c(diǎn)，這K個(gè)點(diǎn)就構(gòu)成了初始復(fù)合形。第26頁(yè),共77頁(yè)，2024年2月25日，星期天有兩種基本運(yùn)算:1)映射---在壞點(diǎn)的對(duì)側(cè)試探新點(diǎn):先計(jì)算除最壞點(diǎn)外各頂點(diǎn)的幾何中心,然后再作映射計(jì)算.2)收縮---保證映射點(diǎn)的“可行”與“下降”X1為最壞點(diǎn)---映射系數(shù)常取若發(fā)現(xiàn)映射點(diǎn)不適用、可行,則將減半后重新映射.3.3復(fù)合形法的搜索方法第27頁(yè),共77頁(yè)，2024年2月25日，星期天3.4復(fù)合形法的迭代步驟(1)構(gòu)造初始復(fù)合形；(2)計(jì)算各頂點(diǎn)的函數(shù)值F(X(j))，j=1,2,….,K。選出好點(diǎn)X(L)和壞點(diǎn)X(H)

；(3)計(jì)算壞點(diǎn)外的其余各頂點(diǎn)的中心點(diǎn)X(0)。第28頁(yè),共77頁(yè)，2024年2月25日，星期天(4)計(jì)算映射點(diǎn)X(R)

檢查X(R)是否在可行域內(nèi)。若X(R)為非可行點(diǎn)，將映射系數(shù)減半后再按上式改變映射點(diǎn)，直到X(R)進(jìn)入可行域內(nèi)為止。(5)構(gòu)造新的復(fù)合形計(jì)算映射點(diǎn)的函數(shù)值F(X(R))，并與壞點(diǎn)的函數(shù)值F(X(H))比較，可能存在兩種情況：

1）映射點(diǎn)優(yōu)于壞點(diǎn)

F(X(R))<F(X(H))

在此情況，用X(R)代替X(`H)，構(gòu)成新的復(fù)合形。第29頁(yè),共77頁(yè)，2024年2月25日，星期天

若經(jīng)過(guò)多次的映射系數(shù)減半，仍不能使映射點(diǎn)由于壞點(diǎn)，則說(shuō)明該映射方向不利，此時(shí)，應(yīng)改變映射方向，取對(duì)次壞點(diǎn)的映射。再轉(zhuǎn)回本步驟的開(kāi)始處，直到構(gòu)成新的復(fù)合形。2）映射點(diǎn)次于壞點(diǎn)

F(X(R))>F(X(H))

這種情況由于映射點(diǎn)過(guò)遠(yuǎn)引起的，減半映射系數(shù)，若有F(X(R))<F(X(H))，這又轉(zhuǎn)化為第一種情況。第30頁(yè),共77頁(yè)，2024年2月25日，星期天3.5判斷終止條件1)各頂點(diǎn)與好點(diǎn)函數(shù)值之差的均方根值小于誤差限，即2）各頂點(diǎn)與好點(diǎn)的函數(shù)值之差的平方和小于誤差限，即3）各頂點(diǎn)與好點(diǎn)函數(shù)值差的絕對(duì)值之和小于誤差限，即

如果不滿足終止迭代條件，則返回步驟2繼續(xù)進(jìn)行下一次迭代；否則，可將最后復(fù)合形的好點(diǎn)X(L)及其函數(shù)值F(X(L))作為最優(yōu)解輸出。第31頁(yè),共77頁(yè)，2024年2月25日，星期天比較復(fù)合形各頂點(diǎn)的函數(shù)值，找出好點(diǎn)XL，壞點(diǎn)XHXH=XRα=0.5α找出次壞點(diǎn)XSH，XH=XSH滿足終止條件？X*=XL,F*=F(XL)結(jié)束3.6流程圖是否

給定K，δ，α，ε，ai,bi

i=1,2,…n產(chǎn)生初始復(fù)合形頂點(diǎn)Xj,j=1,2,…,K計(jì)算復(fù)合形各頂點(diǎn)的函數(shù)值F(Xj),j=1,2,…,K是是是否否否XR∈DFR<F(XH)第32頁(yè),共77頁(yè)，2024年2月25日，星期天3.7復(fù)合形法的Matlab程序

程序清單function[xo,fo,go]=opt_complex(f,g_cons,x0,xl,xu,TolX,TolFun,MaxIter)N=length(x0);M=size(g_cons);M=length(M(:,1));k1=0;k=N+1;%單純形頂點(diǎn)個(gè)數(shù)gx=ones(M,1);whilemax(gx)>0x0=xl+rand(N,1).*xu;gx=feval(g_cons,x0);end第33頁(yè),共77頁(yè)，2024年2月25日，星期天[x1,fx]=gen_complex(x0,k,f,g_cons);flag1=1;flag2=1;flag3=1;k1=0fxx1fprintf('此處暫停，請(qǐng)按下任意鍵繼續(xù)\n')pausewhilek1<MaxIterflag1=1;flag2=1;flag3=1;k1=k1+1[fx,I]=sort(fx);fori=1:kx2(:,i)=x1(:,I(i));endx1=x2;fmax1=fx(k);imax1=I(k);fmin=fx(1);imin=I(1);fmax2=fx(k-1);imax2=I(k-1);%計(jì)算形心xc=zeros(N,1);fori=1:kxc=xc+x1(:,i);endxc=xc-x1(:,imax1);xc=xc/(k-1);gxc=feval(g_cons,xc);alpha=1.31;%反射xr=xc+alpha*(xc-x1(:,imax1));gxr=feval(g_cons,xr)ifmax(gxr)<0fxr=feval(f,xr);iffxr<fmax1fprintf('反射成功\n')fmax1,fxrfmax1=fxr;fx(imax1)=fxr;x1(:,imax1)=xr;flag1=-1;else%反射失敗flgg1=1;end第34頁(yè),共77頁(yè)，2024年2月25日，星期天else%反射失敗flag1=1;endgama=0.7;ifflag1==-1fprintf('延伸\n')xe=xr+gama*(xr-xc);gxe=feval(g_cons,xe)ifmax(gxe)<0fxe=feval(f,xe);iffxe<fmax1fprintf('延伸成功\n')fxe,fmax1fx(imax1)=fxe;fmax1=fxe;x1(:,imax1)=xe;flag2=-1;else%延伸失敗flag2=1;endelse%延伸失敗flag2=1;endendbeta=0.7;ifflag1~=-1&flag2~=-1fprintf('收縮\n')xk=x1(:,imax1)+beta*(xc-x1(:,imax1));gxk=feval(g_cons,xk)ifmax(gxk)<0fxk=feval(f,xk);iffxk<fmax1fprintf('收縮成功\n')fxk,fmax1fmax1=fxk;fx(imax1)=fxk;x1(:,imax1)=xk;flag3=-1;else%收縮失敗flag3=1;endelse第35頁(yè),共77頁(yè)，2024年2月25日，星期天%收縮失敗flag3=1;endendifflag1~=-1&flag2~=-1&flag3~=-1fprintf('flag1,flag2,flag3\n%d%d%d\n',flag1,flag2,flag3)fprintf('重新生成單純形\n')[fx,I]=sort(fx);imin=I(1);x0=x1(:,imin);[x1,fx]=gen_complex(x0,k,f,g_cons)endendxo=x1(:,imin);fo=feval(f,xo);go=feval(g_cons,xo);k1第36頁(yè),共77頁(yè)，2024年2月25日，星期天function[x1,fx]=gen_complex(x0,k,f,g_cons)N=length(x0);M=size(g_cons);M=length(M(:,1));x1(:,1)=x0;fx(1)=feval(f,x0);a=1.3;s=rand(N,k)*2-ones(N,k);s=s/norm(s);k2=1;whilek2<kx0=x1(:,1)+a*s(:,k2);gx=feval(g_cons,x0);ifmax(gx)<0k2=k2+1;x1(:,k2)=x0;fx(k2)=feval(f,x0);elsea=0.7*a;endend

第37頁(yè),共77頁(yè)，2024年2月25日，星期天3.7應(yīng)用復(fù)合形法Matlab程序求約束優(yōu)化問(wèn)題的最優(yōu)解functionopt_complex_test1%opt_complex_test1.mclc;clearall;f=inline('(x(1)-5)^2+4*(x(2)-6)^2','x');TolX=1e-6;TolFun=1e-6;x0=[8,14]';xl=[22]';xu=[79]';MaxIter=65;options=optimset('LargeScale','off');[xo,fxo,g]=opt_complex(f,@fun_cons,x0,xl,xu,TolX,TolFun,MaxIter)%用復(fù)合形法求目標(biāo)函數(shù)最優(yōu)解和最優(yōu)值[xo,fo]=fmincon(f,x0,[],[],[],[],xl,xu,@fun_cons,options)%通過(guò)使用函數(shù)fmincon解決有約束的非線性優(yōu)化問(wèn)題function[cceq]=fun_cons(x)c=[64-x(1)^2-x(2)^2-x(1)+x(2)-10x(1)-10];ceq=[];應(yīng)用opt_complex函數(shù)計(jì)算結(jié)果:xo=[5.21866.0635],fo=0.0639,g=[-0.0000,-9.1551,-4.7814]應(yīng)用fmincon函數(shù)計(jì)算結(jié)果：xo=[5.21866.0635],fo=0.0639。第38頁(yè),共77頁(yè)，2024年2月25日，星期天約束優(yōu)化問(wèn)題的間接解法約束優(yōu)化問(wèn)題的間接解法是將約束優(yōu)化問(wèn)題轉(zhuǎn)化為一系列無(wú)約束優(yōu)化問(wèn)題來(lái)進(jìn)行求解的方法。約束優(yōu)化問(wèn)題的間接解法除拉格朗日乘子法外，常用的方法還有罰函數(shù)法及增廣乘子法。雖然約束優(yōu)化問(wèn)題的間接解法可利用無(wú)約束優(yōu)化問(wèn)題的求解方法進(jìn)行求解，但由于增加了拉格朗日乘子或罰因子，其求解過(guò)程與常規(guī)無(wú)約束優(yōu)化問(wèn)題有所不同。第39頁(yè),共77頁(yè)，2024年2月25日，星期天4.1概述1.基本思想將約束問(wèn)題

轉(zhuǎn)化成無(wú)約束問(wèn)題

求解懲罰函數(shù)可調(diào)參數(shù)*構(gòu)造懲罰函數(shù)

的基本要求:①懲罰項(xiàng)用約束條件構(gòu)造;②到達(dá)最優(yōu)點(diǎn)時(shí),懲罰項(xiàng)的值為0;③當(dāng)約束不滿足或未到達(dá)最優(yōu)點(diǎn)時(shí),懲罰項(xiàng)的值大于0.第四節(jié)懲罰函數(shù)法第40頁(yè),共77頁(yè)，2024年2月25日，星期天

懲罰函數(shù)法是一種很廣泛、很有效的間接解法。它的基本原理是將約束優(yōu)化問(wèn)題中的不等式和不等式約束函數(shù)經(jīng)加權(quán)后，和原目標(biāo)函數(shù)結(jié)合為新的目標(biāo)函數(shù)——懲罰函數(shù)。

將約束優(yōu)化問(wèn)題轉(zhuǎn)換為無(wú)約束優(yōu)化問(wèn)題。求解無(wú)約束優(yōu)化問(wèn)題的極小值，從而得到原約束優(yōu)化問(wèn)題的最優(yōu)解。加權(quán)轉(zhuǎn)化項(xiàng)第四節(jié)懲罰函數(shù)法第41頁(yè),共77頁(yè)，2024年2月25日，星期天

懲罰函數(shù)法是按一定的法則改變加權(quán)因子的值，構(gòu)成一系列的無(wú)約束優(yōu)化問(wèn)題，求一系列無(wú)約束最優(yōu)解，并不斷地逼近原約束優(yōu)化問(wèn)題的最優(yōu)解。因此又稱序列無(wú)約束極小化方法。常稱SUMT方法。根據(jù)它們?cè)趹土P函數(shù)中的作用，分別稱障礙項(xiàng)和懲罰項(xiàng)。

障礙項(xiàng)的作用是當(dāng)?shù)c(diǎn)在可行域內(nèi)時(shí)，在迭代過(guò)程中將阻止迭代點(diǎn)越出可形域。

懲罰項(xiàng)的作用是當(dāng)?shù)c(diǎn)在非可行域或不滿足等式約束條件時(shí)，在迭代過(guò)程中將迫使迭代點(diǎn)逼近約束邊界或等式約束曲面。第42頁(yè),共77頁(yè)，2024年2月25日，星期天4.2分類①內(nèi)點(diǎn)法----將迭代點(diǎn)限制在可行域內(nèi);②外點(diǎn)法----迭代點(diǎn)一般在可行域外;③混合法----將外點(diǎn)法和內(nèi)點(diǎn)法結(jié)合起來(lái)解GP型問(wèn)題.

按照懲罰函數(shù)在優(yōu)化過(guò)程中迭代點(diǎn)是否可行，分為：內(nèi)點(diǎn)法、外點(diǎn)法及混合法。第四節(jié)懲罰函數(shù)法第43頁(yè),共77頁(yè)，2024年2月25日，星期天4.3SUMT內(nèi)點(diǎn)法(內(nèi)點(diǎn)懲罰函數(shù)法、障礙函數(shù)法)1.懲罰函數(shù)的構(gòu)造原問(wèn)題:s.t.可取式中,1)當(dāng)X趨于D的邊界時(shí),中間函數(shù)B(X)趨于無(wú)窮大,故又稱為障礙(圍墻)函數(shù);

r

稱為罰因子，在逐次迭代中越來(lái)越小第44頁(yè),共77頁(yè)，2024年2月25日，星期天4.3.1基本思想：

內(nèi)點(diǎn)法將新目標(biāo)函數(shù)Φ(x,r)構(gòu)筑在可行域D內(nèi)，隨著懲罰因子r(k)的不斷遞減，生成一系列新目標(biāo)函數(shù)Φ(xk,r(k))，在可行域內(nèi)逐步迭代，產(chǎn)生的極值點(diǎn)xk*(r(k))序列從可行域內(nèi)部趨向原目標(biāo)函數(shù)的約束最優(yōu)點(diǎn)x*。例：求下述約束優(yōu)化問(wèn)題的最優(yōu)點(diǎn)。

min.f(x)=xx∈R1s.tg(x)=1-x≤0X1*X2*X*4.3SUMT內(nèi)點(diǎn)法(內(nèi)點(diǎn)懲罰函數(shù)法、障礙函數(shù)法)第45頁(yè),共77頁(yè)，2024年2月25日，星期天4.3.2懲罰函數(shù)的形式：其中：懲罰（加權(quán)）因子罰因子降低系數(shù)（罰因子遞減速率）c：0<c<14.3SUMT內(nèi)點(diǎn)法(內(nèi)點(diǎn)懲罰函數(shù)法、障礙函數(shù)法)第46頁(yè),共77頁(yè)，2024年2月25日，星期天4.3.3迭代步驟：選取合適的初始點(diǎn)x(0)

，以及r(0)、c、計(jì)算精度ε1、ε2

，令k=0；

2.構(gòu)造懲罰（新目標(biāo)）函數(shù)；3.調(diào)用無(wú)約束優(yōu)化方法，求新目標(biāo)函數(shù)的最優(yōu)解xk*和Φ(xk,r(k))；4.判斷是否收斂：運(yùn)用終止準(zhǔn)則①前后兩次無(wú)約束極小點(diǎn)之間的距離

②相鄰兩點(diǎn)罰函數(shù)的相對(duì)誤差若均滿足，停止迭代，有約束優(yōu)化問(wèn)題的最優(yōu)點(diǎn)為x*=xk*；若有一個(gè)準(zhǔn)則不滿足，則令并轉(zhuǎn)入第3步，繼續(xù)計(jì)算。4.3SUMT內(nèi)點(diǎn)法(內(nèi)點(diǎn)懲罰函數(shù)法、障礙函數(shù)法)第47頁(yè),共77頁(yè)，2024年2月25日，星期天下面介紹內(nèi)點(diǎn)法中的初始點(diǎn)、懲罰因子初值及其縮減系數(shù)的選取和收斂條件的確定。1.初始點(diǎn)的選取

初始點(diǎn)應(yīng)選離約束邊界較遠(yuǎn)的可行點(diǎn)。程序設(shè)計(jì)時(shí)，一般，考慮具有人工輸入和計(jì)算機(jī)自動(dòng)生成可行初始點(diǎn)的兩種功能。4.3SUMT內(nèi)點(diǎn)法第48頁(yè),共77頁(yè)，2024年2月25日，星期天1.初始點(diǎn)x(0)

的選擇方法①人工估算，需要校核可行性；②計(jì)算機(jī)隨機(jī)產(chǎn)生，也需校核可行性；③搜索方法：

任意給出一個(gè)初始點(diǎn)；判斷其可行性，若違反了S個(gè)約束，求出不滿足約束中的最大值：

應(yīng)用優(yōu)化方法減少違反約束：

以求得的設(shè)計(jì)點(diǎn)作為新初始點(diǎn)，繼續(xù)其判斷可行性，若仍有不滿足的約束，則重復(fù)上述過(guò)程，直至初始點(diǎn)可行。4.3SUMT內(nèi)點(diǎn)法(內(nèi)點(diǎn)懲罰函數(shù)法、障礙函數(shù)法)第49頁(yè),共77頁(yè)，2024年2月25日，星期天2.懲罰因子的初值的選取懲罰因子的初值選取應(yīng)適當(dāng)，否則會(huì)影響迭代計(jì)算的正常進(jìn)行。太大會(huì)影響迭代次數(shù)，太小會(huì)使懲罰函數(shù)的形態(tài)變壞，難以收斂到極值點(diǎn)。1）取r0=1，根據(jù)試算的結(jié)果，再?zèng)Q定增加或減少r0

值。2）按經(jīng)驗(yàn)公式

計(jì)算r0

值。這樣選取的r0

，可以是懲罰函數(shù)中的障礙項(xiàng)和原目標(biāo)函數(shù)的值大致相等，不會(huì)因障礙項(xiàng)的值太大則起支配作用，也不會(huì)因障礙項(xiàng)的值太小而被忽略掉。第50頁(yè),共77頁(yè)，2024年2月25日，星期天3.懲罰因子的縮減系數(shù)c的選取

在構(gòu)造序列懲罰函數(shù)時(shí)，懲罰因子r是一個(gè)逐次遞減到0的數(shù)列，相鄰兩次迭代的懲罰因子的關(guān)系為：懲罰因子的縮減系數(shù)通常的取值范圍：0.1-0.7之間。第51頁(yè),共77頁(yè)，2024年2月25日，星期天罰因子為使

與原問(wèn)題同解,應(yīng)使*對(duì)于一個(gè)

,求解一個(gè)無(wú)約束優(yōu)化問(wèn)題.前一問(wèn)題的結(jié)果為后一問(wèn)題的初值,故為系列無(wú)約束極小化方法(SequentialUnconstrainedMinimizationTechnique).第52頁(yè),共77頁(yè)，2024年2月25日，星期天4.收斂條件①前后兩次無(wú)約束極小點(diǎn)之間的距離②相鄰兩點(diǎn)罰函數(shù)的相對(duì)誤差第53頁(yè),共77頁(yè)，2024年2月25日，星期天5.幾個(gè)參數(shù)選擇小結(jié)：懲罰因子初始值r(0)

的選擇：

過(guò)大、過(guò)小均不好，建議考慮選擇：2.

降低系數(shù)c的選擇：c的典型值為0.1～0.7。建議先試算。3.

初始點(diǎn)x(0)

的選擇：要求：

①在可行域內(nèi)；②不要離約束邊界太近。方法：

①人工估算，需要校核可行性；②計(jì)算機(jī)隨機(jī)產(chǎn)生，也需校核可行性。4.3SUMT內(nèi)點(diǎn)法(內(nèi)點(diǎn)懲罰函數(shù)法、障礙函數(shù)法)第54頁(yè),共77頁(yè)，2024年2月25日，星期天6.方法評(píng)價(jià)：

用于目標(biāo)函數(shù)比較復(fù)雜，或在可行域外無(wú)定義的場(chǎng)合下；由于優(yōu)化過(guò)程是在可行域內(nèi)逐步改進(jìn)設(shè)計(jì)方案，故在解決工程問(wèn)題時(shí)，只要滿足工程要求，即使未達(dá)最優(yōu)解，接近的過(guò)程解也是可行的；初始點(diǎn)和序列極值點(diǎn)均需嚴(yán)格滿足所有約束條件；不能解決等式約束問(wèn)題。4.3SUMT內(nèi)點(diǎn)法(內(nèi)點(diǎn)懲罰函數(shù)法、障礙函數(shù)法)第55頁(yè),共77頁(yè)，2024年2月25日，星期天

輸出X*，F(xiàn)*=F（X*）結(jié)束是4.3SUMT內(nèi)點(diǎn)罰函數(shù)法迭代步驟用無(wú)約束方法求

的極小點(diǎn)X*輸入X0，r0,c,ε否k=k+1,Xk=X*，rk=crkK=0,Xk=X0,第56頁(yè),共77頁(yè)，2024年2月25日，星期天例:解:懲罰函數(shù)在D內(nèi)

,對(duì)于固定的

,令得r(k)x*f(x*)B(x*)1/22111.51/101.44720.72362.23610.94721/501.20.650.7…1/62501.01790.508955.90170.5179…010.50.54.3SUMT內(nèi)點(diǎn)法(內(nèi)點(diǎn)懲罰函數(shù)法、障礙函數(shù)法)第57頁(yè),共77頁(yè)，2024年2月25日，星期天r(k)x*f(x*)B(x*)1/22111.51/101.44720.72362.23610.94721/501.20.650.7…1/62501.01790.508955.90170.5179…010.50.5第58頁(yè),共77頁(yè)，2024年2月25日，星期天

內(nèi)點(diǎn)法是將懲罰因數(shù)定義于可行域內(nèi)，而外點(diǎn)法與內(nèi)點(diǎn)法不同，是將懲罰項(xiàng)函數(shù)定義于可行區(qū)域的外部。序列迭代點(diǎn)從可行域外部逐漸逼近約束邊界上的最優(yōu)點(diǎn)。4.4外點(diǎn)懲罰函數(shù)法（衰減函數(shù)法）外點(diǎn)法可以用來(lái)求解含不等式和等式約束的優(yōu)化問(wèn)題。對(duì)于約束優(yōu)化問(wèn)題第59頁(yè),共77頁(yè)，2024年2月25日，星期天懲罰因子，它是由小到大。懲罰項(xiàng)

由懲罰項(xiàng)可知，當(dāng)?shù)c(diǎn)不可行時(shí)，懲罰項(xiàng)的值大于零。

當(dāng)?shù)c(diǎn)離約束邊界越遠(yuǎn)時(shí)，懲罰項(xiàng)愈大，這可看成是對(duì)迭代點(diǎn)不滿足約束條件的一種懲罰。轉(zhuǎn)化后的外點(diǎn)懲罰函數(shù)的形式為：第60頁(yè),共77頁(yè)，2024年2月25日，星期天1.基本思想：

外點(diǎn)法將新目標(biāo)函數(shù)Φ(x,r)構(gòu)筑在可行域D外，隨著懲罰因子r(k)的不斷遞增，生成一系列新目標(biāo)函數(shù)Φ(xk,r(k))，在可行域外逐步迭代，產(chǎn)生的極值點(diǎn)xk*(r(k))序列從可行域外部趨向原目標(biāo)函數(shù)的約束最優(yōu)點(diǎn)x*。例：求下述約束優(yōu)化問(wèn)題的最優(yōu)點(diǎn)。

min.f(x)=xx∈R1s.tg(x)=1-x≤0新目標(biāo)函數(shù)：44.4外點(diǎn)懲罰函數(shù)法（衰減函數(shù)法）第61頁(yè),共77頁(yè)，2024年2月25日，星期天懲罰項(xiàng)是罰因子和中間函數(shù)的乘積；內(nèi)點(diǎn)法中隨著設(shè)計(jì)變量移向約束函數(shù)的邊界，中間函數(shù)值不斷增加，罰因子不斷減小，在迭代過(guò)程中懲罰項(xiàng)最終趨于零。外點(diǎn)法，即在迭代過(guò)程中隨著設(shè)計(jì)變量移向約束函數(shù)的邊界，使中間函數(shù)逐步減小，而使罰因子逐步增大。如此構(gòu)造出的罰函數(shù)稱為外點(diǎn)罰函數(shù)，外點(diǎn)罰函數(shù)的具體形式如下。4.4外點(diǎn)懲罰函數(shù)法（衰減函數(shù)法）2.懲罰函數(shù)的構(gòu)造第62頁(yè),共77頁(yè)，2024年2月25日，星期天2.懲罰函數(shù)的構(gòu)造4.4外點(diǎn)懲罰函數(shù)法（衰減函數(shù)法）第63頁(yè),共77頁(yè)，2024年2月25日，星期天2.懲罰函數(shù)的構(gòu)造4.4外點(diǎn)懲罰函數(shù)法（衰減函數(shù)法）第64頁(yè),共77頁(yè)，2024年2月25日，星期天2.懲罰函數(shù)的構(gòu)造考慮非線性規(guī)劃問(wèn)題:s.t.懲罰函數(shù)可取為2)罰因子*1)時(shí),懲罰項(xiàng)為0,不懲罰;時(shí),懲罰項(xiàng)大于0,有懲罰作用.因

邊界時(shí),懲罰項(xiàng)中大括號(hào)中的值趨于0,為保證懲罰作用,應(yīng)取4.4外點(diǎn)懲罰函數(shù)法（衰減函數(shù)法）第65頁(yè),共77頁(yè)，2024年2月25日，星期天3.幾個(gè)參數(shù)的選擇r(0)

的選擇:r(0)

過(guò)大，會(huì)使懲罰函數(shù)的等值線變形或偏心，求極值困難。

r(0)

過(guò)小，迭代次數(shù)太多。x(0)

的選擇：基本上可以在可行域內(nèi)外，任意選擇。遞增系數(shù)c的選擇：

通常選擇5～10，可根據(jù)具體題目，進(jìn)行試算調(diào)整。4.4外點(diǎn)懲罰函數(shù)法（衰減函數(shù)法）第66頁(yè),共77頁(yè)，2024年2月25日，星期天4.終止準(zhǔn)則和約束裕量：

終止準(zhǔn)則：約束裕量：當(dāng)必須嚴(yán)格滿足約束條件時(shí)，選用約束裕量δ。g’=g+δgδδ0δ04.4外點(diǎn)懲罰函數(shù)法（衰減函數(shù)法）第67頁(yè),共77頁(yè)，2024年2月25日，星期天5.外點(diǎn)法迭代步驟

2.構(gòu)造懲罰（新目標(biāo)）函數(shù)，調(diào)用無(wú)約束優(yōu)化方法，求新目標(biāo)函數(shù)的最優(yōu)解xk*和Φ(xk,r