改進共軛梯度法求解無約束優化問題

朱花　吳根師　白玉芳

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

關鍵詞：共軛梯度法；無約束；充分下降性

中圖分類號：O212 文獻標志碼：A 文章編號：2095-9214（2015）12-0124-01

引言

因為共軛梯度法具備收斂速度快、存儲量少等優點，所以該方法可以解決規模較大的優化問題。即使共軛梯度法從上世紀50年代就已經被提出，但是直至今天，其仍然是一個熱門的研究方向，而且其在實際應用以及數學基礎理論上具備著重要的研究意義。

一、共軛梯度法的發展概況

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

二、無約朿最優化問題的基本概念

一般地，無約束最優化問題的數學模型為minf（x），x∈Rn，其中決策變量是x∈Rn目標函數為f（x）。以下將給出無約束最優化問題的最優解與極小點定義：

定義1 在無約束最優化問題minf（x），x∈Rn中，如果存在x*∈Rn，能夠使任意x∈Rn滿足不等式f（x*）≤f（x），那么可以稱x*為目標函數f（x）的整體最優解或者整體極小點；如果x≠x*時存在f（x*）

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

整體極小點一定是局部極小點，但是局部極小點卻不一定是整體極小點，所以在實際問題中，我們需要求解整體極小點，但是在大多數的無約束最優化問題中卻求解局部極小點，這并不是兩個矛盾體，在實際問題中求得的目標函數常常是具有單個極值的良性函數，所以可以說它的局部極小點就是整體極小點。

三、一類求解無約束優化問題的共軛梯度法

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

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

2.算法的充分下降性

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

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

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

假設1 f（x）在水平集Ω={x|f（x）≤f（x1）}上有界；

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

根據假設，不難推導出存在常數M>0，能夠使得‖g（x）‖≤M，k≥1為建立算法全局收斂性的前提條件：

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

四、結語

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

參考文獻：

[1]崔海娟.改進共軛梯度法求解無約束優化問題[D].渤海大學，2014.