改進(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)鍵詞：共軛梯度法；無約束；充分下降性

中圖分類號(hào)：O212 文獻(xiàn)標(biāo)志碼：A 文章編號(hào)：2095-9214（2015）12-0124-01

引言

因?yàn)楣曹椞荻确ň邆涫諗克俣瓤臁⒋鎯?chǔ)量少等優(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)的共軛梯度算法，對(duì)經(jīng)典共軛梯度法進(jìn)行進(jìn)一步的探討十分重要，只有不斷簡(jiǎ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中，如果對(duì)于任意的x*∈Rn，均可以找到x*的一個(gè)鄰域Uδ（x*）={x∈Rn‖x-x*‖<δ，δ>0}（這里‖·‖表示的是歐氏范數(shù)）使得對(duì)于任意的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.新的共軛梯度算法及公式

改進(jìn)的求解方法是一種含參數(shù)的共軛梯度法βk=λ‖gk‖2μ‖gk-1‖2-gTk-1dk-1，其中0≤λ≤μ≤1，‖·‖表示的是歐式范數(shù)，通過推廣標(biāo)準(zhǔn)非精確線搜索，便可以發(fā)現(xiàn)一種新的線搜索f（xk+akdk）-f（xk）≤-ρa(bǔ)2k‖dk‖2σ1gTkdk≤g（xk+akdk）Tdk≤-σ2gTkdk，其中0<ρ≤σ1<1，σ2≥0且σ1+σ2≤1。第一，取初始點(diǎn)x1∈Rn，d1=-g1，k=1，ε>0；第二，如果‖gk‖<ε那么停止搜索，否則根據(jù)線搜索式解得ak，然后由xk+1=xk+akdk，解得xk+1；第三，根據(jù)βk=λ‖gk‖2μ‖gk-1‖2-gTk-1dk-1求得βk+1。當(dāng)k=1時(shí)，dk=-gk，當(dāng)k≥2時(shí)，dk=-gk+βkdk-1，由此求得dk+1，并置k=k+1，轉(zhuǎn)回第二步。

2.算法的充分下降性

在研究無約束最優(yōu)化問題的共軛梯度求解法時(shí)，不難發(fā)現(xiàn)其進(jìn)行充分下降的條件為gTkdk≤-c‖gk‖2，k≥1，其中c>0是常數(shù)，具有重要作用。但是這個(gè)條件并不是所有算法成立的充分條件，其需要在進(jìn)行非精確線性搜索σ1gTkdk≤g（xk+akdk）Tdk≤-σ2gTkdk以及f（xk+akdk）-f（xk）≤-ρa(bǔ)2k‖dk‖2后仍然滿足充分下降性條件gTkdk≤-c‖gk‖2，k≥1才可以。

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

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

假設(shè)1 f（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為建立算法全局收斂性的前提條件：

定理 若兩個(gè)假設(shè)條件均被滿足，{x}是算法產(chǎn)生中產(chǎn)生的，如果對(duì)于k≥1，存在常數(shù)M能夠使得‖g（x）‖≤M成立，那么有l(wèi)imk→∞inf‖gk‖=0改進(jìn)的共軛梯度算法同樣具有全局收斂性。

四、結(jié)語

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

參考文獻(xiàn)：

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