第三章-非線性規(guī)劃無約束問題的最優(yōu)化方法課件

研究生課程《工程數(shù)學(xué)》之“最優(yōu)化方法”第三章無約束問題的最優(yōu)化方法能源與動力工程學(xué)院CollegeofEnergyandPowerEngineering

研究生課程《工程數(shù)學(xué)》之“最優(yōu)化方法”第三章無約束問題的第三章無約束問題的最優(yōu)化方法第一節(jié)變量輪換法第二節(jié)最速下降法第三節(jié)牛頓法第四節(jié)共軛梯度法第三章無約束問題的最優(yōu)化方法第一節(jié)變量輪換法本章主要介紹構(gòu)造無約束問題(多維)搜索方向的方法。這些方法大致可分為兩類：第一類：直接搜索方法。在搜索過程中，只用到目標(biāo)函數(shù)值，不需要計算其導(dǎo)數(shù)。例如，變量輪換法第二類：解析方法。在搜索過程中，要用到目標(biāo)函數(shù)的導(dǎo)數(shù)。例如最速下降法、牛頓法、共軛梯度法等。本章主要介紹構(gòu)造無約束問題(多維)搜索方向的方法。這些方法大

一、基本思想認(rèn)為最有利的搜索方向是各坐標(biāo)軸的方向，因此它輪流按各坐標(biāo)的方向搜索最優(yōu)點。過程：從某一個給定點出發(fā)，按第i個坐標(biāo)軸xi的方向搜索時，假定有n個變量，則只有xi在變化，其余(n-1)個變量都取給定點的值保持不變。這樣依次從x1到xn做了n次單變量的一維搜索，完成了變量輪換法的一次迭代。第一節(jié)變量輪換法

一、基本思想認(rèn)為最有利的搜索方向是各坐標(biāo)軸的方向，因此它輪

二、算法步驟設(shè)問題為記即ei為第i個分量為1，其余分量為0的單位向量。第1步：給定初始點第2步：從x(1)出發(fā)，先沿第1個坐標(biāo)軸方向e1進(jìn)行一維搜索，記求得的最優(yōu)步長為l1，則可得到新的點x(2)：第一節(jié)變量輪換法

二、算法步驟設(shè)問題為記即ei為第i個分量為1，其余分量為0再從x(2)出發(fā)，先沿第2個坐標(biāo)軸方向e2進(jìn)行一維搜索，記求得的最優(yōu)步長為l2，則可得到新的點x(3)：……完成了變量輪換法的一次迭代第一節(jié)變量輪換法再從x(2)出發(fā)，先沿第2個坐標(biāo)軸方向e2進(jìn)行一維搜索，記求第3步：令x(1)=x(n+1)，返回第二步，再沿著各坐標(biāo)軸方向依次進(jìn)行一維搜索。直到最新點x(n+1)滿足給定的精度要求為止，輸出x(n+1)作為f(x)極小點的近似值。1.坐標(biāo)輪換法是每次搜索只允許一個變量變化，其余變量保持不變，即沿坐標(biāo)方向輪流進(jìn)行搜索的尋優(yōu)方法。它把多變量的優(yōu)化問題輪流地轉(zhuǎn)化成單變量的優(yōu)化問題；特點總結(jié)：2.算法的基本思想簡單，不需要進(jìn)行導(dǎo)數(shù)運算；3.搜索效率低，收斂速度慢，只有對那些具有特殊結(jié)構(gòu)的函數(shù)使用起來尚好。第一節(jié)變量輪換法第3步：令x(1)=x(n+1)，返回第二步，再沿著各坐第一節(jié)變量輪換法例題1用變量輪換法求解給定初始點當(dāng)時，停止迭代答案：第一節(jié)變量輪換法例題1第二節(jié)最速下降法解：從初始點出發(fā)，沿x1軸方向e1進(jìn)行一維搜索：第二節(jié)最速下降法解：從初始點出第二節(jié)最速下降法再從x(2)點出發(fā)，沿x2軸方向e2進(jìn)行一維搜索：第二節(jié)最速下降法再從x(2)點第二節(jié)最速下降法再從x(3)點出發(fā)，沿x3軸方向e3進(jìn)行一維搜索：第二節(jié)最速下降法再從x(3)點故即為極小點。f(x(4))=0第二節(jié)最速下降法因為，故以x(4)點作為新的x(1)，進(jìn)行新一輪迭代。故即為極小點。f(x(4))設(shè)問題為一、基本思想式中f(x)具有一階連續(xù)偏導(dǎo)數(shù)，有極小點x*。若現(xiàn)已求得x*的第k次近似值x(k)，為了求得第k+1次近似值x(k+1)

