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

《最优化方法-一维搜索方法.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

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

2、onacci方法--试探点算法6Fibonacci法的引入计算n次函数值，如何取点使最终区间最小？或者最终区间长度为1，计算n次函数值，初始区间最多为多长？78910课堂练习1112黄金分割法思想通过选取试探点使包含极小点的区间不断缩短，直到区间长度小到一定程度，此时区间上各点的函数值均接近极小值。下面推导黄金分割法的计算公式。1314通过确定的取值，使上一次迭代剩余的迭代点恰与下一次迭代的一个迭代点重合，从而减少算法的计算量。同理可得。15算法步骤：16一个以前很好的例子functionansw=goldsection(a,b,eps)%黄金分割

3、法实现一维搜索%a----搜索区间左端点%b----搜索区间右端点%eps----搜索精度%CopyRight@XiaBo%Date:2008.3.20%%定义搜索函数funfunctionf=fun(x)%这里是一个简单的函数定义，倘若在一个大型的优化计算中，这个函数一般是和第k步的迭代点和下降方向有关的%是一个关于步长的函数%x---待求步长值f=x^2-x+2;17%寻找初始分割点x1=a+.382*(b-a);x2=a+.618*(b-a);%搜索主体while(abs(b-a)>eps)%计算分割点处的函数值f1=fun(x1);f2=f

4、un(x2);%比较判断两个分割点处的函数值，进而缩短区间长度if(f1>f2)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);elseb=x2;x2=x1;x1=a+.382*(b-a);endend%返回搜索值answ=(a+b)/2;18黄金分割法的迭代效果：第k次后迭代后所得区间长度为初始区间长度的作业1920作业如果换成了最终区间不大于0.08，如何做？为什么？21…………………….22…………………….233．进退法思想

5、从一点出发,按一定的步长,试图确定出函数值呈现“高-低-高”的三点。一个方向不成功，就退回来，再沿相反方向寻找。进退法的计算步骤（与教材的算法比较P20）如何确定包含极小点的一个区间？24例：25平分法(优点和缺点都突出的方法)能否看出优点和缺点？26275.抛物线插值思想在极小点附近，用二次三项式为什么非要是二次三项式？28如何计算函数令29抛物线插值算法步骤：解出30作业小结各种精确一维搜索算法31不精确一维线搜索32为什么不精确的搜索好？距离最优解远的时候，精度太大算法效率低有些算法的收敛速度不依赖与搜索的精度只要求有充分下降即可这种类似与“

6、充分”、“足够”等描述词汇，在与计算相关的描述中，要特别在意，因为，这里的“充分”，已经不再是理论上的要求，这里的“充分”必须与“可计算”相关（到底要多充分，就是这里的非精确搜索的准测）33Armijo准则Wolfe准则34Goldstein准则3536Armijo准则3738收敛性证明3940懂数学、有能力、不神秘4142主体证明开始(反证法)：434445此引理给出了Wolfe准则单步中至少下降的界（略）46474849Wolfe准则收敛定理：（略）50证明：5152535455