劉慧蓮實驗報告

1、內(nèi)蒙古大學(xué)學(xué)期作業(yè)最優(yōu)化理論與方法學(xué)習(xí)報告學(xué)院：數(shù)學(xué)科學(xué)學(xué)院專業(yè)：運籌學(xué)姓名：劉慧蓮學(xué)號：31336006任課教師：陳國慶2014/7/1一、 總體介紹最優(yōu)化，是應(yīng)用數(shù)學(xué)的一個分支，主要研究以下形式的問題：給定一個函數(shù)，尋找一個元素使得對于所有a中的，（最小化）；或者（最大化）。這類定式有時還稱為“數(shù)學(xué)規(guī)劃”（譬如，線性規(guī)劃）。許多現(xiàn)實和理論問題都可以建模成這樣的一般性框架。典型的，a一般為歐幾里得空間中的子集，通常由一個a必須滿足的約束等式或者不等式來規(guī)定。a的元素被稱為是可行解。函數(shù)f被稱為目標(biāo)函數(shù)，或者費用函數(shù)。一個最小化（或者最大化）目標(biāo)函數(shù)的可行解被稱為最優(yōu)解。一般情況下，會存在若干

2、個局部的極小值或者極大值。局部極小值x*定義為對于一些 0，以及所有的x滿足; 公式成立。這就是說，在周圍的一些閉球上，所有的函數(shù)值都大于或者等于在該點的函數(shù)值。一般的，求局部極小值是容易的，但是要確保其為全域性的最小值，則需要一些附加性的條件，例如，該函數(shù)必須是凸函數(shù)。二、最優(yōu)化方法2.1 最速下降法2.1.1 原理設(shè)目標(biāo)函數(shù)連續(xù)可微，且。由定理可知，若,則是在處的下降方向。最速下降法的基本思想是以負(fù)梯度方向作為下降迭代公式中，并通過求解 確定最佳步長，每一次迭代力求做到數(shù)值最大幅度的下降。 若具有二階連續(xù)偏導(dǎo)，在作的二階泰勒展開式 對求導(dǎo)并令其等于零，得最佳步長也可以用精確一維搜索方法求解

3、，確定最佳步長。2.1.2 步驟（1）給定初始點，允許誤差，置；（2）計算搜索方向；（3）若，則停止計算；否則，確定最佳步長；（4）令，置，轉(zhuǎn)第（2）步。2.1.3 收斂性在最速下降法中，前后兩次的搜索方向垂直，正是這種鋸齒形的搜索軌跡使最速下降法效率低下。其實，最速下降方向反映了目標(biāo)函數(shù)的一種局部性質(zhì)。從局部看，其下降方向是函數(shù)值下降最快的方向，但從全局看，由于鋸齒現(xiàn)象的出現(xiàn)，當(dāng)在極小值 點附近時，即使向著極小值點移 動不太大的距離，也要經(jīng)歷不少的彎路，從而使收斂速度大為減慢。它具有全局收斂性，并且是線性 收斂的。為避免鋸齒現(xiàn)象對收斂速度的影響，在計算初期可使用最速下降法，在迭代一段時間以后

4、，改用其他更有效的方法。2.2共軛梯度法 2.2.1 原理 共軛梯度法是把共軛性與最速下降法相結(jié)合，利用已知點處的梯度構(gòu)造一組共軛方向，并沿這組方向進(jìn)行搜索，求出目標(biāo)函數(shù)的極小值點。2.2.2 步驟（1）選擇初始迭代點，給出允許誤差；（2）計算，置；（3）用其中，為初始迭代點，。計算，和（求也可直接使用精確一維搜索方法）；（4）若，且，則置，轉(zhuǎn)第（3）步；否則，轉(zhuǎn)第（5）步；（5）若，停止計算，即為近似極小值點；否則，令，并轉(zhuǎn)向第（2）步，重新開始迭代。2.2.3 收斂性共軛梯度法具有全局收斂性，且收斂速度快（至少是線性收斂）、存儲空間小等特點，尤其是對正定二次函數(shù)能在有限步內(nèi)達(dá)到極小值點，即

