改進(jìn)共軛梯度法求解無約束優(yōu)化問題

改進(jìn)共軛梯度法求解無約束優(yōu)化問題

文/朱花吳根師白玉芳

摘要：在實(shí)際生活中，最優(yōu)化問題的求解十分普遍，例如大氣模擬、自然科學(xué)、生產(chǎn)管理等等。所以，最優(yōu)化問題的求解已經(jīng)發(fā)展為關(guān)鍵問題。本文將就共軛梯度法的改進(jìn)進(jìn)行研究。首先論述共軛梯度法的發(fā)展概括，然后介紹無約朿最優(yōu)化問題的基本概念，最后探討一類求解無約束優(yōu)化問題的共軛梯度法，本文的研究成果將為優(yōu)化共軛梯度法解決無約束優(yōu)化問題過程提供良好借鑒。

關(guān)鍵詞：共軛梯度法；無約束；充分下降性

中圖分類號:O212文獻(xiàn)標(biāo)志碼：A

引言

因?yàn)楣曹椞荻确ň邆涫諗克俣瓤臁⒋鎯α可俚葍?yōu)點(diǎn)，所以該方法可以解決規(guī)模較大的優(yōu)化問題。即使共軛梯度法從上世紀(jì)50年代就已經(jīng)被提出，但是直至今天，其仍然是一個(gè)熱門的研究方向，而且其在實(shí)際應(yīng)用以及數(shù)學(xué)基礎(chǔ)理論上具備著重要的研究意義。

一、共軛梯度法的發(fā)展概況

共軛梯度法是由幾何學(xué)家Stiefel與計(jì)算數(shù)學(xué)家Hestenes發(fā)明并發(fā)展的，其主要是在20世紀(jì)50年代初為了求解Ax=bx×Rn此線性方程組提出的，其合作發(fā)表的文章至今被認(rèn)為是共軛梯度法研究的奠基之作。一般地，經(jīng)典共軛梯度法可以分為HS共軛梯度法、FR共軛梯度法、PRP共軛梯度法、CD共軛梯度法、LS共軛梯度法、DY共軛梯度法統(tǒng)。為了能夠構(gòu)造運(yùn)算效果更強(qiáng)的共軛梯度算法，對經(jīng)典共軛梯度法進(jìn)行進(jìn)一步的探討十分重要，只有不斷簡化解題過程，提高解題效率，才能為數(shù)學(xué)研究以及實(shí)際應(yīng)用奠定堅(jiān)實(shí)基礎(chǔ)。

二、無約朿最優(yōu)化問題的基本概念

一般地，無約束最優(yōu)化問題的數(shù)學(xué)模型為minf(x),x∈Rn，其中決策變量是x∈Rn目標(biāo)函數(shù)為f(x)。以下將給出無約束最優(yōu)化問題的最優(yōu)解與極小點(diǎn)定義：

定義1在無約束最優(yōu)化問題minf(x),x∈Rn中，如果存在x*∈Rn，能夠使任意x∈Rn滿足不等式f(x*)≤f(x)，那么可以稱x*為目標(biāo)函數(shù)f(x)的整體最優(yōu)解或者整體極小點(diǎn)；如果x≠x*時(shí)存在f(x*)

定義2在無約束最優(yōu)化問題minf(x),x∈Rn中，如果對于任意的x*∈Rn，均可以找到x*的一個(gè)鄰域Uδ(x*)={x∈Rn‖x-x*‖<δ,δ>0}(這里‖·‖表示的是歐氏范數(shù))使得對于任意的x∈Uδ(x*)滿足f(x*)≤f(x)不等式，那么可以稱x*為f(x)的局部最優(yōu)解或者局部極小點(diǎn)；相反地，x≠x*時(shí)，滿足f(x*)

整體極小點(diǎn)一定是局部極小點(diǎn)，但是局部極小點(diǎn)卻不一定是整體極小點(diǎn)，所以在實(shí)際問題中，我們需要求解整體極小點(diǎn)，但是在大多數(shù)的無約束最優(yōu)化問題中卻求解局部極小點(diǎn)，這并不是兩個(gè)矛盾體，在實(shí)際問題中求得的目標(biāo)函數(shù)常常是具有單個(gè)極值的良性函數(shù)，所以可以說它的局部極小點(diǎn)就是整體極小點(diǎn)。

三、一類求解無約束優(yōu)化問題的共軛梯度法

1.新的共軛梯度算法及公式

2.算法的充分下降性

3.算法的全局收斂性證明

為了能夠證明算法的全局收斂性，一般地將給出以下兩個(gè)假設(shè)，并將其充分運(yùn)用在非線性搜索方法的全局收斂性研究中，使得算法的全局收斂性的證明更為簡便。

假設(shè)1f(x)在水平集Ω={x|f(x)≤f(x1)}上有界；

假設(shè)2在水平集Ω中的一個(gè)鄰域U內(nèi)，函數(shù)f(x)連續(xù)可微且梯度向量連續(xù)，則存在常數(shù)L>0，使得‖g(x)-g(y)‖≤L‖x-y‖,?x,y∈U。

根據(jù)假設(shè)，不難推導(dǎo)出存在常數(shù)M>0，能夠使得‖g(x)‖≤M,?k≥1為建立算法全局收斂性的前提條件：

四、結(jié)語

總之，只有不斷研究與改進(jìn)共軛梯度算法，才能使其既具備良好的收斂性質(zhì)，又具備較好的數(shù)值表現(xiàn)，使得無約束最優(yōu)化問題的解題效率大大提高，使得人們的生活隨著共軛梯度法的應(yīng)用范圍日漸廣泛而增添更多的便捷之處。

(作者單位：太原科技大學(xué)化學(xué)與生物工程學(xué)院)

參考文獻(xiàn)：

[1]崔海娟.改進(jìn)共軛梯度法求解無約束優(yōu)化問題[D].渤海大學(xué),2014.