工程最优化第四章

工程最优化第四章第一页，共二十五页，2022年，8月28日学习的重要性：1、工程实践中有时需要直接使用；2、多变量最优化的基础，迭代中经常要用到。方法分类：1、直接法：迭代过程中只需要计算函数值2、间接法或微分法：迭代过程中还需要计算目标函数的导数第二页，共二十五页，2022年，8月28日f(x)xab§4.1搜索区间的确定

常用的一维直接法有消去法和近似法两类。它们都是从某个初始搜索区间出发，利用单峰函数的消去性质，逐步缩小搜索区间，直到满足精度要求为止。§4.1.1单峰函数

定义：如果函数f(x)在区间[a,b]上只有一个极值点,则称f(x)为

[a,b]上的单峰函数。

连续单峰函数f(x)xab不连续单峰函数f(x)xab离散单峰函数f(x)xa

b非单峰函数第三页，共二十五页，2022年，8月28日单峰函数具有一个重要的消去性质定理：设f(x)是区间[a,b]上的一个单峰函数，x*∈[a,b]是其极小点，x1

和x2是[a,b]上的任意两点，且a<x1<x2<b，那么比较f(x1)与f(x2)的值后，可得出如下结论：f(x)xab(I)消去[a,x1]x*x1x2f(x)xab(II)消去[x2,b]x*x2x1(II)

若f(x1)<f(x2),x*∈[a,x2]在单峰函数的区间内，计算两个点的函数值，比较大小后，就能把搜索区间缩小。在已缩小的区间内，仍含有一个函数值，如再计算另一点的函数值，比较后就可进一步缩小搜索区间。（I）若f(x1)≥f(x2)，x*∈[x1,b]第四页，共二十五页，2022年，8月28日§4.1.2进退算法

?如何确定包含极小点在内的初始区间?（一）基本思想：由单峰函数的性质可知，函数值在极小点左边严格下降，在右边严格上升。f(x)xabx*x0x1x2从某个初始点出发，沿函数值下降的方向前进，直至发现函数值上升为止。由两边高，中间低的三点，可确定极小点所在的初始区间x3第五页，共二十五页，2022年，8月28日（二）算法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),aa+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）？？第六页，共二十五页，2022年，8月28日§4.2区间消去法－黄金分割法

消去法的思想：反复使用单峰函数的消去性质，不断缩小包含极小点的搜索区间，直到满足精度为止。

消去法的优点：只需计算函数值，通用性强

消去法的设计原则：（1）迭代公式简单；（2）消去效率高（一）、黄金分割

xabL

λL

(1－λ)L取“＋”，λ=0.618

第七页，共二十五页，2022年，8月28日（二）黄金分割法的基本思想

黄金分割重要的消去性质: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法第八页，共二十五页，2022年，8月28日（三）算法

开始b-x1<x2–a<给定a0,

b0,a=a0,b=

b0,=0.618034x2=a+(b-a),x1=a+b－x2f2=f(x2),f1=f(x1)f1f2是否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第九页，共二十五页，2022年，8月28日!!!在迭代过程中，四个点的顺序始终应该是a<x1<

x2<b但在计算第二个分割点时使用x1=a+b－x2

或x2=a+b－x1,由于舍入误差的影响，可能破坏a<x1<

x2<b这一顺序，导致混乱。迭代中必须采取一些措施：(1)终止限不要取得太小；(2)使用双精度运算；(3)经过若干次运算后，转到算法中的第3步，重新开始。第十页，共二十五页，2022年，8月28日开始b-x1<x2–a<给定a0,

b0,a=a0,b=

b0,=0.618034x2=a+(b-a),x1=a+b－x2f2=f(x2),f1=f(x1)f1f2是否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是第十一页，共二十五页，2022年，8月28日!!!在迭代过程中，四个点的顺序始终应该是a<x1<

x2<b但在计算第二个分割点时使用x1=a+b－x2

或x2=a+b－x1,由于舍入误差的影响，可能破坏a<x1<

x2<b这一顺序，导致混乱。迭代中必须采取一些措施：(1)终止限不要取得太小；(2)使用双精度运算；(3)经过若干次运算后，转到算法中的第3步，重新开始。例4.2.1PP89(四)黄金分割法的优缺点

2、缺点：对解析性能好的单峰函数，与后面要介绍的二次插值法、三次插值法及牛顿－拉夫森法等比较，计算量较大，收敛要慢。1、优点：算法简单，效率高，只计算函数值，对函数要求低，稳定性好，对多峰函数或强扭曲的，甚至不连续的，都有效;第十二页，共二十五页，2022年，8月28日§4.3多项式近似法－二次插值法（一）基本思想对形式复杂的函数，数学运算时不方便找一个近似的、解析性能好、便于计算的简单函数来代替。用近似函数的极小点作为原函数极小点的近似复杂函数f(x)极小点x**

