LM和BFGS算法的性能分析與比較

1、題 目LM和BFGS算法的性能分析與比較目錄摘要1Abstract2第一章 緒論31.1 研究背景31.2 國內(nèi)外研究現(xiàn)狀41.3 研究內(nèi)容51.4 論文結(jié)構(gòu)6第二章 數(shù)值優(yōu)化算法基礎(chǔ)72.1 LM算法72.1.1 非線性最小二乘問題72.1.2 牛頓法（Newton method）72.1.3 Jacobian矩陣82.1.4 LM算法原理92.1.5 LM算法流程102.2 BFGS算法102.2.1 擬牛頓法（Quasi-Newton method）102.2.1 BFGS算法原理112.2.2 BFGS算法流程112.3 Armijo搜索12第三章 基于LM算法與BFGS算法的優(yōu)化問題

2、求解133.1 Rosenbrock函數(shù)的極值求解133.2 不同函數(shù)的極值求解對比19第四章 基于LM算法的前向神經(jīng)網(wǎng)絡(luò)的學(xué)習(xí)254.1 前向神經(jīng)網(wǎng)絡(luò)254.2 基于LM算法的前向神經(jīng)網(wǎng)絡(luò)學(xué)習(xí)264.3 在模式分類中的應(yīng)用28結(jié)論34致謝35參考文獻(xiàn)36摘要數(shù)值優(yōu)化是機(jī)器學(xué)習(xí)的重要部分，不斷研究和改進(jìn)已有的優(yōu)化算法，使其更快更高效，是機(jī)器學(xué)習(xí)領(lǐng)域的一個(gè)重要研究方向。作為數(shù)值優(yōu)化算法中具有代表性的兩個(gè)二階算法，LM和BFGS算法各有優(yōu)缺點(diǎn)，對它們的性能進(jìn)行分析和比較給二階數(shù)值算法的改進(jìn)及更廣泛的應(yīng)用提供重要參考。本論文從LM和BFGS算法的數(shù)學(xué)基礎(chǔ)開始闡述，通過對比兩個(gè)算法求解多個(gè)函數(shù)極小值的

3、問題，我們發(fā)現(xiàn)LM算法和BFGS算法的差異并不大。大多數(shù)情況下LM算法能夠達(dá)到更小的誤差，但是迭代次數(shù)比BFGS算法稍多。對于等高線為橢圓的函數(shù)，LM算法的收斂速度通常比BFGS算法快，但是后期運(yùn)算的迭代次數(shù)比BFGS算法多；而其他情況下LM算法和BFGS算法的收斂速度差別不大。由于LM算法在大部分情況下的極值求解效率稍高，我們實(shí)現(xiàn)了基于LM算法在前向神經(jīng)網(wǎng)絡(luò)中的學(xué)習(xí)，并用于解決模式分類問題。實(shí)驗(yàn)結(jié)果表明基于LM算法的前向神經(jīng)網(wǎng)絡(luò)在垃圾郵件分類應(yīng)用中能取得90%以上的分類正確率。關(guān)鍵詞：數(shù)值優(yōu)化，LM算法，BFGS算法，前向神經(jīng)網(wǎng)絡(luò)AbstractNumerical optimization

4、is an important part of machine learning. The analysis study of existing optimization algorithms to make them faster and more efficient is an important research direction in the field of machine learning. As two popular second-order algorithms, the LM and BFGS algorithms have their own advantages an

5、d disadvantages. The analysis and comparison of their performance have great significance for the improvement of the second-order numerical algorithms and their wider application in engineering areas.This thesis starts from introducing the mathematical foundation of LM and BFGS algorithms. By compar

6、ing the performance of the two algorithms for finding the minima of different functions, we find that the LM and BFGS algorithms have similar performance for numerical optimization problems. In most cases of our experiments, the LM algorithm can achieve smaller error, but the number of iterations is

7、 slightly higher than that of the BFGS algorithm. For the functions with elliptical contours, the convergence speed of the LM algorithm is usually faster than that of the BFGS algorithm, but the iterations of later computation are much more than those of the BFGS algorithm. while in other cases,thei

8、r convergence speed is almost the same. Because of the higher efficiency of the LM algorithm in most cases, the LM algorithm is employed to train feedforward neural networks which are applied to deal with some pattern classification problem. The experimental results show that the feedforward neural

9、network trained by the LM algorithm can reach more than 90% classification accuracy in the applications of classify spam and none spam email.Keywords：Numerical optimization，LM algorithm，BFGS algorithm，F(xiàn)eedforward neural networks第一章 緒論1.1 研究背景優(yōu)化算法是用來求解問題的最優(yōu)解或近似最優(yōu)解的15。我們在工程領(lǐng)域遇到的許多問題都可以建模成最優(yōu)化模型來求解。大部分的