，需選定方向p(k)。p(k)有什么特征呢？令，其中p(k)為某個下降方向?，F(xiàn)將f(x)在p(k)處展開：第二節(jié)最速下降法設(shè)問題為一、基本思想式中f(x)具有一階連續(xù)偏導(dǎo)數(shù)，有極小點略去無窮小，可以得到由于所以上式表明了搜索方向p(k)應(yīng)該滿足的條件：p(k)與x(k)點的梯度的點積小于0。第二節(jié)最速下降法略去無窮小，可以得到由于所以上式表明了搜索方向p(k)應(yīng)該滿因為當(dāng)搜索方向確定后，進(jìn)行下面的一維搜索：顯然，只有

時，目標(biāo)函數(shù)值f(x)在x(k)點附近下降最快，稱之為負(fù)梯度方向?？梢杂靡呀?jīng)學(xué)過的一維搜索方法進(jìn)行搜索，求得步長因子第二節(jié)最速下降法因為當(dāng)搜索方向確定后，進(jìn)行下面的一維搜索：顯然，只有也可以用求導(dǎo)的方法得出最優(yōu)步長因子第二節(jié)最速下降法也可以用求導(dǎo)的方法得出最優(yōu)步長因子第二節(jié)最二、最速下降法的算法步驟第2步：求梯度向量的范數(shù)第1步：給定初始點，及終止誤差，令k=0若，停止計算，輸出x(k)作為極小點的近似值，否則轉(zhuǎn)到下一步。第3步：構(gòu)造負(fù)梯度方向第4步：進(jìn)行一維搜索，求得最佳步長因子后，令然后再令k=k+1，轉(zhuǎn)到第二步。第二節(jié)最速下降法二、最速下降法的算法步驟第2步：求梯度向量的范數(shù)第1步：給定例題2用最速下降法求解下述函數(shù)的極小點。給定初始點答案：第二節(jié)最速下降法例題2用最速下降法求解下述函數(shù)的極小點。給定初始點答案：第解：求最佳步長l0第二節(jié)最速下降法解：求最佳步長l0第二節(jié)最速下降則：第二節(jié)最速下降法則：第二節(jié)最速下降法三、最速下降法的鋸齒現(xiàn)象第二節(jié)最速下降法三、最速下降法的鋸齒現(xiàn)象第二節(jié)最速下一、基本思想為了尋求收斂速度較快的求解無約束問題的優(yōu)化算法，可在每一輪迭代時用適當(dāng)?shù)亩魏瘮?shù)，如x(k)點的二階Taylor多項式來近似目標(biāo)函數(shù)，并用迭代點x(k)處，指向近似二次函數(shù)的極小點方向作為搜索方向p(k)。二、牛頓方向和牛頓方法設(shè)問題為式中f(x)在x(k)點處具有二階連續(xù)偏導(dǎo)數(shù)，且在點x(k)處的黑塞矩陣正定，x(k)是f(x)的一個極小點的第k輪估計值。第三節(jié)牛頓法一、基本思想二、牛頓方向和牛頓方法設(shè)問題為式中f(x)在x(第三節(jié)牛頓法令則1.求Q(x)的平穩(wěn)點：(數(shù))(向量)(矩陣)第三節(jié)牛頓法令則1.求Q(x)的平穩(wěn)點第三節(jié)牛頓法令，記x(k+1)為Q(x)的平穩(wěn)點將b,A的關(guān)系式代入上式，可以得到令—牛頓方向所以實際上，牛頓法已經(jīng)規(guī)定步長因子第三節(jié)牛頓法令第三節(jié)牛頓法2.牛頓法的算法步驟第2步：求梯度向量，并計算第1步：給定初始點，及終止誤差，令k=0若，停止迭代，輸出x(k)作為極小點的近似值，否則轉(zhuǎn)到下一步。第3步：構(gòu)造牛頓方向。根據(jù)確定第4步：根據(jù)計算x(k+1)作為下一輪迭代點，令k=k+1，轉(zhuǎn)第2步。第三節(jié)牛頓法2.牛頓法的算法步驟第2步第三節(jié)牛頓法例題3用牛頓法求解給定初始點答案：與最速下降法的對比：(1)牛頓法對于二次正定函數(shù)只需做1次迭代就得到最優(yōu)解，特別是在極小點附近，收斂性很好，收斂速度快；(2)最速下降法在極小點附近收斂速度很差。第三節(jié)牛頓法例題3用牛頓法求解給定初第三節(jié)牛頓法解：第三節(jié)牛頓法解：構(gòu)造牛頓方向：所以選取作為極小點。第三節(jié)牛頓法構(gòu)造牛頓方向：所以選取作為極小點。第三節(jié)牛第三節(jié)牛頓法與最速下降法進(jìn)行對比求最佳步長l0還需要經(jīng)過10次迭代才能滿足精度要求第三節(jié)牛頓法與最速下降法進(jìn)行對比求最佳第三節(jié)牛頓法3.牛頓法的缺點：牛頓法要求初始解離最優(yōu)解不遠(yuǎn)，若初始點選得離最優(yōu)解太遠(yuǎn)時，牛頓法并不能保證其收斂，甚至也不是下降方向。因此，常將牛頓法與最速下降法結(jié)合起來使用。前期使用最速下降法，當(dāng)?shù)揭欢ǔ潭群?，改用牛頓法，可得到較好的效果。4.修正牛頓法基本思想：保留了從牛頓法中選取牛頓方向作為搜索方向，摒棄其步長恒為1的做法，而用一維搜索確定最優(yōu)步長來構(gòu)造算法。第三節(jié)牛頓法3.牛頓法的缺點：4.第三節(jié)牛頓法5.修正牛頓法的算法步驟第4步：進(jìn)行一維搜索，求lk，使計算x(k+1)作為下一輪迭代點，令k=k+1，轉(zhuǎn)第2步。第1步：給定初始點，及終止誤差，令k=0第2步：求梯度向量，并計算若，停止迭代，輸出x(k)作為極小點的近似值，否則轉(zhuǎn)到下一步。第3步：構(gòu)造牛頓方向。根據(jù)確定第三節(jié)牛頓法5.修正牛頓法的算法步第三節(jié)牛頓法例題4用修正牛頓法求解給定初始點答案：第三節(jié)牛頓法例題4用修正牛頓法求解給第三節(jié)牛頓法解：第三節(jié)牛頓法解：第三節(jié)牛頓法構(gòu)造牛頓方向：從x(0)出發(fā)，沿牛頓方向做一維搜索，令步長變量為l，最優(yōu)步長為l0第三節(jié)牛頓法構(gòu)造牛頓方向：從x(0)出第三節(jié)牛頓法所以選取作為極小點。第三節(jié)牛頓法所以選取作為極小點。第三節(jié)牛頓法6.修正牛頓法的缺點：修正牛頓法雖然比牛頓法有所改進(jìn)，但也有不足之處：(1)要計算黑塞矩陣及其逆矩陣，工作量較大；(2)要求迭代點x(k)處的黑塞矩陣正定?？墒怯行┖瘮?shù)未必滿足上述條件，因而牛頓方向未必是下降的，也有一些函數(shù)的黑塞矩陣是不可逆的，因此不能確定后繼的迭代點，導(dǎo)致迭代工作無法進(jìn)行。第三節(jié)牛頓法6.修正牛頓法的缺點：第四節(jié)共軛梯度法一、基本思想：共軛梯度法是基于共軛方向的一種算法。針對目標(biāo)函數(shù)為二次函數(shù)的問題，其搜索方向是與二次函數(shù)系數(shù)矩陣相關(guān)的共軛方向。用這類方法求解n元二次正定函數(shù)的極小問題，最多進(jìn)行n次一維搜索。二、共軛的概念定義：設(shè)x，y是n維歐氏空間中兩個向量，即，若有，就稱x與y是兩個正交的向量。又設(shè)A是一個n階對稱正定矩陣，若有