简单函数P(x)极小点x*

函数近似，最优点也应近似一次多项式二次多项式三次多项式?如何构造符合要求的多项式?第十三页，共二十五页，2022年，8月28日f(x)P2(x)（二）二次插值多项式近似法（抛物线法）的基本原理设目标函数f(x)在三点x1<

x2<x3上的函数值分别为f1,f2,f3x1x2x3相应的二次插值多项式为P2(x)=a0＋a1x+a2x2

令P2(x)和f(x)在三点上的函数值相等三个待定系数

P2(x1)=a0+a1x1+a2x12＝f1P2(x2)=a0+a1x2+a2x22＝f2

P2(x3)=a0+a1x3+a2x32＝f3a0,a1,a2

P2(x)的平稳点是P2’(x)＝a1+2a2x=0的解所以只需求出a1,a2,最后得第十四页，共二十五页，2022年，8月28日!迭代过程要点

！f(x)P2(x)x1x2x3x1x2x3x**x*x**若任意取x1<

x2<x3

三个点，则求出的x*可能位于给定区间之外或误差太大最初的三个点x1<

x2<x3

应构成一个两边高，中间低的“极小化架子”，即满足f1≥f2，f3≥f2

，且两个等号不同时成立极小化架子可由进退算法求得第十五页，共二十五页，2022年，8月28日在完成一次计算后，得到近似x*，比较f(x*)与f(x2)，以函数值较小的x为起点，缩短步长近似x*

进退算法构造“极小化架子”x1<

x2<x3比较f(x*)与f(x2)，以函数值较小的小者x为中间点，加上左右两点然后进行搜索区间的收缩，再在新区间中重新构造三点组成的“极小化架子”，有两种方法终止准则：采用目标函数值的相对误差或绝对误差来判断（PP91）第十六页，共二十五页，2022年，8月28日f(x)

xx1x2

x3f(x)

xx1x2

x4前进成功

x5极小化架子x1

x2x3前进失败x1x2x3x4x5x6极小化架子x3

x2x1后退h02h04h0h0h02h04h0（三）进退算法（用于求“极小化架子”或初始搜索区间）第十七页，共二十五页，2022年，8月28日（四）逐次二次插值近似法的算法初始点x1，h0，精度ε1，溢出下限ε2，步长缩短率m进退算法搭“极小化架子”x1<x2<x3,或x3<x2<x1计算近似点x*检验精度以x2与x*函数值小者为x1h=mh以x2与x*函数小者为x1，加左右两点构成“极小化架子”第十八页，共二十五页，2022年，8月28日二次插值法的优点：收敛速度较快，约为1.3阶缺点：对强扭曲或多峰的，收敛慢，甚至会失败，故要求函数具有较好的解析性能

（五）二次插值法与黄金分割法的结合黄金分割法二次插值法迭代收敛时迭代不收敛时第十九页，共二十五页，2022年，8月28日§4.4要求计算导数的迭代法如目标函数f(x)可导，可通过解f’(x)＝0求平稳点，进而求出极值点。对高度非线性函数，要用逐次逼近求平稳点§4.4.1Newton-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)

第二十页，共二十五页，2022年，8月28日例题

用Newton-Raphson法求解

初始点取x0=1。（迭代二次）

解：f(x)的一阶和二阶导函数为迭代公式为xK+1=xk－f’(xk)/f”(xk)第一次迭代：x0=1,f’(x0)＝－12,f”(x0)＝36x1＝1－(－12)/36＝1.33第二次迭代：x1=1.33,f’(x1)＝－3.73,f”(x1)＝17.6x2＝1.33－(－3.73)/17.6＝1.54(本例精确解为x*)第二十一页，共二十五页，2022年，8月28日(二)优缺点1、优点：收敛速度快；在f’(x)=0的单根处，是二阶收敛；在f’(x)=0的重根处，是线性收敛。2、缺点：需要求二阶导数，若用数值导数代替，由于舍入误差将影响收敛速度；收敛性还依赖于初始点及函数性质f’(x)x!!!

通常在计算程序中规定最大迭代次数K，当次数达到K还不能满足精度时，则认为不收敛，可更换一个初始点再试。第二十二页，共二十五页，2022年，8月28日§4.4.2对分法假设f(x)是具有极小点的单峰函数，则必存在区间[a,b]，使f’(a)<0,f’(b)>0。由f’(x)的连续性可知，必有x*(a,b