工程最優(yōu)化第四章

工程最優(yōu)化第四章第一頁(yè)，共二十五頁(yè)，2022年，8月28日學(xué)習(xí)的重要性：1、工程實(shí)踐中有時(shí)需要直接使用；2、多變量最優(yōu)化的基礎(chǔ)，迭代中經(jīng)常要用到。方法分類：1、直接法：迭代過(guò)程中只需要計(jì)算函數(shù)值2、間接法或微分法：迭代過(guò)程中還需要計(jì)算目標(biāo)函數(shù)的導(dǎo)數(shù)第二頁(yè)，共二十五頁(yè)，2022年，8月28日f(shuō)(x)xab§4.1搜索區(qū)間的確定

常用的一維直接法有消去法和近似法兩類。它們都是從某個(gè)初始搜索區(qū)間出發(fā)，利用單峰函數(shù)的消去性質(zhì)，逐步縮小搜索區(qū)間，直到滿足精度要求為止?！?.1.1單峰函數(shù)

定義：如果函數(shù)f(x)在區(qū)間[a,b]上只有一個(gè)極值點(diǎn),則稱f(x)為

[a,b]上的單峰函數(shù)。

連續(xù)單峰函數(shù)f(x)xab不連續(xù)單峰函數(shù)f(x)xab離散單峰函數(shù)f(x)xa

b非單峰函數(shù)第三頁(yè)，共二十五頁(yè)，2022年，8月28日單峰函數(shù)具有一個(gè)重要的消去性質(zhì)定理：設(shè)f(x)是區(qū)間[a,b]上的一個(gè)單峰函數(shù)，x*∈[a,b]是其極小點(diǎn)，x1

和x2是[a,b]上的任意兩點(diǎn)，且a<x1<x2<b，那么比較f(x1)與f(x2)的值后，可得出如下結(jié)論：f(x)xab(I)消去[a,x1]x*x1x2f(x)xab(II)消去[x2,b]x*x2x1(II)

若f(x1)<f(x2),x*∈[a,x2]在單峰函數(shù)的區(qū)間內(nèi)，計(jì)算兩個(gè)點(diǎn)的函數(shù)值，比較大小后，就能把搜索區(qū)間縮小。在已縮小的區(qū)間內(nèi)，仍含有一個(gè)函數(shù)值，如再計(jì)算另一點(diǎn)的函數(shù)值，比較后就可進(jìn)一步縮小搜索區(qū)間。（I）若f(x1)≥f(x2)，x*∈[x1,b]第四頁(yè)，共二十五頁(yè)，2022年，8月28日§4.1.2進(jìn)退算法

?如何確定包含極小點(diǎn)在內(nèi)的初始區(qū)間?（一）基本思想：由單峰函數(shù)的性質(zhì)可知，函數(shù)值在極小點(diǎn)左邊嚴(yán)格下降，在右邊嚴(yán)格上升。f(x)xabx*x0x1x2從某個(gè)初始點(diǎn)出發(fā)，沿函數(shù)值下降的方向前進(jìn)，直至發(fā)現(xiàn)函數(shù)值上升為止。由兩邊高，中間低的三點(diǎn)，可確定極小點(diǎn)所在的初始區(qū)間x3第五頁(yè)，共二十五頁(yè)，2022年，8月28日（二）算法1、選定初始點(diǎn)a和步長(zhǎng)h;f(x)

x2、計(jì)算并比較f(a)和f(a+h)；有前進(jìn)(1)和后退(2)兩種情況：(1)前進(jìn)運(yùn)算：若f(a)≥f(a+h),(2)后退運(yùn)算：若f(a)<f(a+h),aa+h則步長(zhǎng)加倍，計(jì)算f(a+3h)。若f(a+h)≤f(a+3h)，令a1=a,b1=a+3h,停止運(yùn)算；否則將步長(zhǎng)加倍，并重復(fù)上述運(yùn)算。a+3hf(x)

xaa+ha+7ha1b1a-ha-3ha-7ha1b1則將步長(zhǎng)改為－h(huán)。計(jì)算f(a－h(huán)),若f(a－h(huán))≥f(a)，令a1=a－h(huán),b1=a+h,停止運(yùn)算；否則將步長(zhǎng)加倍，繼續(xù)后退。(三)

幾點(diǎn)說(shuō)明（P87）？？第六頁(yè)，共二十五頁(yè)，2022年，8月28日§4.2區(qū)間消去法－黃金分割法

消去法的思想：反復(fù)使用單峰函數(shù)的消去性質(zhì)，不斷縮小包含極小點(diǎn)的搜索區(qū)間，直到滿足精度為止。

消去法的優(yōu)點(diǎn)：只需計(jì)算函數(shù)值，通用性強(qiáng)

消去法的設(shè)計(jì)原則：（1）迭代公式簡(jiǎn)單；（2）消去效率高（一）、黃金分割

xabL

λL

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

