工程最优化第四章.ppt

《工程最优化第四章.ppt》由会员分享，可在线阅读，更多相关《工程最优化第四章.ppt（25页珍藏版）》请在三一办公上搜索。

1、第四章 单变量函数的最优化方法,搜索区间的确定 黄金分割法 二次插值法 Newton-Raphson法,要点：单峰函数的消去性质、进退算法基本思想、黄金分割法基本思想，重新开始、二次插值法要求、极小化架子、Newton-Raphson法基本思想、方法比较,学习的重要性：,1、工程实践中有时需要直接使用；,2、多变量最优化的基础，迭代中经常要用到。,方法分类：,1、直接法：迭代过程中只需要计算函数值,2、间接法或微分法：迭代过程中还需要计算目标函数的导数,4.1 搜索区间的确定,常用的一维直接法有消去法和近似法两类。它们都是从某个初始搜索区间出发，利用单峰函数的消去性质，逐步缩小搜索区间，直到满

2、足精度要求为止。,4.1.1 单峰函数,定义：如果函数f(x)在区间a,b上只有一个极值点,则称f(x)为 a,b上的单峰函数。,连续单峰函数,不连续单峰函数,离散单峰函数,非单峰函数,单峰函数具有一个重要的消去性质,定理：设f(x)是区间a,b上的一个单峰函数，x*a,b是其极小点，x1 和x2是a,b上的任意两点，且ax1 x2b，那么比较f(x1)与f(x2)的值后，可得出如下结论：,(I)消去a,x1,(II)消去x2,b,(II)若f(x1)f(x2),x*a,x2,在单峰函数的区间内，计算两个点的函数值，比较大小后，就能把搜索区间缩小。在已缩小的区间内，仍含有一个函数值，如再计算另

3、一点的函数值，比较后就可进一步缩小搜索区间。,（I）若f(x1)f(x2)，x*x1,b,4.1.2 进退算法,?如何确定包含极小点在内的初始区间?,（一）基本思想：,由单峰函数的性质可知，函数值在极小点左边严格下降，在右边严格上升。,从某个初始点出发，沿函数值下降的方向前进，直至发现函数值上升为止。,由两边高，中间低的三点，可确定极小点所在的初始区间,（二）算法,1、选定初始点a 和步长h;,2、计算并比较f(a)和f(a+h)；有前进(1)和后退(2)两种情况：,则步长加倍，计算f(a+3h)。若f(a+h)f(a+3h)，令 a1=a,b1=a+3h,停止运算；否则将步长加倍，并重复上述

4、运算。,则将步长改为h。计算f(ah),若f(ah)f(a)，令 a1=ah,b1=a+h,停止运算；否则将步长加倍，继续后退。,(三)几点说明（P87）,？,4.2 区间消去法黄金分割法,消去法的思想：反复使用单峰函数的消去性质，不断缩小包含 极小点的搜索区间，直到满足精度为止。,消去法的优点：只需计算函数值，通用性强,消去法的设计原则：（1）迭代公式简单；（2）消去效率高,（一）、黄金分割,取“”，=0.61803398874189,（二）黄金分割法的基本思想,黄金分割重要的消去性质:,设x1，x2 为a,b 中对称的两个黄金分割点,x1为a,x2的黄金分割点,x2为x1,b的黄金分割点,

5、在进行区间消去时，不管是消去a,x1，还是消去x2，b，留下来的区间中还含一个黄金分割点，只要在对称位置找另一个黄金分割点，又可以进行下一次区间消去。,每次消去后，新区间的长度约为原区间的0.618倍，经过n次消去后，保留下来的区间长度为0.618nL，需计算函数值的次数为n+1,黄金分割比 0.618，所以此法也称为0.618法,（三）算法,开始,x*a,x2,x*x1,b,!在迭代过程中，四个点的顺序始终应该是 ax1 x2 b,但在计算第二个分割点时使用x1=a+bx2 或 x2=a+b x1,由于舍入误差的影响，可能破坏ax1 x2 b这一顺序，导致混乱。迭代中必须采取一些措施：,(1

6、)终止限不要取得太小；,(2)使用双精度运算；,(3)经过若干次运算后，转到算法中的第3步，重新开始。,开始,b=x2,x2=x1,f2=f1 x1=a+b-x2,f1=f(x1),否,!在迭代过程中，四个点的顺序始终应该是 ax1 x2 b,但在计算第二个分割点时使用x1=a+bx2 或 x2=a+b x1,由于舍入误差的影响，可能破坏ax1 x2 b这一顺序，导致混乱。迭代中必须采取一些措施：,(1)终止限不要取得太小；,(2)使用双精度运算；,(3)经过若干次运算后，转到算法中的第3步，重新开始。,例4.2.1 PP89,(四)黄金分割法的优缺点,2、缺点：对解析性能好的单峰函数，与后面

