工程最优化第四章ppt课件.ppt

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

步缩小搜索区间，直到满足精度要求为止§§4.1.1 4.1.1 单峰函数单峰函数 定义：如果函数定义：如果函数f(x)f(x)在区间在区间[a,b][a,b]上只有一个极值点上只有一个极值点, , 则称则称f(x)f(x)为为 [a, b] [a, b]上的单峰函数上的单峰函数 连续单峰函数连续单峰函数f(x)xab不连续单峰函数不连续单峰函数f(x)xab离散单峰函数离散单峰函数f(x)xa b非单峰函数非单峰函数单峰函数具有一个重要的消去性质单峰函数具有一个重要的消去性质定理：设定理：设f(x)是区间是区间[a,b]上的一个单峰函数，上的一个单峰函数，x*∈∈[a,b]是其极是其极小点，小点， x1 和和x2是是[a, b]上的任意两点，且上的任意两点，且a

在已缩小的区间内，仍含有一个函数值，能把搜索区间缩小在已缩小的区间内，仍含有一个函数值，如再计算另一点的函数值，比较后就可进一步缩小搜索区间如再计算另一点的函数值，比较后就可进一步缩小搜索区间 I）） 若若f(x1)≥f(x2)，，x*∈∈[x1,b]§§4.1.2 4.1.2 进退算法进退算法 ? 如何确定包含极小点在内的初始区间如何确定包含极小点在内的初始区间 ?（一〕基本思想：（一〕基本思想：由单峰函数的性质可知，函数值在极小点左边严格下降，在右由单峰函数的性质可知，函数值在极小点左边严格下降，在右边严格上升边严格上升f(x)xabx*x0 x1x2从某个初始点出发，沿函数值下降的方向前进，直至发现函数从某个初始点出发，沿函数值下降的方向前进，直至发现函数值上升为止值上升为止由两边高，中间低的三点，可确定极小点所在的初始区间由两边高，中间低的三点，可确定极小点所在的初始区间x3（二〕算法（二〕算法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, 停止运算；否则将步长加倍，并重复上述运算停止运算；否则将步长加倍，并重复上述运算a+3hf(x) xaa+ha+7ha1b1a-ha-3ha-7ha1b1 则将步长改为－则将步长改为－h计算f(a－－h), 若若f(a－－h) ≥ f(a)，， 令令 a1=a－－h, b1=a+h, 停止运算；否则将步长加倍，继续后退停止运算；否则将步长加倍，继续后退三三) 几点说明几点说明 （（P87））？？？？§§4.2 4.2 区间消去法－黄金分割法区间消去法－黄金分割法 消去法的思想：反复使用单峰函数的消去性质，不断缩小包含消去法的思想：反复使用单峰函数的消去性质，不断缩小包含 极小点的搜索区间，直到满足精度为止极小点的搜索区间，直到满足精度为止 消去法的优点：只需计算函数值，通用性强消去法的优点：只需计算函数值，通用性强 消去法的设计原则：（消去法的设计原则：（1〕迭代公式简单；（〕迭代公式简单；（2〕消去效率高〕消去效率高 （一）、黄金分割（一）、黄金分割 xabL λL (1－λ)L取取 “ ＋＋”，，λ=0.61803398874189 （二〕黄金分割法的基本思想（二〕黄金分割法的基本思想 黄金分割重要的消去性质黄金分割重要的消去性质: x2abL λL (1－－λ)Lx1 λL (1－－λ)L设设x1 ，，x2 为为[a, b] 中对称的两个黄金中对称的两个黄金分割点分割点x1为为[a, x2]的黄金分割的黄金分割点点x2为为[x1, b]的黄金分割的黄金分割点点 在在进进行行区区间间消消去去时时，，不不管管是是消消去去[a, x1]，，还还是是消消去去[x2，，b]，，留留下下来来的的区区间间中中还还含含一一个个黄黄金金分分割割点点，，只只要要在在对对称称位位置置找找另另一一个个黄黄金金分分割割点点，，又又可可以进行下一次区间消去。

以进行下一次区间消去 每次消去后，新区间的长度约为原区间的每次消去后，新区间的长度约为原区间的0.618倍，经过倍，经过n次消去后，次消去后，保留下来的区间长度为保留下来的区间长度为0.618nL，需计算函数值的次数为，需计算函数值的次数为n+1 黄金分割比黄金分割比λ   0.618，所以此法也称为，所以此法也称为0.618法法 （三〕算法（三〕算法 开场开场b-x1 <  x2 –a< 给定给定a0 , b0 ,  a=a0 ,b= b0 ,  =0.618034x2 =a+ (b-a), x1 =a+b－－x2f2 =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, x2]x*∈∈[x1, b]x*=x1, f*=f1完毕完毕是是x*=x2, f*=f2是是abx2x1x1 ＋＋x2 = a＋＋b!!! 在迭代过程中，四个点的顺序始终应该是在迭代过程中，四个点的顺序始终应该是 a

迭代中必须采这一顺序，导致混乱迭代中必须采取一些措施：取一些措施：(1) 终止限终止限 不要取得太小；不要取得太小；(2) 使用双精度运算；使用双精度运算；(3) 经过若干次运算后，转到算法中的第经过若干次运算后，转到算法中的第3步，重新开始步，重新开始开场开场b-x1 <  x2 –a< 给定给定a0 , b0 ,  a=a0 ,b= b0 ,  =0.618034x2 =a+ (b-a), x1 =a+b－－x2f2 =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是是!!! 在迭代过程中，四个点的顺序始终应该是在迭代过程中，四个点的顺序始终应该是 a

