修正Broyden族擬牛頓算法及其應用.pdf

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

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

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

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

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

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

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