第四章多變量優(yōu)化計算的梯度方法

1、4.4.1 梯度法（最速下降法） 基本思想：函數(shù)的負梯度方向是函數(shù)值在該點下降最快的方向。利用負梯度作為搜索方向，故稱最速下降法或梯度法。 搜索方向s取該點的負梯度方向 (最速下降方向) ，使函數(shù)值在該點附近的范圍內(nèi)下降最快 。梯度法 為了使目標函數(shù)值沿搜索方向 能夠獲得最大的下降值，其步長因子 應(yīng)取一維搜索的最佳步長。即有步長因子 求解方法：解析法：根據(jù)極值點必要條件。黃金分割法牛頓法拋物線法最速下降法的搜索路徑相鄰兩個搜索方向互相垂直 根據(jù)一元函數(shù)極值的必要條件及復(fù)合函數(shù)求導(dǎo)公式得 在最速下降法中，相鄰兩個迭代點上的函數(shù)梯度相互垂直。搜索方向就是負梯度方向，因此相鄰兩個搜索方向互相垂直。形

2、成“之”字形的鋸齒現(xiàn)象，而且越接近極小點鋸齒越細。 圖 最速下降法的搜索路徑最速下降法圖 最速下降法的收斂過程沿負梯度方向進行一維搜索，有例求目標函數(shù) 的極小點。取初始點解：初始點處梯度：沿負梯度方向進行一維搜索，有為一維搜索最佳步長，應(yīng)滿足極值必要條件 例 求目標函數(shù) 的極小點。取初始點第一次迭代設(shè)計點位置和函數(shù)值 因此，迭代終止： 沿負梯度方向進行一維搜索，有為一維搜索最佳步長，應(yīng)滿足極值必要條件 例42 求目標函數(shù) 的極小點。解 取初始點則初始點處梯度：如何求？算出一維搜索最佳步長 第一次迭代設(shè)計點位置和函數(shù)值 繼續(xù)作下去，經(jīng)10次迭代后，得到最優(yōu)解 例 用梯度法求下面無約束優(yōu)化問題：例

3、 用梯度法求下面無約束優(yōu)化問題：例 用梯度法求無約束優(yōu)化問題：例 用梯度法求下面無約束優(yōu)化問題：例 用梯度法求下面無約束優(yōu)化問題：例 用梯度法求下面無約束優(yōu)化問題：梯度法的特點（1）理論明確，程序簡單，對初始點要求不嚴格。（2）對一般函數(shù)而言，梯度法的收斂速度并不快，因為最速下降方向僅僅是指某點的一個局部性質(zhì)。（3）梯度法相鄰兩次搜索方向的正交性，決定了迭代全過程的搜索路線呈鋸齒狀，遠快近慢。（4）梯度法的收斂速度與目標函數(shù)的性質(zhì)密切相關(guān)。對于等值線(面)為同心圓（球）的目標函數(shù)，一次搜索即可達到極小點。4.4.2 共軛梯度法共軛梯度法是共軛方向法中的一種，該方法中每一個共軛向量都是依賴于迭代

4、點處的負梯度而構(gòu)造出來。 從xk出發(fā)，沿負梯度方向作一維搜索:設(shè)與dk共軛的下一個方向dk+1由dk和點xk+1的負梯度的線形組合構(gòu)成，即：共軛條件：4.4.2 共軛梯度法則：解得：4.4.2 共軛梯度法令為函數(shù)的泰勒二次展開式則上兩式相減，并代入4.4.2 共軛梯度法將式與式兩邊相乘，并應(yīng)用共軛條件得：4.4.2 共軛梯度法因此4.4.2 共軛梯度法特點：一階求導(dǎo)、公式結(jié)構(gòu)簡單、所需存儲量少、收斂速度快；理論上對于二次型函數(shù)，最多經(jīng)過n步迭代必能達到最小值。課堂練習： 求目標函數(shù) 的極小點。 取初始點 用共軛梯度法解上題。 （只計算搜索兩次） 基本思想 ： 在xk鄰域內(nèi)用一個二次函數(shù) 來近似

