无约束问题.ppt

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,最优化方法,作者：赵方,学号：,060108010015,第三章 无约束问题,主要内容：,1.,进退法,2.0.618,法,3.Fibonacci,法,（,1,）进退,法,minf(x),xE,：,允许误差,进退法又名加步探索法，是一种区间试探法，,0.618,法和其他一维搜索方法都要事先给定一个包含极小值点的搜索区间，而进退法却不用，主要思路：从一点出发，按一定的步长，试图确定出函数值呈现“高,-,低,-,高”的,3,点，首先从一个方向去找，若不成功，就退回来，再沿相反方向寻找，若方向正确，则加大步长进行探索，最终找到,x1,x2,x3,满足,x1f(x2)0,步长,x,1,=x,0,+h,1),f(x,1,)f(x,0,),成功 令,2,h,h,前进,2)f(x,1,),f(x,0,),失败,退回,x,0,-1/4h,h,重复 到,h=0),的搜索区间，要求选取,x1=0,h0=1,步长倍数,a=2.,解：,取,x1=0,令,x2=x1+ho=1,因为,f(x1)=1,f(x2)=0,所以,f(x2)f(x2),即对,x1,x2,x3,三点，有,x1x2f(x2)f(x3),成立，,在,x2,与,x3,之间插入,x4,点，,x4=(x2+x3)/2=2,f(x4)=5,因为,f(x2)x(x4)0),近似最优解，设初始搜索区间,0,3,精度为,=0.15,（,=),解,：a0=0,b0=3,t1=0.382(3-0)=1.146 f(t1)=,0.2131,t1=0.618(3-0)=1.854 f(t1)=,3.6648,因为,f(t1),所以继续迭代，令,t2=,0.382*,（,1.854-0,）,=,0.7082,t2=t1=1.146,f(t2)=-0.0611,f(t2)=0.2131,f(t2)f(t2),a2=a1=0,b2=t2=1.146 =1.146/3,t3=0.382*(1.146-0)=0.438,t3=t2=0.7082,f(t3)=-0.0611,f(t3)=0.2080,f(t3)f(t3).,四次迭代后，,=0.438/3=0.1460.15,a4=t4=0.708,b4=b3=1.146,故满足精度要求，输出近似最优解为,x=(b4+a4)/2=0.927,所以极小值为,f(x,)=-0.0574.,练一练：,例,2,初始区间,-1,，,1,，区间精度,=0.06.,答案：,因为,(0.279-0.168)/2=0.05550.000000000001,IfFx1Fx2,a=x1;x1=x2;x2=a+0.618*(b-a),b=x2;x2=x1;x1=a+0.382*(,b-a),x,=Minx1,x2,Printx,=,x,Printy,=,Fx,(,3,)、Fibonacci法,f(x,),在,a,b,上,是一个下单峰函数，即,f(x),在,a,b,上只有一个极小点,x0，,且在,a,x0 f(x),降,，,在,x0,b f(x),升,。,消去法基本思路：,x1 ,x2 ,a,b,x1,f(x0),，,去掉,a,x1),区间为,x1,b,，,保留,x2,3,、,Fibonacci,法步骤：,minf(x),，,xa,0,b,0,(1),、确定试点个数,n,(2),、选取第,1,，,2,个试点,t,1,t,1,t,1,=a,0,+(b,0,-a,0,)=b,0,+(a,0,-b,0,),F,n,F,n-2,F,n,F,n-1,t,1,=a,0,+(b,0,-a,0,),F,n,F,n-1,(3),、计算并比较,f(t,1,),f(t,1,),若,f(t,1,)=1/,=12.5,查表可得，,n=6,a0=-1,b0=3,t1=b0+(a0-b0)F5/F6=0.538,t1=a0+(b0-a0)F5/F6=1.462,f(t1)=1.751,f(t1)=2.675,由于,f(t1)f(t2),取,a2=t2=-0.077,b2=1.462,t3=t2=0.583,t3=a2+(b2-a2)F3/F4=0.846,f(t3)=1.870,f(t3)=1.751,由于,f(t3)f(t4)=1.751,取,a4=t4=0.231,b4=b3=0.846,t5=t4=0.583,令,t5=a4+(1/2+)(b4-a4)=0.231+(0.5+0.01)(0.846-0.231)=0.545,f(t5)=1.752f(t5)=1.751,取,a5=0.231,，,b5=0.545,f(t5)(t5)=1.752,所以,t5,为极小点，极小值为,1.751.,与,精确解,进行比较，,t*=0.5,f(t*)=1.75,练一练：,例二试用,fibonacci,法求解,f(t,)=t(2)-6t+2,在区间,0,10,上的极小点，要求缩短后的区间长度不大于原区间长度的,0.5%.,解：经计算，极小点为,3.0,，极小值为,-7,附一维搜索 黄金分割法 二次插值法实现程序,谢谢观看！,