約束優(yōu)化方法

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

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

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

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

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

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

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

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

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

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

。2.比較XL

和X0兩點的目標函數(shù)值，若f(XL)<f(X0)，則取XL

和X0連線方向為可行搜索方向；若f(XL)>f(X0)，則步長α0

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

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

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

α=α0,F0=F(X0)F=F（X）j=1K=K+1是K=0,j=0產(chǎn)生隨機方向α=0.5α否F<F0j=0K<mα≤ε結(jié)束X*=X0,F*=F0是否是否是否X∈D是否第16頁,共77頁，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隨機方向法的Matlab程序第17頁,共77頁，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頁,共77頁，2024年2月25日，星期天例:求2.7隨機方向法的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];計算結(jié)果：x1=[-0.0076-3.0000],f=-2.9999,g=[-0.0000-4.0076]第19頁,共77頁，2024年2月25日，星期天第三節(jié)復(fù)合形法復(fù)合形法是求解約束優(yōu)化問題的一種重要的直接解法?；舅悸罚?/p>

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

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

3.1基本思路

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

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

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

個隨機數(shù)

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

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

若仍不可行，則重復(fù)此步驟，直至進入可行域為止。

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

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

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

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

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

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

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

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

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

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

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

i=1,2,…n產(chǎn)生初始復(fù)合形頂點Xj,j=1,2,…,K計算復(fù)合形各頂點的函數(shù)值F(Xj),j=1,2,…,K是是是否否否XR∈DFR<F(XH)第32頁,共77頁，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;%單純形頂點個數(shù)gx=ones(M,1);whilemax(gx)>0x0=xl+rand(N,1).*xu;gx=feval(g_cons,x0);end第33頁,共77頁，2024年2月25日，星期天[x1,fx]=gen_complex(x0,k,f,g_cons);flag1=1;flag2=1;flag3=1;k1=0fxx1fprintf('此處暫停，請按下任意鍵繼續(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);%計算形心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頁,共77頁，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頁,共77頁，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頁,共77頁，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頁,共77頁，2024年2月25日，星期天3.7應(yīng)用復(fù)合形法Matlab程序求約束優(yōu)化問題的最優(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ù)合形法求目標函數(shù)最優(yōu)解和最優(yōu)值[xo,fo]=fmincon(f,x0,[],[],[],[],xl,xu,@fun_cons,options)%通過使用函數(shù)fmincon解決有約束的非線性優(yōu)化問題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ù)計算結(jié)果:xo=[5.21866.0635],fo=0.0639,g=[-0.0000,-9.1551,-4.7814]應(yīng)用fmincon函數(shù)計算結(jié)果：xo=[5.21866.0635],fo=0.0639。第38頁,共77頁，2024年2月25日，星期天約束優(yōu)化問題的間接解法約束優(yōu)化問題的間接解法是將約束優(yōu)化問題轉(zhuǎn)化為一系列無約束優(yōu)化問題來進行求解的方法。約束優(yōu)化問題的間接解法除拉格朗日乘子法外，常用的方法還有罰函數(shù)法及增廣乘子法。雖然約束優(yōu)化問題的間接解法可利用無約束優(yōu)化問題的求解方法進行求解，但由于增加了拉格朗日乘子或罰因子，其求解過程與常規(guī)無約束優(yōu)化問題有所不同。第39頁,共77頁，2024年2月25日，星期天4.1概述1.基本思想將約束問題

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

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

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

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

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

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

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

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

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

r

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

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

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

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

，令k=0；

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

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

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

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

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

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

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

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

計算r0

值。這樣選取的r0

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

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

與原問題同解,應(yīng)使*對于一個

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

的選擇：

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

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

初始點x(0)

的選擇：要求：

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

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

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

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

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

,對于固定的

,令得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)點法(內(nèi)點懲罰函數(shù)法、障礙函數(shù)法)第57頁,共77頁，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頁,共77頁，2024年2月25日，星期天

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

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

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

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

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

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

的選擇:r(0)

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

r(0)

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

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

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

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

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