使用黄金分割法确定步长牛顿法.doc
数学与计算科学学院实 验 报 告实验项目名称 使用黄金分割法确定步长的牛顿法 所属课程名称 最优化方法 实 验 类 型 算法编程 实 验 日 期 201 班 级 信 学 号 姓 名 成 绩 一、实验概述：【实验目的】(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逐步缩小，直到满足预先给定的精度时，即获得一维优化问题的近似最优解。插入点原理图如下：算法流程图:图1 2.牛顿法： 设是二次可微实函数，Hesse矩阵正定。在附近用二次Taylor展开近似，为的二次近似。将上式右边极小化，便得：， 这就是牛顿法的迭代公式。在这个公式里，步长因子。令，则上式也可写成：显然，牛顿法也可以看成在椭球范数下的最速下降法。 事实上，对于，是极小化问题 的解。该极小化问题依赖于所取的范数，当采取范数时，所得方法为最速下降法。当采用椭球范数时，所得方法即为牛顿法。【实验环境】Windows7Matlab 7.0二、实验内容：【实验方案】算例： 的极小值， 。要求: 1、利用使用黄金分割法确定步长的牛顿法 编写一维搜索方法（含黄金分割法确定步长）；2、在使用共轭梯度法梯度法进行搜索时可以调用一维搜索方法。【实验过程】1. 黄金分割法程序流程图2. 牛顿法的改进算法： 给出初始点。第k步迭代为：（1）令，其中：，如果正定；否则。（2）计算的Cholesky分解，。（3）解得。（4）令【实验结论】（结果）【实验小结】（收获体会） 这次实验，使最优化方法这门课的一些理论知识与实践相结合，更加深刻了我对这门课的认识，巩固了我的理论知识。我个人得到了不少的收获,一方面加深了我对课本理论的认识,另一方面也提高了个人对于实际问题的解答能力。对于牛顿法和黄金分割法的原理与应用有个深刻认识,也将老师在课堂上的讲解真正的融会贯通,这次的实验非常有意义.三、指导教师评语及成绩：评 语评语等级优良中及格不及格1.实验报告按时完成,字迹清楚,文字叙述流畅,逻辑性强2.实验方案设计合理3.实验过程（实验步骤详细,记录完整,数据合理,分析透彻）4实验结论正确. 成 绩： 指导教师签名： 批阅日期：附录1：源 程 序#include <stdlib.h>#include <stdio.h>#include <math.h>/原函数#define f(x1,x2) x1*x1+x2*x2-x1*x2-10*x1-4*x2+60 /梯度模#define tdm(x1,x2) sqrt(2*x1-x2-10)*(2*x1-x2-10)+(2*x2-x1-4)*(2*x2-x1-4) /x1的偏导数#define G1(x1,x2) 2*x1-x2-10 /x2的偏导数#define G2(x1,x2) 2*x2-x1-4 /一维搜索/进退法求搜索区间const float eps=0.001;/eps为计算精度； double HJFC(double x1,double s1) int k=1,i,j; double a0=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;i<2;i+) for(j=0;j<2;j+) yij=x1j+ai*s1j; for(i=0;i<2;i+) fi=f(yi0,yi1); if(f0>f1) while(k) b0=2*b0; a2=a1+b0; for(j=0;j<2;j+) y2j=x1j+a2*s1j; f2=f(y20,y21); if(f2>f1) m=a0; n=a2; k=0; else k=1;a1=a2;f1=f2; else while(k) b0=2*b0; a2=a0-b0; for(j=0;j<2;j+) y2j=x1j+a2*s1j; f2=f(y20,y21); if(f2>f0) 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;i<2;i+) for(j=0;j<2;j+) yij=x1j+ai*s1j;for(i=0;i<2;i+) fi=f(yi0,yi1);do if(f0<f1) n=a1; a1=a0; f1=f0; a0=n-0.618*(n-m); for(j=0;j<2;j+) y0j=x1j+a0*s1j; f0=f(y00,y01); else m=a0; a0=a1; f0=f1; a1=m+0.618*(n-m); for(j=0;j<2;j+) y1j=x1j+a1*s1j; f1=f(y10,y11); c=(n-m)/(b1-a1);while(fabs(c)>eps);ak2=(m+n)/2;return ak2; /共轭梯度法void main()double x2,s2,g4,bita,arph;/x数组为函数解的转置矩阵；s数组为搜索方向的转置矩阵；g数组为梯度转置矩阵；arph为最优步长；int k=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 bita=(g0*g0+g1*g1)/(g2*g2+g3*g3); s0=-g0+bita*s0; s1=-g1+bita*s1; arph=HJFC(x,s); x0=x0+arph*s0; x1=x1+arph*s1; g2=g0; g3=g1; g0=G1(x0,x1); g1=G2(x0,x1); printf("第%d次迭代：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实验方案（思路、步骤和方法等）：这是实验报告极其重要的内容。概括整个实验过程。对于验证性实验，要写明依据何种原理、操作方法进行实验，要写明需要经过哪几个步骤来实现其操作。对于设计性和综合性实验，在上述内容基础上还应该画出流程图、设计思路和设计方法，再配以相应的文字说明。对于创新性实验，还应注明其创新点、特色。6实验过程（实验中涉及的记录、数据、分析）：写明具体实验方案的具体实施步骤，包括实验过程中的记录、数据和相应的分析。7实验结论（结果）：根据实验过程中得到的结果，做出结论。8实验小结：本次实验心得体会、思考和建议。9指导教师评语及成绩：指导教师依据学生的实际报告内容，给出本次实验报告的评价。12
