使用黄金分割法确定步长的牛顿法

数学与计算科学学院实验报告实验项目名称使用黄金分割法确定步长的牛顿法所属课程名称最优化方法实验类型算法编程实验日期201班级信学号姓名成绩1一、实验概述：【实验目的】(1)掌握Matlab数值计算的基本方法；(2)掌握最速下降法；(3)掌握黄金分割法确定步长。【实验原理】1.黄金分割法:一维搜索是解函数极小值的方法之一，其解法思想为沿某一已知方向求目标函数的极小值点。一维搜索的解法很多，这里主要采用黄金分割法（0.618法）。该方法用不变的区间缩短率0.618代替斐波那契法每次不同的缩短率，从而可以看成是斐波那契法的近似，实现起来比较容易，也易于人们所接受。黄金分割法是用于一元函数f(x)在给定初始区间[a,b]内搜索极小点xmin的一种方法。它是优化计算中的经典算法，以算法简单、收敛速度均匀、效果较好而著称，是许多优化算法的基础，但它只适用于一维区间上的凸函数，即只在单峰区间内才能进行一维寻优，其收敛效率较低。其基本原理是：依照“去劣存优”原则、对称原则、以及等比收缩原则来逐步缩小搜索区间。具体步骤是：在区间[a,b]内取点：a1，a2把[a,b]分为三段。①如果f(a1)f(a2)，令a=a1,a1=a2,a2=a+0.618*(b-a)；②如果f(a1)f(a2)，令b=a2，a2=a1,a1=b-0.618*(b-a)；如果｜(b-a)/b｜和｜(y1-y2)/y2｜都大于收敛精度ε重新开始循环。因为[a,b]为单峰区间，这样每次可将搜索区间缩小0.618倍，处理后的区间都将包含极小点的区间缩小，然后在保留下来的区间上作同样的处理，如此迭代下去，将使搜索区[a,b]逐步缩小，直到满足预先给定的精度时，即获得一维优化问2题的近似最优解。插入点原理图如下：算法流程图:3图12.牛顿法：设fx是二次可微实函数，nkxR，Hesse矩阵2kfx正定。在kx附近用二次Taylor展开近似f，212TTkTkkkkfxsqsfxsfxssfxsksxx，kqs为fx的二次近似。将上式右边极小化，便得：121kkkkxxfxfx，这就是牛顿法的迭代公式。4在这个公式里，步长因子1k。令2,kkkkGfxgfx，则上式也可写成：11kkkkxxGg显然，牛顿法也可以看成在椭球范数kG下的最速下降法。事实上，对于Tkkkfxsfxgs，ks是极小化问题minnTksRgss的解。该极小化问题依赖于所取的范数，当采取2l范数时，kksg，所得方法为最速下降法。当采用椭球范数kG时，1kkksGg，所得方法即为牛顿法。【实验环境】Windows7Matlab7.0二、实验内容：【实验方案】算例：2212121212(,)10460fxxxxxxxx的极小值，0.001。要求:1、利用使用黄金分割法确定步长的牛顿法编写一维搜索方法（含黄金分割法确定步长）；2、在使用共轭梯度法梯度法进行搜索时可以调用一维搜索方法。【实验过程】1.黄金分割法程序流程图52.牛顿法的改进算法：给出初始点0nxR。第k步迭代为：（1）令kkGvIkG，其中：0kv，如果kG正定0,kv；否则。（2）计算_kG的Cholesky分解，_TkkkkGLDL。（3）解_kkGdg得kd。（4）令1kkkxxd【实验结论】（结果）67【实验小结】（收获体会）这次实验，使最优化方法这门课的一些理论知识与实践相结合，更加深刻了我对这门课的认识，巩固了我的理论知识。我个人得到了不少的收获,一方面加深了我对课本理论的认识,另一方面也提高了个人对于实际问题的解答能力。对于牛顿法和黄金分割法的原理与应用有个深刻认识,也将老师在课堂上的讲解真正的融会贯通,这次的实验非常有意义.三、指导教师评语及成绩：评语评语等级优良中及格不及格1.实验报告按时完成,字迹清楚,文字叙述流畅,逻辑性强2.实验方案设计合理3.实验过程（实验步骤详细,记录完整,数据合理,分析透彻）4实验结论正确.成绩：指导教师签名：批阅日期：附录1：源程序#includestdlib.h#includestdio.h#includemath.h//原函数#definef(x1,x2)x1*x1+x2*x2-x1*x2-10*x1-4*x2+60//梯度模#definetdm(x1,x2)sqrt((2*x1-x2-10)*(2*x1-x2-10)+(2*x2-x1-4)*(2*x2-x1-4))//x1的偏导数#defineG1(x1,x2)2*x1-x2-10//x2的偏导数#defineG2(x1,x2)2*x2-x1-4//一维搜索8//进退法求搜索区间constfloateps=0.001;//eps为计算精度；doubleHJFC(doublex1[],doubles1[]){intk=1,i,j;doublea0=1,b0=0.5,a1,b1,a[3],f[3],y[3][2],m,n,ak2,c;//a0为初始步长，b0为初始步长增量；a1,b1为进退法确定的最终区间；a[0]=a0;a[1]=a0+b0;for(i=0;i2;i++)for(j=0;j2;j++)y[i][j]=x1[j]+a[i]*s1[j];for(i=0;i2;i++)f[i]=f(y[i][0],y[i][1]);if(f[0]f[1])while(k){b0=2*b0;a[2]=a[1]+b0;for(j=0;j2;j++)y[2][j]=x1[j]+a[2]*s1[j];f[2]=f(y[2][0],y[2][1]);if(f[2]f[1]){m=a[0];n=a[2];k=0;}else{k=1;a[1]=a[2];f[1]=f[2];}}elsewhile(k){b0=2*b0;a[2]=a[0]-b0;9for(j=0;j2;j++)y[2][j]=x1[j]+a[2]*s1[j];f[2]=f(y[2][0],y[2][1]);if(f[2]f[0]){m=a[2];n=a[1];k=0;}else{k=1;a[0]=a[2];f[0]=f[2];}}//黄金分割法求最佳步长a1=m;b1=n;a[0]=n-0.618*(n-m);a[1]=m+0.618*(n-m);for(i=0;i2;i++)for(j=0;j2;j++)y[i][j]=x1[j]+a[i]*s1[j];for(i=0;i2;i++)f[i]=f(y[i][0],y[i][1]);do{if(f[0]f[1]){n=a[1];a[1]=a[0];f[1]=f[0];a[0]=n-0.618*(n-m);for(j=0;j2;j++)y[0][j]=x1[j]+a[0]*s1[j];f[0]=f(y[0][0],y[0][1]);}else{m=a[0];a[0]=a[1];10f[0]=f[1];a[1]=m+0.618*(n-m);for(j=0;j2;j++)y[1][j]=x1[j]+a[1]*s1[j];f[1]=f(y[1][0],y[1][1]);}c=(n-m)/(b1-a1);}while(fabs(c)eps);ak2=(m+n)/2;returnak2;}//共轭梯度法voidmain(){doublex[2],s[2],g[4],bita,arph;//x数组为函数解的转置矩阵；s数组为搜索方向的转置矩阵；g数组为梯度转置矩阵；arph为最优步长；intk=1;//k为迭代次数；//赋初值；printf(请输入初始x1、x2:\n\n);scanf(%d%d,&x[0],&x[1]);printf(过程如下：\n\n);g[0]=G1(x[0],x[1]);g[1]=G2(x[0],x[1]);while(tdm(x[0],x[1])eps)//迭代终止准则；{if(k==1){s[0]=-g[0];s[1]=-g[1];bita=0;}else{bita=(g[0]*g[0]+g[1]*g[1])/(g[2]*g[2]+g[3]*g[3]);s[0]=-g[0]+bita*s[0];s[1]=-g[1]+bita*s[1];11}arph=HJFC(x,s);x[0]=x[0]+arph*s[0];x[1]=x[1]+arph*s[1];g[2]=g[0];g[3]=g[1];g[0]=G1(x[0],x[1]);g[1]=G2(x[0],x[1]);printf(第%d次迭代：\n\n,k);printf(步长steplength=%f\t,arph);printf(bb=%f\t\n,bita);printf(x[0]=%f\tx[1]=%f\n\n\n,x[0],x[1]);k++;}k--;printf(最后结果为：\n);printf(最优解为:\nx[0]=%f\nx[1]=%f\n最小值为：min=%f\n迭代次数为：n=%d\n,x[0],x[1],f(x[0],x[1]),k);}附录2：实验报告填写说明1．实验项目名称：要求与实验教学大纲一致。2．实验目的：目的要明确，要抓住重点，符合实验教学大纲要求。3．实验原理：简要说明本实验项目所涉及的理论知识。4．实验环境：实验用的软、硬件环境。5．实验方案（思路、步骤和方法等）：这是实验报告极其重要的内容。概括整个实验过程。对于验证性实验，要写明依据何种原理、操作方法进行实验，要写明需要经过哪几个步骤来实现其操作。对于设计性和综合性实验，在上述内容基础上还应该画出流程图、设计思路和设计方法，再配以相应的文字说明。对于创新性实验，还应注明其创新点、特色。126．实验过程（实验中涉及的记录、数据、分析）：写明具体实验方案的具体实施步骤，包括实验过程中的记录、数据和相应的分析。7．实验结论（结果）：根据实验过程中得到的结果，做出结论。8．实验小结：本次实验心得体会、思考和建议。9．指导教师评语及成绩：指导教师依据学生的实际报告内容，给出本次实验报告的评价。