共軛梯度法反演

1、共軛梯度法反演第1頁，共30頁，2022年，5月20日，7點11分，星期一主要內(nèi)容一、共軛梯度法簡介二、共軛梯度法原理基本原理2.1 問題的等價2.2 最速下降法2.3 共軛梯度法2.4 共軛梯度法共軛梯度法基本步驟三、共軛梯度法的優(yōu)缺點四、共軛梯度法的適用范圍五、共軛梯度法的改進(jìn)*2第2頁，共30頁，2022年，5月20日，7點11分，星期一從概率論觀點來看，非線性反演可以分為：統(tǒng)計方法和確定性方法。非線性反演統(tǒng)計方法蒙特卡洛方法模擬退火法遺傳算法確定性方法最速下降法牛頓法共軛梯度法變尺度法*3第3頁，共30頁，2022年，5月20日，7點11分，星期一一、共軛梯度法簡介確定性非線性反演方法

2、采用的反演策略是非線性問題的線性化,主要利用目標(biāo)函數(shù)的梯度信息,通過反復(fù)迭代,尋找反演的最優(yōu)解。雖然統(tǒng)計類反演的最大優(yōu)點是不完全依賴于初始猜測,理論上在反演過程中不會陷入局部極值。但是,這類方法的計算工作量巨大,效率很低。地球物理反演中涉及的模型參數(shù)成百上千,就目前的計算條件來說,統(tǒng)計類方法仍然不能滿足大規(guī)模地球物理反演的要求。*4第4頁，共30頁，2022年，5月20日，7點11分，星期一共軛梯度法一開始是由Schmidt于1908年引入梯度類方法計算效率高,特別是大約1951年，Hestenes和Stiefel經(jīng)過不斷的改進(jìn),并且和統(tǒng)計類反演方法結(jié)合形成了統(tǒng)計加迭代的組合反演方法,消除了依