5、代替原目標函數(shù)，并將 的極小點作為對目標函數(shù) 求優(yōu)的下一個迭代點 。經(jīng)多次迭代，使之逼近目標函數(shù) 的極小點。 牛頓法是求函數(shù)極值的最古老算法之一。 4.4.3 牛頓法和修正牛頓法設(shè) 為 的極小點 這就是多元函數(shù)求極值的牛頓法迭代公式。 牛頓法例44 求目標函數(shù) 的極小點。解 取初始點經(jīng)過一次迭代即求得極小點函數(shù)極小值 例 用牛頓法求解函數(shù)的極小值初始起始點1，1T。 對于正定二次函數(shù)，該方法可以直達極小點。因此對于非二次函數(shù)，如果采用上述牛頓迭代公式，有時會使函數(shù)值上升 。牛頓法的缺點修正牛頓法（阻尼牛頓法） 阻尼因子 ，沿牛頓方向進行一維搜索的最佳步長，由下式求得： 阻尼牛頓法程序框圖 （1

6、） 初始點應(yīng)選在X*附近，有一定難度； （2） 盡管每次迭代都不會是函數(shù)值上升，但不能保證每次下降 ； （3） 若迭代點的海賽矩陣為奇異，則無法求逆矩陣，不能構(gòu)造牛頓法方向； （4）不僅要計算梯度，還要求海賽矩陣及其逆矩陣，計算量和存儲量大。此外，對于二階不可微的F(X)也不適用。 特定條件下它具有收斂最快的優(yōu)點阻尼牛頓法方法特點一般迭代式：梯度法：牛頓法：阻尼牛頓法：修正牛頓法既保持了牛頓法收斂快的特性又放寬了對初始點選擇的要求，并能保證每次迭代都使目標函數(shù)值下降。在實際應(yīng)用中由于要求海森矩陣是非奇異的，另外求逆陣的計算工作量大，尤其是維數(shù)較高時，計算量與存貯量都隨n2增加。在A點由于函數(shù)接

7、近平方函數(shù)，因而由A點進行搜索，用牛頓方向更有效和更快；若從B點進行搜索，由于此點的目標函數(shù)不完全是二次函數(shù)，因此采用梯度方向進行搜索可以獲得更好的效果4.4.4 變尺度法1. 變尺度的基本思想： 發(fā)揚梯度法和牛頓法各自的優(yōu)點，避免兩者各自的缺點，將兩者結(jié)合起來，形成變尺度法。構(gòu)造變尺度矩陣的遞推公式：修正矩陣: DFP公式: 4.4.4.4 DFP變尺度法的特點和BFGS變尺度法 DFP變尺度法的特點： (1)DFP變尺度法不需要求Hessian矩陣及其逆陣，但需利用一階導(dǎo)數(shù)信息。 DFP法開始時是梯度法，所以從任一初始點通過梯度方向找到一個比較好的迭代點，這為以后的逐次迭代，創(chuàng)造了有利的條

8、件。(2)DFP法的收斂速度介于梯度法和牛頓法之間。 (3)計算實踐表明，一維搜索的精度對收斂速度影響不大。但如果精度太低，也有可能會使汁算失效，因此對一維搜索的精度要求一般不低于終止計算的精度。 DFP變尺度法雖收斂速度較快，但是它也存在數(shù)值計算穩(wěn)定性較差的問題，于是在70年代初又提出了另一種變尺度法BFGS變尺度法，這種方法與DFP方法的不同之處，在于近似矩陣的計算不同。（目前最成功的變尺度法） 由于BFGS變尺度法對一維最優(yōu)化搜索精度要求較低，因而，在迭代中H 矩陣不易退化為病態(tài)矩陣，從而保證了算法數(shù)值計算的穩(wěn)定性。牛頓法和變尺度法4.5 多變量無約束優(yōu)化計算方法小結(jié) 在梯度算法類中，像牛頓法和修正牛頓法需要用到目標函數(shù)的二階導(dǎo)數(shù)，稱這些算法為二階方法；算法中僅用到目標函數(shù)的一階導(dǎo)數(shù)，如梯度法、共扼梯度法、變尺度法，稱為一階方法；按此分類方法，各種非梯度算法又稱為零階方法。 非導(dǎo)數(shù)類算法，由于在計算中不需求目標函數(shù)的導(dǎo)數(shù)，所以這類算法適合于不易求導(dǎo)數(shù)的優(yōu)化問題，這給工程問題的計算帶來很多的方便。另外，計算較為穩(wěn)定，編程簡單和所需的存貯單元量少也是它的優(yōu)點。缺點是收斂速