5、具有二次終結(jié)性。p-r-p法對大規(guī)模優(yōu)化問題有較好的效果。2.3 牛頓法2.3.1 原理牛頓法是利用二次函數(shù)近似目標(biāo)函數(shù)，設(shè)是二次可微實函數(shù)，是的極小值點的一個估計，作在處的二階泰勒展開式為求的駐點，令，即，設(shè)在處的矩陣可逆，由上式得到牛頓法的迭代公式，稱牛頓方向。2.3.2 步驟（1）給定初始點，給出允許誤差，置；（2）計算，；（3）若，停止計算；否則，令；（4）求解令，置，轉(zhuǎn)第（2）步。當(dāng)恒為1時，阻尼牛頓法就退化為牛頓法，因此收斂速度不會低于牛頓法。在一定條件下具有全局收斂性，且為二階收斂，可用于求解非正定二次函數(shù)的極小值點。2.3.3收斂性牛頓 法具有二階收斂速度，這是它的最大的優(yōu)點中

6、，對二次正定函數(shù)，僅需一步迭代即可達(dá)到最優(yōu)解，具有二次終止性。它是局部收斂的，即初始點選擇不當(dāng)，可能會導(dǎo)致不收斂；牛頓法不是下降算法，當(dāng)二階矩陣非正定時，不能保證牛頓方向是下降方向；二階矩陣必須可逆，否則算法將無法進(jìn)行下去；對函數(shù)分析性質(zhì)要求苛刻，計算量大，僅適合小規(guī)模優(yōu)化問題。2.4 變尺度法（dfp法）2.4.1 原理變尺度法是在處，按某種規(guī)則產(chǎn)生一個對稱正定矩陣（稱之為尺度矩陣），并以作為處的搜索方向。顯然，只要，就是下降方向。若取,就是最速下降方向；若取，就是牛頓方向（如果存在）。我們已經(jīng)知道，前者收斂太慢，有鋸齒現(xiàn)象，而后者計算量較大，可能不收斂。2.4.2 步驟（1）取初始點，給出

7、允許誤差，置；（2）計算，若，得到極小值點，停止迭代；（3）令，其中為最佳步長，即（4）計算，若，得 到極小值點，停止迭代；（5）若，令，置，轉(zhuǎn)第（3）步；（6）若，計算和，按式（7）計算和，對dfp法，按公式計算出，置，轉(zhuǎn)第（3）步。2.4.3 收斂性對于正定二次函數(shù)，在精確一維搜索的前提下，算法具有以下性質(zhì)：（1）變尺度法具有二次終結(jié)性；（2）算法產(chǎn)生的搜索方向共軛；（3）迭代量保持滿足擬牛頓 方程。對于一般的目標(biāo)函數(shù)，算法具有：（1）保持尺度矩陣對稱正定；（2）在一定條件下，超線性收斂。對嚴(yán)格凸函數(shù)，精確一維搜索的前提下，算法具有：（1）bfgs具有全局收斂性；（2）bfgs法與dfp法

8、相比，雖然公式復(fù)雜，但bfgs法有更好的數(shù)值穩(wěn)定性，具有整體更優(yōu)的特點，尤其是bfgs與wolfe不精確一維搜索結(jié)合被公認(rèn)為目前最好的變尺度法。三、作業(yè)分析作業(yè)中對十個n元函數(shù)在無約束條件下求最小值，并做出了每個函數(shù)當(dāng)n=2時的圖像。在函數(shù)執(zhí)行過程中都取n=10，分別用了最速下降法、牛頓法、共軛梯度法、dfp方法求解了其最優(yōu)值、最優(yōu)解、x的迭代次數(shù)、梯度的迭代次數(shù)、時間和精度。后面用表格進(jìn)行一一列出。3.1算法函數(shù)的m文件fun1.m。梯度函數(shù)的m文件gfun1.m, hesse矩陣文件hess1.m,最速下降法grad1.m，阻尼牛頓法znnewtoon1.m，共軛梯度法frcg1.m,秩一

