第6章-多維約束優(yōu)化方法

第6章多維約束優(yōu)化方法6.1隨機(jī)方向法 976.2復(fù)合形法 996.3可行方向法 1046.3.1可行方向的產(chǎn)生方法 1046.3.2尋優(yōu)策略 1056.3.3算法步驟 1076.4懲罰函數(shù)法 1106.4.1內(nèi)點(diǎn)懲罰函數(shù)法 1116.4.2外點(diǎn)懲罰函數(shù)法 1146.4.3混合懲罰函數(shù)法 1166.5網(wǎng)格法 1186.6線性逼近法 1196.7廣義簡(jiǎn)約梯度法 1226.8二次規(guī)劃法 1256.9結(jié)構(gòu)設(shè)計(jì)的優(yōu)化準(zhǔn)則法 126§6.0引言機(jī)械優(yōu)化設(shè)計(jì)中的問(wèn)題，大多數(shù)屬于約束優(yōu)化設(shè)計(jì)問(wèn)題，其數(shù)學(xué)模型為根據(jù)求解方式的不同，可分為:直接解法，間接解法。

直接解法通常適用于僅含不等式約束的問(wèn)題，思路是在m個(gè)不等式約束條件所確定的可行域內(nèi)，選擇一個(gè)初始點(diǎn)，然后決定可行搜索方向S，且以適當(dāng)?shù)牟介L(zhǎng)，沿d方向進(jìn)行尋優(yōu)，得到一個(gè)使目標(biāo)函數(shù)值下降的可行的新點(diǎn)，即完成一次迭代。再以新點(diǎn)為起點(diǎn)，重復(fù)上述尋優(yōu)過(guò)程，直至滿足收斂條件?？尚行裕哼m用性：步長(zhǎng)可行搜索方向

可行搜索方向：當(dāng)設(shè)計(jì)點(diǎn)沿該方向作微量移動(dòng)時(shí)，目標(biāo)函數(shù)值將下降，且不會(huì)越出可行域。隨機(jī)方向法、復(fù)合形法、可行方向法等

間接解法的基本思路是將約束優(yōu)化問(wèn)題通過(guò)一定形式的變換，轉(zhuǎn)化為一個(gè)或一系列的無(wú)約束優(yōu)化問(wèn)題。再對(duì)新的目標(biāo)函數(shù)進(jìn)行無(wú)約束優(yōu)化計(jì)算，從而間接地搜索到原約束問(wèn)題的最優(yōu)點(diǎn)。罰函數(shù)法。等式約束優(yōu)化問(wèn)題的拉格朗日乘子法

極值點(diǎn)處：其中為待定系數(shù)，稱為拉格朗日乘子。等同于以下無(wú)約束優(yōu)化問(wèn)題

例：增加一個(gè)斜坡，把碗底移動(dòng)了多維有約束優(yōu)化方法在求解約束優(yōu)化問(wèn)題時(shí)，雖然可以利用第三章的無(wú)約束優(yōu)化方法，再加上約束的邏輯判斷，使搜索點(diǎn)保持在可行域內(nèi)逐步逼近約束極值點(diǎn)，但這樣處理太復(fù)雜，缺乏嚴(yán)格的科學(xué)性。因此，出現(xiàn)了一些直接求解約束優(yōu)化問(wèn)題的方法，其基本思路也是數(shù)值迭代法。目前，約束優(yōu)化方法雖然不如無(wú)約束優(yōu)化方法那樣多而完善，但對(duì)求解工程優(yōu)化問(wèn)題已有很多較好的方法。(1).直接解法

直接法包括：網(wǎng)格法、分層降維枚舉法、復(fù)合形法、隨機(jī)試驗(yàn)法、隨機(jī)方向法、可變?nèi)莶罘ê涂尚蟹较蚍ā?2).間接解法

間接法包括：罰函數(shù)法、內(nèi)點(diǎn)罰函數(shù)法、外點(diǎn)罰函數(shù)法、混合罰函數(shù)法、精確罰函數(shù)法、廣義乘子法、廣義簡(jiǎn)約梯度法和約束變尺度法。對(duì)比無(wú)約束優(yōu)化方法：

直接尋優(yōu)：不需要利用目標(biāo)函數(shù)和約束函數(shù)的梯度，就可直接利用迭代點(diǎn)和目標(biāo)函數(shù)值的信息來(lái)構(gòu)造搜索方向。間接尋優(yōu)：須利用目標(biāo)、約束函數(shù)的梯度，其中也包括利用差分來(lái)近似梯度的應(yīng)用。§6-1隨機(jī)方向法基本思想：利用計(jì)算機(jī)產(chǎn)生的隨機(jī)數(shù)構(gòu)成隨機(jī)方向組，在可行域內(nèi)沿該方向組中最好的方向進(jìn)行尋優(yōu)。屬于直接解法。

一、隨機(jī)方向的產(chǎn)生（random,ran）二、方法首先選定可行（在可行域內(nèi)）初始點(diǎn)，利用隨機(jī)函數(shù)構(gòu)成隨方向，按給定初始步長(zhǎng)取得試探點(diǎn)，檢查適用性（目標(biāo)下降）和可行性，均滿足則作為新起點(diǎn)，繼續(xù)取試探點(diǎn)，否則重新產(chǎn)生隨機(jī)方向，以最終成功點(diǎn)為起點(diǎn)，繼續(xù)尋優(yōu)。如M個(gè)試探方向均失敗，則縮短步長(zhǎng)繼續(xù)。終止條件：步長(zhǎng)足夠小。流程圖太復(fù)雜,須重畫(huà)思路較清晰的尋找隨機(jī)方向改進(jìn)算法的程序流程簡(jiǎn)圖尋找極值點(diǎn)的雙向?qū)?yōu)改進(jìn)算法程序流程簡(jiǎn)圖