10、機(jī)器學(xué)習(xí)算法本質(zhì)都是建立優(yōu)化模型，將學(xué)習(xí)問題轉(zhuǎn)化為優(yōu)化問題，通過數(shù)值優(yōu)化算法對目標(biāo)函數(shù)進(jìn)行優(yōu)化，從而訓(xùn)練出有效的結(jié)果。近年來，人工智能迅速發(fā)展起來，為能完成更多更復(fù)雜的智能應(yīng)用，機(jī)器學(xué)習(xí)技術(shù)的發(fā)展備受期待。機(jī)器學(xué)習(xí)基于數(shù)據(jù)統(tǒng)計(jì)并嚴(yán)重依賴于數(shù)值優(yōu)化算法的效率，如今智能應(yīng)用中的計(jì)算量日益龐大，計(jì)算平臺越來越強(qiáng)大，人們對速度、精度以及效率的追求不斷提高。數(shù)值優(yōu)化作為機(jī)器學(xué)習(xí)的一個(gè)重要支柱，對優(yōu)化算法的改進(jìn)和研究成為機(jī)器學(xué)習(xí)領(lǐng)域的重要課題9,12。從最流行的梯度下降法（Gradient Descent，GD）、牛頓法（Newtons method）、擬牛頓法（Quasi-Newton method），

11、到目前一些啟發(fā)式算法如模擬退火算法（Simulated Annealing Algorithm，SAA）、粒子群優(yōu)化算法（Particle Swarm Optimization，PSO）、差分衍化算法（Differential Evolution，DE）、遺傳算法（Genetic Algorithm，GA）等。不同的算法都有各自的優(yōu)點(diǎn)和局限性，針對不同的問題，結(jié)合問題需求選擇適合的優(yōu)化算法將對最終結(jié)果產(chǎn)生很大影響。對各有優(yōu)勢和局限性的優(yōu)化算法性能進(jìn)行仔細(xì)分析比較，不僅能幫助那些正在為如何選擇合適的優(yōu)化算法而發(fā)愁的人們，而且能給那些正在進(jìn)行優(yōu)化算法改進(jìn)研究的人員們提供一些參考數(shù)據(jù)，從而設(shè)計(jì)出應(yīng)用

12、更廣泛的新算法，以解決更具挑戰(zhàn)性的機(jī)器學(xué)習(xí)問題。數(shù)值優(yōu)化算法可分為一階算法和二階算法，一階優(yōu)化算法如梯度下降法以及一些它的改進(jìn)算法是神經(jīng)網(wǎng)絡(luò)里很常用的算法15。一階優(yōu)化算法只需要計(jì)算一階偏導(dǎo)數(shù)，計(jì)算量少算法簡單，但有時(shí)候收斂速度很慢。如在目標(biāo)函數(shù)（代價(jià)函數(shù)）較為平坦的區(qū)域，梯度的變化十分小使收斂速度會很慢。還有在深度神經(jīng)網(wǎng)絡(luò)中網(wǎng)絡(luò)深度較深的情況下，其梯度可能消失而導(dǎo)致收斂速度緩慢對于這種情況進(jìn)行二階偏導(dǎo)尋優(yōu)效果可能會更好。二階的優(yōu)化算法，如傳統(tǒng)的牛頓算法是需要計(jì)算二階偏導(dǎo)的，這使得計(jì)算量比一階算法多，且復(fù)雜度和難度都升高。但是二階算法卻具有收斂速度快并且不容易陷入鞍點(diǎn)的優(yōu)點(diǎn)。對于本論文中所研究

13、的兩個(gè)算法：LM（LevenbergMarquardt algorithm）和BFGS（Broyden-Fletcher-Goldfarb-Shanno algorithm）算法都是改進(jìn)的二階算法，不需要直接計(jì)算二階偏導(dǎo)海森（Hessian）矩陣，而是計(jì)算擬海森矩陣或近似的海森矩陣，大大減小了計(jì)算復(fù)雜度，是目前較為受歡迎的兩個(gè)二階算法。其中LM算法通過引入阻尼系數(shù)正則化海森矩陣，不僅保證了海森矩陣正定可逆，并且避免在靠近鞍點(diǎn)的地方梯度向錯誤的方向移動10。而BFGS算法通過梯度迭代來近似海森矩陣的逆矩陣減少計(jì)算量13。對非線性優(yōu)化領(lǐng)域具有代表性的LM和BFGS算法性能進(jìn)行分析比較，將為今后優(yōu)化

14、算法的應(yīng)用、改進(jìn)和設(shè)計(jì)提供重要參考資料。1.2 國內(nèi)外研究現(xiàn)狀機(jī)器學(xué)習(xí)的主流是神經(jīng)網(wǎng)絡(luò)，為使得神經(jīng)網(wǎng)絡(luò)能夠有更多更廣泛的應(yīng)用，機(jī)器學(xué)習(xí)領(lǐng)域的學(xué)者們也在努力進(jìn)行優(yōu)化算法的改進(jìn)。李南星、盛益強(qiáng)、倪宏分別采用LM、Adam和GD算法訓(xùn)練MLP模型，對比分析MLP模型的測試集MSE，確定使用LM算法的MLP模型提出一種基于CT圖像準(zhǔn)確預(yù)測顱骨聲參數(shù)的方法1。Mohammad Mehdi Ebadzadeh和Armin Salimi-Badr提出了一種基于LM算法的相關(guān)模糊規(guī)則模糊神經(jīng)網(wǎng)絡(luò)模型（CFNN），用于逼近非線性函數(shù)，特別是輸入變量之間高相關(guān)性的模糊規(guī)則數(shù)量較少的函數(shù)。該算法已被成功應(yīng)用于靜態(tài)函

