共軛梯度法反演

共軛梯度法反演第一頁，共三十頁，2022年，8月28日主要內(nèi)容一、共軛梯度法簡介二、共軛梯度法原理基本原理2.1問題的等價(jià)2.2最速下降法2.3共軛梯度法2.4共軛梯度法共軛梯度法基本步驟三、共軛梯度法的優(yōu)缺點(diǎn)四、共軛梯度法的適用范圍

五、共軛梯度法的改進(jìn)

*2第二頁，共三十頁，2022年，8月28日從概率論觀點(diǎn)來看，非線性反演可以分為：統(tǒng)計(jì)方法和確定性方法。非線性反演統(tǒng)計(jì)方法蒙特卡洛方法模擬退火法遺傳算法……確定性方法最速下降法牛頓法共軛梯度法變尺度法……*3第三頁，共三十頁，2022年，8月28日一、共軛梯度法簡介確定性非線性反演方法采用的反演策略是非線性問題的線性化,主要利用目標(biāo)函數(shù)的梯度信息,通過反復(fù)迭代,尋找反演的最優(yōu)解。雖然統(tǒng)計(jì)類反演的最大優(yōu)點(diǎn)是不完全依賴于初始猜測,理論上在反演過程中不會(huì)陷入局部極值。但是,這類方法的計(jì)算工作量巨大,效率很低。地球物理反演中涉及的模型參數(shù)成百上千,就目前的計(jì)算條件來說,統(tǒng)計(jì)類方法仍然不能滿足大規(guī)模地球物理反演的要求。*4第四頁，共三十頁，2022年，8月28日共軛梯度法一開始是由Schmidt于1908年引入梯度類方法計(jì)算效率高,特別是大約1951年，Hestenes和Stiefel經(jīng)過不斷的改進(jìn),并且和統(tǒng)計(jì)類反演方法結(jié)合形成了統(tǒng)計(jì)加迭代的組合反演方法,消除了依賴于初始猜測的缺點(diǎn),成了一種廣受歡迎的反演方案。。一、共軛梯度法簡介*5第五頁，共三十頁，2022年，8月28日二、共軛梯度法原理基本原理通常對于一個(gè)反演問題，都是尋找目標(biāo)函數(shù)的極值以獲取對應(yīng)的極小值解作為反演結(jié)果。得目標(biāo)函數(shù)：(1)則2.1問題的等價(jià)*6第六頁，共三十頁，2022年，8月28日2.2最速下降法基本思想：

任取一個(gè)迭代初始向量x(0)，構(gòu)造迭代序列x(0),

x(1),x(2),

...，使得(x(0))>

(x(1))>

(x(2))>

...，且每一步都以“最快的速度”下降到(x)的極小值，求得對應(yīng)的x值即為反演的結(jié)果。二、共軛梯度法反演的基本原理*7第七頁，共三十頁，2022年，8月28日具體做法：(2)該方向?yàn)椋?3)2.2最速下降法二、共軛梯度法反演的基本原理*8第八頁，共三十頁，2022年，8月28日我們假設(shè)在點(diǎn)X0處開始沿負(fù)梯度方向搜索,到達(dá)點(diǎn)X1,即為了使搜索能夠快速到達(dá)極值點(diǎn)選取α使

達(dá)到最小,即

(4)或者:(5)2.2最速下降法二、共軛梯度法反演的基本原理*9第九頁，共三十頁，2022年，8月28日2.2最速下降法(5)式說明,如果α的取值,使得φ’(x1)與r0正交,即前一次搜索的方向必與下一次的搜索方向正交,這樣使得最速下降的搜索路徑成空間鋸齒形,且下降方向是一組交替平行的梯度方向(右圖)。這啟示我們,雖然最速下降的搜索過程有成百上千次,但實(shí)際上只需要一組n個(gè)

彼此正交的梯度方向就可以搜索到極值解。最速下降法搜索路徑二、共軛梯度法反演的基本原理*10第十頁，共三十頁，2022年，8月28日2.3共軛梯度法二、共軛梯度法反演的基本原理*11第十一頁，共三十頁，2022年，8月28日共軛向量的構(gòu)造設(shè)有一組n維彼此關(guān)于n×n的正定對稱矩陣A共軛的向量，能夠使我們分別沿著這n個(gè)共軛向量所指的方向各搜索一次,就可以達(dá)到極值點(diǎn)。設(shè)有一組線性無關(guān)的向量,可以通過對它們的線性組合構(gòu)造出一組n個(gè)彼此共軛的向量。2.3共軛梯度法二、共軛梯度法反演的基本原理*12第十二頁，共三十頁，2022年，8月28日共軛向量的構(gòu)造(6)