隨機(jī)數(shù)的產(chǎn)生隨機(jī)方向由列陣表示，其每個(gè)元素均應(yīng)為正負(fù)幾率相同隨機(jī)數(shù)，否則不能保證尋優(yōu)方向的隨機(jī)特性。高級(jí)計(jì)算機(jī)語(yǔ)言均提供了產(chǎn)生隨機(jī)數(shù)的函數(shù)，如VisualBasic語(yǔ)言為random、RND；Fortran語(yǔ)言為SEED(INTEGER(4)iseed)、random、rand；Matlib語(yǔ)言為rand、randn；C語(yǔ)言為randomize(void)、rand(void)、srand(unsigned)、random(int)。由于C語(yǔ)言的適用性、可移植性強(qiáng)，所以本文對(duì)TurboC隨機(jī)數(shù)產(chǎn)生的實(shí)現(xiàn)提出相關(guān)技巧。TurboC產(chǎn)生隨機(jī)數(shù)有兩種方法：（１）由randomize(void)、rand(void)產(chǎn)生[0,32767]區(qū)間的隨機(jī)整數(shù)。該方法產(chǎn)生的隨機(jī)數(shù)與時(shí)鐘有關(guān)，適合于兩個(gè)隨機(jī)數(shù)相差時(shí)間較長(zhǎng)的情況，如集中給出隨機(jī)數(shù)，則在當(dāng)前計(jì)算機(jī)的運(yùn)算速度下會(huì)產(chǎn)生相同的隨機(jī)數(shù)。因此隨機(jī)方向法不能采用這種方法產(chǎn)生隨機(jī)數(shù)。（２）由srand(unsignedseed)、random(intnum)產(chǎn)生[0,num-1]區(qū)間的隨機(jī)整數(shù)（該隨機(jī)數(shù)與seed的數(shù)值有關(guān)），可用于隨機(jī)方向法。方向列陣的元素不能都是大于零的，因此可由以下程序段產(chǎn)生[-50，50]區(qū)間內(nèi)的隨機(jī)數(shù)：srand(seed1);seed1+=57;seed1=seed1%10001;dum=random(101)-50;相關(guān)技巧為：以累加素?cái)?shù)的方法保證每個(gè)隨機(jī)數(shù)對(duì)應(yīng)的seed均不同，為保證seed不超出unsigned數(shù)據(jù)類型的范圍將其限制在一定范圍之內(nèi)，以減去中間值的方法保證隨機(jī)數(shù)為正和為負(fù)的機(jī)率相同。最壞點(diǎn)：目標(biāo)函數(shù)值最大的點(diǎn)；中心點(diǎn)：除去最壞點(diǎn)的復(fù)合形幾何中心；映射點(diǎn)：最壞點(diǎn)相對(duì)于中心點(diǎn)的對(duì)稱點(diǎn)或其拉近點(diǎn)；復(fù)合形的收縮：因映射系數(shù)不斷減半，各頂點(diǎn)的距離逐漸縮短§6-2復(fù)合形法一、基本思想（摸魚(yú)）通過(guò)對(duì)復(fù)合形各頂點(diǎn)的函數(shù)值計(jì)算與比較，找出壞點(diǎn)，反復(fù)進(jìn)行壞點(diǎn)的映射與復(fù)合形的收縮，使之逐步逼近約束極值點(diǎn)。初始復(fù)合形：N+1~2N個(gè)隨機(jī)可行點(diǎn)組成；單形替換法框圖二、初始復(fù)合形的構(gòu)成

隨機(jī)產(chǎn)生，逐一調(diào)入可行域

三、復(fù)合形法的迭代步驟1初始復(fù)合形。計(jì)算各頂點(diǎn)函數(shù)值，確定壞點(diǎn)、次壞點(diǎn)、好點(diǎn)；2計(jì)算中心點(diǎn)X0，計(jì)算映射點(diǎn)，并檢查是否在可行域內(nèi)。若為非可行點(diǎn)，將映射系數(shù)縮半后改變映射點(diǎn)，直到映射點(diǎn)進(jìn)入可行域內(nèi)；3構(gòu)成新的復(fù)合形計(jì)算映射點(diǎn)目標(biāo)函數(shù)，并與壞點(diǎn)函數(shù)值相比較，若優(yōu)于壞點(diǎn)，則替換，否則縮半映射系數(shù)。M次縮短后仍不優(yōu)，則改用次壞點(diǎn)映射方向。4判斷終止條件：四、特點(diǎn)（1）復(fù)合形法是求解約束非線性優(yōu)化問(wèn)題的一種直接方法，僅通過(guò)選取各頂點(diǎn)并比較各點(diǎn)處函數(shù)值的大小，就可尋找下一步的探索方向。但復(fù)合形各頂點(diǎn)的選擇和替換，不僅要滿足目標(biāo)函數(shù)值下降的要求，還應(yīng)當(dāng)滿足所有的約束條件。（2）復(fù)合形法適用于僅含不等式約束的問(wèn)題。（3）沿映射方向進(jìn)行一次有約束的一維尋優(yōu)得到映射點(diǎn)可能會(huì)更好。(可行域?yàn)橥辜?(單形替換法)五、例5-2

（1）取頂點(diǎn)數(shù)為2N=4，產(chǎn)生初始復(fù)合形的頂點(diǎn)并檢驗(yàn)可行性，計(jì)算各點(diǎn)的目標(biāo)函數(shù)值，確定好點(diǎn)、次壞點(diǎn)、壞點(diǎn)。