15、數(shù)逼近，時(shí)間序列預(yù)測，非線性動態(tài)系統(tǒng)辨識和現(xiàn)實(shí)世界復(fù)雜回歸問題等7個(gè)測試實(shí)例。根據(jù)測試觀察，它可以比其他過去的算法更好地逼近非線性函數(shù)，結(jié)構(gòu)更緊湊，模糊規(guī)則數(shù)更少2。權(quán)凌霄、郭海鑫、盛世偉、李雷提出一種使用遺傳算法和LM算法相結(jié)合的優(yōu)化算法，采用遺傳算法確定BP神經(jīng)網(wǎng)絡(luò)的最佳初始權(quán)值矩陣，應(yīng)用LM算法在局部解空間里訓(xùn)練BP神經(jīng)網(wǎng)絡(luò)尋求全局最優(yōu)解?？勺C明該方法解決了標(biāo)準(zhǔn)BP神經(jīng)網(wǎng)絡(luò)在故障診斷時(shí)存在的一些缺點(diǎn)，比如學(xué)習(xí)效率不高、收斂速度很慢、容易陷入局部極小值點(diǎn)以及對初始參數(shù)較為敏感等。此外該算法除了保留了BP神經(jīng)網(wǎng)絡(luò)的廣泛映射能力還提升了學(xué)習(xí)速度和精確搜索的能力。通過對MOOG D761-271

16、6A機(jī)械反饋伺服閥進(jìn)行故障診斷，進(jìn)一步說明了該方法具有實(shí)用性和高效性3。王良詣、姜禮杰、王勇針對曲柄轉(zhuǎn)角限定和未限定的平面四桿機(jī)構(gòu)軌跡綜合問題,將遺傳算法全局搜索快速收斂和BFGS算法局部快速收斂的優(yōu)越性，設(shè)計(jì)出一種結(jié)合了遺傳算法和BFGS算法的平面四桿機(jī)構(gòu)優(yōu)化算法。和其他啟發(fā)式智能算法運(yùn)用在一些實(shí)例上得出的優(yōu)化結(jié)果進(jìn)行對比，可證明關(guān)于曲柄轉(zhuǎn)角限定以及曲柄轉(zhuǎn)角未限定的平面四桿機(jī)構(gòu)的軌跡擬合問題中，這種結(jié)合遺傳算法和BFGS算法的新算法具有非常好的全局收斂性能4。 Neculai Andrei提出了用于無約束優(yōu)化問題的雙參數(shù)標(biāo)度BFGS算法。此方法中，在原有的BFGS修正公式的前兩項(xiàng)進(jìn)

17、行正參數(shù)縮放，而第三項(xiàng)進(jìn)行另一種正參數(shù)縮放。選擇這種參數(shù)調(diào)整是為了改進(jìn)BFGS修正的矩陣的特征值結(jié)構(gòu)。通過對縮放的BFGS矩陣的特征值進(jìn)行聚類來確定如何縮放BFGS修正公式的前兩個(gè)項(xiàng)的參數(shù)。另一方面，縮放第三項(xiàng)參數(shù)的確定是與共軛梯度方法的共軛條件最小化相結(jié)合得到的。忽略優(yōu)化目標(biāo)函數(shù)的凸性，使用非精確線性搜索法Wolfe搜索時(shí)，可證明雙參數(shù)標(biāo)度BFGS法的全局收斂性是很好的。使用80個(gè)無約束優(yōu)化測試函數(shù)和中等規(guī)模數(shù)量的變量，經(jīng)過實(shí)驗(yàn)初步證明，這種雙參數(shù)標(biāo)度BFGS方法比標(biāo)準(zhǔn)BFGS修正或其他一些縮放BFGS方法更有效5。1.3 研究內(nèi)容本課題從LM算法和BFGS算法最基礎(chǔ)的數(shù)學(xué)原理開始研究，然后

18、通過求解一些多維函數(shù)極值問題對這兩個(gè)優(yōu)化算法的性能進(jìn)行比較分析。為了進(jìn)行公平的比較，這兩個(gè)算法所采用的停止條件、尋優(yōu)起始點(diǎn)都是相同的。通過比較LM算法和BFGS算法在求解過程中的運(yùn)算復(fù)雜度、迭代次數(shù)、計(jì)算精度、運(yùn)算時(shí)間等，結(jié)合兩個(gè)算法的尋優(yōu)軌跡圖以及函數(shù)變化曲線圖分析出兩個(gè)算法在求解這類問題時(shí)的各自的優(yōu)點(diǎn)和局限性。通過比較結(jié)果，決定將LM算法運(yùn)用到實(shí)際應(yīng)用中。本論文最后設(shè)計(jì)實(shí)現(xiàn)了基于LM算法前向神經(jīng)網(wǎng)絡(luò)的學(xué)習(xí)。一個(gè)三層的前向神經(jīng)網(wǎng)絡(luò)理論上可以逼近閉區(qū)間上任意一個(gè)連續(xù)的函數(shù)，三層前向神經(jīng)網(wǎng)絡(luò)是常用的模型之一，而傳統(tǒng)的前向神經(jīng)網(wǎng)絡(luò)用的最多的是梯度下降法優(yōu)化目標(biāo)函數(shù)。這種算法收斂速度很慢，并易陷入局