迭代中必须采这一顺序，导致混乱迭代中必须采取一些措施：取一些措施：(1) 终止限终止限 不要取得太小；不要取得太小；(2) 使用双精度运算；使用双精度运算；(3) 经过若干次运算后，转到算法中的第经过若干次运算后，转到算法中的第3步，重新开始步，重新开始例例4.2.1 PP89(四四) 黄金分割法的优缺点黄金分割法的优缺点 2、缺点：对解析性能好的单峰函数，与后面要介绍的二次插值法、三次、缺点：对解析性能好的单峰函数，与后面要介绍的二次插值法、三次 插值法及牛顿－拉夫森法等比较，计算量较大，收敛要慢插值法及牛顿－拉夫森法等比较，计算量较大，收敛要慢1、优点：算法简单，效率高，只计算函数值，对函数要求低，稳定性好，、优点：算法简单，效率高，只计算函数值，对函数要求低，稳定性好， 对多峰函数或强扭曲的，甚至不连续的，都有效对多峰函数或强扭曲的，甚至不连续的，都有效;§§4.3 4.3 多项式近似法－二次插值法多项式近似法－二次插值法 （一〕基本思想（一〕基本思想对形式复杂的对形式复杂的函数，数学运函数，数学运算时不方便算时不方便找一个近似的、解析找一个近似的、解析性能好、便于计算的性能好、便于计算的简单函数来代替。

简单函数来代替用近似函数的极用近似函数的极小点作为原函数小点作为原函数极小点的近似极小点的近似复杂函数复杂函数 f(x) 极小点极小点x** 简单函数简单函数P(x) 极小点极小点x* 函数近似，函数近似，最优点也应近最优点也应近似似一次多项式一次多项式二次多项式二次多项式三次多项式三次多项式? 如何构造符合要求的多项式如何构造符合要求的多项式 ?f(x)P2(x)（二〕二次插值多项式近似法〔抛物线法〕的基本原理（二〕二次插值多项式近似法〔抛物线法〕的基本原理设目标函数设目标函数 f(x)在三点在三点x1 < x2

求平稳点，进而求出极值点对高度非线性函数，要用逐次逼近求平稳点对高度非线性函数，要用逐次逼近求平稳点 §4.4.1 Newton-Raphson§4.4.1 Newton-Raphson法法 要求目标函数要求目标函数f(x)在搜索区间内具有二阶连续导数，且已知在搜索区间内具有二阶连续导数，且已知f ’(x)和和f ”(x)的的表达式表达式 （一）（一） 基本思想基本思想 采用迭代法求采用迭代法求φ(x)=0的根的根 xk φ(x) xxk+1 xk+2 φ’(xk)=－－φ(xk)/(xk＋＋1－－xk) xK+1=xk－－φ(xk)/ φ’(xk) 用于求用于求φ(x) ＝＝f ’(x)＝＝0的根的根 xK+1=xk－－f ’(xk)/ f ”(xk) 例题例题4.4.1 用用Newton-Raphson法求解法求解 初始点取初始点取 x0 = 1迭代二次）迭代二次） 解：解：f(x) 的一阶和二阶导函数为的一阶和二阶导函数为 迭代公式为迭代公式为 xK+1=xk－－f ’(xk)/ f ”(xk) 第一次迭代：第一次迭代： x0 = 1, f ’(x0)＝－＝－12, f ”(x0)＝＝36 x1＝＝1－－(－－12)/36＝＝1.33 第二次迭代：第二次迭代： x1 = 1.33, f ’(x1)＝－＝－3.73, f ”(x1)＝＝17.6 x2＝＝1.33－－(－－3.73)/17.6＝＝1.54 (本例精确解为本例精确解为 x* )(二二) 优缺点优缺点1、优点：收敛速度快；在、优点：收敛速度快；在f ’(x)=0的单根处，是二阶收敛；在的单根处，是二阶收敛；在f ’(x)=0的的 重根处，是线性收敛。

重根处，是线性收敛2、缺点：需要求二阶导数，若用数值导数代替，由于舍入误差将影响收敛、缺点：需要求二阶导数，若用数值导数代替，由于舍入误差将影响收敛 速度；速度； 收敛性还依赖于初始点及函数性质收敛性还依赖于初始点及函数性质f ’(x) x!!! 通常在计算程序中规定最大迭代次数通常在计算程序中规定最大迭代次数K，当次数达到，当次数达到K还不能满还不能满足精度时，足精度时， 则认为不收敛，可更换一个初始点再试则认为不收敛，可更换一个初始点再试§§4.4.2 4.4.2 对分法对分法假设假设 f(x) 是具有极小点的单峰函数，是具有极小点的单峰函数，则必存在区间则必存在区间[a, b]，使，使f ’(a)<0, f ’(b)>0由由f ’(x)的连续性可知，必有的连续性可知，必有x* (a, b)，使，使f ’(x)=0f ’(x)xaba1b1a2b2优点：总能找到最优点优点：总能找到最优点缺点：要计算导数值，收敛速度为一阶缺点：要计算导数值，收敛速度为一阶§§4.4.3 4.4.3 割线法割线法a f ’(x)x bx*基本思想：用割线代替基本思想：用割线代替Newton-Raphson法中的法中的切线，并与区间消去法相切线，并与区间消去法相结合。

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