一種BFGS校正的改進(jìn)信賴域方法

章安閣　張舸

摘? 要： 本文利用經(jīng)典的信賴域方法，針對無約束優(yōu)化問題，對信賴域進(jìn)行改進(jìn)，并在此基礎(chǔ)上對算法進(jìn)行BFGS校正。數(shù)值實驗證明，相比傳統(tǒng)的信賴域方法，改進(jìn)的信賴域方法在計算效率上有了很大提高;而加入BFGS校正后，新算法相比改進(jìn)的信賴域方法又有了進(jìn)一步的提高。

關(guān)鍵詞： 無約束最優(yōu)化;信賴域法;BFGS校正

中圖分類號： O224? ? 文獻(xiàn)標(biāo)識碼： A? ? DOI：10.3969/j.issn.1003-6970.2019.07.020

【Abstract】： We proposed an improved trust region method with BFGS， which is based on the traditional trust region method and used to improve the trust region for unconstrained optimization problems. On this basis， the BFGS correction of the algorithm is carried out. The numerical experiments show that， comparing with the traditional trust region method， the improved trust region method with BFGS has greatly improved the computational efficiency， and compared with the improved trust region method after adding BFGS correction， the new algorithm has further improved.

【Key words】： Unconstrained optimization; Trust region method; BFGS correction

0? 引言

分析表1，可以看出，對于測試函數(shù) ，當(dāng)? 取 時，計算次數(shù)最少;對比每一行的第二列和第三列數(shù)據(jù)，或者是第四列和第五列數(shù)據(jù)，會發(fā)現(xiàn)，加入BFGS校正后，計算次數(shù)也或多或少地有所下降，只有當(dāng) 取 ， 時次數(shù)增加了16，在可接受的范圍內(nèi)。但是當(dāng) 時，傳統(tǒng)的信賴域方法只需要計算21次，兩種方法都不如傳統(tǒng)的信賴域法的計算效率。但是本文提出的加入BFGS修正的改進(jìn)信賴域方法（算法2）也只是稍遜于傳統(tǒng)的信賴域方法。在維度 時，計算次數(shù)相比 時有了明顯增加，但是對比之下還是當(dāng) 取 時，計算次數(shù)最少;對比每一行的第二列和第三列數(shù)據(jù)，或者是第四列和第五列數(shù)據(jù)，會發(fā)現(xiàn)，加入BFGS校正后，計算次數(shù)也或多或少地有所下降，增加也是在1-2之內(nèi)浮動。同樣的，此時用傳統(tǒng)的信賴域方法，計算次數(shù)要達(dá)到2000多次。顯然，我們的方法是有效的。因此，我們可以得出初步結(jié)論，當(dāng)問題的維數(shù)很高，使用傳統(tǒng)的信賴域方法需要大規(guī)模的計算時間和空間，而本文中提到的兩個算法相比傳統(tǒng)的信賴域方法在處理大規(guī)模問題時有著非常明顯的優(yōu)點。可以說，算法是有效的。

對于測試函數(shù) ，當(dāng) ，傳統(tǒng)的信賴域方法得出最優(yōu)解的計算次數(shù)是42，單純的BFGS算法得出最優(yōu)解的計算次數(shù)是115;當(dāng) ，傳統(tǒng)的信賴域方法得出最優(yōu)解的計算次數(shù)是65，單純的BFGS算法得出最優(yōu)解的計算次數(shù)是323。算法的具體的實驗數(shù)據(jù)如下。

當(dāng)維度較低時（dim=8），除了在θ取0.5時，次數(shù)翻了一番，當(dāng)θ取其他值時，算法2相比算法1 在計算次數(shù)上有所減少，觀察第三列數(shù)據(jù)，我們還可以發(fā)現(xiàn)當(dāng)θ的值變動，計算次數(shù)的變化并不大，而且當(dāng)θ取1.5時，算法2計算次數(shù)最少（28次），相比傳統(tǒng)的信賴域法（42次）和單純的BFGS算法（115次），都是算法2更好。;當(dāng)維度升高（dim=40），除了在θ取0.75時，算法2相比算法1的計算次數(shù)有所上升，其他情況下算法2都要比算法1的計算次數(shù)少。同樣的，當(dāng)θ取1.5時，算法2計算次數(shù)最少（41次），相比傳統(tǒng)的信賴域法（65次）和單純的BFGS算法（323次），也是算法2更好。

5 總結(jié)

信賴域法和BFGS修正都是在計算優(yōu)化問題時的常用方法，本文提出了一種加入了BFGS修正的改進(jìn)的信賴域算法，是二者優(yōu)點的一個融合。近年來，數(shù)值優(yōu)化方法的發(fā)展很快，文獻(xiàn)[1-4]都是對信賴域法進(jìn)行了大量的改進(jìn)，文獻(xiàn)[5-7]更是將信賴域法與BFGS方法進(jìn)行了各種糅合，本文提出的算法亦是如此，且在計算次數(shù)上有了減少。未來，針對此算法，也可以用其他的測試問題進(jìn)行進(jìn)一步的測試與研究。在以后的研究中，作者將亦會把本文的思想應(yīng)用于最優(yōu)化算法中直接法[8-10]的研究。感謝導(dǎo)師賀祖國教授對本文算法的寶貴意見與指導(dǎo)。

參考文獻(xiàn)

G. X. Ma， “A Modified Trust Region Methods for Un-con?-

strained Optimization （in Chinese），” Master's Thesis， 2003.

J. Nocedal and Y. Yuan， “Combining Trust Region and Line Search， Y. Yuan， ed.，” Advances in Nonlinear Pro-gramming，

Kluwer， 1998， pp. 153-175.

Q. H. Zhou， Y. R. Zhang， F. X. Xu and Y. Geng， “An Improved Trust Region Method for Unconstrained Opti-mization，” accepted by Science China Mathematics.

Qinghua Zhou， Yarui Zhang， Xiaoli Zhang， “An Improved Line Search and Trust Region Algorithm” accepted by A Journal of Software Engineering and Applications， 2013， 6， 49-52.

景書杰， 張小亮. 解線性約束優(yōu)化問題的自適應(yīng)-BFGS信賴域算法[J]. 2010.《山西大學(xué)學(xué)報（自然科學(xué)版）》， 33（4）： 500-503.

袁功林， 韋增欣. 一個新的BFGS信賴域算法[J]. 2004.《廣西科學(xué)》， 11（3）： 195-196， 200.

李文鈺. 一類修正的BFGS信賴域方法[D]. 碩士學(xué)位論文， 2008.

M. J. D. Powell*UOBYQA： unconstrained optimization by quadratic approximation， Report No. DAMTP 2000/NA 14， University of Cambridge.

M. J. D. Powell*.The NEWUOA software for unconstrained optimization without derivatives.， Report No. DAMTP 2007/NA05， University of Cambridge.

賀祖國. 混合策略的直接法研究. [學(xué)位論文]. 中國科學(xué)院： 2002.