19、部最優(yōu)解，而運(yùn)用LM算法訓(xùn)練的前向神經(jīng)網(wǎng)絡(luò)具有超線性收斂。從UCI上下載幾個(gè)數(shù)據(jù)集作為樣本和測試集，將其用來訓(xùn)練和測試運(yùn)用了LM算法前向神經(jīng)網(wǎng)絡(luò)。最后通過調(diào)整隱層神經(jīng)元數(shù)量對該算法性能做出分析。 1.4 論文結(jié)構(gòu) 本論文由五個(gè)部分組成，包括四個(gè)章節(jié)和一個(gè)總結(jié)。第一章是緒論部分，闡述了本課題的研究意義、現(xiàn)狀和內(nèi)容。第二章是優(yōu)化算法的基礎(chǔ)知識部分，介紹LM算法和BFGS算法的一些基礎(chǔ)數(shù)學(xué)原理、兩個(gè)算法的基本流程以及步長搜索算法的數(shù)學(xué)基礎(chǔ)算法流程。第三章是LM算法和BFGS算法求解優(yōu)化問題的實(shí)驗(yàn)結(jié)果和分析比較。第四章是介紹前向神經(jīng)網(wǎng)絡(luò)的基礎(chǔ)知識以及運(yùn)用LM算法的前向神經(jīng)網(wǎng)絡(luò)的的實(shí)際運(yùn)用。最后是總結(jié)，

20、通過實(shí)驗(yàn)得出的總結(jié)論，對LM算法和BFGS算法性能各自的優(yōu)缺點(diǎn)做出最終的比較和分析。第2章 數(shù)值優(yōu)化算法基礎(chǔ)2.1 LM算法LM算法是用來解決最小二乘問題最常用的方法，它結(jié)合了梯度下降法和高斯-牛頓法（Gauss-Newton method，G-N），當(dāng)實(shí)際值與理想值相差很多的時(shí)候，LM算法接近于梯度下降法，而當(dāng)實(shí)際值與理想值比較接近的時(shí)候，LM算法則表現(xiàn)得像高斯牛頓法。2.1.1 非線性最小二乘問題 非線性最小二乘問題作為無約束優(yōu)化問題中很重要的一個(gè)的應(yīng)用，其在實(shí)際應(yīng)用中的很多方面都有涉及。非線性最小二乘問題也被稱作無約束極小平方和函數(shù)17，其基本形式如下：( 2.1.1 ) ( 2.1.2

21、 ) 式中為自變量，S為目標(biāo)函數(shù)。當(dāng)訓(xùn)練神經(jīng)網(wǎng)絡(luò)模型時(shí)，為誤差函數(shù)（代價(jià)函數(shù)），為理想值，為實(shí)際值，S為誤差平方和，前面的系數(shù)只是為了方便后續(xù)計(jì)算并不影響整體思想，為神經(jīng)網(wǎng)絡(luò)中的權(quán)值或閾值，需要找到合適的 的值使得S的值最小。神經(jīng)網(wǎng)絡(luò)的優(yōu)化過程就是方差或均方差最小化的過程。2.1.2 牛頓法（Newton method） 前面提到的梯度下降法是根據(jù)一階泰勒級數(shù)展開式推導(dǎo)而來，而本節(jié)的牛頓法是忽略了高階無窮小的二階泰勒級數(shù)展開式推導(dǎo)得到，如下所示：( 2.1.3 )其中，為函數(shù)的梯度向量，為函數(shù)的二階偏導(dǎo)，即海森矩陣。牛頓法的關(guān)鍵就是要求出這個(gè)二次逼近的駐點(diǎn)，從而得到函數(shù)的極小值。所以得到必要條

22、件： ( 2.1.4 ) 可求得 為： ( 2.1.5 ) 式（2.1.5）也稱為牛頓方向，是保證函數(shù)值下降的搜索方向。從而得到牛頓法的迭代方程： ( 2.1.6 ) 2.1.3 Jacobian矩陣假設(shè)我們所討論的目標(biāo)函數(shù)為如下的平方和函數(shù)的形式 ( 2.1.7 ) 則函數(shù)的梯度的第j個(gè)元素為 ( 2.1.8 ) 則函數(shù)的梯度可表示為： ( 2.1.9 ) 其中 稱為雅克比（Jacobian）矩陣，其形式為： ( 2.1.10 ) 2.1.4 LM算法原理式（2.1.3）中提到的海森矩陣，它作為函數(shù)的二階偏導(dǎo)矩陣，其第j，k個(gè)元素為： ( 2.1.11 ) 當(dāng)假設(shè) 很小時(shí)，可得到近似的海森矩

23、陣： ( 2.1.12 )將（2.1.12）和（2.1.9）代入（2.1.6）可得： ( 2.1.13 ) 式（2.1.13）就是高斯-牛頓法，相比傳統(tǒng)的牛頓法，高斯-牛頓法不需要計(jì)算二階偏導(dǎo)，大大減少了計(jì)算量，但是得到的近似海森矩陣并不一定可逆，因此對原來的近似海森矩陣做了修改： ( 2.1.14 ) 式中加入阻尼系數(shù)，因此得到了LM算法： ( 2.1.15 ) 由（2.1.15）式可看出，當(dāng)變得很大，LM算法接近于小學(xué)習(xí)率的梯度下降法，而當(dāng)趨近于0時(shí)，LM算法變成了高斯-牛頓法。阻尼系數(shù)的選擇對LM算法來說是十分關(guān)鍵的，它對優(yōu)化成功率和效率都有很大影響。增大阻尼系數(shù)會減小學(xué)習(xí)率也就是步長會

