內(nèi)點(diǎn)法的基本原理以及舉例計(jì)算

1、精選優(yōu)質(zhì)文檔-傾情為你奉上一、 內(nèi)點(diǎn)法1. 基本原理內(nèi)點(diǎn)法的特點(diǎn)是將構(gòu)造的新的無約束目標(biāo)函數(shù)懲罰函數(shù)定義在可行域內(nèi)，并在可行域內(nèi)求懲罰函數(shù)的極值點(diǎn)，即求解無約束問題時(shí)的探索點(diǎn)總是在可行域內(nèi)部，這樣，在求解內(nèi)點(diǎn)懲罰函數(shù)的序列無約束優(yōu)化問題的過程中，所求得的系列無約束優(yōu)化問題的解總是可行解，從而在可行域內(nèi)部逐步逼近原約束優(yōu)化問題的最優(yōu)解。內(nèi)點(diǎn)法是求解不等式約束最優(yōu)化問題的一種十分有效方法，但不能處理等式約束。因?yàn)闃?gòu)造的內(nèi)點(diǎn)懲罰函數(shù)是定義在可行域內(nèi)的函數(shù)，而等式約束優(yōu)化問題不存在可行域空間，因此，內(nèi)點(diǎn)法不能用來求解等式約束優(yōu)化問題。對于目標(biāo)函數(shù)為min s.t. （u=1,2,3,m）的最優(yōu)化問題，

2、利用內(nèi)點(diǎn)法進(jìn)行求解時(shí)，構(gòu)造懲罰函數(shù)的一般表達(dá)式為或者 而對于受約束于的最優(yōu)化問題，其懲罰函數(shù)的一般形式為或式中，-懲罰因子，是遞減的正數(shù)序列，即 通常取。上述懲罰函數(shù)表達(dá)式的右邊第二項(xiàng)，稱為懲罰項(xiàng)，有時(shí)還稱為障礙項(xiàng)。說明：當(dāng)?shù)c(diǎn)在可行域內(nèi)部時(shí)，有（=1，2，3，4，m），而，則懲罰項(xiàng)恒為正值，當(dāng)設(shè)計(jì)點(diǎn)由可行域內(nèi)部向約束邊界移動(dòng)時(shí)，懲罰項(xiàng)的值要急劇增大并趨向無窮大，于是懲罰函數(shù)的值也急劇增大直至無窮大，起到懲罰的作用，使其在迭代過程中始終不會(huì)觸及約束邊界。2. 內(nèi)點(diǎn)法的迭代步驟（1）取初始懲罰因子，允許誤差；（2）在可行域內(nèi)取初始點(diǎn)，令；（3）構(gòu)造懲罰函數(shù)，從點(diǎn)出發(fā)用無約束優(yōu)化方法求解懲罰函數(shù)

3、的極值點(diǎn)；（4）檢查迭代終止準(zhǔn)則：如果滿足或則停止迭代計(jì)算，并以為原目標(biāo)函數(shù)的約束最優(yōu)解，否則轉(zhuǎn)入下一步； 根據(jù)情況，終止準(zhǔn)則還可有如下的形式：或或5）取，轉(zhuǎn)向步驟3）。 遞減系數(shù)，常取0.1，亦可取0.02。采用內(nèi)點(diǎn)法應(yīng)注意的幾個(gè)問題：（1）初始點(diǎn)的選取初始點(diǎn)必須嚴(yán)格在可行域內(nèi)，滿足所有的約束條件，避免為約束邊界上的點(diǎn)。如果約束條件比較簡單，可以直接人工輸入；若問題比較復(fù)雜，可采用隨機(jī)數(shù)的方式產(chǎn)生初始點(diǎn)，具體方程參照復(fù)合形法介紹。（2）關(guān)于初始懲罰因子的選擇。實(shí)踐經(jīng)驗(yàn)表明，初始懲罰因子選的恰當(dāng)與否，會(huì)顯著地影響內(nèi)點(diǎn)法的收斂速度，甚至解題的成敗。若值選得太小，則在新目標(biāo)函數(shù)即懲罰函數(shù)中懲罰項(xiàng)的

