1、,4.6.5,牛頓法,擬牛頓法,&,x,1,x,2,0,Penalty method,實際化工過程數(shù)學(xué)模型：求解復(fù)雜、計算量大 數(shù)值算法實現(xiàn)模型求解：迭代形式逐漸逼近最優(yōu)解x*， 求解過程：在可行域范圍或非可行域內(nèi)按照一定策略搜索最優(yōu)值的問題 。 初始點 更新點 最優(yōu)解X* 判斷所得點是否足夠接近 ，滿足則停止搜索,系統(tǒng)思想,迭代法共同特點：對求解變量的數(shù)值進(jìn)行逐步改進(jìn)，使之從開始不能滿足方程的要求，逐漸逼近方程所要求的解，每一次迭代所提供的信息（表明待解變量的數(shù)值同方程的解尚有距離的信息），用來產(chǎn)生下一次改進(jìn)值，迭代方案有多種，這就形成了不同的迭代方法。,變量輪換 單純形法 最速下降法 共軛

2、梯度法 牛頓法 &擬牛頓法,系統(tǒng)思想,一.牛頓法,1.問題提出 最速下降法：當(dāng)前迭代點 Xk,迭代簡單，但容易產(chǎn)生鋸齒現(xiàn)象，使得收斂緩慢，即一階逼近函數(shù)得到的模型比較粗糙。 提高逼近階數(shù) 牛頓法：二階逼近函數(shù)算法，快速收斂,牛頓迭代,最速下降,圖4-12 從目標(biāo)函數(shù)值近似值的觀點 比較最速下降法和牛頓法,一、牛頓法,將f(xk+1)在x=xk處一階泰勒展開：,目標(biāo)函數(shù)趨于零,一.牛頓法,將f(xk+1)在x=xk處二階泰勒展開：,目標(biāo)函數(shù)趨于零,一.牛頓法, 一維搜索簡化公式,一. 牛頓法,推廣到多元函數(shù)情況，即得到求解多元函數(shù)極小的牛頓迭代算法：,一. 牛頓法,Newton迭代公式,其中,1

3、.牛頓法幾何解釋,幾何直觀解釋：最密切的二次曲線逼近,2.Newton算法,Step1: 給初始點x0,精度0,k=0 Step2: 計算 Step3: 由方程組 H(x k) x k = -h k 解出xk+1, 當(dāng)H k可逆時，xk+1=xk-Hk-1.hk Step4:,例1.,設(shè),解：,故, = (),故,所以,進(jìn)而得,因此所求的牛頓方向為,由, = (),例2：,用牛頓法求解：,解：, = (),3. 牛頓法優(yōu)缺點,優(yōu)點, ,(1) 要求函數(shù)二階可微.,缺點, , =( ),二. 阻尼牛頓法Newton法改進(jìn),這樣往往可以克服上述缺點.,針對缺點中的(2), 在求新迭代點時，不直接用

4、公式進(jìn)行迭代，而是以 作為搜索方向進(jìn)行一維搜索，求步長 ，使,1. 基本思想,2. 阻尼牛頓法算法,Step2:,計算,Step4:,令,轉(zhuǎn)Step2., = (),3. 收斂性定理,1.分析： Newton法 優(yōu)點：高收斂速度（二階收斂） 缺點：對初始點目標(biāo)函數(shù)要求高，計算量，存 儲量大（需要計算、存儲hessian矩陣及其逆矩陣） 擬牛頓法模擬牛頓法給出的一個“保優(yōu)去劣”的算法,考慮Newton迭代公式： 搜索方向為 進(jìn)行改進(jìn)：一、避免求逆矩陣，用 則上式變?yōu)?此時搜索方向為 步長因子為 二、更大的靈活性，一般化,這樣的H k存在？ 1、為保證 總是下降方向，要求每一個G k均稱為正定矩陣