第七頁(yè)，共二十五頁(yè)，2022年，8月28日（二）黃金分割法的基本思想

黃金分割重要的消去性質(zhì):x2abL

λL

(1－λ)Lx1

λL

(1－λ)L設(shè)x1，x2為[a,b]中對(duì)稱的兩個(gè)黃金分割點(diǎn)x1為[a,x2]的黃金分割點(diǎn)x2為[x1,b]的黃金分割點(diǎn)

在進(jìn)行區(qū)間消去時(shí)，不管是消去[a,x1]，還是消去[x2，b]，留下來(lái)的區(qū)間中還含一個(gè)黃金分割點(diǎn)，只要在對(duì)稱位置找另一個(gè)黃金分割點(diǎn)，又可以進(jìn)行下一次區(qū)間消去。每次消去后，新區(qū)間的長(zhǎng)度約為原區(qū)間的0.618倍，經(jīng)過(guò)n次消去后，保留下來(lái)的區(qū)間長(zhǎng)度為0.618nL，需計(jì)算函數(shù)值的次數(shù)為n+1

黃金分割比λ0.618，所以此法也稱為0.618法第八頁(yè)，共二十五頁(yè)，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結(jié)束是x*=x2,f*=f2是abx2x1x1＋x2=a＋b第九頁(yè)，共二十五頁(yè)，2022年，8月28日!!!在迭代過(guò)程中，四個(gè)點(diǎn)的順序始終應(yīng)該是a<x1<

x2<b但在計(jì)算第二個(gè)分割點(diǎn)時(shí)使用x1=a+b－x2

或x2=a+b－x1,由于舍入誤差的影響，可能破壞a<x1<

x2<b這一順序，導(dǎo)致混亂。迭代中必須采取一些措施：(1)終止限不要取得太??；(2)使用雙精度運(yùn)算；(3)經(jīng)過(guò)若干次運(yùn)算后，轉(zhuǎn)到算法中的第3步，重新開始。第十頁(yè)，共二十五頁(yè)，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結(jié)束是x*=x2,f*=f2是第十一頁(yè)，共二十五頁(yè)，2022年，8月28日!!!在迭代過(guò)程中，四個(gè)點(diǎn)的順序始終應(yīng)該是a<x1<

x2<b但在計(jì)算第二個(gè)分割點(diǎn)時(shí)使用x1=a+b－x2

或x2=a+b－x1,由于舍入誤差的影響，可能破壞a<x1<

x2<b這一順序，導(dǎo)致混亂。迭代中必須采取一些措施：(1)終止限不要取得太??；(2)使用雙精度運(yùn)算；(3)經(jīng)過(guò)若干次運(yùn)算后，轉(zhuǎn)到算法中的第3步，重新開始。例4.2.1PP89(四)黃金分割法的優(yōu)缺點(diǎn)

2、缺點(diǎn)：對(duì)解析性能好的單峰函數(shù)，與后面要介紹的二次插值法、三次插值法及牛頓－拉夫森法等比較，計(jì)算量較大，收斂要慢。1、優(yōu)點(diǎn)：算法簡(jiǎn)單，效率高，只計(jì)算函數(shù)值，對(duì)函數(shù)要求低，穩(wěn)定性好，對(duì)多峰函數(shù)或強(qiáng)扭曲的，甚至不連續(xù)的，都有效;第十二頁(yè)，共二十五頁(yè)，2022年，8月28日§4.3多項(xiàng)式近似法－二次插值法（一）基本思想對(duì)形式復(fù)雜的函數(shù)，數(shù)學(xué)運(yùn)算時(shí)不方便找一個(gè)近似的、解析性能好、便于計(jì)算的簡(jiǎn)單函數(shù)來(lái)代替。用近似函數(shù)的極小點(diǎn)作為原函數(shù)極小點(diǎn)的近似復(fù)雜函數(shù)f(x)極小點(diǎn)x**

簡(jiǎn)單函數(shù)P(x)極小點(diǎn)x*

函數(shù)近似，最優(yōu)點(diǎn)也應(yīng)近似一次多項(xiàng)式二次多項(xiàng)式三次多項(xiàng)式?如何構(gòu)造符合要求的多項(xiàng)式?第十三頁(yè)，共二十五頁(yè)，2022年，8月28日f(shuō)(x)P2(x)（二）二次插值多項(xiàng)式近似法（拋物線法）的基本原理設(shè)目標(biāo)函數(shù)f(x)在三點(diǎn)x1<

x2<x3上的函數(shù)值分別為f1,f2,f3x1x2x3相應(yīng)的二次插值多項(xiàng)式為P2(x)=a0＋a1x+a2x2

令P2(x)和f(x)在三點(diǎn)上的函數(shù)值相等三個(gè)待定系數(shù)

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

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

P2(x)的平穩(wěn)點(diǎn)是P2’(x)＝a1+2a2x=0的解所以只需求出a1,a2,最后得第十四頁(yè)，共二十五頁(yè)，2022年，8月28日!迭代過(guò)程要點(diǎn)

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