取映射因子α為1.3在可行域之外，取映射因子α為1.0上課之前用M語(yǔ)言畫(huà)出該題的圖示在可行域之外，取映射因子α為0.4#include<math.h>/*數(shù)學(xué)庫(kù)*/#include<stdlib.h>/*標(biāo)準(zhǔn)輸入輸出庫(kù)*/#include<time.h>/*時(shí)間庫(kù)*/#defineK6/*復(fù)合形的頂點(diǎn)數(shù)*/#definee0.001/*以復(fù)合形大小判斷收斂精度*/doublefun(doublex1[3]);/*三維優(yōu)化問(wèn)題目標(biāo)函數(shù)*/inttj(doublexx[3]);/*檢驗(yàn)可行點(diǎn)的子程序*/intcomplex();/*復(fù)合形法子程序*/voidini_complex();/*產(chǎn)生初始復(fù)合形的子程序*/main()/*主函數(shù)*/{doublea[3]={-100,-200,-30},b[3]={1,3,5};/*設(shè)計(jì)變量的上下界{82,82,10},b[3]={220,210,50}*/doublezj[6][3];/*復(fù)合形頂點(diǎn)坐標(biāo)*/doublexc[3],y=0;/*最優(yōu)點(diǎn)（中心點(diǎn)），最優(yōu)解*/inti,k,k1;/**/time_tt;srand((unsigned)time(&t));/*顯示時(shí)間*/for(i=1;;i++){ini_complex(a,b,zj);/*產(chǎn)生初始復(fù)合形*/if(complex(zj,xc,y)){printf("\n最優(yōu)點(diǎn)坐標(biāo)：x1=%12.5ex2=%12.5ex3=%12.5e\n最優(yōu)解為%12.5e\n",xc[0],xc[1],xc[2],y);exit(0);}else{printf("\n第%d次重新產(chǎn)生初始復(fù)合形\n",i);}}}/*結(jié)束主程序*//*產(chǎn)生初始復(fù)合形的子程序*/voidini_complex(a,b,zj)/*上界，下界，各頂點(diǎn)坐標(biāo)*/doublea[3],b[3],zj[6][3];{doublex[6][3],s[3];/*初始復(fù)合形頂點(diǎn)坐標(biāo)(只保證其一可行);頂點(diǎn)坐標(biāo)之和*/doublebkx[6][3],xd[3];/*形成的初始復(fù)合形中不可行的頂點(diǎn)坐標(biāo),其中所有可行點(diǎn)的中心點(diǎn)坐標(biāo)*/intq=1,m=0,i,k,k1;/*可行點(diǎn)數(shù),不可行點(diǎn)數(shù)*/time_tt;srand((unsigned)time(&t));/*顯示時(shí)間*/cx:for(i=0;i<3;i++)x[0][i]=a[i]+rand()*(b[i]-a[i])/32767;/*產(chǎn)生隨機(jī)點(diǎn)*/if(!tj(x[0]))gotocx;/*如果不在可行域，則重新產(chǎn)生*/for(i=0;i<3;i++)zj[0][i]=x[0][i];/*zj數(shù)組用來(lái)存放滿足條件的復(fù)合形的頂點(diǎn)，后同．*/for(k=1;k<K;k++)/*隨機(jī)產(chǎn)生其它頂點(diǎn)*/{for(i=0;i<3;i++)x[k][i]=a[i]+rand()*(b[i]-a[i])/32767;}for(i=0;i<3;i++)s[i]=x[0][i];q=1;m=0;/*可行點(diǎn)數(shù)、不可行點(diǎn)數(shù)*/for(k=1;k<K;k++){if(tj(x[k]))/*如果第k個(gè)頂點(diǎn)在可行域*/{for(i=0;i<3;i++){zj[q][i]=x[k][i];/*頂點(diǎn)*/s[i]=s[i]+x[k][i];/*頂點(diǎn)坐標(biāo)和*/}q=q+1;/*可行點(diǎn)的數(shù)目+1*/}else {bkx[m][i]=x[k][i];m=m+1;}/**/}/*隨機(jī)產(chǎn)生的頂點(diǎn)中，有(q)個(gè)可行點(diǎn)，其坐標(biāo)保存于zj[][]；有m個(gè)不可行點(diǎn)，其坐標(biāo)保存于bkx[][]*/for(i=0;i<3;i++)xd[i]=s[i]/(q+0.0);/*初始復(fù)合形中所有可行點(diǎn)的中心點(diǎn)坐標(biāo)*/for(k1=0;k1<K-q;k1++)/*采用與中心點(diǎn)距離減半法，將不可行點(diǎn)拉進(jìn)可行域*/{cl:for(i=0;i<3;i++)bkx[k1][i]=xd[i]+0.5*(bkx[k1][i]-xd[i]);if(!tj(bkx[k1]))gotocl;/*如果仍不可行，則繼續(xù)拉近*/for(i=0;i<3;i++){zj[q][i]=bkx[k1][i];q=q+1;}/*zj[][]保存可行點(diǎn)的坐標(biāo)*/}return;}/*結(jié)束產(chǎn)生初始復(fù)合形的子程序*/映射系數(shù)法一維尋優(yōu)法復(fù)合形法的改進(jìn)（1）當(dāng)沿映射方向：最壞點(diǎn)中心點(diǎn)尋優(yōu)時(shí)，如最優(yōu)點(diǎn)為最壞點(diǎn)，則最壞點(diǎn)在非凸性約束邊界上，須令該最壞點(diǎn)向最好點(diǎn)靠攏，移動(dòng)距離為兩點(diǎn)間距離的一半?？煞磸?fù)按以下公式修正，直至最壞點(diǎn)為可行點(diǎn)。（2）當(dāng)約束邊界為直線時(shí)，易造成復(fù)合形兩條或兩條以上的棱線重合或接近于重合，這種情況也是復(fù)合形降維的原因之一。須在必要時(shí)移動(dòng)新頂點(diǎn)，使復(fù)合形保持維數(shù)不變。為避免三點(diǎn)共線的情況，可在更新復(fù)合形之后逐個(gè)比較頂點(diǎn)間連線，適當(dāng)?shù)匾苿?dòng)復(fù)合形頂點(diǎn)，使同一頂點(diǎn)處的相鄰棱線保持一定的角度。設(shè)三點(diǎn)序號(hào)為1、2、3，點(diǎn)1與點(diǎn)2的連線表示為s1、點(diǎn)1與點(diǎn)3的連線表示為s2、點(diǎn)3移動(dòng)的方向?yàn)閟3。如果方向s1、s2平行，則滿足式（6.2-2）。

