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

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

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

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

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

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

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

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

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

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