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

1、1,精确一维搜索,2. Fibonacci与黄金分割法,3. 进退法,4. 平分法,1. 一维最优化问题,5. 抛物线搜索法,2,一维搜索的基本概念,3,一. 一维最优化问题,下降迭代算法中最优步长的确定,.,.,一维最优化问题：,极值点的必要条件：,4,1. 下单峰函数,定义：设,是区间,上的一元函数，,是,在,上的极小点，且对任意的,有,（a）当,时，,（b）当,.,.,.,.,.,则称 下是单峰函数。,.,.,有没有特殊形式的下单峰函数,5,性质：通过计算区间,内两个不同点的函数值，就可以,确定一个包含极小点的子区间。,定理,设,是区间,上的一元函数，,是,在,上的极小点。任取点,则有,

2、（1）如果,，则,（2）如果,则,.,.,.,.,.,如何确定一个下单峰函数呢？,6,Fibonacci方法-试探点算法,7,Fibonacci法的引入,计算n次函数值，如何取点使最终区间最小？,或者最终区间长度为1，计算n次函数值，初始区间最多为多长？,8,9,10,11,课堂练习,12,13,黄金分割法,思想,通过选取试探点使包含极小点的区间不断缩短，,直到区间长度小到一定程度，此时区间上各点的函数,值均接近极小值。,下面推导黄金分割法的计算公式。,14,15,通过确定 的取值，使上一次迭代剩余的迭代点恰与下一次迭代的一个迭代点重合，从而减少算法的计算量。,同理可得。,16,算法步骤：,1

3、7,一个以前很好的例子 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;,18,% 寻找初始分割点 x1=a+.382*(b-a); x2=a+.618*

4、(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;,19,黄金分割法的迭代效果：第k次后迭代后所得区间长度为,初始区间长度的,作业,

5、20,21,作业,如果换成了最终区间不大于0.08，如何做？,为什么？,22,.,23,.,24,3进退法,思想,从一点出发,按一定的步长, 试图确定出函数值呈现“高 - 低 - 高”,的三点。一个方向不成功，就退回来，再沿相反方向寻找。,进退法的计算步骤（与教材的算法比较P20）,如何确定包含极小点的一个区间？,25,例：,26,平分法(优点和缺点都突出的方法),能否看出 优点和缺点？,27,28,5. 抛物线插值,思想,在极小点附近，用二次三项式,为什么非要是二次三项式？,29,如何计算函数,令,30,抛物线插值算法步骤：,解出,31,作业,小结各种精确一维搜索算法,32,不精确一维线搜索,33,为什么不精确的搜索好？,距离最优解远的时候，精度太大 算法效率低 有些算法的收敛速度不依赖与搜索的精度 只要求有充分下降即可 这种类似与“充分”、“足够”等描述词汇，在与计算相关的描述中，要特别在意，因为，这里的“充分”，已经不再是理论上的要求，这里的“充分”必须与“可计算”相关 （到底要多充分，就是这里的非精确搜索的准测）,34,Armijo 准则,Wolfe 准则,35,Goldstein 准则,36,37,Armijo 准则,38,39,收敛性证明,40,41,懂数学、有能力、不神秘,42,43,主体证明