(7)

(8)2.3共軛梯度法二、共軛梯度法反演的基本原理*13第十三頁，共三十頁，2022年，8月28日2.4共軛梯度法共軛梯度法基本步驟二、共軛梯度法反演的基本原理*14第十四頁，共三十頁，2022年，8月28日2.4共軛梯度法共軛梯度法基本步驟二、共軛梯度法反演的基本原理(9)(10)*15第十五頁，共三十頁，2022年，8月28日(11)(12)2.4共軛梯度法共軛梯度法基本步驟二、共軛梯度法反演的基本原理*16第十六頁，共三十頁，2022年，8月28日優(yōu)

點(diǎn)三、共軛梯度法的優(yōu)缺點(diǎn)*17第十七頁，共三十頁，2022年，8月28日計(jì)算效率比較最速下降法共軛梯度法三、共軛梯度法的優(yōu)缺點(diǎn)*18第十八頁，共三十頁，2022年，8月28日局限性三、共軛梯度法的優(yōu)缺點(diǎn)*19第十九頁，共三十頁，2022年，8月28日P1全局極小值P2局部極小值三、共軛梯度法優(yōu)缺點(diǎn)局限性*20第二十頁，共三十頁，2022年，8月28日三、共軛梯度法的優(yōu)缺點(diǎn)

局限性初始猜測反演結(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第二十一頁，共三十頁，2022年，8月28日最速下降法反映的目標(biāo)函數(shù)的一種局部性質(zhì),從局部看,最速下降方向是目標(biāo)函數(shù)值下降最快的方向,選擇這樣的方向進(jìn)行搜索是有利的.但從全局來看,由于鋸齒現(xiàn)象的影響,即使向著極小點(diǎn)移近不太大的距離,也要經(jīng)歷不小的”彎路”,因此收斂速度大為減慢.最速下降法一般適用于計(jì)算過程的前期迭代,或者作為間插步驟.四、共軛梯度法的適用范圍

*22第二十二頁，共三十頁，2022年，8月28日傳統(tǒng)的共軛梯度法在地球物理反演和最優(yōu)化等方面,得到了廣泛的應(yīng)用，但在非線性反演中，共軛梯度法在很大的程度上依賴于初始值的猜測，不能確保收斂到全局極小值，然而相對于其它的非線性反演方法,共軛梯度法效率高,計(jì)算穩(wěn)定,適用于大規(guī)模的地球物理反演問題。四、共軛梯度法的適用范圍

*23第二十三頁，共三十頁，2022年，8月28日為了能夠使共軛梯度法收斂到全局極小值，為此一些學(xué)者不斷探索，提出了兩種解決方案，一種是直接改進(jìn)共軛梯度算法本身以達(dá)到有條件全局收斂的目的；另一種是利用啟發(fā)式非線性反演具有全局搜索的能力，加上共軛梯度法的高效計(jì)算的混合算法。五、共軛梯度法的改進(jìn)

*24第二十四頁，共三十頁，2022年，8月28日五、共軛梯度法的改進(jìn)該方法采用非啟發(fā)式反演方法,快速收斂到某一極值;再用啟發(fā)式反演方法跳出局部極值;然后使用非啟發(fā)式反演方法收斂到另一局部極值,反復(fù)進(jìn)行此過程;并在解空間范圍內(nèi)搜索,保留所有的局部極值,最終確定最優(yōu)解。它繼承了隨機(jī)爬山能夠全局尋優(yōu)、共軛梯度法計(jì)算速度快和精度高的優(yōu)點(diǎn),能快速搜索到全局最優(yōu)解。4.1隨機(jī)共軛梯度法*25第二十五頁，共三十頁，2022年，8月28日*26五、共軛梯度法的改進(jìn)4.1隨機(jī)共軛梯度法模型修改模型參數(shù)計(jì)算目標(biāo)函數(shù)S(x)和△S△S<0CG反演終止是否收斂是否是否第二十六頁，共三十頁，2022年，8月28日試驗(yàn)證明,這種方法是一種高效的反演算法,特別適用于求解非線性、多極值的最優(yōu)化問題和地球物理反問題。4.1隨機(jī)共軛梯度法五、共軛梯度法的改進(jìn)*27第二十七頁，共三十頁，2022年，8月28日在大規(guī)模的地球物理反演中