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

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

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

3.收斂準則①點距準則②目標函數(shù)下降量準則③

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

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

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

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

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

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

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

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

③②前進運算

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

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

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

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

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

消去

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

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

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

（a）

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

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

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

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

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

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

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

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

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

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

2）求

3）終止條件判斷

若滿足條件，則得近似解停止計算，否則轉(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次迭代達最優(yōu)點2023/2/1424.3牛頓法1）

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

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

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

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

③計算插值多項式的極小點2023/2/1494.4.3二次插值法的迭代過程④終止判斷a.若便可得到極小點

b.若

必須縮小搜索區(qū)間根據(jù)區(qū)間消去原理，先比較和的大小，然后確定從四點中舍去得到新三點，然后再轉(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停（失敗）TFFTFT采用序列消去原理縮短探索區(qū)間2023/2/1544.4.5二次插值法的特點

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

牛頓法收斂快，但