修正Broyden族擬牛頓算法及其應(yīng)用.pdf

1、最優(yōu)化問(wèn)題及其理論和算法來(lái)源于經(jīng)濟(jì)，管理，工程等許多重要領(lǐng)域，同時(shí)和計(jì)算數(shù)學(xué)中的微分方程數(shù)值解法，非線性方程組數(shù)值解法等分支有著密切的聯(lián)系和應(yīng)用.傳統(tǒng)的Broyden族擬牛頓算法因?yàn)槠淞己玫臄?shù)值效果和快速收斂速度已成為求解最優(yōu)化問(wèn)題頗受歡迎的一類(lèi)算法.自上世紀(jì)60年代以來(lái)，傳統(tǒng)的Broyden族擬牛頓算法的理論受到了廣泛的重視并且已經(jīng)取得了豐碩的成果.當(dāng)目標(biāo)函數(shù)是凸函數(shù)時(shí)，該類(lèi)算法的局部收斂性和全局收斂性理論已得到很好的解決.

2、當(dāng)目標(biāo)函數(shù)是非凸函數(shù)時(shí)，Dai構(gòu)造了一個(gè)反例說(shuō)明了使用非精確搜索的BFGS算法對(duì)非凸函數(shù)不是全局收斂的.來(lái)自工程中的許多實(shí)際問(wèn)題往往是是非凸的.研究求解非凸的優(yōu)化問(wèn)題的擬牛頓算法的全局收斂性具有現(xiàn)實(shí)的理論意義和實(shí)際意義. 本文首先研究求解非凸的無(wú)約束優(yōu)化問(wèn)題的修正BFGS算法以及Broyden族擬牛頓算法的全局收斂性及其超線性收斂性.在此基礎(chǔ)上，我們研究求解非線性最小二乘問(wèn)題的結(jié)構(gòu)化擬牛頓法及其收斂性理論.最后，我們研究求解變分

3、不等式問(wèn)題的模單調(diào)下降的BFGS算法及其全局收斂性分析. 首先，在第二章到第四章，我們研究求解下面無(wú)約束優(yōu)化問(wèn)題的算法：minf(x)，x∈Rn，其中f：Rn→R是一光滑函數(shù).最近，Zhang，Deng和Chen以及Wei，Yu和Yuan等分別提出了滿足新的擬牛頓方程的擬牛頓算法，希望提高傳統(tǒng)擬牛頓算法的效率.他們對(duì)所提出的擬牛頓算法的局部收斂性進(jìn)行了分析.但是，當(dāng)目標(biāo)函數(shù)f是非凸函數(shù)時(shí)，這些算法的全局收斂性尚不清楚.我們?cè)贚i

4、和Fukushima全局化MBFGS和CBFGS算法的基礎(chǔ)上，分別提出基于Zhang，Deng和Chen以及Wei，Yu和Yuan等的擬牛頓方程的修正的BFGS算法和保守修正的BFGS算法.在較弱的條件下，我們證明這兩種方法用于求解非凸函數(shù)的無(wú)約束優(yōu)化問(wèn)題時(shí)，具有全局收斂性及其超線性收斂性.進(jìn)而，在第四章，我們研究修正的Broyden族擬牛頓算法及其全局收斂性.我們證明無(wú)論是基于傳統(tǒng)的擬牛頓方程還是Zhang，Deng和Chen以及We

5、i，Yu和Yuan等的擬牛頓方程的修正的Broyden族擬牛頓算法在適當(dāng)?shù)臈l件下，不但是局部超線性收斂的，而且具有全局收斂性. 求解非線性最小二乘問(wèn)題的結(jié)構(gòu)化擬牛頓法的全局收斂性問(wèn)題是人們關(guān)注的研究難點(diǎn)課題.研究該問(wèn)題的主要困難在于結(jié)構(gòu)化擬牛頓法產(chǎn)生的矩陣不能保證對(duì)稱(chēng)正定性.本文第五章致力于該問(wèn)題的研究.我們?cè)趯?duì)Yabe和Takahashi及Yabe和Yamaki提出的分解結(jié)構(gòu)化擬牛頓算法進(jìn)行仔細(xì)分析的基礎(chǔ)上，結(jié)合第四章的思想，

6、提出了一種滿秩分解的結(jié)構(gòu)化的Broyden族算法.該算法的特點(diǎn)是，無(wú)論迭代點(diǎn)是否在解x*的附近，都能保證算法產(chǎn)生的迭代矩陣是正定的.我們證明，采用Wolfe線性搜索的這種結(jié)構(gòu)化Broyden族擬牛頓法具有全局收斂性和超線性收斂性.此外，利用該算法與Gauss-Newton算法雜交使用，我們證明雜交算法對(duì)零殘差問(wèn)題是二次收斂的. 在第六章，通過(guò)QR正交分解，我們對(duì)Yabe和Takahashi的結(jié)構(gòu)化分解形式的BFGS算法進(jìn)行改進(jìn).

7、改進(jìn)后的分解形式的結(jié)構(gòu)化BFGS算法總使得迭代矩陣是正定的.在適當(dāng)?shù)臈l件下，我們證明這種分解形式的結(jié)構(gòu)化BFGS算法的局部超線性收斂性. 第七章，我們研究求解對(duì)稱(chēng)變分不等式的KKT系統(tǒng)的具有單調(diào)下降性的BFGS算法.我們首先將對(duì)稱(chēng)變分不等式的KKT系統(tǒng)轉(zhuǎn)化為等價(jià)的非光滑方程組.然后考察用擬牛頓算法求解該非光滑方程組.我們對(duì)Li和Fukushima提出的非單調(diào)線性搜索加以改進(jìn)，在此基礎(chǔ)上構(gòu)造一個(gè)使方程組模函數(shù)單調(diào)遞減的BFGS算法