改進(jìn)共軛梯度法求解無約束二次凸規(guī)劃問題

喬熔巖， 趙新國

(1.中國人民解放軍裝備學(xué)院 研究生二隊(duì)，北京 101416； 2.中國人民解放軍裝備學(xué)院 航天指揮系，北京 101416)

1 引 言

共軛梯度法在構(gòu)造共軛方向時(shí)，初始方向選定為已知點(diǎn)的負(fù)梯度方向，有一定的局限性，而且采取邊搜索邊構(gòu)造的方式，構(gòu)造過程比較復(fù)雜.本文將對經(jīng)典共軛梯度法進(jìn)行改進(jìn)，即先利用n的任一組正交基，直接構(gòu)造出一組共軛方向，然后讓初始點(diǎn)沿這組方向進(jìn)行一維最優(yōu)搜索，求出極小值點(diǎn).

2 改進(jìn)共軛梯度法的基礎(chǔ)理論

2.1 共軛方向的構(gòu)造通式

取d1=α1. 因?yàn)?/p>

(1)

所以取d2=A-1α2. 構(gòu)造d3=α3+k1d1，令

(2)

(3)

這說明上述構(gòu)成的d3與d1，d2關(guān)于A共軛. 再構(gòu)造d4=A-1α4+p1d2，令

(4)

(5)

(6)

這說明所構(gòu)成的d4也與d1，d2，d3關(guān)于A共軛.

現(xiàn)將此構(gòu)造方法進(jìn)行推廣，給出d2m-1和d2m(其中m=1,2,3,…)的構(gòu)造通式

d2m-1=α2m-1+k1d1+k2d3+…+km-1d2m-3，

(7)

d2m=A-1α2m+p1d2+p2d4+…+pm-1d2m-2.

(8)

令

(9)

由式(9)得

再令

(10)

由式(10)得

由此可根據(jù)通式(7)，(8)，構(gòu)造出一組方向d1,d2,…,dn.

2.2 構(gòu)造方法的理論證明

(11)

即αi與d2m關(guān)于A共軛，根據(jù)數(shù)學(xué)歸納法可知定理1成立.

定理2已知

其中x∈n，A為n階正定矩陣，b為n維列向量，c為常數(shù)，方向d1,d2,…,dn是由一組正交基α1,α2,…,αn，根據(jù)通式(7)，(8)構(gòu)造的，現(xiàn)任取向量αj(其中j為偶數(shù))，則有A-1αj與d1,d3,…，d2m-1關(guān)于A共軛，其中2m-1≤n，m=1,2,3,….

(12)

即A-1αj與d2m-1關(guān)于A共軛，根據(jù)數(shù)學(xué)歸納法可知定理2成立.

現(xiàn)利用定理1和定理2，來證明由通式(7)和(8)所構(gòu)造的d1,d2,…,dn是關(guān)于A共軛的.

由式(1)～(6)可知，d1，d2，d3和d4是關(guān)于A共軛的. 現(xiàn)假設(shè)已構(gòu)造的d1,d2,…,d2m-3,d2m-2關(guān)于A共軛，其中2m-2

(13)

(14)

3 改進(jìn)共軛梯度法的應(yīng)用

3.1 方法的基本計(jì)算過程

第一：確定初始點(diǎn)x0、精度ε和一組正交基α1,α2,…,αn(可取單位坐標(biāo)基)；

第二：利用式(7)，(8)直接構(gòu)造出一組方向d1,d2,…,dn關(guān)于A共軛；

第三：以x0為起點(diǎn)，首先沿方向d1進(jìn)行一維最優(yōu)步長搜索，求出步長λ1和x1=x0+λ1d1.如果‖f(x1)‖≤ε，則停止搜索，求出f(x1)；否則再以x1為起點(diǎn)，沿方向d2進(jìn)行一維最優(yōu)步長搜索，以此類推，直到找到滿足精度要求的點(diǎn)為止.

3.2 方法收斂性的證明

已知

