部分可分非線性方程組與優(yōu)化問(wèn)題的稀疏擬牛頓法.pdf

1、擬牛頓法是求解非線性方程組和最優(yōu)化問(wèn)題頗受歡迎的一類算法.該類算法具有超線性收斂速度，而且，若采用適當(dāng)線性搜索或信賴域技術(shù)，算法可具有全局收斂性.然而，擬牛頓法產(chǎn)生的擬牛頓矩陣往往是稠密的，因此不能直接用于求解大規(guī)模問(wèn)題.
　　來(lái)自科學(xué)計(jì)算和工程等領(lǐng)域的許多實(shí)際問(wèn)題一般都具有一些特殊的稀疏結(jié)構(gòu).比如微分方程采用有限元法或者有限差分法離散化后得到的非線性方程組，其Jacobian矩陣具有一定的稀疏結(jié)構(gòu).很多無(wú)約束優(yōu)化問(wèn)題可寫(xiě)成若干個(gè)

2、分量函數(shù)的和，其中每個(gè)分量函數(shù)只跟少數(shù)幾個(gè)變量有關(guān).因此，根據(jù)問(wèn)題的稀疏特征或者目標(biāo)函數(shù)的特殊結(jié)構(gòu)，設(shè)計(jì)高效的稀疏擬牛頓算法，具有重要的理論意義和實(shí)際應(yīng)用價(jià)值，也是優(yōu)化界關(guān)注的一個(gè)重要課題，并取得了一系列重要成果.目前已提出了多種稀疏擬牛頓法，這些算法充分利用了問(wèn)題的稀疏特征，并且保留了傳統(tǒng)擬牛頓法的超線性收斂性等重要性質(zhì).稀疏擬牛頓法已成為求解大規(guī)模非線性方程組和最優(yōu)化問(wèn)題的一類重要算法.
　　迄今為止，關(guān)于稀疏擬牛頓法的研究主

3、要集中于對(duì)算法的局部收斂性質(zhì)的研究，對(duì)于算法的全局收斂性質(zhì)的研究工作很少.這是由于稀疏擬牛頓法產(chǎn)生的擬牛頓矩陣要保持問(wèn)題的稀疏結(jié)構(gòu)，使得傳統(tǒng)擬牛頓法的某些重要性質(zhì)如對(duì)稱正定性、最小變化性等發(fā)生了改變，從而大大增加了研究稀疏擬牛頓法的全局收斂性的難度.本文在對(duì)稀疏擬牛頓法的性質(zhì)進(jìn)行深入分析的基礎(chǔ)上，采用線性搜索技術(shù)，研究求解非線性方程組和最優(yōu)化問(wèn)題的一些重要的稀疏擬牛頓法的全局收斂性.
　　我們首先研究求解大規(guī)模非線性方程組的稀疏擬

4、牛頓法.Schubert方法是較早被提出的用于求解方程組的稀疏擬牛頓法，作為Broyden秩一修正公式的稀疏推廣，Schubert修正公式能夠精確保持方程組的Jacobian矩陣的稀疏結(jié)構(gòu).但在實(shí)際計(jì)算中，由于Schubert修正公式過(guò)于嚴(yán)格地保持矩陣的稀疏結(jié)構(gòu)，數(shù)值表現(xiàn)有時(shí)不如Broyden秩一方法好.在本文中我們重點(diǎn)關(guān)注部分可分離的非線性方程組，借助于分塊BFGS算法的思想，我們提出兩種分塊擬牛頓算法.當(dāng)非線性方程組的導(dǎo)數(shù)信息不可用