§6-3可行方向法可行方向法是求解大型約束優(yōu)化問(wèn)題的主要方法之一。這種方法的基本原理是在可行域內(nèi)選擇一個(gè)初始點(diǎn)，當(dāng)確定了一個(gè)可行方向S和適當(dāng)?shù)牟介L(zhǎng)后，按式:進(jìn)行迭代計(jì)算，迭代點(diǎn)具有可行性和適用性。在不斷調(diào)整可行方向的過(guò)程中，使迭代點(diǎn)逐步逼近約束極值點(diǎn)。一、基本尋優(yōu)過(guò)程

第一步迭代都是從可行的初始點(diǎn)出發(fā)，沿該點(diǎn)的負(fù)梯度方向，第二步尋優(yōu)至某一個(gè)約束面（只有一個(gè)起作用的約束時(shí)）上,或約束面的交集（有幾個(gè)起作用的約束時(shí)）上。第三步按以下三個(gè)策略尋優(yōu)。沿非線性約束面的搜索：一般是沿著起作用約束的邊界以割線方式逐步逼近極值點(diǎn)。尋優(yōu)策略一：當(dāng)前點(diǎn)在約束面上，則產(chǎn)生一個(gè)可行方向?qū)?yōu)，得到新點(diǎn)在可行域內(nèi)，則命名為當(dāng)前點(diǎn)。尋優(yōu)策略二：若得到的新點(diǎn)在可行域外，則取可行方向與約束面的交點(diǎn)為當(dāng)前點(diǎn)。尋優(yōu)策略三：沿約束面搜索。非線性約束面須將進(jìn)入非可行域內(nèi)的新點(diǎn)設(shè)法調(diào)整到約束面上，即沿約束函數(shù)的梯度方向。假設(shè)約束函數(shù)線性，則步長(zhǎng)估計(jì)為二、適用可行方向的數(shù)學(xué)條件

可行方向是指沿該方向作微小移動(dòng)后，所得到的新點(diǎn)是可行點(diǎn)，且目標(biāo)函數(shù)值有所下降。

可行方向Ｓ應(yīng)滿足兩個(gè)條件：1）可行性條件2)適用性條件下降可行性條件：沿該方向做微小移動(dòng)后，所得到的新點(diǎn)為可行點(diǎn)。SS滿足可行和下降條件，即式:在點(diǎn)x(k)

，約束曲面的切線和目標(biāo)函數(shù)等值線的切線所圍成的扇形區(qū)，稱為可行下降方向區(qū)。三、可行方向的產(chǎn)生方法滿足可行、下降條件的方向位于可行下降扇形區(qū)內(nèi)，在扇形區(qū)內(nèi)尋找一個(gè)最有利的方向作為本次尋優(yōu)的方向。（1）負(fù)梯度方向

（2）優(yōu)選方向法

由條件：求一個(gè)以尋優(yōu)方向S為設(shè)計(jì)變量的約束優(yōu)化問(wèn)題

s.t.將約束３作為探測(cè)點(diǎn)的調(diào)整依據(jù)，則各函數(shù)均為設(shè)計(jì)變量S的線性函數(shù)，因此尋優(yōu)方向的確定成為一個(gè)（線性）規(guī)劃問(wèn)題。（３）梯度投影法

當(dāng)x(k)點(diǎn)目標(biāo)函數(shù)的負(fù)梯度方向不滿足可行條件時(shí)，可將方向投影到約束面（或約束面的交集）上，得到投影向量

Sk。P——投影算子，為n×n階矩陣

G——起作用約束函數(shù)的梯度矩陣，n×J階矩陣；

x(k)S(k)g1(x)=0g2(x)=0g3(x)=0g4(x)=0四、步長(zhǎng)的確定(確定尋優(yōu)點(diǎn)之后)確定的步長(zhǎng)應(yīng)使新的迭代點(diǎn)為可行點(diǎn)，且目標(biāo)函數(shù)具有最大的下降量?！s束一維搜索1）取最優(yōu)步長(zhǎng)從x(k)點(diǎn)出發(fā)，沿S(k)

方向進(jìn)行一維尋優(yōu)，取得最優(yōu)步長(zhǎng)，計(jì)算新點(diǎn)x的值。2）取到約束邊界的最大步長(zhǎng)

從x(k)

點(diǎn)出發(fā)，沿S(k)

方向進(jìn)行一維尋優(yōu)，得到的新點(diǎn)x為不可行點(diǎn)。

改變步長(zhǎng)，使新點(diǎn)x返回到約束面上來(lái)。使新點(diǎn)x恰好位于約束面上的步長(zhǎng)稱為最大步長(zhǎng)。調(diào)整探測(cè)點(diǎn)至可行域之內(nèi)的改進(jìn)算法流程簡(jiǎn)圖約束一維搜索：與以前所講過(guò)的一維搜索相比，約束一維搜索的特點(diǎn)在于：確定初始區(qū)間時(shí)，對(duì)產(chǎn)生的每一個(gè)探測(cè)點(diǎn)都進(jìn)行可行性判斷，如違反了某個(gè)或某些約束條件，就必須減少步長(zhǎng)因子，以使新的探測(cè)點(diǎn)落在最近的一個(gè)約束曲面上或約束曲面的一個(gè)容許的區(qū)間內(nèi)。0x1x2x(k)S(k)xk+1g2(x)=0g1(x)=0a*S

