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

1、沙理工大数学与计算科学学院实验报告实验项目名称使用黄金分割法确定步长的牛顿法所属课程名称最优化方法实验类型算法编程实验日期201班级信学号姓名一、实验概述：【实验目的】(1)掌握Matlab数值计算的基本方法；(2)掌握最速下降法；(3)掌握黄金分割法确定步长。【实验原理】1.黄金分割法：一维搜索是解函数极小值的方法之一，其解法思想为沿某一已知方向求目标函数的极小值点。一维搜索的解法很多，这里主要采用黄金分割法(0.618法)。该方法用不变的区间缩短率0.618代替斐波那契法每次不同的缩短率，从而可以看成是斐波那契法的近似，实现起来比较容易，也易于人们所接受。黄金分割法是用于一元函数f(x)在

2、给定初始区间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)23+21=01=0618所谓的“黄金分率厂是指将一线段分成两段的方.法，使整成K与较长段的长度比值等于较长段与较短段的比曲，即:A=A:

3、(-A)算法流程图：图12.牛顿法：设f(x)是二次可微实函数，xkwRn,Hesse矩阵bf(xk)正定。在xk附近用二次Taylor展开近似f,f(xk+s)qtk)(s)=f(xkTs+f(xkfs+1sT2f(xk)s2s=x-xk,q(k*s)为f(x)的二次近似。将上式右边极小化，便得：_.-4xk4t=xk-f(xk)1Vf(xk),这就是牛顿法的迭代公式。在这个公式里，步长因子=1。令Gk=2f(Xk)项=Vf(Xk),则上式也可写成：1xki=xk-Gkgk显然，牛顿法也可以看成在椭球范数|L下的最速下降法。事实上，对于f(Xk+s产f(Xk)+g：s,TSk是极小化问题mi

4、n猾的解。该极小化问题依赖于所取的范数，当采取12范sRn闾数时，Sk=-gk,所得方法为最速下降法。当采用椭球范数Uh时，W=-Gjgk,所得方法即为牛顿法。【实验环境】Windows7Matlab7.0二、实验内容：【实验方案】算例：f(x1,x2)=x12+x22x1x210x14x2+60的极小值，00.001o要求：1、利用使用黄金分割法确定步长的牛顿法编写一维搜索方法(含黄金分割法确定步长)；2、在使用共物梯度法梯度法进行搜索时可以调用一维搜索方法。【实验过程】1.黄金分割法程序流程图1/?F-steplengtli=07336683bb=0T000001x01=7.99988(1

5、xtl=S.999869最后结毗解为,-xLI1=5.999869最小值为：迭央次数为：n=42Pressanykeytocontinue【实验小结】（收获体会）这次实验，使戢优化方法这门课的一些理论知识与实践相结合，更加深刻了我对这门课的认识，巩固了我的理论知识。我个人得到了不少的收获，一方面加深了我对课本理论的认识，另一方面也提高r个人对于实际问题的解答能力。对于牛顿法和黄金分割法的原理与应用有个深刻认识，也将老师在课堂上的讲解真正的融会贯通，这次的实验非常后意义.三、指导教师评语及成绩：评语评语等级优良中及格/、及格1.实验报告按时完成，字迹清楚，文字叙述流畅，逻辑性强2.实验方案设计合

6、理3.实验过程（实验步骤详细，记录完整，数据合理，分析透彻）4实验结论正确.成绩：指导教师签名：批阅日期：附录1:源程序#include#include#include/原函数#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/一维搜索/进退法求搜索区间constfloateps=

7、0.001;/eps为计算精度；doubleHJFC(doublex1,doubles1)(intk=1,i,j;doublea0=1,b0=0.5,a1,b1,a3,f3,y32,m,n,ak2,c;/a0为初始步长，b0为初始步长增量；a1,b1为进退法确定的最终区间;a0=a0;a1=a0+b0;for(i=0;i2;i+)for(j=0;j2;j+)yij=x1j+ai*s1j;for(i=0;if1)while(k)(b0=2*b0;a2=a1+b0;for(j=0;jf1)(m=a0;n=a2;k=0;else(k=1;a1=a2;f1=f2;elsewhile(k)(b0=2*b

8、0;a2=a0-b0;for(j=0;jf0)(m=a2;n=a1;k=0;else(k=1;a0=a2;f0=f2;/黄金分割法求最佳步长a1=m;b1=n;a0=n-0.618*(n-m);a1=m+0.618*(n-m);for(i=0;i2;i+)for(j=0;j2;j+)yij=x1j+ai*s1j;for(i=0;i2;i+)fi=f(yi0,yi1);do(if(f0f1)(n=a1;a1=a0;f1=f0;a0=n-0.618*(n-m);for(j=0;j2;j+)y0j=x1j+a0*s1j;f0=f(y00,y01);else(m=a0;a0=a1;f0=f1;a1=m

9、+0.618*(n-m);for(j=0;jeps);ak2=(m+n)/2;returnak2;共辗梯度法voidmain()doublex2,s2,g4,bita,arph;arph/x数组为函数解白转置矩阵；s数组为搜索方向的转置矩阵；g数组为梯度转置矩阵;为最优步长；intk=1;/k为迭代次数；赋初值；printf(请输入初始x1、x2:nn);scanf(%d%d,&x0,&x1);printf(过程如下：nn);g0=G1(x0,x1);g1=G2(x0,x1);while(tdm(x0,x1)eps)迭代终止准则；if(k=1)s0=-g0;s1=-g1;bita=0;else

10、bita=(g0*g0+g1*g1)/(g2*g2+g3*g3);s0=-g0+bita*s0;s1=-g1+bita*s1;10arph=HJFC(x,s);x0=x0+arph*s0;x1=x1+arph*s1;g2=g0;g3=gi;g0=G1(x0,x1);g1=G2(x0,x1);printf(第次迭代：nn,k);printf(步长steplength=%ft,arph);printf(bb=%ftn,bita);printf(x0=%ftx1=%fnnn,x0,x1);k+;)k-;printf(最后结果为：n);printf(最优解为：nx0=%fnx1=%fn最小值为：min=%fn迭代次数为：n=%dn,x0,x1,f(x0,x1),k);)附录2:实验报告填写说明1 .实验项目名称：要求与实验教学大纲一致。2 .实验目的：目的要明确，要抓住重点，符合实验教学大纲要求。3 .实验原理：简要说明本实验项目所涉及的理论知识。4 .实验环境：实验用的软、硬件环境。5 .实验方案（思路、步骤和方法等）：这是实验报告极其重要的内容。概括整个实验过程。对于验证性实验，要写明依据何种原理、操作方法进行实验，要写明需要经过哪几个步骤来实现其操作。对于设计性和综合性实验，在上述内容基础上还应该画出流程图、设计思路和设计方法，再配以相应的文字说明。对于创新