，則稱向量x，y關(guān)于A共軛正交，簡稱關(guān)于A共軛。第四節(jié)共軛梯度法一、基本思想：第四節(jié)共軛梯度法例：向量x，y關(guān)于A共軛。向量x，y關(guān)于A共軛。但是，另外，向量(1,0)T與(0,1)T顯然是正交的，但是它們不是關(guān)于A共軛。而向量(1,1)T與(1,-1)T顯然是正交的，而且它們還關(guān)于A共軛。第四節(jié)共軛梯度法例：向量x，y第四節(jié)共軛梯度法三、共軛方向設(shè)一組非零向量，A為n階對稱正定矩陣，若有下式成立：。稱向量組關(guān)于A共軛，也稱它們?yōu)橐唤MA共軛方向，或稱為A的n個共軛方向。若A是n階單位矩陣時：則p(i)，p(j)是正交向量。設(shè)有二維二次函數(shù)其等值線為為以x0為中心的橢圓。第四節(jié)共軛梯度法三、共軛方向第四節(jié)共軛梯度法根據(jù)可知，x0是f(x)的極小點。設(shè)x1是某等值線上的一點，該等值線在點x1處的法向量為若記又設(shè)是該等值線在點x1處的一個切向量，則有切向量與法向量正交，即第四節(jié)共軛梯度法根據(jù)可知，x0第四節(jié)共軛梯度法所以，等值線上一點處的切向量與由該點指向極小點的向量關(guān)于A共軛。四、正定二次函數(shù)的共軛梯度法用不同方法產(chǎn)生關(guān)于A共軛的一組共軛方向組就得到不同的共軛方向法。用迭代點處的負(fù)梯度向量為基礎(chǔ)產(chǎn)生一組共軛方向的方法叫做共軛梯度法。因此，對于以上定義的正定二維二次函數(shù)，若依次沿著方向和進(jìn)行一維搜索，則經(jīng)過兩次迭代必可到達(dá)極小點。第四節(jié)共軛梯度法所以，等值線上第四節(jié)共軛梯度法考慮第1步：任意取定初始點x(0)，并取初始搜索方向p(0)為x(0)的負(fù)梯度方向。以x(0)為出發(fā)點沿p(0)方向進(jìn)行一維搜索：若則x(1)就是最優(yōu)解，否則繼續(xù)進(jìn)行迭代。第2步：以x(1)點處的負(fù)梯度方向與上一個搜索方向的組合來形成下一個搜索方向p(1)，令第四節(jié)共軛梯度法考慮第1步：任第四節(jié)共軛梯度法第3步：以x(1)點為出發(fā)點沿p(1)方向進(jìn)行最佳一維搜索：，為待定常數(shù)，使得p(1)與p(0)關(guān)于A共軛。第四節(jié)共軛梯度法第3步：以x(第四節(jié)共軛梯度法若則x(2)就是最優(yōu)解，否則繼續(xù)進(jìn)行迭代?！C上所述，對于正定n維二次函數(shù)，共軛梯度法的公式為第四節(jié)共軛梯度法若則x(2)第四節(jié)共軛梯度法(k=0,1,…(n-1))(k=0,1,…(n-2))Fletcher和Reeves