9、校正法sr11.m，bfgs法bfgs1.m，dfp法dfp1.m。 fun1.m程序如下：function f=fun1(xx)n=length(xx);for i=1:n x(i)=sym(x,num2str(i);endf(1)=(x(1)-1)4;for i=2:n f(i)=f(i-1)+(x(i)-1)4;endf1=f(n);f=subs(f1,x,xx);gfun.m程序如下：function gf=gfun1(xx)n=length(xx);for i=1:nx(i)=sym(x,num2str(i);f(1)=(x(1)-1)4;endfor i=2:n f(i)=f(i-

10、1)+(x(i)-1)4;endf1=f(n);gf1=jacobian(f1,x);gf2=subs(gf1,x,xx);gf=gf2;grad1.m程序如下：function x,val,k,gk,t,gn=grad1(fun1,gfun1)% x0初始點，fun6,gfun6,hess6分別是目標(biāo)函數(shù)，梯度% x,val分別是近似最優(yōu)點和最優(yōu)解% k,gk分別是迭代次數(shù)，梯度迭代次數(shù)% t,gn分別是計算時間，精度ticn=input(n=n)x0=zeros(n,1);for i=1:n x0(i)=2.0;endx0;maxk=2000;rho=0.5; sigma=0.4;k=0;

11、 epsilon=1e-5;while (kmaxk) g=feval(gfun1,x0); gk=k; %梯度迭代次數(shù) dk=-g; if (norm(g)epsilon) gn=norm(g); %精度 break; end m=0; mk=0; while(m=20) fv1 = feval(fun1,x0+rhom*dk); fv2 = feval(fun1,x0)+sigma*rhom*g*dk ; if(fv1fv2) mk=m; break; end m=m+1; end x0=x0+rhomk*dk; k=k+1;endx=x0;val=feval(fun1,x);t=toc;

12、hess1.m程序如下：function hfv=hess1(xx)n=length(xx);for i=1:n x(i)=sym(x,num2str(i);endf(1)=(x(1)-1)4;for i=2:n f(i)=f(i-1)+(x(i)-1)4;endf1=f(n);gf=jacobian(f1,x);hf=zeros(n,n);hf=jacobian(gf,x);hfv=subs(hf,x,xx);znnewtoon1.m程序如下：function x,val,k,gk,t,gn=znnewtoon1(fun1,gfun1,hess1)% x0初始點，fun6,gfun6,hes

13、s6分別是目標(biāo)函數(shù)，梯度和hess矩陣函數(shù)% x,val分別是近似最優(yōu)點和最優(yōu)解% k,gk分別是迭代次數(shù)，梯度迭代次數(shù)% t,gn分別是計算時間，精度ticn=input(n=n)x0=zeros(n,1);for i=1:n x0(i)=2.0;endx0;maxk=2000;rho=0.5; sigma=0.4;k=0; epsilon=1e-5;while (kmaxk) g=feval(gfun1,x0); gk=k; %梯度迭代次數(shù) g=feval(hess1,x0); dk=-gg; if (norm(g)epsilon) gn=norm(g); %精度 break; end m

14、=0; mk=0; while(m1e5) fv1 = feval(fun1,x0+rhom*dk); fv2 = feval(fun1,x0)+sigma*rhom*g*dk ; if(fv1=fv2) mk=m; break; end m=m+1; end x0=x0+rhomk*dk; k=k+1;endx=x0;val=feval(fun1,x);toc;t=toc;enddfp1.程序如下：functionx,val,k,gk,t,gn=dfp1(fun1,gfun1)ticn=input(n=n)x0=zeros(n,1);for i=1:n x0(i)=2;endx0;maxk=

15、2000;rho=0.5;sigma=0.4;epsilon=1e-5;k=0;n=length(x0)hk=inv(feval(hess1,x0);while(kmaxk) g=feval(gfun1,x0); gk=k; if(norm(g)epsilon) gn=norm(g);break;end dk=-hk*g; m=0;mk=0; while(m=20) if(feval(fun1,x0+rhom*dk)0) hk=hk-(hk*yk*yk*hk)/(yk*hk*yk)+(sk*sk)/(sk*yk); end k=k+1;x0=x;endval=feval(fun1,x0);t=

16、toc;frcg1.m 程序如下：functionx,val,k,gk,t,gn=frcg1(fun1,gfun1)ticn=input(n=n)x0=zeros(n,1);for i=1:n x0(i)=2;endx0;maxk=2000;rho=0.5;sigma=0.4;k=0;epsilon=1e-4;n=length(x0);while(k=0.0) d=-g; end end if(norm(g)epsilon) gn=norm(g); break;end m=0;mk=0; while(m=20) if(feval(fun1,x0+rhom*d)feval(fun1,x0)+si

17、gma*rhom*g*d) mk=m;break; end m=m+1; end x0=x0+rhomk*d; val=feval(fun1,x0); g0=g;d0=d; k=k+1;endx=x0;val=feval(fun1,x);t=toc;3.2 十個函數(shù)不同方法下的運行結(jié)果與三圖維如下。1.最速下降法牛頓法共軛梯度法dfp法n10101010x1.00921.00921.00921.00921.00921.00921.00921.00921.00921.00921.00771.00771.00771.00771.00771.00771.00771.00771.00771.00771

18、.01991.01991.01991.01991.01991.01991.01991.01991.01991.01991.00771.00771.00771.00771.00771.00771.00771.00771.00771.0077val7.3084e-083.5287e-081.5654e-063.4305e-08k1457126917gk1457126917t363.176379.070325.847610.0622gn9.9983e-065.7913e-069.9549e-055.6699e-06從上面的表格可以看出在n=10時，牛頓法與法的最優(yōu)解相同且最優(yōu)，但是法的計算時間最短。

19、最速下降法的計算值最大且迭代次數(shù)最多、時間最長、精度最高。牛頓法的迭代次數(shù)最少整體來看對于該函數(shù)來講法還是最合適的。2.3. 最速下降法牛頓法共軛梯度法dfp法n10101010x1.6783 1.6783 1.6783 1.6783 1.6783 1.6783 1.6783 1.6783 1.6783 1.67831.67831.67831.67831.67831.67831.67831.67831.67831.67831.67831.67831.67831.67831.67831.67831.67831.67831.67831.67831.67831.67831.67831.67831.6

20、7831.67831.67831.67831.67831.67831.6783val -8.1685-8.1685-8.1685-8.1685k71255gk71255t7.93645.73686.45335.8030gn8.2235e-061.5291e-101.8760e-052.0955e-07從上面的表格可以看出當(dāng)n=10時以上的四種方法得到的最優(yōu)值、最優(yōu)解相同。但是共軛梯度法與法的迭代次數(shù)最少為。牛頓法迭代次數(shù)雖多，但是其得到最優(yōu)的時間最少，精度最高。相比而言，對于這個函數(shù)來說用牛頓法相對較好。 4. 最速下降法牛頓法共軛梯度法dfp法n10101010x-0.1454-0.1454

21、-0.1454-0.1454-0.1454-0.1454-0.1454-0.1454-0.1454-0.14540.15640.15640.15640.15640.15640.15640.15640.15640.15640.1564-0.1488-0.1488-0.1488-0.1488-0.1488-0.1488-0.1488-0.1488-0.1488-0.14880.19560.19560.19560.19560.19560.19560.19560.19560.19560.1956val10.000010.000010.000010.0000k4466gk4466t3.85864.152

22、34.89264.9071gn4.5981e-094.9462e-064.7052e-056.1854e-08從上面的表格可以看出當(dāng)n=10時以上的四種方法得到的最優(yōu)值相同，此時共軛梯度法得到的最優(yōu)解是最小的，其迭代次數(shù)與時間最多且精度最小最速下降法的迭代次數(shù)與牛頓法的迭代次數(shù)最少，但是最速下降法的迭代時間最少且精度最高。相比而言，對于這個函數(shù)來說用最速下降法相對較好。 5.最速下降法牛頓法共軛梯度法dfp法n10101010x0.444500.00040.00040.00040.00040.00040.00040.000000000000000-0.15180.00020.00030.000

23、30.00030.00030.00030.00030.00050.00090000000000val1.9779e-1102.3321e-100k11341591gk11341591t2.4101e+034.6423119.40752.7793gn9.8608e-0605.2162e-050從上面的表格可以看出當(dāng)n=10時以上的四種方法最速下降法得到的值最大，其迭代次數(shù)與時間也最多當(dāng)然其精度也最高。在得到最小值時牛頓法與法兩者的迭代次數(shù)最小，精度一樣，但是法的時間較少，因此對于求最大值而言，共軛梯度法較好一點對于求最小值時，法較好。.最速下降法牛頓法共軛梯度法dfp法n10101010x11.

24、4128-0.896811.4128-0.896811.4128-0.896811.4128-0.896811.4128-0.896811.4128-0.896811.4128-0.896811.4128-0.896811.4128-0.896811.4128-0.896811.4128-0.896811.4128-0.896811.4128-0.896811.4128-0.896811.4128-0.896811.4128-0.896811.4128-0.896811.4128-0.896811.4128-0.896811.4128-0.8968val 244.9213244.9213244

25、.9213244.9213k66459gk66459t7.86157.8615152.27128.6736gn8.4381e-078.4381e-074.4006e-052.5273e-07從上面的表格可以看出當(dāng)n=10時以上的四種方法得到的最優(yōu)值、最優(yōu)解都相同。此時共軛梯度法的迭代次數(shù)與時間最少且得到的精度最小。最速下降法與牛頓法的迭代次數(shù)與時間最少且得到的精度最高。因此對于該函數(shù)來說用最速下降法與牛頓法來說都行法次之，用共軛梯度法求解交果最差。 7. 最速下降法牛頓法共軛梯度法dfp法n10101010x0.21540.21540.21540.21540.21540.21540.21540

26、.21540.21540.21540.19400.19400.19400.19400.19400.19400.19400.19400.19400.19400.17440.17440.17440.17440.17440.17440.17440.17440.17440.17440.40370.40370.40370.40370.40370.40370.40370.40370.40370.4037val6.93156.93156.93156.9315k3293gk3293t5.24664.88989.73895.2614gn6.8105e-076.1344e-065.5136e-051.2767e-

27、06從上面的表格可以看出當(dāng)n=10時以上的四種方法得到的最優(yōu)值都相同。此時dfp法的最優(yōu)值最大且得到的精度最高， dfp法與最速下降法的迭代次數(shù)相同牛頓法的最優(yōu)值最小且其迭代次數(shù)與時間最少。共軛梯度法的迭代次數(shù)與時間最多且得到的精度最小。因此對于該函數(shù)來說用牛頓法來說較好法與最速下降法次之，用共軛梯度法求解交果最差。8. 最速下降法牛頓法共軛梯度法dfp法n10101010x0.99560.98680.96050.88300.66270.1018-0.8878-1.0996-0.8905-1.09751.67831.67831.67831.67831.67831.67831.67831.678

28、31.67831.678311111111111111111111val 3.8229e-13-8.168500k2281200gk2281200t524.85415.73683.98266.3421gn8.5057e-061.5291e-1000從上面的表格可以看出當(dāng)n=10時以上的四種方法牛頓法得到的值最小、x的解最大、迭代次數(shù)較小、精度最大。最速下降法得到的值最大，其迭代次數(shù)與時間最大且精度較小。共軛梯度法與dfp法得到的最優(yōu)值，最優(yōu)解相同且迭代次數(shù)與精度也相同，但是共軛梯度法的計算時間最少。因此對于該函數(shù)來說用牛頓法求解最小值來說較好用最速下降法求最大值來說較好。9最速下降法牛頓法共軛梯度法dfp法n10101010x1.0000-1.0000-1.0000-1.0000-1.0000-1.0000-1.0000-1.0000-1.0000-1.0000在20時矩陣是奇異的1.0000-1.0000-1.0000-1.0000-1.0000-1.0000-1.0000-1.0000-1.0000-1.0000在12時矩陣是奇異的val 3.9892e-131.1757e-11k17229gk17229t589.5016101.5668gn7.8755e-068.6731e-