24、縮短，減小阻尼系數(shù)會增大學(xué)習(xí)率也即步長增長，所以LM算法中已經(jīng)包括了學(xué)習(xí)率的調(diào)整。起初，將阻尼系數(shù)設(shè)為一個(gè)較小的值，如果得到的新函數(shù)值沒有減小則增大阻尼系數(shù)的值，重新計(jì)算函數(shù)值，一直重復(fù)該步驟最終將會使函數(shù)值減小因?yàn)榇藭r(shí)相當(dāng)于朝著最速下降的方向。如果第一次就使得函數(shù)值減小，那么減小阻尼系數(shù)的值，此時(shí)算法將接近高斯-牛頓法較快的收斂，因此LM算法很好的折中了牛頓法和最速下降法的優(yōu)點(diǎn)，保證了算法的收斂性和運(yùn)算速度。2.1.5 LM算法流程LM算法主要包括六個(gè)步驟，其流程如下：1、 首先初始化、阻尼系數(shù)、參數(shù)、誤差容限，初始矩陣I為單位矩陣，求出初始函數(shù)值以及；2、 計(jì)算出雅克比矩陣；3、 計(jì)算海森

25、矩陣修正式以及函數(shù)梯度；4、 檢驗(yàn)迭代終止條件，如果滿足，則目前的就是最優(yōu)解坐標(biāo)停止迭代，否則往下；5、 計(jì)算出增量，根據(jù)得到新的函數(shù)值以及；6、 如果函數(shù)值下降，即，則，且縮小阻尼系數(shù)為，跳轉(zhuǎn)到第2步。否則不作更新，且放大阻尼系數(shù)為，跳轉(zhuǎn)到第3步。 其中迭代是從開始的，阻尼系數(shù)的初始值一般取比較小的值如0.01，而調(diào)整參數(shù)>1，如。這里對阻尼系數(shù)的調(diào)整用到的是信賴域法。2.2 BFGS算法 1970年Broyden，F(xiàn)letcher，Goldfarb，Shanno提出了一種不易變?yōu)槠娈惥仃嚨木仃嚨拚▽⑵涿麨锽FGS算法，該算法可使用非精確搜索方法，其具有全局收斂性和超線性收斂性

26、6，后來被證實(shí)是解決無約束優(yōu)化問題最有效的方法之一。一直以來，BFGS算法被公認(rèn)為是擬牛頓法中數(shù)值優(yōu)化效果最好的算法。2.2.1 擬牛頓法（Quasi-Newton method）式（2.1.6）得到了牛頓迭代，從之前的敘述我們可知，牛頓迭代中的需要求海森矩陣的逆，計(jì)算量很大，還要求函數(shù)必須有連續(xù)的二階偏導(dǎo)，并且不能保證海森矩陣正定可逆。因此擬牛頓法的提出就是用擬海森矩陣或是擬海森矩陣的逆來代替原來的海森矩陣，通常，保證擬海森矩陣正定對稱13。擬牛頓法的關(guān)鍵就是如何求出每一步的或，確保可以求出使函數(shù)下降的方向。關(guān)于或的修正方法，有DFP（Davidon-Fletcher-Powell）法、BF

27、GS算法。對二階泰勒展開式（2.1.3）進(jìn)行求導(dǎo)得到： ( 2.2.1 ) ( 2.2.2 ) 式（2.2.2）就是擬牛頓條件，式中并不是牛頓法搜索方向而是增量。2.2.1 BFGS算法原理BFGS算法采用秩2修正法修正： ( 2.2.3 ) 式中 ，。 矩陣正定是使目標(biāo)函數(shù)下降的條件，而保證其正定的充要條件是： ( 2.2.4 ) 所以BFGS算法中在該條件下對矩陣進(jìn)行修正就可以使得目標(biāo)函數(shù)下降。2.2.2 BFGS算法流程BFGS算法流程主要包括五個(gè)部分：1、 求解搜索的方向： ( 2.2.5 ) 2、 沿著搜索到的方向進(jìn)行線性搜索學(xué)習(xí)率: ( 2.2.6 ) 得到新的點(diǎn)： ( 2.2.7

28、 )3、 運(yùn)用式（2.2.3）修正得到；4、 判斷迭代終止條件是否滿足： ( 2.2.8 ) 上述流程 從k=0開始迭代，初始一般為單位矩陣。當(dāng)滿足終止條件說明達(dá)到收斂，即為所求點(diǎn)的坐標(biāo)結(jié)束迭代。否則將修正得到的帶入第一步，重新進(jìn)入整個(gè)流程重復(fù)迭代，直到滿足收斂條件。2.3 Armijo搜索有很多可進(jìn)行學(xué)習(xí)率搜索的一維線性搜索方法，大致分為兩類：精確線性搜索和非精確線性搜索。常用的精確線性搜索方法有黃金分割法（0.618法）等，常見的非精確線性搜索方法有Armijo法、Goldstein法以及Wolf-Powell法等6。精確線性搜索方法要求求出學(xué)習(xí)率作為自變量的一元函數(shù)的最小值點(diǎn)，計(jì)算量很大