(k)aMS

(k)x如得到的相鄰三個(gè)探測(cè)點(diǎn)都是可行點(diǎn)，而且函數(shù)值呈“大－?。蟆弊兓?，則與前面一維搜索相同，兩端點(diǎn)所決定的區(qū)間就是初始區(qū)間，接著縮小區(qū)間的到一維最小點(diǎn)。如最后得到的探測(cè)點(diǎn)落在約束曲面的一個(gè)容限之內(nèi)，而且函數(shù)值比前一點(diǎn)的小，則該點(diǎn)就是一維極小點(diǎn)。f(a1)f(a2)f(a1)f(a2)a1

a1

a2a0a0

a2f(a’3)f(a’3)a’3a’3f(a3)f(a3)a3a31）設(shè)計(jì)點(diǎn)x(k)

及約束允差滿足五、收斂條件2）設(shè)計(jì)點(diǎn)x(k)

滿足庫(kù)恩-塔克條件基于盲人探路尋優(yōu)思想的可行方向法程序框圖例題5-3：用可行方向法求約束優(yōu)化問(wèn)題解:(1)取初始點(diǎn)，則起作用約束集:Jk={1}(2)尋找最優(yōu)方向，即解一個(gè)以可行方向?yàn)樵O(shè)計(jì)變量的規(guī)劃問(wèn)題：1s1s2用圖解法：最優(yōu)方向：0--11

(3)沿S

(0)方向進(jìn)行一維尋優(yōu)：x(1)在約束邊界g3(x)=0上:g3(x(1))=0(4)第二次迭代，用梯度投影法確定可行方向迭代點(diǎn)x的目標(biāo)函數(shù)負(fù)梯度不滿足方向的可行條件，將投影到約束邊界g3(x)=0上。投影算子：由上式可求得：本次尋優(yōu)方向S(1)為沿約束邊界g3(x)=0的方向，求最佳步長(zhǎng)求得：g5(x)=068x1x2g4(x)=0g3(x)=0g2(x)=0g1(x)=0x(0)S(0)（5）收斂精度判斷：由于Jk={3，5}代入KKT條件：可見(jiàn)滿足KKT條件，是優(yōu)化問(wèn)題的極值點(diǎn)。由于目標(biāo)函數(shù)是凸函數(shù)，可行域是凸集，該點(diǎn)也是優(yōu)化問(wèn)題的全局極值點(diǎn)?！?-4懲罰函數(shù)法前述方法為直接法，本節(jié)為間接法，將約束優(yōu)化問(wèn)題轉(zhuǎn)化為無(wú)約束優(yōu)化問(wèn)題來(lái)求解。

（1）懲罰函數(shù)法的基本思想：在原目標(biāo)函數(shù)中，按照一定規(guī)則，添加一些與約束函數(shù)相關(guān)的項(xiàng)，形成一系列新的目標(biāo)函數(shù)（即懲罰函數(shù)）。然后用無(wú)約束優(yōu)化方法依次求新目標(biāo)函數(shù)的最優(yōu)點(diǎn)。獲得的序列最優(yōu)點(diǎn)收斂于原約束優(yōu)化問(wèn)題的極值點(diǎn)。（2）構(gòu)成的新目標(biāo)函數(shù)，稱為懲罰函數(shù)。前提：一是不能破壞約束問(wèn)題的約束條件，二是使它歸結(jié)到原約束問(wèn)題的同一最優(yōu)點(diǎn)上去。一般形式為：按一定的法則構(gòu)成序列罰因子r1

和r2

的值，得到序列無(wú)約束優(yōu)化問(wèn)題，依次求得序列無(wú)約束問(wèn)題的最優(yōu)點(diǎn)，則序列最優(yōu)點(diǎn)收斂于原約束優(yōu)化問(wèn)題的極值點(diǎn)。從而有（3）懲罰項(xiàng)必須具有以下極限性質(zhì)：

根據(jù)懲罰項(xiàng)的不同構(gòu)成形式，懲罰函數(shù)法又可分為外點(diǎn)懲罰函數(shù)法、內(nèi)點(diǎn)懲罰函數(shù)法和混合懲罰函數(shù)法。6.4.1內(nèi)點(diǎn)法：將懲罰函數(shù)定義于可行域內(nèi)，序列最優(yōu)點(diǎn)在可行域內(nèi)逐步逼近約束邊界上的極值點(diǎn)。內(nèi)點(diǎn)法只能用來(lái)求解具有不等式約束的優(yōu)化問(wèn)題。懲罰函數(shù)的形式：或：rk是懲罰因子，一個(gè)遞減并趨近于0的正數(shù)序列，即:迭代過(guò)程中“障礙項(xiàng)”的作用是阻止迭代點(diǎn)越出可行域。當(dāng)?shù)c(diǎn)靠近某一約束邊界時(shí)，其值趨近于0，而“障礙項(xiàng)”的值陡然增加，并趨近于無(wú)窮大，好像在可行域的邊界上壘起了一道“高墻”，使迭代點(diǎn)不能越出可行域。只有當(dāng)懲罰因子時(shí)，才能求得約束邊界上的最優(yōu)點(diǎn)

流程圖：核心為無(wú)約束優(yōu)化方法(5)例5-3用內(nèi)點(diǎn)法求的約束極值點(diǎn)。解:用內(nèi)點(diǎn)法求解該問(wèn)題時(shí)，首先構(gòu)造內(nèi)點(diǎn)懲罰函數(shù):用解析法求函數(shù)的極小值，運(yùn)用極值條件：