5、時(shí)，我們提出一種分塊Broyden秩一算法，算法中采用分塊Broyden秩一修正.該算法無(wú)需計(jì)算導(dǎo)數(shù)，且能夠近似保持Jacobian矩陣的稀疏結(jié)構(gòu).當(dāng)非線性方程組的導(dǎo)數(shù)信息可通過(guò)自動(dòng)微分問(wèn)接計(jì)算時(shí)，我們提出一種分塊伴隨Broyden算法，算法中采用分塊伴隨Broyden修正.該修正公式也可近似保持Jacobian矩陣的稀疏結(jié)構(gòu)，并保留了伴隨Broyden修正公式的線性不變性.我們采用一種無(wú)導(dǎo)數(shù)非單調(diào)線性搜索技術(shù)研究算法的全局收斂性，在適

6、當(dāng)條件下，建立了上述兩種稀疏擬牛頓算法的全局收斂性.我們還證明，經(jīng)過(guò)一定的迭代步后，單位步長(zhǎng)可以取到.此時(shí)，算法在方程組解的局部還原為單位步長(zhǎng)稀疏擬牛頓法，從而具有超線性收斂速度.我們還對(duì)算法進(jìn)行數(shù)值檢驗(yàn)，并將該兩種稀疏擬牛頓算法與Broyden秩一方法和伴隨Broyden方法進(jìn)行了比較.結(jié)果表明，稀疏算法在迭代次數(shù)，函數(shù)值計(jì)算次數(shù)和計(jì)算時(shí)間方面均有出色表現(xiàn).我們也將這兩種稀疏算法與Schubert方法進(jìn)行比較，數(shù)值結(jié)果進(jìn)一步驗(yàn)證了這兩

7、種稀疏擬牛頓算法的優(yōu)越性.
　　其次，針對(duì)目標(biāo)函數(shù)具有部分可分離結(jié)構(gòu)的無(wú)約束優(yōu)化問(wèn)題，我們提出一種稀疏的投影分塊PSB算法.算法針對(duì)目標(biāo)函數(shù)的Hessian矩陣的稀疏結(jié)構(gòu)，采用分塊PSB修正.由于簡(jiǎn)單的分塊PSB修正公式不能保正Hessian矩陣的近似矩陣的正定性，從而不能保證擬牛頓方向是目標(biāo)函數(shù)的下降方向.因此我們對(duì)擬牛頓方向進(jìn)行投影，提出一種投影的分塊PSB算法，該算法可以保證產(chǎn)生目標(biāo)函數(shù)的一個(gè)充分下降方向.在適當(dāng)條件下，我們

8、證明了采用Armijo或者Wolfe搜索的算法用于求解一致凸函數(shù)極小化問(wèn)題時(shí)具有全局收斂性和超線性收斂速度.此外我們還通過(guò)數(shù)值計(jì)算，將分塊PSB算法與已有的求解大規(guī)模最優(yōu)化問(wèn)題的著名的分塊BFGS算法以及有限內(nèi)存BFGS(L-BFGS)算法在30個(gè)測(cè)試問(wèn)題上進(jìn)行數(shù)值比較.結(jié)果表明，本文提出的分塊PSB算法在迭代次數(shù)，函數(shù)值計(jì)算次數(shù)，梯度值計(jì)算次數(shù)和計(jì)算時(shí)間方面均有較好的表現(xiàn).
　　最后，我們研究求解對(duì)稱非線性方程組的擬牛頓算法，基

9、于自動(dòng)微分技術(shù)，我們提出兩類擬牛頓算法.首先，類似于Powell對(duì)稱化技術(shù)，我們將伴隨Broyden修正公式對(duì)稱化，提出一種對(duì)稱伴隨Broyden修正.該修正公式保持了原伴隨Broyden修正公式的最小變化性質(zhì)和仿射不變性.此外，我們還提出一類新的伴隨秩二擬牛頓修正公式，該修正公式不僅具有和BFGS修正公式類似的正定性和最小變化性質(zhì)，而且能夠精確保證擬牛頓矩陣與方程組的Jacobian矩陣沿?cái)M牛頓方向一致.我們證明，在適當(dāng)條件下這兩種算