最优化方法-一维搜索方法.ppt

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,2021/10/10,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,2021/10/10,*,精确一维搜索,2.,Fibonacci,与,黄金分割法,3.进退法,4.平分法,1.一维最优化问题,5.,抛物线搜索法,2021/10/10,1,一维搜索的基本概念,2021/10/10,2,一.一维最优化问题,下降迭代算法中最优步长的确定,.,.,一维最优化问题：,极值点的必要条件：,2021/10/10,3,1.下单峰函数,定义,：设,是区间,上的一元函数，,是,在,上的极小点，且对任意的,有,（,a）,当,时，,（,b）,当,.,.,.,.,.,则称 下是单峰函数。,.,.,有没有特殊形式的下单峰函数,2021/10/10,4,性质：通过计算区间,内两个不同点的函数值，就可以,确定一个包含极小点的子区间。,定理,设,是区间,上的一元函数，,是,在,上的极小点。任取点,则有,（1）如果,，则,（2）如果,则,.,.,.,.,.,如何确定一个下单峰函数呢？,2021/10/10,5,Fibonacci,方法,-,试探点算法,2021/10/10,6,Fibonacci,法的引入,计算,n,次函数值，如何取点使最终区间最小？,或者最终区间长度为,1,，计算,n,次函数值，初始区间最多为多长？,2021/10/10,7,2021/10/10,8,2021/10/10,9,2021/10/10,10,课堂练习,2021/10/10,11,2021/10/10,12,黄金分割法,思想,通过选取试探点使包含极小点的区间不断缩短，,直到区间长度小到一定程度，此时区间上各点的函数,值均接近极小值。,下面推导黄金分割法的计算公式。,2021/10/10,13,2021/10/10,14,通过确定 的取值，使上一次迭代剩余的迭代点恰与下一次迭代的一个迭代点重合，从而减少算法的计算量。,同理可得。,2021/10/10,15,算法步骤：,2021/10/10,16,一个以前很好的例子,function answ=goldsection(a,b,eps),%,黄金分割法实现一维搜索,%a -,搜索区间左端点,%b -,搜索区间右端点,%eps-,搜索精度,%CopyRightXiaBo,%Date:2008.3.20,%,定义搜索函数,fun,function f=fun(x)%,这里是一个简单的函数定义，倘若在一个大型的优化计算中，这个函数一般是和第,k,步的迭代点和下降方向有关的,%,是一个关于步长的函数,%x-,待求步长值,f=x2-x+2;,2021/10/10,17,%,寻找初始分割点,x1=a+.382*(b-a);,x2=a+.618*(b-a);,%,搜索主体,while(abs(b-a)eps),%,计算分割点处的函数值,f1=fun(x1);,f2=fun(x2);,%,比较判断两个分割点处的函数值，进而缩短区间长度,if(f1f2),a=x1;x1=x2;,x2=a+.618*(b-a);,elseif(f1=f2),a=x1;b=x2;,x1=a+.382*(b-a);,x2=a+.618*(b-a);,else,b=x2;x2=x1;,x1=a+.382*(b-a);,end,end,%,返回搜索值,answ=(a+b)/2;,2021/10/10,18,黄金分割法的迭代效果：第,k,次后迭代后所得区间长度为,初始区间长度的,作业,2021/10/10,19,2021/10/10,20,作业,如果换成了最终区间不大于,0.08,，如何做？,为什么？,2021/10/10,21,.,2021/10/10,22,.,2021/10/10,23,3,进退法,思想,从一点出发,按一定的步长,试图确定出函数值呈现“高-低-高”,的三点。一个方向不成功，就退回来，再沿相反方向寻找。,进退法的计算步骤（与教材的算法比较,P20,）,如何确定包含极小点的一个区间？,2021/10/10,24,例：,2021/10/10,25,平分法,(,优点和缺点都突出的方法,),能否看出 优点和缺点？,2021/10/10,26,2021/10/10,27,5.,抛物线插值,思想,在极小点附近，用二次三项式,为什么非要是二次三项式？,2021/10/10,28,如何计算函数,令,2021/10/10,29,抛物线插值算法步骤：,解出,2021/10/10,30,作业,小结各种精确一维搜索算法,2021/10/10,31,不精确一维线搜索,2021/10/10,32,为什么不精确的搜索好？,距离最优解远的时候，精度太大 算法效率低,有些算法的收敛速度不依赖与搜索的精度,只要求有充分下降即可,这种类似与“充分”、“足够”等描述词汇，在与计算相关的描述中，要特别在意，因为，这里的“充分”，已经不再是理论上的要求，这里的“充分”必须与“可计算”相关,（到底要多充分，就是这里的非精确搜索的准测）,2021/10/10,33,Armijo,准则,Wolfe,准则,2021/10/10,34,Goldstein,准则,2021/10/10,35,2021/10/10,36,Armijo,准则,2021/10/10,37,2021/10/10,38,收敛性证明,2021/10/10,39,2021/10/10,40,懂数学、有能力、不神秘,2021/10/10,41,2021/10/10,42,主体证明开始,(,反证法,),：,2021/10/10,43,2021/10/10,44,2021/10/10,45,此引理给出了,Wolfe,准则单步中至少下降的界（略）,2021/10/10,46,2021/10/10,47,2021/10/10,48,2021/10/10,49,Wolfe,准则收敛定理：,（略）,2021/10/10,50,证明：,2021/10/10,51,2021/10/10,52,2021/10/10,53,2021/10/10,54,2021/10/10,55,