一維無約束優(yōu)化

2023/2/111.約束極值存在的條件：(K—T條件)

2.迭代算法迭代格式：使得

3.收斂準(zhǔn)則①點(diǎn)距準(zhǔn)則②目標(biāo)函數(shù)下降量準(zhǔn)則③

梯度準(zhǔn)則④K-T條件準(zhǔn)則知識(shí)點(diǎn)回顧2023/2/12第4章一維無約束優(yōu)化方法2023/2/134.二次插值法（拋物線法）

1.確定初始區(qū)間的進(jìn)退法2.黃金分割法(0.618法）3.牛頓法掌握其基本思想、特點(diǎn)2023/2/14

工程實(shí)際中，所有設(shè)計(jì)問題幾乎都是約束問題。

約束優(yōu)化設(shè)計(jì)問題→無約束問題來求解。此外，有些約束優(yōu)化設(shè)計(jì)方法，也可以借助于無約束優(yōu)化方法的策略思想來構(gòu)造。

引言第4章一維無約束優(yōu)化方法2023/2/15引言數(shù)值迭代格式給定求一個(gè)變量一維函數(shù)的極值問題機(jī)械最優(yōu)化設(shè)計(jì)雖大都為多維問題，但在數(shù)值迭代計(jì)算中要進(jìn)行一維搜索，即把多維問題轉(zhuǎn)化為一維問題來處理，一維搜索是優(yōu)化方法的基礎(chǔ)。第4章一維無約束優(yōu)化方法2023/2/16一維搜索方法分兩步：（1）確定初始搜索區(qū)間；（2）求出該區(qū)間內(nèi)的最優(yōu)步長(zhǎng)因子。第4章一維無約束優(yōu)化方法2023/2/17一維優(yōu)化方法分為兩類：（1）直接法——按照某種規(guī)律取若干點(diǎn)計(jì)算其函數(shù)值，然后通過直接比較函數(shù)值的大小來確定最優(yōu)解，常用的有黃金分割法,Fibonaui（分?jǐn)?shù)法）（2）間接法——利用函數(shù)的一階導(dǎo)數(shù)、二階導(dǎo)數(shù)來求解，故又稱解析法，常用的有牛頓法和二次插值法等。第4章一維無約束優(yōu)化方法2023/2/184.1確定初始區(qū)間的進(jìn)退法探索區(qū)間的確定方法有外推法及進(jìn)退法，常用的是進(jìn)退法。2023/2/194.1確定初始區(qū)間的進(jìn)退法搜索區(qū)間內(nèi)函數(shù)具有單峰性，也就是在區(qū)間[a，b]中函數(shù)是凸函數(shù)，具有高—低—高的特性。在區(qū)間上具有唯一的極小值。即當(dāng)時(shí)，有2023/2/1104.1確定初始區(qū)間的進(jìn)退法4.1.1方法的建立給定初始點(diǎn)和初始步長(zhǎng)步驟：（1）令??計(jì)算，（2）比較、函數(shù)值大小。

2023/2/1114.1確定初始區(qū)間的進(jìn)退法4.1.1方法的建立前進(jìn)運(yùn)算a.前進(jìn)運(yùn)算：

方向正確，作前進(jìn)運(yùn)算。計(jì)算三點(diǎn)的函數(shù)值滿足高—低—高的特性若則搜索區(qū)間為

否則，將步長(zhǎng)再加倍，重復(fù)上述運(yùn)算，直至函數(shù)值滿足高—低—高的特性。2023/2/1124.1確定初始區(qū)間的進(jìn)退法4.1.1方法的建立b.后退運(yùn)算：方向不正確，作后退運(yùn)算，即反向搜索。否則，將步長(zhǎng)再加倍繼續(xù)后退，直至函數(shù)值滿足高—低—高的特性。若計(jì)算三點(diǎn)的函數(shù)值滿足高—低—高的特性搜索區(qū)間為2023/2/1134.1確定初始區(qū)間的進(jìn)退法4.1.2程序框圖①前進(jìn)運(yùn)算

③②前進(jìn)運(yùn)算

2023/2/1144.1確定初始區(qū)間的進(jìn)退法4.1.2程序框圖前進(jìn)運(yùn)算

和依次往右趕，始終比較和作代換，計(jì)算2023/2/1154.1確定初始區(qū)間的進(jìn)退法4.1.2程序框圖后退運(yùn)算

①②③2023/2/1164.1確定初始區(qū)間的進(jìn)退法4.1.2程序框圖后退運(yùn)算計(jì)算作代換無論前進(jìn)還是后退運(yùn)算，都是左邊的點(diǎn)為，右邊的點(diǎn)為和依次往左趕，2023/2/1174.2黃金分割法Fibonaui（分?jǐn)?shù)法）和黃金分割法都是應(yīng)用序列消去原理的直接搜索方法。2023/2/1184.2黃金分割法4.2.1序列消去原理基本思想：在搜索區(qū)間內(nèi)選取計(jì)算點(diǎn)并比較其函數(shù)值，消去部分區(qū)間，以縮短搜索區(qū)間。消去在縮短了的探索區(qū)間內(nèi)保留了一個(gè)點(diǎn)，再取一個(gè)新點(diǎn)，比較此兩點(diǎn)的函數(shù)值大小，進(jìn)一步將新區(qū)間縮短，直至區(qū)間長(zhǎng)度小于某一給定的精度ε，則認(rèn)為找到了極值點(diǎn)。探索區(qū)間