其中x∈n，A為n階正定對稱矩陣，b為n維列向量，c為常數(shù)，d1,d2,…,dn是由一組正交基α1,α2,…,αn，根據(jù)通式(7)，(8)構(gòu)造的關(guān)于A共軛的方向，以任意點(diǎn)x0為起點(diǎn)，依次沿d1,d2,…,dn進(jìn)行一維最優(yōu)步長搜索，得到點(diǎn)x1,x2,…,xn，其中λ1,λ2,…,λn為相應(yīng)的最優(yōu)步長，則xn是f(x)的唯一極小點(diǎn).

證由3.1中的方法可知

則有

(15)

任取方向dj(其中j=1,2,…,n)，則有

(16)

(17)

根據(jù)最優(yōu)步長λj的求解過程可知，λj是式(18)的解

(18)

(19)

其中j=1,2,…,n. 又設(shè)存在一組數(shù)β1,β2,…,βn，使得

(20)

(21)

3.3 實(shí)例求解與比較

分別用共軛梯度法和改進(jìn)共軛梯度法求解如下問題：

初始點(diǎn)x0=(5,5)T，求解過程如表1所示.

表1 兩種方法的計(jì)算步驟

由表1所示，改進(jìn)共軛梯度法比共軛梯度法在求解例題時(shí)，計(jì)算步驟要減少一步，其主要原因是，共軛梯度法在構(gòu)造d2之前，要多計(jì)算一步求去解f(x1)，而改進(jìn)共軛梯度法則不用.

現(xiàn)將3.3中f(x)推廣為n元函數(shù)，則利用共軛梯度法求解時(shí)，每構(gòu)造新的搜素方向之前，都要多計(jì)算一步去求解上一點(diǎn)的梯度，這就在整體計(jì)算步驟上，比改進(jìn)共軛梯度法多出n-1步. 從構(gòu)造搜索方向的方法來看，共軛梯度法的初始方向選定為初始點(diǎn)的負(fù)梯度方向，且新方向的構(gòu)造也必須借助于上一點(diǎn)的梯度. 而改進(jìn)共軛梯度法則不同，它在構(gòu)造搜素方向時(shí)，不用依賴于負(fù)梯度方向，只要任意給出一組正交基，就可以直接構(gòu)造出所有的搜素方向. 而在選取正交基時(shí)，一般取單位坐標(biāo)基即可，這樣非常簡單方便.

4 總 結(jié)

本文首先對經(jīng)典的共軛梯度法進(jìn)行了分析，指出了其在構(gòu)造共軛方向上的局限性和復(fù)雜性. 然后根據(jù)二次正定函數(shù)的特性，對經(jīng)典方法進(jìn)行了改進(jìn)，并利用數(shù)學(xué)歸納法對其進(jìn)行了證明，同時(shí)給出了方法應(yīng)用時(shí)的具體計(jì)算步驟，并對方法的收斂性進(jìn)行了證明.從實(shí)例求解的結(jié)果看，該方法的計(jì)算步驟要比共軛梯度法少，在求解搜素方向時(shí)，也具有一定的靈活性和應(yīng)用價(jià)值.

[參 考 文 獻(xiàn)]

[1] 陳寶林.最優(yōu)化理論與算法[M]. 2版. 北京：清華大學(xué)出版社，2005：120-360.

[2] 陳慶華，郭全魁，宋華文.裝備運(yùn)籌學(xué)教程[M].北京：國防工業(yè)出版社，2007：1-50.

[3] 《運(yùn)籌學(xué)》教材編寫組.運(yùn)籌學(xué)[M].北京：清華大學(xué)出版社，1994：1-120.

[4] 張俊學(xué).作戰(zhàn)運(yùn)籌學(xué)[M].北京：解放軍出版社，2000：1-200.

[5] 鄧乃揚(yáng).無約束最優(yōu)化方法[M].北京：科學(xué)出版社，1982：20-50.

[6] Powell M J D.Nonlinear optimizatiion[M]. London：Academic Press，1982:1-10.

[7] Luenberger D G..Introduction to linear and nonlinear programming[M]. Addison-wesley，1984：1-50.

[8] Avril M..Nonlinear programming: analysis and methods[M].Prentice-Hall, Inc.，1976:20-30.

[9] 席少霖，趙鳳治.最優(yōu)化計(jì)算方法[M].上海：上?？茖W(xué)技術(shù)出版社，1983:25-120.