即：由圖可見(jiàn),在可行域內(nèi),x1隨著r的減小而減小.當(dāng)x2=0時(shí),目標(biāo)函數(shù)值隨著x1的減小而減小.

當(dāng)r0時(shí),懲罰函數(shù)的最優(yōu)點(diǎn)趨近于原目標(biāo)函數(shù)的極值點(diǎn)[1,0]x1x2（6）、1）

初始點(diǎn)x0的選取使用內(nèi)點(diǎn)法時(shí)，初始點(diǎn)應(yīng)選擇一個(gè)離約束邊界較遠(yuǎn)的可行點(diǎn)。如太靠近某一約束邊界，構(gòu)造的懲罰函數(shù)可能由于障礙項(xiàng)的值很大而變得畸形，使求解無(wú)約束優(yōu)化問(wèn)題發(fā)生困難.2）

懲罰因子初值r(0)的選取懲罰因子的初值應(yīng)適當(dāng)，否則會(huì)影響迭代計(jì)算的正常進(jìn)行。一般而言，太大，將增加迭代次數(shù)；太小，會(huì)使懲罰函數(shù)的性態(tài)變壞，甚至難以收斂到極值點(diǎn)。無(wú)一般性的有效方法。對(duì)于不同的問(wèn)題，都要經(jīng)過(guò)多次試算，才能決定一個(gè)適當(dāng)

r(0)

3)懲罰因子的縮減系數(shù)c的選取在構(gòu)造序列懲罰函數(shù)時(shí)，懲罰因子r是一個(gè)逐次遞減到0的數(shù)列，相鄰兩次迭代的懲罰因子的關(guān)系為:式中的c稱為懲罰因子的縮減系數(shù)，c為小于1的正數(shù)。一般的看法是，c值的大小在迭代過(guò)程中不起決定性作用，通常的取值范圍在0.1~0.7之間。

4)收斂條件(7)算法步驟①選擇可行域內(nèi)初始點(diǎn)。②選取初始罰因子r、罰因子縮減系數(shù)c=0.1-0.5，K＝0。

③求罰函數(shù)最優(yōu)點(diǎn)，。④按終止準(zhǔn)則判別，如滿足則輸出最優(yōu)解。⑤。⑥轉(zhuǎn)至3防越界可隨r的減小而增大1、懲罰因子初始值以原目標(biāo)函數(shù)和罰函數(shù)的數(shù)值相等為原則設(shè)置，有一定局限性（例題*1000才可以）2、如不采用加高圍墻的防越界方法，則須調(diào)整he1e2隨r變小等一些措施，碰巧才能求得約束最優(yōu)點(diǎn)。3、按給定的低精度，不采用加固圍墻的方法則越界，采用該方法能尋得最優(yōu)點(diǎn)，但是提高精度則出現(xiàn)計(jì)算失敗的現(xiàn)象。如何修補(bǔ)程序的漏洞使之適合于高精度求優(yōu)？#include<stdio.h>#include<math.h>intK=0;/*調(diào)用目標(biāo)函數(shù)次數(shù)*/voidmain();/*主程序*/voidsumt();/*內(nèi)點(diǎn)懲罰函數(shù)法子程序*/voidpower();/*鮑威爾法子程序*/voidJT();/*進(jìn)退法確定極值點(diǎn)所在區(qū)間*/intGolden();/*黃金分割法子程序*/doublefunc();/*計(jì)算懲罰函數(shù)值*/doublefunc0();/*原目標(biāo)函數(shù)值*/intgau();/*約束函數(shù)的函數(shù)*/voidmain(){intn=2;/*維數(shù)*/doublex0[2];/*初始點(diǎn),返回最優(yōu)點(diǎn)*/doubley[1],h;/*最優(yōu)解,初始步長(zhǎng)*/doublee1,e2,e3;/*收斂精度值:一維尋優(yōu),POWELL法*/doubleg[3];x0[0]=-3;x0[1]=3;/*可行點(diǎn)*/e1=1.0e-5;e2=1.0e-5;e3=1.0e-5;h=0.1;sumt(n,x0,e1,e2,e3,h,y);/*維數(shù)，初始點(diǎn)(返回最優(yōu)點(diǎn)),一維、Powell收斂精度值,進(jìn)退法初始步長(zhǎng)，最優(yōu)解*/printf(“……);}voidsumt(n,x0,e1,e2,e3,h,y)/*內(nèi)點(diǎn)懲罰函數(shù)法子程序*/intn;/*維數(shù)*/doublex0[2];/*初始點(diǎn),返回最優(yōu)點(diǎn)*/doubley[1];/*最優(yōu)解*/doublee1,e2,e3;/*收斂精度值:一維尋優(yōu),POWELL法,懲罰函數(shù)法*/doubleh;/*進(jìn)退法初始步長(zhǎng)*/{inti,k;doublexl[2];/*存儲(chǔ)初始點(diǎn)*/doubler,c=0.1;/*懲罰因子及其遞減系數(shù)*/doubleg[3];/*約束函數(shù)的函數(shù)值*/doublef,f0,dum;/*尋優(yōu)解，初始解，臨時(shí)變量*/f0=func0(x0[0],x0[1]);/*初始點(diǎn)目標(biāo)函數(shù)值*/y[0]=f0;gau(x0[0],x0[1],g);