2023/2/1194.2黃金分割法4.2.1序列消去原理消去

探索區(qū)間在縮短的區(qū)間內(nèi)取兩個(gè)點(diǎn)，比較其函數(shù)值，才能進(jìn)一步縮短搜索區(qū)間，為了與前兩種情況一至，便簡(jiǎn)化迭代程序，將第（3）種情況和（1）、（2）種情況合并，只按以下兩種情況考慮：為縮短后的探索區(qū)間。為縮短后的探索區(qū)間。消去

消去

2023/2/1204.2.2黃金分割法的基本思想通過計(jì)算和比較單峰區(qū)間內(nèi)兩點(diǎn)的函數(shù)值，不斷舍棄單峰區(qū)間的左端或右端的一部分，使探索區(qū)間按等比例等速縮小，直至極小點(diǎn)所在區(qū)間縮小到某一給定的精度ε，而得到近似最優(yōu)解，又稱它為0.618法。2023/2/1214.2.2黃金分割法的基本思想黃金分割法在探索區(qū)間的插入點(diǎn)有以下規(guī)律：（1）首輪在區(qū)間內(nèi)插入的兩個(gè)點(diǎn)與區(qū)間兩端點(diǎn)的距離相等，即相距兩端點(diǎn)具有對(duì)稱性。2023/2/1224.2.2黃金分割法的基本思想黃金分割法在探索區(qū)間的插入點(diǎn)有以下規(guī)律：（2）在縮短后的區(qū)間內(nèi)插入一個(gè)點(diǎn)，新區(qū)間的三段和原區(qū)間的三段具有相同的比例分布。如果把區(qū)間長(zhǎng)度看作是1，則有：解上式得：最長(zhǎng)段與較長(zhǎng)段之比相等2023/2/1234.2.3黃金分割法的迭代過程①在初始區(qū)間取兩個(gè)試點(diǎn)

②計(jì)算函數(shù)值③比較

迭代過程2023/2/1244.2.3黃金分割法的迭代過程③比較求新區(qū)間增加一個(gè)新點(diǎn)

（a）

2023/2/1254.2.3黃金分割法的迭代過程③比較（b）求（b）新區(qū)間增加一個(gè)新點(diǎn)

④新區(qū)間小于給定的精度ε時(shí)，終止迭代，所求的最優(yōu)點(diǎn)

否則轉(zhuǎn)第3步繼續(xù)迭代。2023/2/1264.2.4程序框圖開始結(jié)束TTFF給定a,b,ε2023/2/1272023/2/1282023/2/1296次迭代達(dá)最優(yōu)點(diǎn)2023/2/130練習(xí)

1.試用黃金分割法求函數(shù)的最優(yōu)解。初始區(qū)間[a,b]=[1,7],精度ε=0.01.最優(yōu)解：2023/2/131重點(diǎn)內(nèi)容1、搜索區(qū)間內(nèi)函數(shù)應(yīng)具有什么性質(zhì)？2、黃金分割法的基本思想是什么？3、黃金分割法的區(qū)間縮短實(shí)質(zhì)上采用的是什么原理？4、黃金分割法首輪搜索區(qū)間插入點(diǎn)具有什么特點(diǎn)？2023/2/132知識(shí)點(diǎn)回顧1.用進(jìn)退法確定初始區(qū)間時(shí)，搜索區(qū)間內(nèi)函數(shù)具有什么性質(zhì)？2.用進(jìn)退法確定初始區(qū)間，直至函數(shù)滿足什么特性時(shí)停止搜索？

3.黃金分割法的基本思想是什么？4.黃金分割法中的0.618的含義是什么？本次課的內(nèi)容一維牛頓法（切線法）二次插值法（拋物線法）1、基本思想

2、迭代公式和迭代步驟3、程序框圖4、特點(diǎn)2023/2/1344.3一維牛頓法（1）牛頓法的基本思想

用二次函數(shù)逐點(diǎn)近似原目標(biāo)函數(shù)，以二次函數(shù)的極小點(diǎn)來近似原目標(biāo)函數(shù)的極小點(diǎn)，用切線代替弧線逐漸逼近函數(shù)的根值。2023/2/135（1）牛頓法的基本思想

當(dāng)目標(biāo)函數(shù)有一階連續(xù)導(dǎo)數(shù)，且二階導(dǎo)數(shù)大于零時(shí)，函數(shù)的極小值點(diǎn)應(yīng)滿足極值存在的必要條件，所以求函數(shù)的極小值點(diǎn)也就是求解方程的根。在曲線上作一系列切線，使之與軸的交點(diǎn)逐漸逼近方程的根。4.3一維牛頓法2023/2/136（2）牛頓法的迭代公式與軸的交點(diǎn)為推廣到k步得迭代公式過點(diǎn)的切線方程為