29、并且有些函數(shù)求不到最小值點(diǎn)。而非精確線性搜索只要求學(xué)習(xí)率使得函數(shù)在處的值比小，因此在計(jì)算上容易實(shí)現(xiàn)，計(jì)算量也相應(yīng)比精確線性搜索少7。本課題運(yùn)用的是Armijo型線性搜索，對于給定的，取使得： ( 2.3.1 ) 當(dāng)時(shí)，可保證牛頓法和擬牛頓法的超線性收斂性。利用函數(shù)，可將（2.3.1）等價(jià)為： ( 2.3.2 )由于是在處的下降方向且滿足，則式（2.3.1）對充分小的正數(shù)均成立。在BFGS算法中應(yīng)用Armijo搜素算法時(shí)，并不能保證。但是Armijo搜索算法因?yàn)楹唵吻页绦蛉菀讓?shí)現(xiàn)而深受歡迎，本課題使用該方法并不會影響LM算法和BFGS算法的性能對比分析，但為了保證矩陣的對稱正定性，采用如下修正方

30、式： ( 2.3.3 ) 只要對稱正定，（2.3.3）式可保證矩陣對稱正定。第3章 基于LM算法與BFGS算法的優(yōu)化問題求解本章將運(yùn)用LM算法和BFGS算法求解一些函數(shù)的最優(yōu)解，其中大部分函數(shù)是數(shù)值優(yōu)化領(lǐng)域經(jīng)典的測試函數(shù)，如Rosenbrock函數(shù)、Beale函數(shù)、Powells Quadratic函數(shù)等。針對不同的函數(shù)，兩個(gè)算法選取相同的起始點(diǎn)開始迭代，并且統(tǒng)一終止迭代的條件，誤差容限精度相等。LM算法的阻尼系數(shù)初始值為2，調(diào)整系數(shù)為1.5，兩個(gè)算法的誤差精度都設(shè)為。運(yùn)行算法后通過比較算法的迭代次數(shù)、誤差、運(yùn)算時(shí)間以及尋優(yōu)軌跡圖進(jìn)行兩個(gè)算法性能的分析。運(yùn)用優(yōu)化算法對目標(biāo)函數(shù)進(jìn)行優(yōu)化的實(shí)質(zhì)就是

31、求解目標(biāo)函數(shù)的最小值或極小值，其過程就是從一初始點(diǎn)開始，根據(jù)優(yōu)化算法得到的方向和步長運(yùn)行到下一個(gè)點(diǎn)，直到找到一個(gè)函數(shù)值最小的點(diǎn)。整個(gè)過程就像一個(gè)下山的過程，一直朝著高度減小的方向走，直到走到山底。而這個(gè)尋找下降方向和每一步步長的過程就是優(yōu)化算法的任務(wù)。3.1 Rosenbrock函數(shù)的極值求解 圖 3.1.1 Rosenbrock函數(shù)（N=2）三維曲面圖由于Rosenbrock函數(shù)的全局最優(yōu)解位于一個(gè)平坦的“山谷”中，要收斂到全局最小值點(diǎn)是比較困難的，所以它常被用來作為優(yōu)化算法的測試函數(shù)，其公式如下： ( 3.1.1 ) 其中，該函數(shù)沒有局部最優(yōu)解，只在處也即時(shí)有一個(gè)全局最優(yōu)解0。 當(dāng)Rose

32、nbrock函數(shù)N=2時(shí)，其方程為：( 3.1.2 ) 其三維曲面圖如圖3.1.1所示。運(yùn)用LM算法和BFGS算法求解N=2的Rosenbrock函數(shù)的全局最優(yōu)解，理想的最優(yōu)解在其函數(shù)值為0。選取起始點(diǎn)為，兩個(gè)算法運(yùn)行后的尋優(yōu)軌跡圖和函數(shù)值變化曲線圖如下：圖3.1.2 起始點(diǎn)為的等高線尋優(yōu)軌跡圖 圖3.1.3 起始點(diǎn)為的函數(shù)值變化曲線選取起始點(diǎn)為，兩個(gè)算法運(yùn)行后的尋優(yōu)軌跡圖和函數(shù)值變化曲線圖如下：圖3.1.4 起始點(diǎn)為的等高線尋優(yōu)軌跡圖圖3.1.5 起始點(diǎn)為的函數(shù)值變化曲線選取起始點(diǎn)為，兩個(gè)算法運(yùn)行后的尋優(yōu)軌跡圖如圖3.1.6所示，函數(shù)值變化曲線圖如圖3.1.7所示。選取起始點(diǎn)為，兩個(gè)算法運(yùn)行

33、后的尋優(yōu)軌跡圖如圖3.1.8所示，函數(shù)值變化曲線圖如圖3.1.9所示。選取起始點(diǎn)為，兩個(gè)算運(yùn)行后的尋優(yōu)軌跡圖如圖3.1.10所示，函數(shù)值變化曲線如圖3.1.11所示。圖3.1.6 起始點(diǎn)為的等高線尋優(yōu)軌跡圖圖3.1.7 起始點(diǎn)為的函數(shù)值變化曲線圖3.1.8 起始點(diǎn)為的等高線尋優(yōu)軌跡圖 圖3.1.9 起始點(diǎn)為的函數(shù)值變化曲線 圖3.1.10 起始點(diǎn)為的等高線尋優(yōu)軌跡圖圖3.1.11 起始點(diǎn)為的函數(shù)值變化曲線根據(jù)以上不同起始點(diǎn)的等高線尋優(yōu)軌跡圖和函數(shù)值變化曲線，可看出，對Rosenbrock函數(shù)（N=2）求解極小值時(shí)，在起始點(diǎn)靠近全局最優(yōu)解的時(shí)候或是起始點(diǎn)距離全局最優(yōu)解較遠(yuǎn)的情況下，LM算法的收斂

