刘慧莲实验报告

内蒙古大学学期作业最优化理论与方法学习报告学院：数学科学学院专业：运筹学姓名：刘慧莲学号：31336006任课教师：陈国庆2014/7/1一、 总体介绍最优化，是应用数学的一个分支，主要研究以下形式的问题：给定一个函数，寻找一个元素使得对于所有A中的，（最小化）；或者（最大化）。这类定式有时还称为“数学规划”（譬如，线性规划）。许多现实和理论问题都可以建模成这样的一般性框架。典型的，A一般为欧几里得空间中的子集，通常由一个A必须满足的约束等式或者不等式来规定。A的元素被称为是可行解。函数f被称为目标函数，或者费用函数。一个最小化（或者最大化）目标函数的可行解被称为最优解。一般情况下，会存在若干个局部的极小值或者极大值。局部极小值x*定义为对于一些 0，以及所有的x满足; 公式成立。这就是说，在周围的一些闭球上，所有的函数值都大于或者等于在该点的函数值。一般的，求局部极小值是容易的，但是要确保其为全域性的最小值，则需要一些附加性的条件，例如，该函数必须是凸函数。二、最优化方法2.1 最速下降法2.1.1 原理设目标函数连续可微，且。由定理可知，若,则是在处的下降方向。最速下降法的基本思想是以负梯度方向作为下降迭代公式中，并通过求解 确定最佳步长，每一次迭代力求做到数值最大幅度的下降。 若具有二阶连续偏导，在作的二阶泰勒展开式 对求导并令其等于零，得最佳步长也可以用精确一维搜索方法求解，确定最佳步长。2.1.2 步骤（1）给定初始点，允许误差，置；（2）计算搜索方向；（3）若，则停止计算；否则，确定最佳步长；（4）令，置，转第（2）步。2.1.3 收敛性在最速下降法中，前后两次的搜索方向垂直，正是这种锯齿形的搜索轨迹使最速下降法效率低下。其实，最速下降方向反映了目标函数的一种局部性质。从局部看，其下降方向是函数值下降最快的方向，但从全局看，由于锯齿现象的出现，当在极小值 点附近时，即使向着极小值点移 动不太大的距离，也要经历不少的弯路，从而使收敛速度大为减慢。它具有全局收敛性，并且是线性 收敛的。为避免锯齿现象对收敛速度的影响，在计算初期可使用最速下降法，在迭代一段时间以后，改用其他更有效的方法。2.2共轭梯度法 2.2.1 原理 共轭梯度法是把共轭性与最速下降法相结合，利用已知点处的梯度构造一组共轭方向，并沿这组方向进行搜索，求出目标函数的极小值点。2.2.2 步骤（1）选择初始迭代点，给出允许误差；（2）计算，置；（3）用其中，为初始迭代点，。计算，和（求也可直接使用精确一维搜索方法）；（4）若，且，则置，转第（3）步；否则，转第（5）步；（5）若，停止计算，即为近似极小值点；否则，令，并转向第（2）步，重新开始迭代。2.2.3 收敛性共轭梯度法具有全局收敛性，且收敛速度快（至少是线性收敛）、存储空间小等特点，尤其是对正定二次函数能在有限步内达到极小值点，即具有二次终结性。P-R-P法对大规模优化问题有较好的效果。2.3 牛顿法2.3.1 原理牛顿法是利用二次函数近似目标函数，设是二次可微实函数，是的极小值点的一个估计，作在处的二阶泰勒展开式为求的驻点，令，即，设在处的矩阵可逆，由上式得到牛顿法的迭代公式，称牛顿方向。2.3.2 步骤（1）给定初始点，给出允许误差，置；（2）计算，；（3）若，停止计算；否则，令；（4）求解令，置，转第（2）步。当恒为1时，阻尼牛顿法就退化为牛顿法，因此收敛速度不会低于牛顿法。在一定条件下具有全局收敛性，且为二阶收敛，可用于求解非正定二次函数的极小值点。2.3.3收敛性牛顿 法具有二阶收敛速度，这是它的最大的优点中，对二次正定函数，仅需一步迭代即可达到最优解，具有二次终止性。它是局部收敛的，即初始点选择不当，可能会导致不收敛；牛顿法不是下降算法，当二阶矩阵非正定时，不能保证牛顿方向是下降方向；二阶矩阵必须可逆，否则算法将无法进行下去；对函数分析性质要求苛刻，计算量大，仅适合小规模优化问题。2.4 变尺度法（DFP法）2.4.1 原理变尺度法是在处，按某种规则产生一个对称正定矩阵（称之为尺度矩阵），并以作为处的搜索方向。显然，只要，就是下降方向。若取,就是最速下降方向；若取，就是牛顿方向（如果存在）。我们已经知道，前者收敛太慢，有锯齿现象，而后者计算量较大，可能不收敛。2.4.2 步骤（1）取初始点，给出允许误差，置；（2）计算，若，得到极小值点，停止迭代；（3）令，其中为最佳步长，即（4）计算，若，得 到极小值点，停止迭代；（5）若，令，置，转第（3）步；（6）若，计算和，按式（7）计算和，对DFP法，按公式计算出，置，转第（3）步。2.4.3 收敛性对于正定二次函数，在精确一维搜索的前提下，算法具有以下性质：（1）变尺度法具有二次终结性；（2）算法产生的搜索方向共轭；（3）迭代量保持满足拟牛顿 方程。对于一般的目标函数，算法具有：（1）保持尺度矩阵对称正定；（2）在一定条件下，超线性收敛。对严格凸函数，精确一维搜索的前提下，算法具有：（1）BFGS具有全局收敛性；（2）BFGS法与DFP法相比，虽然公式复杂，但BFGS法有更好的数值稳定性，具有整体更优的特点，尤其是BFGS与Wolfe不精确一维搜索结合被公认为目前最好的变尺度法。三、作业分析作业中对十个n元函数在无约束条件下求最小值，并做出了每个函数当n=2时的图像。在函数执行过程中都取n=10，分别用了最速下降法、牛顿法、共轭梯度法、DFP方法求解了其最优值、最优解、x的迭代次数、梯度的迭代次数、时间和精度。后面用表格进行一一列出。3.1算法函数的m文件fun1.m。梯度函数的m文件gfun1.m, Hesse矩阵文件Hess1.m,最速下降法grad1.m，阻尼牛顿法znnewtoon1.m，共轭梯度法frcg1.m,秩一校正法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-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分别是目标函数，梯度% x,val分别是近似最优点和最优解% k,gk分别是迭代次数，梯度迭代次数% 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; %梯度迭代次数 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;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,Hess6分别是目标函数，梯度和Hess矩阵函数% x,val分别是近似最优点和最优解% k,gk分别是迭代次数，梯度迭代次数% 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; %梯度迭代次数 G=feval(Hess1,x0); dk=-Gg; if (norm(g)epsilon) gn=norm(g); %精度 break; end m=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=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=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)+sigma*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 十个函数不同方法下的运行结果与三图维如下。1.最速下降法牛顿法共轭梯度法DFP法n10101010x1.00921.00921.00921.00921.00921.00921.00921.00921.00921.00921.00771.00771.00771.00771.00771.00771.00771.00771.00771.00771.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时，牛顿法与法的最优解相同且最优，但是法的计算时间最短。最速下降法的计算值最大且迭代次数最多、时间最长、精度最高。牛顿法的迭代次数最少整体来看对于该函数来讲法还是最合适的。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.67831.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从上面的表格可以看出当n=10时以上的四种方法得到的最优值、最优解相同。但是共轭梯度法与法的迭代次数最少为。牛顿法迭代次数虽多，但是其得到最优的时间最少，精度最高。相比而言，对于这个函数来说用牛顿法相对较好。 4. 最速下降法牛顿法共轭梯度法DFP法n10101010x-0.1454-0.1454-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.15234.89264.9071gn4.5981e-094.9462e-064.7052e-056.1854e-08从上面的表格可以看出当n=10时以上的四种方法得到的最优值相同，此时共轭梯度法得到的最优解是最小的，其迭代次数与时间最多且精度最小最速下降法的迭代次数与牛顿法的迭代次数最少，但是最速下降法的迭代时间最少且精度最高。相比而言，对于这个函数来说用最速下降法相对较好。 5.最速下降法牛顿法共轭梯度法DFP法n10101010x0.444500.00040.00040.00040.00040.00040.00040.000000000000000-0.15180.00020.00030.00030.00030.00030.00030.00030.00050.00090000000000val1.9779e-1102.3321e-100k11341591gk11341591t2.4101e+034.6423119.40752.7793gn9.8608e-0605.2162e-050从上面的表格可以看出当n=10时以上的四种方法最速下降法得到的值最大，其迭代次数与时间也最多当然其精度也最高。在得到最小值时牛顿法与法两者的迭代次数最小，精度一样，但是法的时间较少，因此对于求最大值而言，共轭梯度法较好一点对于求最小值时，法较好。.最速下降法牛顿法共轭梯度法DFP法n10101010x11.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.9213244.9213k66459gk66459t7.86157.8615152.27128.6736gn8.4381e-078.4381e-074.4006e-052.5273e-07从上面的表格可以看出当n=10时以上的四种方法得到的最优值、最优解都相同。此时共轭梯度法的迭代次数与时间最少且得到的精度最小。最速下降法与牛顿法的迭代次数与时间最少且得到的精度最高。因此对于该函数来说用最速下降法与牛顿法来说都行法次之，用共轭梯度法求解交果最差。 7. 最速下降法牛顿法共轭梯度法DFP法n10101010x0.21540.21540.21540.21540.21540.21540.21540.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-06从上面的表格可以看出当n=10时以上的四种方法得到的最优值都相同。此时DFP法的最优值最大且得到的精度最高， DFP法与最速下降法的迭代次数相同牛顿法的最优值最小且其迭代次数与时间最少。共轭梯度法的迭代次数与时间最多且得到的精度最小。因此对于该函数来说用牛顿法来说较好法与最速下降法次之，用共轭梯度法求解交果最差。8. 最速下降法牛顿法共轭梯度法DFP法n10101010x0.99560.98680.96050.88300.66270.1018-0.8878-1.0996-0.8905-1.09751.67831.67831.67831.67831.67831.67831.67831.67831.67831.678311111111111111111111val 3.8229e-13-8.168500k2281200gk2281200t524.85415.73683.98266.3421gn8.5057e-061.5291e-1000从上面的表格可以看出当n=10时以上的四种方法牛顿法得到的值最小、x的解最大、迭代次数较小、精度最大。最速下降法得到的值最大，其迭代次数与时间最大且精度较小。共轭梯度法与DFP法得到的最优值，最优解相同且迭代次数与精度也相同，但是共轭梯度法的计算时间最少。因此对于该函数来说用牛顿法求解最小值来说较好用最速下降法求最大值来说较好。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-05从上面的表格可以看出当n=10时以上的四种方法最速下降法得到的值最大、迭代次数较大、时间最多、精度最大共轭梯度法得到的值较小、迭代次数较小、时间最少、精度较小两者此时的最优解是相同的牛顿法与DFP法得不到的最优值，因为他们在一定程度是相对应的矩阵是奇异的因此对于该函数来说用共轭梯度法求解最值来说较好。 10. 最速下降法牛顿法共轭梯度法DFP法n10101010x0.39520.00000.000000.0000-0.0000-0.000000.00000.00200000000000-0.21380.02740.0014-0.0028-0.00100.0000-0.0033-0.00130.00120.00180000000.1110000val1.5659e-1104.9957e-106.0397e-31k5221791gk5221791t626.57253.0813103.15133.0539gn8.8281e-0607.3567e-051.0880e-14从上面的表格可以看出当n=10时以上的四种方法DFP法得到的值最大、迭代次数最少、时间最少、精度最大。共轭梯度法得到的值较小、迭代次数较多、时间较长、精度较小。最速下降法得到的值较大、迭代次数最多、时间最长、精度较小。牛顿法得到的值最小，迭代次数最少、时间较短、精度最小。因此对于该函数来说用DFP法求解最大值来说较好用牛顿法来求解最小值来说最好。四、结论综上所述，对于不同的函数来说求解最大(小)值所用的最优方法来说也是不同的，即使是对于同一个函数来说，虽说有时得到的最优值是相同的，但此时的最优解也不一定想同，而且还有他们在迭代过程的迭代次数与时间也不可能一样，甚至是在得到最优解的同时，此时的一切都可以得到最优，这样的概率几乎是微乎其微的。因此在现实生活中我们要根据实际的要求来选择适合不同场合的最优方法来满足不同的需求。通过对这门课的学习也让我得到了人生的感悟，不能在呼太多，因为得到最多的不一定是最好的，因为你以时间或金钱来做代价。要活得自在就要有自己的目标，自己的特色，相信在不远的将来，你也会有适合你的相对最优的路去。风正劲足正当扬帆破浪，任重道远更需策马加鞭这也为我们的生活立了一个很好的起锚点。谢谢老师的教导，作业完成至此。