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

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

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

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

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

5、立上式求得，由于約束條件的限制，可得無約束極值點為當取1，0.1,0.01,0時，可得最優(yōu)解為，編程方式實現(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)%利用進退法確定高低高區(qū)間，利用黃金分割法進行求解h1=0;%步長的初始點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);%利用黃金分割點法進行求解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. 迭代點的尋優(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; %給定初始點r=1;c=0.1;epson=0.001;x1=fsearchx(x0,0.1,epson);while no