34、速度大部分情況下是比BFGS算法快的，但是當(dāng)收斂到一定情況下時(shí)，LM算法收斂速度減慢，學(xué)習(xí)率變小，而BFGS算法的學(xué)習(xí)率卻是波動較小的。表3.1.1 LM算法和BFGS算法求解Rosenbrock函數(shù)（N=2）最小值性能比較起始點(diǎn)LM迭代次數(shù)BFGS迭代次數(shù)LM誤差BFGS誤差LM運(yùn)行時(shí)間BFGS運(yùn)行時(shí)間17219.6977×10-194.1686×10-15 2.9078 s 4.1040 s15201.2860×10-181.190×10-12 3.1835 s 3.9293 s15131.2180×10-181.3221×10-

35、13 2.5712 s 2.8510 s15248.9131×10-182.1171×10-15 2.3726 s 5.0641 s17471.3383×10-191.3341×10-13 2.8489 s 6.3435 s20672.3622×10-193.1778×10-17 3.2620 s 5.9763 s表3.1.2 起始點(diǎn)為的不同維度Rosenbrock函數(shù)求解對比NLM迭代次數(shù)BFGS迭代次數(shù)LM誤差BFGS誤差LM運(yùn)行時(shí)間BFGS運(yùn)行時(shí)間217219.6977×10-194.1686×10-15 2

36、.9078 s4.1040 s316268.9500×10-174.3454×10-14 5.6207 s9.7260 s417285.7859×10-176.7678×10-13 6.8435 s9.3070 s518345.2980×10-172.6506×10-15 8.7447 s22.2176 s619395.3814×10-171.9618×10-13 8.7363 s22.238 s720425.6127×10-171.9924×10-1414.8170 s31.7683 s822

37、474.3400×10-174.4370×10-1312.7125 s25.9286 s923504.5391×10-174.5391×10-1720.3751 s42.9034 s1024554.7539×10-172.8375×10-1222.6591 s39.0883 s通過以上的對比，用LM算法和BFGS算求解Rosenbrock函數(shù)（N=2）最小值時(shí)，大部分情況下LM算法運(yùn)行的速度是比BFGS算法快的，并且LM算法的收斂速度也更快一些，需要的迭代次數(shù)也比BFGS算法少，最終得到的誤差比BFGS算小很多。針對二元的Rosenb

38、rock函數(shù)求解最小值，LM算法在運(yùn)行速度、收斂速度、誤差、迭代次數(shù)上是比BFGS算法適合的。取式（3.1.1）不同的N即不同維度的Rosenbrock函數(shù)，從同一個(gè)起始點(diǎn)運(yùn)行LM算法和BFGS算法，得到如表3.1.2不同的比較。 兩個(gè)算法對不同維度的Rosenbrock函數(shù)求解最小值，通過對比結(jié)果可知，LM算法計(jì)算的精度比BFGS算法高，運(yùn)算的速度也更快，迭代次數(shù)少。目前還不能就此得出LM算法比BFGS算法更優(yōu)越的結(jié)論，下面要用LM算法和BFGS算法求解不同函數(shù)的極值，再進(jìn)行針對不同函數(shù)的對比。3.2 不同函數(shù)的極值求解對比選擇作為起始點(diǎn)，用這兩個(gè)算法對下式函數(shù)求解其極小值： ( 3.2.1

39、 )該函數(shù)在只有一個(gè)全局最優(yōu)解，其值為0，LM算法和BFGS算法在函數(shù)等高線上的尋優(yōu)軌跡圖3.2.1和函數(shù)值變化曲線圖3.2.2為： 圖 3.2.1 求最優(yōu)解的等高線尋優(yōu)軌跡圖由圖3.2.1和圖3.2.2可知，LM算法的收斂速度是更快的，從等高線尋優(yōu)軌跡圖中可看出，在起始點(diǎn)的時(shí)候函數(shù)值是較大的，而LM算法在前面的幾次迭代中函數(shù)值迅速的下降到了較小的值，BFGS算法前面幾次迭代中下降的速度是沒有LM算法快的，也就是說LM算法收斂得比較快，但是當(dāng)函數(shù)減小到一定值的時(shí)候，LM算法的下降變得非常慢，使得它最終的迭代次數(shù)超過了BFGS算法的。從表3.2.2中可看出，兩個(gè)算法得到的的極小值中，BFGS算法

40、得到的值是更小的且更接近目標(biāo)值0，雖然相差不大，但是說明LM算法并不是對所有的函數(shù)求解都有更高的精度，其次LM算法的運(yùn)行時(shí)間和迭代次數(shù)這次計(jì)算中都超過了BFGS算法。圖 3.2.2 求解極小值的函數(shù)變化曲線圖選取起始點(diǎn)坐標(biāo)為，用這兩個(gè)算法求解De Jong函數(shù)的極小值。De Jong函數(shù)在處有一個(gè)全局最優(yōu)解0。其函數(shù)表達(dá)式為： ( 3.2.2 ) 兩個(gè)算法對其求解的等高線尋優(yōu)軌跡圖和函數(shù)值變化曲線圖如下所示：圖3.2.3 求解De Jong函數(shù)的等高線尋優(yōu)軌跡圖 從求解De Jong函數(shù)的圖3.2.3和圖3.2.4這兩個(gè)比較圖，可得到類似于求解函數(shù)的結(jié)果，也就是LM算法的收斂速度是比BFGS算

