《工程最优化第四章.ppt》由会员分享，可在线阅读，更多相关《工程最优化第四章.ppt（25页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、工程最优化第四章现在学习的是第1页，共25页学习的重要性：学习的重要性：1、工程实践中有时需要直接使用；工程实践中有时需要直接使用；2、多变量最优化的基础，迭代中经常要用到。多变量最优化的基础，迭代中经常要用到。方法分类：方法分类：1、直接法：、直接法：迭代过程中只需要计算函数值迭代过程中只需要计算函数值2、间接法或微分法：、间接法或微分法：迭代过程中还需要计算目标函数的导数迭代过程中还需要计算目标函数的导数现在学习的是第2页，共25页f(x)xab4.1 搜索区间的确定搜索区间的确定 常用的一维直接法有常用的一维直接法有消去法消去法和和近似法近似法两类。它们都是从某个两类。它们都是从某个初始
2、搜索区间出发，利用初始搜索区间出发，利用单峰函数的消去性质单峰函数的消去性质，逐步缩小搜索区，逐步缩小搜索区间，直到满足精度要求为止。间，直到满足精度要求为止。4.1.1 单峰函数单峰函数 定义：定义：如果函数如果函数f(x)在区间在区间a,b上只有一个极值点上只有一个极值点,则称则称f(x)为为 a,b上的单峰函数。上的单峰函数。连续单峰函数连续单峰函数f(x)xab不连续单峰函数不连续单峰函数f(x)xab离散单峰函数离散单峰函数f(x)xa b非单峰函数非单峰函数现在学习的是第3页，共25页单峰函数具有一个重要的消去性质单峰函数具有一个重要的消去性质定理：定理：设设f(x)是区间是区间a
3、,b上的一个单峰函数，上的一个单峰函数，x*a,b是其极小点，是其极小点，x1 和和x2是是a,b上的任意两点，且上的任意两点，且ax1 x2b，那么比较，那么比较f(x1)与与f(x2)的的值后，可得出如下结论：值后，可得出如下结论：f(x)xab(I)消去消去a,x1 x*x1x2f(x)xab(II)消去消去x2,bx*x2x1(II)若若f(x1)f(x2),x*a,x2在单峰函数的区间内，计算两个点的函数值，比较大小后，就能把搜索在单峰函数的区间内，计算两个点的函数值，比较大小后，就能把搜索区间缩小。在已缩小的区间内，仍含有一个函数值，如再计算另一点的区间缩小。在已缩小的区间内，仍含
4、有一个函数值，如再计算另一点的函数值，比较后就可进一步缩小搜索区间函数值，比较后就可进一步缩小搜索区间。（I）若若f(x1)f(x2)，x*x1,b现在学习的是第4页，共25页4.1.2 进退算法进退算法?如何确定包含极小点在内的初始区间如何确定包含极小点在内的初始区间?（一）（一）基本思想：基本思想：由单峰函数的性质可知，函数值在极小点左边严格下降，在右边严格由单峰函数的性质可知，函数值在极小点左边严格下降，在右边严格上升。上升。f(x)xabx*x0 x1x2从某个初始点出发，沿函数值下降的方向前进，直至发现函数值从某个初始点出发，沿函数值下降的方向前进，直至发现函数值上升为止。上升为止。
5、由两边高，中间低的三点，可确定极小点所在的初始区间由两边高，中间低的三点，可确定极小点所在的初始区间x3现在学习的是第5页，共25页（二）（二）算法算法1、选定初始点选定初始点a 和步长和步长h;f(x)x2、计算并比较计算并比较f(a)和和f(a+h)；有前进；有前进(1)和后退和后退(2)两种情况：两种情况：(1)前进运算：若前进运算：若f(a)f(a+h),(2)后退运算：若后退运算：若f(a)f(a+h),a a+h 则步长加倍，计算则步长加倍，计算f(a+3h)。若。若f(a+h)f(a+3h)，令令 a1=a,b1=a+3h,停止运算；否则将步长加倍，并重复上述运算。停止运算；否则
6、将步长加倍，并重复上述运算。a+3hf(x)xaa+ha+7ha1b1a-ha-3ha-7ha1b1 则将步长改为则将步长改为h。计算。计算f(ah),若若f(ah)f(a)，令令 a1=ah,b1=a+h,停止运算；否则将步长加倍，继续后退。停止运算；否则将步长加倍，继续后退。(三三)几点说明几点说明 （P87）？现在学习的是第6页，共25页4.2 区间消去法黄金分割法区间消去法黄金分割法 消去法的思想：消去法的思想：反复使用单峰函数的消去性质，不断缩小包含反复使用单峰函数的消去性质，不断缩小包含 极小点的搜索区间，直到满足精度为止。极小点的搜索区间，直到满足精度为止。消去法的优点：消去法的
7、优点：只需计算函数值，通用性强只需计算函数值，通用性强 消去法的设计原则：（消去法的设计原则：（1）迭代公式简单；（）迭代公式简单；（2）消去效率高）消去效率高（一）、（一）、黄金分割黄金分割 xabL L (1)L取取“”，=0.61803398874189 现在学习的是第7页，共25页（二）（二）黄金分割法的基本思想黄金分割法的基本思想 黄金分割重要的黄金分割重要的消去性质消去性质:x2abL L L (1(1)L)Lx1 L L (1(1)L)L设设x1，x2 为为a,b 中对称的两个黄金分割点中对称的两个黄金分割点x1为为a,x2的黄的黄金分割点金分割点x2为为x1,b的的黄金分割点黄
8、金分割点 在在进进行行区区间间消消去去时时，不不管管是是消消去去a,x1，还还是是消消去去x2，b，留留下下来来的的区区间间中中还还含含一个黄金分割点，只要在对称位置找另一个黄金分割点，又可以进行下一次区间消去。一个黄金分割点，只要在对称位置找另一个黄金分割点，又可以进行下一次区间消去。每次消去后，新区间的长度约为原区间的每次消去后，新区间的长度约为原区间的0.618倍，经过倍，经过n次消去后次消去后，保留下来的，保留下来的区间区间长度为长度为0.618nL，需，需计算函数值的次数为计算函数值的次数为n+1 黄金分割比黄金分割比 0.618，所以此法也称为，所以此法也称为0.618法法 现在学
9、习的是第8页，共25页（三）（三）算法算法 开始开始b-x1 x2 a 给定给定a0,b0,a=a0,b=b0,=0.618034x2=a+(b-a),x1=a+bx2f2=f(x2),f1=f(x1)f1 f2是是否否a=x1,x1=x2,f1=f2 x2=a+b-x1,f2=f(x2)否否b=x2,x2=x1,f2=f1 x1=a+b-x2,f1=f(x1)否否x*a,x2x*x1,bx*=x1,f*=f1结束结束是是x*=x2,f*=f2是是abx2x1x1 x2=ab现在学习的是第9页，共25页!在迭代过程中，四个点的顺序始终应该是在迭代过程中，四个点的顺序始终应该是 ax1 x2 b
10、但在计算第二个分割点时使用但在计算第二个分割点时使用x1=a+bx2 或或 x2=a+b x1,由于舍入误差的影响，可能破坏由于舍入误差的影响，可能破坏ax1 x2 b这一顺序，导致混乱。迭代中必须采取一些措施：这一顺序，导致混乱。迭代中必须采取一些措施：(1)终止限终止限 不要取得太小；不要取得太小；(2)使用双精度运算使用双精度运算；(3)经过若干次运算后，转到算法中的第经过若干次运算后，转到算法中的第3步，步，重新开始。重新开始。现在学习的是第10页，共25页开始开始b-x1 x2 a 给定给定a0,b0,a=a0,b=b0,=0.618034x2=a+(b-a),x1=a+bx2f2=
11、f(x2),f1=f(x1)f1 f2是是否否a=x1,x1=x2,f1=f2 x2=a+b-x1,f2=f(x2)否否b=x2,x2=x1,f2=f1 x1=a+b-x2,f1=f(x1)否否x*=x1,f*=f1结束结束是是x*=x2,f*=f2是是现在学习的是第11页，共25页!在迭代过程中，四个点的顺序始终应该是在迭代过程中，四个点的顺序始终应该是 ax1 x2 b但在计算第二个分割点时使用但在计算第二个分割点时使用x1=a+bx2 或或 x2=a+b x1,由于舍入误差的影响，由于舍入误差的影响，可能破坏可能破坏ax1 x2 b这一顺序，导致混乱。迭代中必须采取一些措施：这一顺序，导
12、致混乱。迭代中必须采取一些措施：(1)终止限终止限 不要取得太小；不要取得太小；(2)使用双精度运算使用双精度运算；(3)经过若干次运算后，转到算法中的第经过若干次运算后，转到算法中的第3步，步，重新开始。重新开始。例例4.2.1 PP89(四四)黄金分割法的优缺点黄金分割法的优缺点 2、缺点：对解析性能好的单峰函数，与后面要介绍的二次插值法、三次缺点：对解析性能好的单峰函数，与后面要介绍的二次插值法、三次 插值法及牛顿拉夫森法等比较，计算量较大，收敛要慢。插值法及牛顿拉夫森法等比较，计算量较大，收敛要慢。1、优点：算法简单，效率高，只计算函数值，对函数要求低，稳定性好，优点：算法简单，效率高
13、，只计算函数值，对函数要求低，稳定性好，对多峰函数或强扭曲的，甚至不连续的，都有效对多峰函数或强扭曲的，甚至不连续的，都有效;现在学习的是第12页，共25页4.3 多项式近似法多项式近似法二次插值法二次插值法 （一）（一）基本思想基本思想对形式复杂的对形式复杂的函数，数学运函数，数学运算时不方便算时不方便找一个近似的、解析找一个近似的、解析性能好、便于计算的性能好、便于计算的简单函数来代替。简单函数来代替。用近似函数的极用近似函数的极小点作为原函数小点作为原函数极小点的近似极小点的近似复杂函数复杂函数 f(x)极小点极小点x*简单函数简单函数P(x)极小点极小点x*函数近似，函数近似，最优点也
14、应近似最优点也应近似一次多项式一次多项式二次多项式二次多项式三次多项式三次多项式?如何构造符合要求的多项式如何构造符合要求的多项式?现在学习的是第13页，共25页f(x)P2(x)（二）（二）二次插值多项式近似法（抛物线法）的基本原理二次插值多项式近似法（抛物线法）的基本原理设目标函数设目标函数 f(x)在三点在三点x1 x2 x3 上的函数值分别为上的函数值分别为f 1,f2,f3 x1x2x3相应的二次插值多项式为相应的二次插值多项式为 P2(x)=a0a1x+a2x2 令令P2(x)和和f(x)在三点上的函数值相等在三点上的函数值相等三个待定系数三个待定系数 P2(x1)=a0+a1x1
15、+a2x12 f1 P2(x2)=a0+a1x2+a2x22f2 P2(x3)=a0+a1x3+a2x32f3a0,a1,a2 P2(x)的平稳点是的平稳点是 P2(x)a1+2a2x=0 的解的解 所以只需求出所以只需求出a1,a2,最后得最后得现在学习的是第14页，共25页!迭代过程要点迭代过程要点！f(x)P2(x)x1x2x3x1x2x3x*x*x*若任意取若任意取x1 x2 x3 三个点，三个点，则求出的则求出的x*可能位于给定区间之外或误差太大可能位于给定区间之外或误差太大最初的三个点最初的三个点x1 x2 x3 应构成一个两边高，中间低的应构成一个两边高，中间低的“极小化架子极小
16、化架子”，即满足即满足f1f2，f3f2，且两个等号不同时成立，且两个等号不同时成立极小化架子极小化架子可由进退算法求得可由进退算法求得现在学习的是第15页，共25页在完成一次计算后，得到近似在完成一次计算后，得到近似x*，比较比较f(x*)与与f(x2)，以函数值较小的，以函数值较小的x为起点，缩短步长为起点，缩短步长近似近似x*进退算法进退算法构造构造“极小化架子极小化架子”x1 x2 x3比比较较f(x*)与与f(x2)，以以函函数数值值较较小小的的小者小者x为中间点，加上左右两点为中间点，加上左右两点 然后进行搜索区间的收缩，再在新区间中然后进行搜索区间的收缩，再在新区间中重新构造三点
17、组成的重新构造三点组成的“极小化架子极小化架子”，有两种方法，有两种方法终止准则：终止准则：采用目标函数值的相对误差或绝对误差来判断采用目标函数值的相对误差或绝对误差来判断（PP91）现在学习的是第16页，共25页f(x)xx1x2 x3f(x)xx1x2 x4前进成功前进成功 x5极小化架子极小化架子 x1 x2 x3前进失败前进失败x1x2x3x4x5x6极小化架子极小化架子 x3 x2 x1后退后退h02h04h0h0h02h04h0（三）（三）进退算法（用于求进退算法（用于求“极小化架子极小化架子”或初始搜索区间）或初始搜索区间）现在学习的是第17页，共25页（四）（四）逐次二次插值近
18、似法的算法逐次二次插值近似法的算法初始点初始点x1，h0，精度，精度1，溢出下限，溢出下限2，步长缩短率，步长缩短率m进退算法搭进退算法搭“极小化架子极小化架子”x1x2x3,或或x3x2x1计算近似点计算近似点x*检验精度检验精度以以x2与与x*函数值小者为函数值小者为x1h=mh以以x2与与x*函函数数小小者者为为x1，加加左左右两点构成右两点构成“极小化架子极小化架子”现在学习的是第18页，共25页二次插值法的优点：二次插值法的优点：收敛速度较快，约为收敛速度较快，约为1.3阶阶缺点：缺点：对强扭曲或多峰的，收敛慢，甚至会失败，故要求函数具有较好对强扭曲或多峰的，收敛慢，甚至会失败，故要
19、求函数具有较好 的解析性能的解析性能（五）（五）二次插值法与黄金分割法的结合二次插值法与黄金分割法的结合 黄金分割法黄金分割法二次插值法二次插值法迭代收敛时迭代收敛时迭代不收敛时迭代不收敛时现在学习的是第19页，共25页4.4 要求计算导数的迭代法要求计算导数的迭代法 如目标函数如目标函数f(x)可导，可通过解可导，可通过解f(x)0求平稳点，进而求出极值点。求平稳点，进而求出极值点。对高度非线性函数，要用逐次逼近求平稳点对高度非线性函数，要用逐次逼近求平稳点 4.4.1 Newton-Raphson法法 要求目标函数要求目标函数f(x)在搜索区间内具有二阶连续导数，且已知在搜索区间内具有二阶
20、连续导数，且已知f(x)和和f”(x)的表达式的表达式（一）（一）基本思想基本思想 采用迭代法求采用迭代法求(x)=0的根的根 xk(x)xxk+1 xk+2(xk)=(xk)/(xk1xk)xK+1=xk(xk)/(xk)用于求用于求(x)f(x)0的根的根 xK+1=xkf(xk)/f”(xk)现在学习的是第20页，共25页例题例题4.4.1 用用Newton-Raphson法求解法求解 初始点取初始点取 x0=1。（迭代二次）。（迭代二次）解：解：f(x)的一阶和二阶导函数为的一阶和二阶导函数为 迭代公式为迭代公式为 xK+1=xkf(xk)/f”(xk)第一次迭代：第一次迭代：x0=1
21、,f(x0)12,f”(x0)36 x11(12)/361.33 第二次迭代：第二次迭代：x1=1.33,f(x1)3.73,f”(x1)17.6 x21.33(3.73)/17.61.54(本例精确解为本例精确解为 x*)现在学习的是第21页，共25页(二二)优缺点优缺点1、优点：收敛速度快；、优点：收敛速度快；在在f(x)=0的单根处，是二阶收敛；在的单根处，是二阶收敛；在f(x)=0的的 重根处，是线性收敛。重根处，是线性收敛。2、缺点：、缺点：需要求二阶导数，若用数值导数代替，由于舍入误差将影响收敛需要求二阶导数，若用数值导数代替，由于舍入误差将影响收敛 速度；速度；收敛性还依赖于初始
22、点及函数性质收敛性还依赖于初始点及函数性质f(x)x!通常在计算程序中规定最大迭代次数通常在计算程序中规定最大迭代次数K，当次数达到，当次数达到K还不能满足精度还不能满足精度时，时，则认为不收敛，可更换一个初始点再试。则认为不收敛，可更换一个初始点再试。现在学习的是第22页，共25页4.4.2 对分法对分法假设假设 f(x)是具有极小点的单峰函数，是具有极小点的单峰函数，则必存在区间则必存在区间a,b，使，使f(a)0。由由f(x)的连续性可知，必有的连续性可知，必有x*(a,b)，使，使f(x)=0f(x)xaba1b1a2b2优点：优点：总能找到最优点总能找到最优点缺点：缺点：要计算导数值
23、，收敛速度为一阶要计算导数值，收敛速度为一阶现在学习的是第23页，共25页4.4.3 割线法割线法a f(x)x bx*基本思想：用割线代替基本思想：用割线代替Newton-Raphson法中的切线，法中的切线，并与区间消去法相结合。并与区间消去法相结合。c!新区间两端点的导数值异号新区间两端点的导数值异号4.4.4 三次插值多项式近似法三次插值多项式近似法基本思想与二次插值法类似：用四个已知值（如两个点函数值及其导数值）基本思想与二次插值法类似：用四个已知值（如两个点函数值及其导数值）构造一个三次多项式构造一个三次多项式P3(x)，用，用P3(x)的极小点近似目标函数的极小点的极小点近似目标
24、函数的极小点x*三次插值法的收敛速度比二次插值法要快。三次插值法的收敛速度比二次插值法要快。4.5 不精确一维搜索不精确一维搜索 (P99)现在学习的是第24页，共25页4.6 方法综述方法综述（1）如目标函数能求二阶导数：如目标函数能求二阶导数：用用Newton-Raphson法法 收敛快收敛快（2）如目标函数能求一阶导数如目标函数能求一阶导数：首先考虑用三次插值法，收敛较快：首先考虑用三次插值法，收敛较快 对分法收敛速度慢，但可靠对分法收敛速度慢，但可靠（3）只需计算函数值的方法只需计算函数值的方法：首先考虑用二次插值法首先考虑用二次插值法,收敛快收敛快 黄金分割法收敛速度较慢，但可靠黄金分割法收敛速度较慢，但可靠 作业：作业：P451 3（后退时采用（后退时采用h=0.25h）P451 4 P451 8现在学习的是第25页，共25页