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

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

2、時(shí)，構(gòu)造懲罰函數(shù)的一般表達(dá)式為(X,r(k)f(X)r(k)m11gu(X)mm或者(X,rk)f(X)rklngu(X)f(X)rklngu(X)u1u1而對(duì)于f(X)受約束于gu(X)0(u1,2,m)的最優(yōu)化問(wèn)題，其懲罰函數(shù)的一般形式為(X,rk)f(X)rkm1u1gu(X)或(X,rk)f(X)rkmlngu(X)u1k-懲罰因子，是遞減的正數(shù)序列，即式中，rr0r1r2rkrk10limrk0k通常取rk1.0,0.1,0.01,0.001,。上述懲罰函數(shù)表達(dá)式的右邊第二項(xiàng)，稱為懲罰項(xiàng)，有時(shí)還稱為障礙項(xiàng)。說(shuō)明：當(dāng)?shù)c(diǎn)在可行域內(nèi)部時(shí)，有(X)0（，），而rk0，則懲罰guu=123

3、4m項(xiàng)恒為正值，當(dāng)設(shè)計(jì)點(diǎn)由可行域內(nèi)部向約束邊界移動(dòng)時(shí)，懲罰項(xiàng)的值要急劇增大并趨向無(wú)窮大，于是懲罰函數(shù)的值也急劇增大直至無(wú)窮大，起到懲罰的作用，使其在迭代過(guò)程中始終不會(huì)觸及約束邊界。2.內(nèi)點(diǎn)法的迭代步驟（1）取初始懲罰因子r(0)0，允許誤差0；（2）在可行域D內(nèi)取初始點(diǎn)X0，令k1；（3）構(gòu)造懲罰函數(shù)(X,rk)，從X(k1)點(diǎn)出發(fā)用無(wú)約束優(yōu)化方法求解懲罰函數(shù)(X,rk)的極值點(diǎn)X(rk)；（4）檢查迭代終止準(zhǔn)則：如果滿足X(rk)X(rk1)1105107或kk1(X,r)(X,r)2103104(X,rk1)則停止迭代計(jì)算，并以X(rk)為原目標(biāo)函數(shù)f(X)的約束最優(yōu)解，否則轉(zhuǎn)入下一步；根

4、據(jù)情況，終止準(zhǔn)則還可有如下的形式：f(Xk)f(Xk1)或r或mk11gu(X)rkmlngu(X)u15）取rk1Crk,X0X(rk),kk1，轉(zhuǎn)向步驟3）。遞減系數(shù)C0.10.5，常取0.1，亦可取0.02。采用內(nèi)點(diǎn)法應(yīng)注意的幾個(gè)問(wèn)題：（1）初始點(diǎn)0的選取X初始點(diǎn)X0必須嚴(yán)格在可行域內(nèi)，滿足所有的約束條件，避免為約束邊界上的點(diǎn)。如果約束條件比較簡(jiǎn)單，可以直接人工輸入；若問(wèn)題比較復(fù)雜，可采用隨機(jī)數(shù)的方式產(chǎn)生初始點(diǎn)X0，具體方程參照復(fù)合形法介紹。（2）關(guān)于初始懲罰因子r(0)的選擇。實(shí)踐經(jīng)驗(yàn)表明，初始懲罰因子r(0)選的恰當(dāng)與否，會(huì)顯著地影響內(nèi)點(diǎn)法的收斂速度，甚至解題的成敗。若r0(X,rk

5、值選得太小，則在新目標(biāo)函數(shù)即懲罰函數(shù))中懲罰項(xiàng)的作用就會(huì)很小，這時(shí)求(X,rk)的無(wú)約束極值，猶如原目標(biāo)函數(shù)f(X)本身的無(wú)約束極值，而這個(gè)極值點(diǎn)又不大可能接近f(X)的約束極值點(diǎn)，且有跑出可行域的危險(xiǎn)。相反，若r0值取得過(guò)大，則開始幾次構(gòu)造的懲罰函數(shù)(X,rk)的無(wú)約束極值點(diǎn)就會(huì)離約束邊界很遠(yuǎn)，將使計(jì)算效率降低?？扇0150，但多數(shù)情況是取r01。通常，當(dāng)初始點(diǎn)X0是一個(gè)嚴(yán)格的內(nèi)點(diǎn)時(shí)，則應(yīng)使懲罰項(xiàng)m1r0在新目標(biāo)函u1gu(X0)k0)的作用相當(dāng)，于是得數(shù)(X,r)中所起的作用與原目標(biāo)函數(shù)f(X0r0mf(X)11gu(X0)倘若約束區(qū)域是非凸的且初始點(diǎn)X0亦不靠近約束邊界，則r0的取值可

6、更小，約為上式算得值的0.10.5倍。開始r(0),1,C在可行域內(nèi)選取X(0)k=1X(k1)點(diǎn)出發(fā)求解：min(X,r(k),得X*(r(k)f(Xk)f(Xk1X(rk)X(rk1r(k1)Cr(k)X*X*(r(k)1f(X*)f(X*(r(k)停止kk1內(nèi)點(diǎn)法的計(jì)算程序框圖例題：用內(nèi)點(diǎn)法求minf(X)x12x22s.t.g(X)1x10（u=1,2,3,m）的約束最優(yōu)解。（取0.001）解：構(gòu)造內(nèi)點(diǎn)懲罰函數(shù)為kmklngu(X)x12x22r(k)ln(1x1)(X,r)f(X)ru1用極值條件進(jìn)行求解2x1r(k)2x20 x1x10，x21聯(lián)立上式求得*(k)112r(k)*(

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

8、長(zhǎng)的步長(zhǎng)h2=h1+st;f1=fh(x0,h1,s,r);f2=fh(x0,h2,s,r);iff1f2h3=h2+st;f3=fh(x0,h3,s,r);whilef2f3h1=h2;h2=h3;h3=h3+st;f2=f3;f3=fh(x0,h3,s,r);endelsest=-st;v=h1;h1=h2;h2=v;v=f1;f1=f2;f2=v;h3=h2+st;f3=fh(x0,h3,s,r);whilef2f3h1=h2;h2=h3;h3=h3+st;f2=f3;f3=fh(x0,h3,s,r);endend%得到高低高的區(qū)間a=min(h1,h3);b=max(h1,h3);%利

9、用黃金分割點(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);whileabs(a-b)0.0001iff1f2a=h1;h1=h2;f1=f2;h2=a+0.618*(b-a);f2=fh(x0,h2,s,r);elseb=h2;h2=h1;f2=f1;h1=a+0.382*(b-a);f1=fh(x0,h1,s,r);endendh=0.5*(a+b);迭代點(diǎn)的尋優(yōu)函數(shù)functionf=fsearchx(x0,r,epson)x00=x0;m=length(x0);s=zeros(m,1);fori=1:ms(i)=1;h=fsearchh(x0,r,s);x1=x0+h*s;s(i)=0;x0=x1;endwhilenorm(x1-x00)epsonx00=x1;fori=1:ms(i)=1;h=fsearchh(x0,r,s);x1=x0+h*s;s(i)=0;x0=x1;endendf=x1;主程序clearclcx0=2;2;%給定初