3、賴于初始猜測的缺點,成了一種廣受歡迎的反演方案。一、共軛梯度法簡介*5第5頁，共30頁，2022年，5月20日，7點11分，星期一二、共軛梯度法原理基本原理通常對于一個反演問題，都是尋找目標(biāo)函數(shù)的極值以獲取對應(yīng)的極小值解作為反演結(jié)果。得目標(biāo)函數(shù)： (1)則2.1 問題的等價*6第6頁，共30頁，2022年，5月20日，7點11分，星期一2.2 最速下降法基本思想：任取一個迭代初始向量 x(0)，構(gòu)造迭代序列 x(0), x(1) , x(2), . . . ，使得 (x(0) (x(1) (x(2) . . .，且每一步都以 “最快的速度” 下降到 (x) 的極小值，求得對應(yīng)的x值即為反演的結(jié)

4、果。二、共軛梯度法反演的基本原理*7第7頁，共30頁，2022年，5月20日，7點11分，星期一具體做法： (2)該方向為： (3)2.2 最速下降法二、共軛梯度法反演的基本原理*8第8頁，共30頁，2022年，5月20日，7點11分，星期一我們假設(shè)在點X0 處開始沿負(fù)梯度方向 搜索,到達(dá)點X1 ,即為了使搜索能夠快速到達(dá)極值點選取使 達(dá)到最小,即 (4)或者: (5)2.2 最速下降法二、共軛梯度法反演的基本原理*9第9頁，共30頁，2022年，5月20日，7點11分，星期一2.2 最速下降法(5)式說明,如果的取值,使得(x1 ) 與r0正交,即前一次搜索的方向必與下一次的搜索方向正交,這

5、樣使得最速下降的搜索路徑成空間鋸齒形,且下降方向是一組交替平行的梯度方向(右圖) 。這啟示我們,雖然最速下降的搜索過程有成百上千次,但實際上只需要一組n 個 彼此正交的梯度方向就可以搜索到極值解。最速下降法搜索路徑二、共軛梯度法反演的基本原理*10第10頁，共30頁，2022年，5月20日，7點11分，星期一2.3 共軛梯度法二、共軛梯度法反演的基本原理*11第11頁，共30頁，2022年，5月20日，7點11分，星期一共軛向量的構(gòu)造設(shè)有一組n 維彼此關(guān)于nn 的正定對稱矩陣A共軛的向量 ，能夠使我們分別沿著這n個共軛向量所指的方向各搜索一次,就可以達(dá)到極值點 。設(shè)有一組線性無關(guān)的向量 ,可以

6、通過對它們的線性組合構(gòu)造出一組n個彼此共軛的向量。2.3 共軛梯度法二、共軛梯度法反演的基本原理*12第12頁，共30頁，2022年，5月20日，7點11分，星期一共軛向量的構(gòu)造 (6) (7) (8)2.3 共軛梯度法二、共軛梯度法反演的基本原理*13第13頁，共30頁，2022年，5月20日，7點11分，星期一2.4 共軛梯度法共軛梯度法基本步驟二、共軛梯度法反演的基本原理*14第14頁，共30頁，2022年，5月20日，7點11分，星期一2.4 共軛梯度法共軛梯度法基本步驟二、共軛梯度法反演的基本原理(9)(10)*15第15頁，共30頁，2022年，5月20日，7點11分，星期一 (1

7、1) (12)2.4 共軛梯度法共軛梯度法基本步驟二、共軛梯度法反演的基本原理*16第16頁，共30頁，2022年，5月20日，7點11分，星期一優(yōu)點三、共軛梯度法的優(yōu)缺點*17第17頁，共30頁，2022年，5月20日，7點11分，星期一計算效率比較最速下降法共軛梯度法三、共軛梯度法的優(yōu)缺點*18第18頁，共30頁，2022年，5月20日，7點11分，星期一局限性三、共軛梯度法的優(yōu)缺點*19第19頁，共30頁，2022年，5月20日，7點11分，星期一P1全局極小值P2局部極小值三、共軛梯度法優(yōu)缺點局限性*20第20頁，共30頁，2022年，5月20日，7點11分，星期一三、共軛梯度法的優(yōu)缺

8、點局 限 性初始猜測反演結(jié)果目標(biāo)函數(shù)值(2,-1)(3.0，0.0)0.6011(-2,-1)(-3.0,0.0)0.7606(-1.5,0)(-0.0958,0)0.9932(4,-1)(3.0，0.0)0.6011 從理論上說，共軛梯度法近乎完美，但自問世以來的幾十年中，共軛梯度法仍然在不斷改進(jìn)中。在非線性反演中，共軛梯度法最大的局限性在于依賴于初始值，不能確保收斂到全局極小值。*21第21頁，共30頁，2022年，5月20日，7點11分，星期一最速下降法反映的目標(biāo)函數(shù)的一種局部性質(zhì),從局部看, 最速下降方向是目標(biāo)函數(shù)值下降最快的方向,選擇這樣的方向進(jìn)行搜索是有利的.但從全局來看,由于鋸齒

9、現(xiàn)象的影響, 即使向著極小點移近不太大的距離,也要經(jīng)歷不小的”彎路”,因此收斂速度大為減慢.最速下降法一般適用于計算過程的前期迭代,或者作為間插步驟.四、共軛梯度法的適用范圍*22第22頁，共30頁，2022年，5月20日，7點11分，星期一傳統(tǒng)的共軛梯度法在地球物理反演和最優(yōu)化等方面,得到了廣泛的應(yīng)用，但在非線性反演中，共軛梯度法在很大的程度上依賴于初始值的猜測，不能確保收斂到全局極小值，然而相對于其它的非線性反演方法,共軛梯度法效率高,計算穩(wěn)定,適用于大規(guī)模的地球物理反演問題。四、共軛梯度法的適用范圍*23第23頁，共30頁，2022年，5月20日，7點11分，星期一為了能夠使共軛梯度法收

10、斂到全局極小值，為此一些學(xué)者不斷探索，提出了兩種解決方案，一種是直接改進(jìn)共軛梯度算法本身以達(dá)到有條件全局收斂的目的；另一種是利用啟發(fā)式非線性反演具有全局搜索的能力，加上共軛梯度法的高效計算的混合算法。五、共軛梯度法的改進(jìn)*24第24頁，共30頁，2022年，5月20日，7點11分，星期一五、共軛梯度法的改進(jìn)該方法采用非啟發(fā)式反演方法, 快速收斂到某一極值; 再用啟發(fā)式反演方法跳出局部極值; 然后使用非啟發(fā)式反演方法收斂到另一局部極值, 反復(fù)進(jìn)行此過程; 并在解空間范圍內(nèi)搜索, 保留所有的局部極值, 最終確定最優(yōu)解。它繼承了隨機爬山能夠全局尋優(yōu)、共軛梯度法計算速度快和精度高的優(yōu)點, 能快速搜索到

11、全局最優(yōu)解。4.1 隨機共軛梯度法*25第25頁，共30頁，2022年，5月20日，7點11分，星期一*26五、共軛梯度法的改進(jìn)4.1 隨機共軛梯度法模型修改模型參數(shù)計算目標(biāo)函數(shù)S(x)和SS0CG反演終止是否收斂是否是否第26頁，共30頁，2022年，5月20日，7點11分，星期一試驗證明, 這種方法是一種高效的反演算法, 特別適用于求解非線性、多極值的最優(yōu)化問題和地球物理反問題。4.1 隨機共軛梯度法五、共軛梯度法的改進(jìn)*27第27頁，共30頁，2022年，5月20日，7點11分，星期一在大規(guī)模的地球物理反演中,需要象隨機共軛梯度法這樣既計算效率高,又能保證全局收斂的算法。幸運的是,隨機共軛梯度法繼承了啟發(fā)式非線性反演的能夠并行化的優(yōu)點。合適的并行