4.3一維牛頓法2023/2/137（2）牛頓法的迭代公式迭代公式也可由Taylor公式展開得到：

在點(diǎn)附近用二次函數(shù)來逼近原目標(biāo)函數(shù)，故在點(diǎn)用Taylor公式展開，保留到二次項(xiàng)。令4.3一維牛頓法2023/2/1384.3一維牛頓法（3）牛頓法的迭代步驟給定搜索區(qū)間，初始點(diǎn)，迭代精度ε，令1）計(jì)算

2）求

3）終止條件判斷

若滿足條件，則得近似解停止計(jì)算，否則轉(zhuǎn)步驟4）4）令轉(zhuǎn)步驟1）。自己列出程序框圖2023/2/139（4）牛頓法的程序框圖

給定x(0),a,b,εk=0TF結(jié)束開始4.3一維牛頓法2023/2/1402023/2/1412次迭代達(dá)最優(yōu)點(diǎn)2023/2/1424.3牛頓法1）

優(yōu)點(diǎn)是收斂速度快，2）缺點(diǎn)是需要計(jì)算函數(shù)的一階和二階導(dǎo)數(shù)，增加了每次迭代的工作量。如果用數(shù)值微分計(jì)算函數(shù)的二階導(dǎo)數(shù)，其舍入誤差將嚴(yán)重影響牛頓法的收斂速度，的值越小問題越嚴(yán)重。3）牛頓法要求初始點(diǎn)離極值點(diǎn)不太遠(yuǎn)，否則有可能使極小化序列發(fā)散或收斂到非極小點(diǎn)。（5）牛頓法的特點(diǎn)2023/2/1434.4二次插值法（拋物線法）4.4.1二次插值法基本思想利用目標(biāo)函數(shù)在三個(gè)點(diǎn)的信息:

構(gòu)造一個(gè)與目標(biāo)函數(shù)值相接近的插值多項(xiàng)式，用該多項(xiàng)式的最優(yōu)解作為原目標(biāo)函數(shù)的近似最優(yōu)解，隨著搜索區(qū)間的逐次縮短，多項(xiàng)式的最優(yōu)點(diǎn)與原函數(shù)最優(yōu)點(diǎn)的距離逐漸減小，直至滿足精度要求。2023/2/1444.4.2二次插值法的公式推導(dǎo)設(shè)函數(shù)極值點(diǎn)所在區(qū)間內(nèi)有三個(gè)點(diǎn)其函數(shù)值為滿足，即滿足高—低—高特性。構(gòu)造二次插值多項(xiàng)式多項(xiàng)式的最優(yōu)解（x2,f2)作為原目標(biāo)函數(shù)的近似最優(yōu)解2023/2/1454.4.2二次插值法的公式推導(dǎo)構(gòu)造二次插值多項(xiàng)式：（4-3）——待定系數(shù)對(duì)（4-3）式求導(dǎo)，令導(dǎo)數(shù)等于零，得插值多項(xiàng)式的極小點(diǎn)：極小點(diǎn)：2023/2/1464.4.2二次插值法的公式推導(dǎo)構(gòu)造二次插值多項(xiàng)式：（4-3）將三點(diǎn)的值代入（4-3）即可求待定系數(shù)（4-4）2023/2/1474.4.2二次插值法的公式推導(dǎo)由（4-4）可以求得（4-6）

（4-7）將代入得極小點(diǎn)（4-8）2023/2/1484.4.3二次插值法的迭代過程

①確定初始搜索區(qū)間給定初始插值點(diǎn)迭代精度ε。②計(jì)算

③計(jì)算插值多項(xiàng)式的極小點(diǎn)2023/2/1494.4.3二次插值法的迭代過程④終止判斷a.若便可得到極小點(diǎn)

b.若

必須縮小搜索區(qū)間根據(jù)區(qū)間消去原理，先比較和的大小，然后確定從四點(diǎn)中舍去得到新三點(diǎn)，然后再轉(zhuǎn)步驟③。2023/2/150

4.4.4二次插值法的程序框圖A=0停（失?。㏕FFTFT必須縮短搜索區(qū)間2023/2/151

4.4.4二次插值法的程序框圖求2023/2/152

4.4.4二次插值法的程序框圖求xm2023/2/153

4.4.4二次插值法的程序框圖A=0停（失?。㏕FFTFT采用序列消去原理縮短探索區(qū)間2023/2/1544.4.5二次插值法的特點(diǎn)

拋物線法充分利用了函數(shù)的性態(tài)。對(duì)于二次函數(shù)用二次插值法求解，在理論上一次迭代可達(dá)到最優(yōu)點(diǎn)。對(duì)于非二次函數(shù)，在極值點(diǎn)附近函數(shù)呈現(xiàn)二次性態(tài)，因而收斂速度也較快。4.4.6各種一維優(yōu)化方法的比較

牛頓法收斂快，但