5、 2、為易于計算，要求有簡單的迭代形式，最簡單的迭代關(guān)系為,擬牛頓條件,分析：Hk-1需滿足的條件，并利用此條件確定G k 由歸納法，若由H k可求Hk+1, 則在xk+1點，Taylor展開 想到,在確定擬牛頓方程式的Hk+1時，若矩陣Hk+1對稱，則需要待定（n+n2)/2個未知數(shù)，n個方程，所以擬牛頓方程一般有無窮個解，故由擬牛頓方程確定的一族算法，通常稱之為擬牛頓法,擬Newton算法,1、給定初始點x0,正定矩陣H0,精度0,k=0 2、計算搜索方向 3、令xk+1=xk+tk.sk,其中 tk為f(xk+tkSk)=min f(xk+tsk) 4、若 ，則xk+1為最優(yōu)解，否則轉(zhuǎn)步

6、驟5 5、 按照校正公式 Gk+1=Gk+Gk,計算GK+1使得Gk+1滿足擬牛頓條件或擬Newton方程：Gk+1*y k=dk 令k=k+1,轉(zhuǎn)步驟2,DFP算法,1、DFP算法提出：(1)Davidon (2)Fletcher&Powell (3)多變量無約束優(yōu)化 2、如何確定G(k)?秩2校正法,根據(jù)擬Newton條件：Gk+1yk=dk,我們有 滿足上述方程的解很多，可如下確定一組解 則我們可以取,即 由此得到Gk的DFP校正公式 性質(zhì)：H00 ,則可以推出Hk0 正交繼承性,DFP算法步驟,將擬Newton法第5步驟改為: 5、按DFP校正公式 計算Gk,k=k+1,轉(zhuǎn)步驟2,BF

7、GS算法,Summary 非線性問題規(guī)劃求解,變量輪換法 單純形法,最速下降法 共軛梯度法,牛頓法 擬牛頓法,無約束最優(yōu)化問題,有約束最優(yōu)化問題,單變量函數(shù)的優(yōu)化 一維搜索,多變量函數(shù)的優(yōu)化策略,系統(tǒng)思想,Summary,無約束多變量函數(shù)的優(yōu)化策略,1、選擇初始點x0 。當(dāng)然初始點離最小點越近越好。 2、確定搜索方向 Sk ，使目標(biāo)函數(shù)從 xk 沿此方向下降。 3、在xk 方向上進(jìn)行一維搜索。在由 xk 出發(fā)的射線 x=xk+kSk (k0)上選取步長 k ,使一元（ ）函數(shù) f(xk+kSk ) 在 =k處取最小值。它是一個單變量函數(shù)極小問題。由此得到新點 xk+1=xk+ k Sk (k0

8、) 4、檢驗xk+1 是否最優(yōu)解。,共同缺點在于有多重局部解存在時，不一定能找出全局最優(yōu)解,Summary,變量輪換法特點： 可靠性較高，屬于直接法，只需目標(biāo)函數(shù)值信息，不需要目標(biāo)函數(shù)導(dǎo)數(shù)。 程序簡單，易于掌握。但是搜索效率低，且越接近極值點，搜索速度越慢。,單純形法特點：是不需要復(fù)雜的導(dǎo)數(shù)運算，它朝最優(yōu)點的移動完全由上一個單純形的結(jié)果所定，計算機上使用時貯存少。但由于步長固定，故缺少加速的方法。,單純形：指多維空間的凸多邊形的頂點數(shù)比空間維數(shù)多，如正四面體,Summary,最速下降法特點： 前后兩步迭代的搜索方向相互正交，對f（x)的尺度太靈敏，收斂緩慢，容易在x空間上產(chǎn)生大量的擺動，可能產(chǎn)生鋸齒現(xiàn)象,共軛梯度法 特點： 增大了很少的計算量 結(jié)合了梯度向量的信息及前一次迭代的梯度向量信息，優(yōu)點在于僅僅需要在每部計算中存儲少量的信息，可應(yīng)用到大問題上,直接 搜索法方法簡單，但收斂速度一般比較慢，需要計算大量的函數(shù)值,牛頓法需要最少的迭代 缺點：有多重局部解存在時，牛頓法不一定能找出全局最優(yōu)解 2.需要解