x2<x3

三個(gè)點(diǎn)，則求出的x*可能位于給定區(qū)間之外或誤差太大最初的三個(gè)點(diǎn)x1<

x2<x3

應(yīng)構(gòu)成一個(gè)兩邊高，中間低的“極小化架子”，即滿足f1≥f2，f3≥f2

，且兩個(gè)等號(hào)不同時(shí)成立極小化架子可由進(jìn)退算法求得第十五頁(yè)，共二十五頁(yè)，2022年，8月28日在完成一次計(jì)算后，得到近似x*，比較f(x*)與f(x2)，以函數(shù)值較小的x為起點(diǎn)，縮短步長(zhǎng)近似x*

進(jìn)退算法構(gòu)造“極小化架子”x1<

x2<x3比較f(x*)與f(x2)，以函數(shù)值較小的小者x為中間點(diǎn)，加上左右兩點(diǎn)然后進(jìn)行搜索區(qū)間的收縮，再在新區(qū)間中重新構(gòu)造三點(diǎn)組成的“極小化架子”，有兩種方法終止準(zhǔn)則：采用目標(biāo)函數(shù)值的相對(duì)誤差或絕對(duì)誤差來(lái)判斷（PP91）第十六頁(yè)，共二十五頁(yè)，2022年，8月28日f(shuō)(x)

xx1x2

x3f(x)

xx1x2

x4前進(jìn)成功

x5極小化架子x1

x2x3前進(jìn)失敗x1x2x3x4x5x6極小化架子x3

x2x1后退h02h04h0h0h02h04h0（三）進(jìn)退算法（用于求“極小化架子”或初始搜索區(qū)間）第十七頁(yè)，共二十五頁(yè)，2022年，8月28日（四）逐次二次插值近似法的算法初始點(diǎn)x1，h0，精度ε1，溢出下限ε2，步長(zhǎng)縮短率m進(jìn)退算法搭“極小化架子”x1<x2<x3,或x3<x2<x1計(jì)算近似點(diǎn)x*檢驗(yàn)精度以x2與x*函數(shù)值小者為x1h=mh以x2與x*函數(shù)小者為x1，加左右兩點(diǎn)構(gòu)成“極小化架子”第十八頁(yè)，共二十五頁(yè)，2022年，8月28日二次插值法的優(yōu)點(diǎn)：收斂速度較快，約為1.3階缺點(diǎn)：對(duì)強(qiáng)扭曲或多峰的，收斂慢，甚至?xí)?，故要求函?shù)具有較好的解析性能

（五）二次插值法與黃金分割法的結(jié)合黃金分割法二次插值法迭代收斂時(shí)迭代不收斂時(shí)第十九頁(yè)，共二十五頁(yè)，2022年，8月28日§4.4要求計(jì)算導(dǎo)數(shù)的迭代法如目標(biāo)函數(shù)f(x)可導(dǎo)，可通過(guò)解f’(x)＝0求平穩(wěn)點(diǎn)，進(jìn)而求出極值點(diǎn)。對(duì)高度非線性函數(shù)，要用逐次逼近求平穩(wěn)點(diǎn)§4.4.1Newton-Raphson法

要求目標(biāo)函數(shù)f(x)在搜索區(qū)間內(nèi)具有二階連續(xù)導(dǎo)數(shù)，且已知f’(x)和f”(x)的表達(dá)式（一）基本思想

采用迭代法求φ(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)

第二十頁(yè)，共二十五頁(yè)，2022年，8月28日例題

用Newton-Raphson法求解

初始點(diǎn)取x0=1。（迭代二次）

解：f(x)的一階和二階導(dǎo)函數(shù)為迭代公式為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*)第二十一頁(yè)，共二十五頁(yè)，2022年，8月28日(二)優(yōu)缺點(diǎn)1、優(yōu)點(diǎn)：收斂速度快；在f’(x)=0的單根處，是二階收斂；在f’(x)=0的重根處，是線性收斂。2、缺點(diǎn)：需要求二階導(dǎo)數(shù)，若用數(shù)值導(dǎo)數(shù)代替，由于舍入誤差將影響收斂速度；收斂性還依賴于初始點(diǎn)及函數(shù)性質(zhì)f’(x)x!!!

通常在計(jì)算程序中規(guī)定最大迭代次數(shù)K，當(dāng)次數(shù)達(dá)到K還不能滿足精度時(shí)，則認(rèn)為不收斂，可更換一個(gè)初始點(diǎn)再試。第二十二頁(yè)，共二十五頁(yè)，2022年，8月28日§4.4.2對(duì)分法假設(shè)f(x)是具有極小點(diǎn)的單峰函數(shù)，則必存在區(qū)間[a,b]，使f’(a)<0,f’(b)>0。由f’(x)的連續(xù)性可知，必有x*(a,b