7、要介绍的二次插值法、三次 插值法及牛顿拉夫森法等比较，计算量较大，收敛要慢。,1、优点：算法简单，效率高，只计算函数值，对函数要求低，稳定性好，对多峰函数或强扭曲的，甚至不连续的，都有效;,4.3 多项式近似法二次插值法,（一）基本思想,对形式复杂的函数，数学运算时不方便,复杂函数 f(x),极小点x*,函数近似，最优点也应近似,一次多项式二次多项式三次多项式,?如何构造符合要求的多项式?,（二）二次插值多项式近似法（抛物线法）的基本原理,设目标函数 f(x)在三点x1 x2 x3 上的函数值分别为f 1,f2,f3,相应的二次插值多项式为 P2(x)=a0a1x+a2x2,令P2(x)和f(

8、x)在三点上的函数值相等,三个待定系数,P2(x)的平稳点是 P2(x)a1+2a2x=0 的解,所以只需求出a1,a2,最后得,!迭代过程要点！,若任意取x1 x2 x3 三个点，,则求出的x*可能位于给定区间之外或误差太大,最初的三个点x1 x2 x3 应构成一个两边高，中间低的“极小化架子”，即满足f1f2，f3f2，且两个等号不同时成立,极小化架子可由进退算法求得,在完成一次计算后，得到近似x*，,然后进行搜索区间的收缩，再在新区间中重新构造三点组成的“极小化架子”，有两种方法,终止准则：采用目标函数值的相对误差或绝对误差来判断（PP91）,前进成功,极小化架子 x1 x2 x3,前进

9、失败,x1,x2,极小化架子 x3 x2 x1,后退,h0,2h0,4h0,h0,h0,2h0,4h0,（三）进退算法（用于求“极小化架子”或初始搜索区间）,（四）逐次二次插值近似法的算法,初始点x1，h0，精度1，溢出下限2，步长缩短率m,二次插值法的优点：收敛速度较快，约为1.3阶,缺点：对强扭曲或多峰的，收敛慢，甚至会失败，故要求函数具有较好 的解析性能,（五）二次插值法与黄金分割法的结合,4.4 要求计算导数的迭代法,如目标函数f(x)可导，可通过解f(x)0求平稳点，进而求出极值点。对高度非线性函数，要用逐次逼近求平稳点,4.4.1 Newton-Raphson法,要求目标函数f(x

10、)在搜索区间内具有二阶连续导数，且已知f(x)和f”(x)的表达式,（一）基本思想,采用迭代法求(x)=0的根,xk+1,xk+2,(xk)=(xk)/(xk1xk),xK+1=xk(xk)/(xk),用于求(x)f(x)0的根,xK+1=xkf(xk)/f”(xk),例题4.4.1 用Newton-Raphson法求解 初始点取 x0=1。（迭代二次）,解：f(x)的一阶和二阶导函数为,迭代公式为 xK+1=xkf(xk)/f”(xk),第一次迭代：x0=1,f(x0)12,f”(x0)36 x11(12)/361.33,第二次迭代：x1=1.33,f(x1)3.73,f”(x1)17.6

11、x21.33(3.73)/17.61.54,(本例精确解为 x*),(二)优缺点,1、优点：收敛速度快；在f(x)=0的单根处，是二阶收敛；在f(x)=0的 重根处，是线性收敛。,2、缺点：需要求二阶导数，若用数值导数代替，由于舍入误差将影响收敛 速度；收敛性还依赖于初始点及函数性质,!通常在计算程序中规定最大迭代次数K，当次数达到K还不能满足精度时，则认为不收敛，可更换一个初始点再试。,4.4.2 对分法,假设 f(x)是具有极小点的单峰函数，,则必存在区间a,b，使f(a)0。,由f(x)的连续性可知，必有x*(a,b)，使f(x)=0,优点：总能找到最优点,缺点：要计算导数值，收敛速度为

12、一阶,4.4.3 割线法,x*,基本思想：用割线代替Newton-Raphson法中的切线，并与区间消去法相结合。,c,!新区间两端点的导数值异号,4.4.4 三次插值多项式近似法,基本思想与二次插值法类似：用四个已知值（如两个点函数值及其导数值）构造一个三次多项式P3(x)，用P3(x)的极小点近似目标函数的极小点x*,三次插值法的收敛速度比二次插值法要快。,4.5 不精确一维搜索(P99),4.6 方法综述,（1）如目标函数能求二阶导数：用Newton-Raphson法 收敛快,（2）如目标函数能求一阶导数：首先考虑用三次插值法，收敛较快 对分法收敛速度慢，但可靠,（3）只需计算函数值的方法：首先考虑用二次插值法,收敛快 黄金分割法收敛速度较慢，但可靠,作业：P451 3（后退时采用h=0.25h）P451 4 P451 8,