r=fabs(f0*(g[0]+g[1]+g[2]));/*初始懲罰因子避免被零除*/if(r<1)r=1;/*避免初始罰因子過(guò)小*/for(k=1;;k++){xl[0]=x0[0];xl[1]=x0[1];power(n,x0,e1,e2,h,y,r);/*Powell法，維數(shù)，初始點(diǎn)，兩個(gè)精度，進(jìn)退法步長(zhǎng)，最優(yōu)解，懲罰因子*/h=h*c;/*一維尋優(yōu)的步長(zhǎng)也遞減,減小越界的幅度*/f=func0(x0[0],x0[1]);/*尋優(yōu)點(diǎn)目標(biāo)函數(shù)值*/dum=fabs(f-f0);if(fabs(f0)>1)dum=dum/fabs(f0);

if(k>6&&dum<e3)/*k>100*/{y[0]=f;return;}/*x0[2]返回最優(yōu)點(diǎn)*y返回最優(yōu)解*/r=c*r;/*更新懲罰因子*/f0=f;}/*計(jì)算循環(huán)*/}/*結(jié)束內(nèi)點(diǎn)懲罰函數(shù)法子程序*/§6-4.2外點(diǎn)懲罰函數(shù)法

外點(diǎn)法是從可行域的外部構(gòu)造一個(gè)點(diǎn)序列去逼近原約束問(wèn)題的極值點(diǎn)。外點(diǎn)法可以用來(lái)求解含不等式和等式約束的優(yōu)化問(wèn)題。

外點(diǎn)懲罰函數(shù)的形式為：

r是懲罰因子,懲罰項(xiàng)的作用是迫使迭代點(diǎn)逼近約束邊界或等式約束曲面。由懲罰項(xiàng)的形式可知，當(dāng)?shù)c(diǎn)x

不可行時(shí)，懲罰項(xiàng)的值大于0。加懲罰項(xiàng)就象在邊界外堆土堆一樣，越堆越高。注意如極值點(diǎn)不在邊界上，離極值點(diǎn)太遠(yuǎn)的初始點(diǎn)不合適。（1）如極值點(diǎn)在邊界上，則序列最優(yōu)點(diǎn)在非可行域一側(cè)。（2）初始點(diǎn)無(wú)特殊要求。（3）初始罰因子不宜太大，也不宜跟初始點(diǎn)有關(guān)，可針對(duì)不同約束設(shè)置不同的值，設(shè)置原則是“首次起作用時(shí)，在邊界外某段距離處，懲罰項(xiàng)的值與目標(biāo)函數(shù)的值相當(dāng)”。（4）懲罰因子的遞增系數(shù)可設(shè)置在5~10范圍內(nèi)。

例5-4用外點(diǎn)法求解下列有約束優(yōu)化問(wèn)題解：懲罰函數(shù)為：

求偏導(dǎo)，得

無(wú)約束目標(biāo)函數(shù)極小化問(wèn)題的極值點(diǎn)系列為：當(dāng)懲罰因子漸增時(shí)，由下表可看出收斂情況。r0.01-0.80975-50.00000-24.9650-49.99770.1-0.45969-5.00000-2.2344-4.947410.23607-0.500000.96310.1295100.83216-0.050002.30682.000110000.99800-0.000502.66242.6582∞108/38/3內(nèi)點(diǎn)法與外點(diǎn)法的比較懲罰項(xiàng)罰因子初始點(diǎn)尋得邊界最優(yōu)點(diǎn)內(nèi)點(diǎn)法域內(nèi)(邊界內(nèi)側(cè))壘墻遞減必須域內(nèi)在域內(nèi)逼近外點(diǎn)法域外(邊界外側(cè)堆土堆)遞增可域內(nèi)，也可域外在域外逼近內(nèi)點(diǎn)法適用于只含不等式約束的優(yōu)化問(wèn)題，外點(diǎn)法還可含等式約束§6-4.3混合懲罰函數(shù)法在可行域外側(cè)、內(nèi)側(cè)均設(shè)置懲罰項(xiàng)

：例5-5等式約束起到降維的作用。漸近尋優(yōu)懲罰函數(shù)法具有漸進(jìn)尋優(yōu)的特點(diǎn)，對(duì)于約束邊界與目標(biāo)函數(shù)等值線接近于平行的優(yōu)化問(wèn)題，也可以取得較好的尋優(yōu)效果。該類優(yōu)化問(wèn)題的邊界極值點(diǎn)，稱為畸形極值點(diǎn)。改進(jìn)隨機(jī)方向法的計(jì)算結(jié)果基于盲人探路優(yōu)化思想的復(fù)合形法加固圍墻的內(nèi)點(diǎn)懲罰函數(shù)法和外點(diǎn)懲罰函數(shù)法§6-5網(wǎng)格法1基本思想(Meshmethod)網(wǎng)格法是直接在設(shè)計(jì)變量的可行域內(nèi)，有規(guī)律地取一系列點(diǎn)，如分布網(wǎng)格，取網(wǎng)格上下的結(jié)點(diǎn)，求這些點(diǎn)的目標(biāo)函數(shù)值，找出其中較小的點(diǎn)，作為第一次優(yōu)化點(diǎn)；然后在第一次迭代優(yōu)化點(diǎn)附近，取一定的范圍，再細(xì)分網(wǎng)格，計(jì)算網(wǎng)格結(jié)點(diǎn)的目標(biāo)函數(shù)值，進(jìn)行比較，找出第二次迭代的優(yōu)化點(diǎn)，這樣一直迭代下去，直到滿足精度要求為止［7（如圖7）。］李兵.基于網(wǎng)格法的汽車(chē)轉(zhuǎn)向梯形機(jī)構(gòu)的優(yōu)化設(shè)計(jì)(Optimumdesignofautomobilesteeringtrapeziumusingmeshmethod).機(jī)械工程師,2005年第8期2迭代步驟（1）在變量的可行域內(nèi)分布網(wǎng)格，網(wǎng)格的間隔為（2）計(jì)算網(wǎng)格的結(jié)點(diǎn)（3）逐點(diǎn)檢查網(wǎng)格結(jié)點(diǎn)是否符合約束條件，對(duì)符合約束條件的點(diǎn)，計(jì)算其目標(biāo)函數(shù)值，然后進(jìn)行比較，找出函數(shù)值最小的點(diǎn)，為本次迭代的最優(yōu)點(diǎn)。（4）迭代終止精度指標(biāo)；（5）如不滿足精度指標(biāo)，則在本次迭代最優(yōu)點(diǎn)附近，取下次迭代的變量的上、下限。然后轉(zhuǎn)到第一步，分布網(wǎng)格，重新計(jì)算?；诰W(wǎng)格法的汽車(chē)轉(zhuǎn)向梯形機(jī)構(gòu)的優(yōu)化設(shè)計(jì)《機(jī)械工程師》2005年第8期OptimumDesignofAutomobileSteeringTrapeziumUsingMeshMethod關(guān)鍵詞：網(wǎng)格法,轉(zhuǎn)向梯形,優(yōu)化設(shè)計(jì)作者：李兵概述：介紹了網(wǎng)格法的基本原理,建立了用于汽車(chē)轉(zhuǎn)向梯形機(jī)構(gòu)優(yōu)化設(shè)計(jì)的數(shù)學(xué)模型,并運(yùn)用此數(shù)學(xué)模型對(duì)BJ130型汽車(chē)的轉(zhuǎn)向梯形機(jī)構(gòu)進(jìn)行了優(yōu)化設(shè)計(jì).§6-6線性逼近法在某個(gè)近似點(diǎn)處，將約束函數(shù)和目標(biāo)函數(shù)進(jìn)行泰勒展開(kāi)，只保留一次項(xiàng)，從而轉(zhuǎn)化為線性規(guī)劃問(wèn)題。求解該線性規(guī)劃，并將其極值點(diǎn)作為原問(wèn)題新的近似點(diǎn)。然后再在該近似點(diǎn)處展開(kāi)。重復(fù)至相鄰兩次極值點(diǎn)足夠接近為止。