41、法快的，但是當(dāng)函數(shù)值減小到一定程度后，LM算法變得比BFGS算法慢。從表3.2.2可知，這兩個(gè)算法對De Jong函數(shù)的求解結(jié)果中，LM算法比BFGS算法的誤差略小，但是相差不大，而LM算法的迭代次數(shù)比BFGS算法多一點(diǎn)相差也不算大。圖3.2.4 求解De Jong函數(shù)時(shí)的函數(shù)值變化曲線選取起始點(diǎn)為，運(yùn)用這兩個(gè)算法對Beale函數(shù)求解極小值，Beale函數(shù)在有一個(gè)全局最優(yōu)解0，其函數(shù)表達(dá)式為： ( 3.2.3 ) 這兩個(gè)算法對Beale函數(shù)求解極值的等高線尋優(yōu)軌跡圖和函數(shù)值變化曲線如下所示：圖3.2.5 求解Beale函數(shù)的等高線尋優(yōu)軌跡圖 對于Beale函數(shù)的求解，從圖3.2.5和圖3.2.

42、6中可看出兩個(gè)算法中，BFGS算法這次收斂得稍微快一點(diǎn)，但并不是很明顯，迭代次數(shù)也更少一點(diǎn)，相差也不大，說明對于Beale函數(shù)這兩個(gè)算法的求解能力差別不太大，但LM算法這次依舊是誤差更小一點(diǎn)。圖3.2.6 求解Beale函數(shù)時(shí)的函數(shù)值變化曲線選取起始點(diǎn)為，運(yùn)用這兩個(gè)算法求解Booths函數(shù)的極小值， Booths函數(shù)在處有一個(gè)全局最優(yōu)解0，其函數(shù)表達(dá)式為： ( 3.2.4 ) 這兩個(gè)算法對Beale函數(shù)求解極值的等高線尋優(yōu)軌跡圖和函數(shù)值變化曲線如下所示：圖3.2.7 求解Booths函數(shù)的等高線尋優(yōu)軌跡圖從圖3.2.7和圖3.2.8中可看出，BFGS算法與LM算法的收斂速度是幾乎一樣的，但是B

43、FGS算法的最終迭代次數(shù)比LM算法少，而更多的迭代次數(shù)也使得LM算法最終得到的結(jié)果誤差比BFGS算法小。圖3.2.8 求解Booths函數(shù)時(shí)的函數(shù)值變化曲線下面要運(yùn)用這兩個(gè)算法求解Powells Quadratic函數(shù)的極小值，作為又一個(gè)經(jīng)典的優(yōu)化測試函數(shù)，Powells Quadratic函數(shù)在處有一個(gè)全局最優(yōu)解0，其函數(shù)表達(dá)式如下： ( 3.2.5 ) 由于該函數(shù)為多維函數(shù)，所以只繪制了兩個(gè)算法求解極值的函數(shù)值變化曲線圖，如下所示：圖3.2.9 求解Powells Quadratic函數(shù)時(shí)的函數(shù)值變化曲線表3.2.1 兩個(gè)算法求解不同函數(shù)極小值時(shí)的迭代次數(shù)對比目標(biāo)函數(shù) LM算法/次BFGS

44、算法/次5948Rosenbrock1721De Jong5954Beale1513Booth's116Powells Quadratic6563 表3.2.2 兩個(gè)算求解不同函數(shù)極小值的誤差對比目標(biāo)函數(shù) LM算法BFGS算法2.1855×10-226.3902×10-23Rosenbrock9.6977×10-194.1686×10-15De Jong2.0980×10-223.4835×10-19Beale 4.9849×10-172.1005×10-15Booth's6.8371×1

45、0-188.5438×10-14Powells Quadratic1.4580×10-239.9354×10-20 從以上幾個(gè)函數(shù)求解極值的對比，可看出其實(shí)LM算法和BFGS算法的求解差別不大，只不過在大部分情況下LM算法的求解誤差是比BFGS算法小的。并且從等高線的尋優(yōu)軌跡圖中可以總結(jié)出，LM算法在求解的過程中，前期的收斂是較BFGS算法稍快的，特別是對于等高線圖類似于橢圓的函數(shù)。而當(dāng)函數(shù)值下降到一定程度時(shí)，LM算法的步伐放慢，BFGS算法的迭代次數(shù)相對比LM算法少，但是最終結(jié)束迭代，LM算法得到誤差更小的結(jié)果。針對LM算法在大部分情況下誤差更小并且收斂速度較快的結(jié)果，在下一章將進(jìn)行基于LM算法的前向神經(jīng)網(wǎng)絡(luò)的研究，并運(yùn)用于實(shí)際二分類問題。第四章 基于LM算法的前向神經(jīng)網(wǎng)絡(luò)的學(xué)習(xí)4.1 前向神經(jīng)網(wǎng)