4、作用就會(huì)很小，這時(shí)求的無約束極值，猶如原目標(biāo)函數(shù)本身的無約束極值，而這個(gè)極值點(diǎn)又不大可能接近的約束極值點(diǎn)，且有跑出可行域的危險(xiǎn)。相反，若值取得過大，則開始幾次構(gòu)造的懲罰函數(shù)的無約束極值點(diǎn)就會(huì)離約束邊界很遠(yuǎn)，將使計(jì)算效率降低?？扇?50，但多數(shù)情況是取。 通常，當(dāng)初始點(diǎn)是一個(gè)嚴(yán)格的內(nèi)點(diǎn)時(shí)，則應(yīng)使懲罰項(xiàng)在新目標(biāo)函數(shù)中所起的作用與原目標(biāo)函數(shù)的作用相當(dāng)，于是得倘若約束區(qū)域是非凸的且初始點(diǎn)亦不靠近約束邊界，則的取值可更小，約為上式算得值的0.10.5倍。內(nèi)點(diǎn)法的計(jì)算程序框圖例題：用內(nèi)點(diǎn)法求 min s.t. （u=1,2,3,m）的約束最優(yōu)解。（取0.001）解：構(gòu)造內(nèi)點(diǎn)懲罰函數(shù)為用極值條件進(jìn)行求解，聯(lián)

5、立上式求得，由于約束條件的限制，可得無約束極值點(diǎn)為當(dāng)取1，0.1,0.01,0時(shí)，可得最優(yōu)解為，編程方式實(shí)現(xiàn)：1. 懲罰函數(shù)function f=fun(x,r)f=x(1,1)2+x(2,1)2-r*log(x(1,1)-1);2. 步長的函數(shù)function f=fh(x0,h,s,r)%h為步長%s為方向%r為懲罰因子x1=x0+h*s;f=fun(x1,r);3. 步長尋優(yōu)函數(shù)function h=fsearchh(x0,r,s)%利用進(jìn)退法確定高低高區(qū)間，利用黃金分割法進(jìn)行求解h1=0;%步長的初始點(diǎn)st=0.001; %步長的步長h2=h1+st;f1=fh(x0,h1,s,r);

6、f2=fh(x0,h2,s,r);if f1>f2 h3=h2+st; f3=fh(x0,h3,s,r); while f2>f3 h1=h2; h2=h3; h3=h3+st; f2=f3; f3=fh(x0,h3,s,r); endelse st=-st; v=h1; h1=h2; h2=v; v=f1; f1=f2; f2=v; h3=h2+st; f3=fh(x0,h3,s,r); while f2>f3 h1=h2; h2=h3; h3=h3+st; f2=f3; f3=fh(x0,h3,s,r); endend%得到高低高的區(qū)間a=min(h1,h3);b=max

7、(h1,h3);%利用黃金分割點(diǎn)法進(jìn)行求解h1=1+0.382*(b-a);h2=1+0.618*(b-a);f1=fh(x0,h1,s,r);f2=fh(x0,h2,s,r);while abs(a-b)>0.0001 if f1>f2 a=h1; h1=h2; f1=f2; h2=a+0.618*(b-a); f2=fh(x0,h2,s,r); else b=h2; h2=h1; f2=f1; h1=a+0.382*(b-a); f1=fh(x0,h1,s,r); endendh=0.5*(a+b);4. 迭代點(diǎn)的尋優(yōu)函數(shù)function f=fsearchx(x0,r,epson)x00=x0;m=length(x0);s=zeros(m,1);for i=1:m s(i)=1; h=fsearchh(x0,r,s); x1=x0+h*s; s(i)=0; x0=x1;endwhile norm(x1-x00)>epson x00=x1; for i=1:m s(i)=1; h=fsearchh(x0,r,s); x1=x0+h*s; s(i)=0; x0=x1; endendf=x1;5. 主程序clearclcx0=2;2; %給定初始點(diǎn)r=1;c=0.1;epson=0.001;x1=fsearchx(x0,0.1,epson);while no