部分可分最優(yōu)化問題的稀疏擬Newton法的收斂性質(zhì).pdf

1、擬Newton法是求解最優(yōu)化問題的一類十分有效的算法。該類算法的主要優(yōu)點有，在一定條件下算法具有全局收斂性和超線性收斂速度，并且無需計算目標(biāo)函數(shù)的二階導(dǎo)數(shù)。因而擬Newton法已成為求解中小規(guī)模最優(yōu)化問題的一類最受歡迎的算法。然而擬Newton法產(chǎn)生的矩陣通常稠密的。因此，該類算法難以直接用于求解大規(guī)模最優(yōu)化問題。為了使得擬Newton法能用于求解大規(guī)模最優(yōu)化問題，學(xué)者們提出了多種形式的稀疏擬Newton法。這些稀疏擬Newton法充分

2、利用目標(biāo)函數(shù)的Hessian矩陣的結(jié)構(gòu)和稀疏性，使得擬Newton矩陣具有與目標(biāo)函數(shù)的Hessian陣相同或相似的稀疏結(jié)構(gòu)。從而可用于求解大規(guī)模最優(yōu)化問題。
　　 迄今為止，關(guān)于稀疏擬Newton法的研究主要集中于關(guān)于算法的局部收斂性方面，并已取得許多重要成果。關(guān)于稀疏擬Newton法的全局收斂性研究尚不多見。本文主要研究具有部分可分結(jié)構(gòu)的最優(yōu)化問題的稀疏擬Newton法。側(cè)重于BFGS和DFP擬Newton法的研究。該算法能保

3、證擬Newton矩陣具有與目標(biāo)函數(shù)的Hessian陣相同的稀疏性。算法產(chǎn)生的方向是目標(biāo)函數(shù)的下降方向。在一定的條件下，證明算法DFP算法局部超線性收斂性和CBFGS算法用于求解非凸函數(shù)極小化問題時具有全局收斂性和超線性收斂性。而且，單位步長最終可以取得，研究的問題包括目標(biāo)函數(shù)的Hessian矩陣為三對角矩陣和五對角矩陣這兩類特殊問題。還進行了數(shù)值試驗.結(jié)果表明本文提出的部分可分稀疏擬Newton法明顯優(yōu)于通常BFGS算法和某些稀疏BFG