§6-7廣義簡(jiǎn)約梯度法

用來(lái)求解具有非線性等式約束和變量界限約束的優(yōu)化問(wèn)題。設(shè)法處理約束函數(shù)，將原問(wèn)題轉(zhuǎn)化成僅具有變量邊界約束的優(yōu)化問(wèn)題?！?-8二次規(guī)劃法（逼近）

將原問(wèn)題轉(zhuǎn)化為一系列二次規(guī)劃問(wèn)題。求子問(wèn)題得到本次迭代的搜索方向，沿搜索方向?qū)?yōu)，最終逼近問(wèn)題的極值點(diǎn)。該算法是利用擬牛頓法（變尺度法）來(lái)近似構(gòu)造海賽矩陣，從而建立二次規(guī)劃子問(wèn)題的。補(bǔ)充選講材料5.3序列二次規(guī)劃法序列二次規(guī)劃法的基本原理是將原問(wèn)題轉(zhuǎn)化為一系列二次規(guī)劃子問(wèn)題。

對(duì)于相對(duì)應(yīng)的拉格朗日函數(shù)為：在xk點(diǎn)作泰勒展開(kāi)，取二次近似表達(dá)式令拉格朗日函數(shù)的一階導(dǎo)數(shù)為

，H(k)用變尺度矩陣Bk來(lái)代替

將等式約束函數(shù)在xk作泰勒展開(kāi)，取線性近似式:構(gòu)成二次規(guī)劃子問(wèn)題

求解上述二次規(guī)劃子問(wèn)題，得到的d就是搜索方向。沿搜索方向進(jìn)行一維搜索確定步長(zhǎng)，最終得到原問(wèn)題的最優(yōu)點(diǎn)。

對(duì)具有不等式約束的非線性規(guī)劃問(wèn)題：構(gòu)成二次規(guī)劃子問(wèn)題為:

求解時(shí)，在每次迭代中應(yīng)對(duì)不等式約束進(jìn)行判斷，保留其中的起作用約束，除掉不起作用的約束，將起作用的約束納入等式約束中。這樣，其中不等式約束的子問(wèn)題和只具有等式約束的子問(wèn)題保持了一致。

§6-9結(jié)構(gòu)設(shè)計(jì)的優(yōu)化準(zhǔn)則法通常是在保證性能約束條件下，滿足結(jié)構(gòu)體積盡量小以減輕重量或節(jié)約材料。其性能約束一般是取結(jié)構(gòu)固有頻率禁區(qū)約束、振型約束、結(jié)構(gòu)變形或許用應(yīng)力約束。直接從結(jié)構(gòu)力學(xué)出發(fā)，以滿應(yīng)力設(shè)計(jì)和同步失效準(zhǔn)則為原則進(jìn)行設(shè)計(jì)，稱為準(zhǔn)則法。以極大值原理為基礎(chǔ)，基于結(jié)構(gòu)彈性力學(xué)模型和泛函極值的求解方法，為形狀優(yōu)化及拓?fù)浼安季謨?yōu)化。若桿件截面積為A、軸向受力為S、桿長(zhǎng)為l、許用應(yīng)力為[σ]，則優(yōu)化問(wèn)題為：等式約束可唯一確定設(shè)計(jì)變量總結(jié)1、掌握直接解法和間接解法的思想；2、掌握隨機(jī)方向法、復(fù)合形法、可行方向法、網(wǎng)格法、三種懲罰函數(shù)法的尋優(yōu)思想；3、圍墻土堆法的三種懲罰項(xiàng)構(gòu)成及尋優(yōu)步驟；4、編程：外點(diǎn)懲罰函數(shù)法。加一個(gè)等式約束figure;%B卷試題6[x1,x2]=meshgrid(-5:0.1:12,-6:0.1:6);z=x1.^3+x2.^3-2*x1-4*x2+6;%v=[10