最优化方法-一维搜索方法课件

精确一维搜索精确一维搜索2.Fibonacci与与黄金分割法黄金分割法3.进退法进退法 4.平分法平分法1.一维最优化问题一维最优化问题 5.抛物线搜索法抛物线搜索法1一维搜索的基本概念一维搜索的基本概念2一一.一维最优化问题一维最优化问题下降迭代算法中最优步长的确定下降迭代算法中最优步长的确定.一维最优化问题：一维最优化问题：极值点的必要条件：极值点的必要条件：31.下单峰函数下单峰函数定义定义：设：设是区间是区间上的一元函数，上的一元函数，是是在在上的极小点，且对任意的上的极小点，且对任意的有有（a）当当时，时，（b）当当.则称则称 下是单峰函数。下是单峰函数。.有没有特殊形有没有特殊形式的下单峰函式的下单峰函数数4性质：通过计算区间性质：通过计算区间内两个不同点的函数值，就可以内两个不同点的函数值，就可以确定一个包含极小点的子区间。确定一个包含极小点的子区间。定理定理 设设是区间是区间上的一元函数，上的一元函数，是是在在上的极小点。任取点上的极小点。任取点则有则有（1）如果）如果，则，则（2）如果）如果则则.如何确定一个下如何确定一个下单峰函数呢？单峰函数呢？5Fibonacci方法方法-试探点算法试探点算法6Fibonacci法的引入法的引入计算计算n次函数值，如何取点使最终区间最小？次函数值，如何取点使最终区间最小？或者最终区间长度为或者最终区间长度为1，计算，计算n次函数值，初始区次函数值，初始区间最多为多长？间最多为多长？78910课堂练习1112黄金分割法黄金分割法思想通过选取试探点使包含极小点的区间不断缩短，通过选取试探点使包含极小点的区间不断缩短，直到区间长度小到一定程度，此时区间上各点的函数直到区间长度小到一定程度，此时区间上各点的函数值均接近极小值。值均接近极小值。下面推导黄金分割法的计算公式。下面推导黄金分割法的计算公式。1314通过确定通过确定 的取值，使上一次迭代剩余的迭代点恰与下一次的取值，使上一次迭代剩余的迭代点恰与下一次迭代的一个迭代点重合，从而减少算法的计算量。迭代的一个迭代点重合，从而减少算法的计算量。同理可得。同理可得。15算法步骤：算法步骤：16v一个以前很好的例子一个以前很好的例子vfunction answ=goldsection(a,b,eps)v%黄金分割法实现一维搜索黄金分割法实现一维搜索v%a -搜索区间左端点搜索区间左端点v%b -搜索区间右端点搜索区间右端点v%eps-搜索精度搜索精度v%CopyRightXiaBov%Date:2008.3.20 v%定义搜索函数定义搜索函数funvfunction f=fun(x)%这里是一个简单的函数定义，这里是一个简单的函数定义，倘若在一个大型的优化计算中，这个函数一般是和第倘若在一个大型的优化计算中，这个函数一般是和第k步的迭代点和下降方向有关的步的迭代点和下降方向有关的v%是一个关于步长的函数是一个关于步长的函数v%x-待求步长值待求步长值vf=x2-x+2;17v%寻找初始分割点寻找初始分割点vx1=a+.382*(b-a);vx2=a+.618*(b-a);v%搜索主体搜索主体vwhile(abs(b-a)eps)v%计算分割点处的计算分割点处的函数值函数值v f1=fun(x1);v 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);endend%返回搜索值返回搜索值answ=(a+b)/2;18黄金分割法的迭代效果：第黄金分割法的迭代效果：第k次后迭代后所得区间长度为次后迭代后所得区间长度为初始区间长度的初始区间长度的作业作业1920作业作业如果换成了最终区间不大于0.08，如何做？为什么？21.22.233进退法进退法思想思想 从一点出发从一点出发,按一定的步长按一定的步长,试图确定出函数值呈现试图确定出函数值呈现“高高-低低-高高”的三点。一个方向不成功，就退回来，再沿相反方向寻找。的三点。一个方向不成功，就退回来，再沿相反方向寻找。进退法的计算步骤（与教材的算法比较进退法的计算步骤（与教材的算法比较P20）如何确定包含极小点的一个区间？如何确定包含极小点的一个区间？24例：例：25平分法平分法(优点和缺点都突出的方法)能否看出 优点和缺点？26275.抛物线插值抛物线插值思想思想在极小点附近，用二次三项式在极小点附近，用二次三项式为什么非要是二次三项式？28如何计算函数如何计算函数令令29抛物线插值算法步骤：抛物线插值算法步骤：解出解出30作业v小结各种精确一维搜索算法小结各种精确一维搜索算法31不精确一维线搜索不精确一维线搜索32为什么不精确的搜索好？为什么不精确的搜索好？v距离最优解远的时候，精度太大距离最优解远的时候，精度太大 算法效率低算法效率低v有些算法的收敛速度不依赖与搜索的精度有些算法的收敛速度不依赖与搜索的精度v只要求有充分下降即可只要求有充分下降即可 这种类似与这种类似与“充分充分”、“足够足够”等描述词汇，在与等描述词汇，在与计算相关的描述中，要特别在意，因为，这里的计算相关的描述中，要特别在意，因为，这里的“充分充分”，已经不再是理论上的要求，这里的，已经不再是理论上的要求，这里的“充分充分”必须与必须与“可计算可计算”相关相关（到底要多充分，就是这里的非精确搜索的准测）（到底要多充分，就是这里的非精确搜索的准测）33Armijo 准则准则 Wolfe 准则准则34Goldstein 准则准则3536Armijo 准则准则3738收敛性证明收敛性证明3940懂数学、有能力、不神秘4142主体证明开始主体证明开始(反证法反证法)：434445 此引理给出了此引理给出了Wolfe准则单步中至少下降的界（略）准则单步中至少下降的界（略）46474849Wolfe准则收敛定理：准则收敛定理：（略）（略）50证明：证明：5152535455写在最后写在最后成功的基础在于好的学习习惯成功的基础在于好的学习习惯The foundation of success lies in good habits谢谢聆听 学习就是为了达到一定目的而努力去干,是为一个目标去战胜各种困难的过程,这个过程会充满压力、痛苦和挫折Learning Is To Achieve A Certain Goal And Work Hard,Is A Process To Overcome Various Difficulties For A Goal