劉 巍， 谷 闊， 譚佳偉， 劉慶懷

（長(zhǎng)春工業(yè)大學(xué)應(yīng)用數(shù)學(xué)研究所，吉林長(zhǎng)春 130012）

1 引言與問(wèn)題提出

全局最優(yōu)化問(wèn)題是一類(lèi)較難求解且非常重要的問(wèn)題。在很多文獻(xiàn)中可以發(fā)現(xiàn)有大量的文章是關(guān)于全局優(yōu)化問(wèn)題的。已有的全局優(yōu)化算法大體可分為三類(lèi)[1]:第一類(lèi)是變換函數(shù)法，即利用輔助函數(shù)，從一個(gè)局部極小點(diǎn)出發(fā)，找到比這個(gè)局部極小點(diǎn)更優(yōu)的另一個(gè)局部極小點(diǎn)（新局部極小點(diǎn)具有更小的目標(biāo)函數(shù)值），如填充函數(shù)法[2]、打洞函數(shù)法[3]和水平值下降算法;第二類(lèi)是適用于具有特殊結(jié)構(gòu)的最優(yōu)化問(wèn)題（如D.C規(guī)劃和不定二次規(guī)劃的方法）;第三類(lèi)是運(yùn)用啟發(fā)式搜索或隨機(jī)搜索算法。例如模擬退火算法[4]、遺傳算法、神經(jīng)網(wǎng)絡(luò)算法、禁忌搜索算法、蟻群算法、粒子群算法，然而，這些算法都有一定的局限性。

另外，對(duì)全局優(yōu)化算法還進(jìn)行如下研究:

1）混合方法。綜合利用各種不同方法的優(yōu)點(diǎn)，構(gòu)造出性能比較良好的混合優(yōu)化方法。

2）并行算法?？紤]一種比較好的并行策略設(shè)計(jì)并行優(yōu)化算法，文獻(xiàn)[5-6]研究了一系列水平值估計(jì)算法，主要是采用一致分布的數(shù)值積分逼近水平集構(gòu)造實(shí)現(xiàn)算法。

受水平值下降算法思想的啟發(fā)，與傳統(tǒng)優(yōu)化算法-牛頓法相結(jié)合，針對(duì)多項(xiàng)式函數(shù)極小化問(wèn)題提出一種新的求解一維無(wú)約束全局優(yōu)化問(wèn)題的算法。主要思路是先找到最優(yōu)值的范圍，然后找到對(duì)應(yīng)的最優(yōu)解。算法不僅具有大范圍收斂性，而且收斂速度快。利用了多項(xiàng)式第二判別矩陣[7]降低了算法的整體復(fù)雜性，而且，由于其它所有函數(shù)都可以通過(guò)擬合等方法轉(zhuǎn)化為多項(xiàng)式函數(shù)求解，所以，文中對(duì)多項(xiàng)式函數(shù)全局優(yōu)化問(wèn)題算法的研究可推廣到其它函數(shù)。

考慮一維無(wú)約束全局最優(yōu)化問(wèn)題

式中:f（x）——多項(xiàng)式函數(shù)。

2 基本概念與基本定理

定義1 設(shè) f（x）=a0xn+a1xn-1+…+an，其導(dǎo)式記為:

定義矩陣

為多項(xiàng)式 f（x）的第二判別矩陣，記為Discr（f）。

定義2 設(shè) f（x）是一個(gè)n次多項(xiàng)式。f（x）的判別式序列 D1（f），D2（f），…，Dn（f）就是f（x）的第二判別矩陣Discr（f）的偶階順序主子式序列;f（x）的重因子序列Δ0（f），Δ1（f），…，Δn-1（f）就是 f（x）與 f′（x）的子結(jié)式多項(xiàng)式序列。

2.1 符號(hào)修訂規(guī)則

對(duì)于給定的有限個(gè)實(shí)數(shù)的序列l(wèi)1，l2，…，ln（l1≠0），寫(xiě)出相應(yīng)于這個(gè)序列的符號(hào)列 s1= sign（l1），s2=sign（l2），…，sn=sign（ln）。將[s1，s2，…，sn]叫做原序列的符號(hào)表。根據(jù)這個(gè)符號(hào)表可以定義一個(gè)符號(hào)修訂表[ε1，ε2，…，εn]，其構(gòu)造規(guī)則如下:

定理1 設(shè)σ0=1，σi=Dqi是n次多項(xiàng)式f（x）的判別多項(xiàng)式序列D1（f），D2（f），…，Dn（f）中第i個(gè)不等于零的項(xiàng)（i=1，…，k）。又設(shè)si=qi+1-qi-1（i=0，1，…，k-1;q0=0），判別式序列的符號(hào)修訂表的變號(hào)數(shù)為ν。如果Dl（f）≠0，Dm（f）=0（m＞l），那么:

1）f（x）的互異共軛虛根對(duì)的數(shù)目為ν。

2）f（x）的互異實(shí)根個(gè)數(shù)為

3）α是 f（x）的 m重根，當(dāng)且僅當(dāng) α是Δn-l（f）的m-1重根。

4）D1（f），D2（f），…，Dn（f）（除去一個(gè)正常數(shù)因子外）是無(wú)重根多項(xiàng)式 f/gcd（f，f′）的判別式序列。

2.2 牛頓法思想

設(shè)已知方程 f（x）=0有近似根 xk（假定f′（xk）≠0），將函數(shù) f（x）在點(diǎn) xk展開(kāi)，有

于是方程f（x）=0可近似地表示為

這是個(gè)線性方程，記其根為 xk+1，則xk+1的計(jì)算公式為

這就是牛頓法。

定義3 對(duì)于迭代過(guò)程xk+1=φ（xk），如果φ（p）（x）在所求根x*的鄰近連續(xù)，并且

則該迭代過(guò)程在點(diǎn)x*鄰近是p階收斂的。

3 主要結(jié)果

3.1 算法步驟

步驟1:任意選取一初始曲線y0=f（x0），允許誤差ε＞0，步長(zhǎng)λ0=1，令k:=0，zk=f（x）-yk;

步驟2:判斷zk=0是否有根，若有根，執(zhí)行步驟3，否則轉(zhuǎn)步驟4;

步驟3:令yk+1=yk-λk，k:=k+1，轉(zhuǎn)步驟2;

終止準(zhǔn)則:若λk≤ε，且zk=f（x）-yk=0有解，停止，計(jì)算zk=f（x）-yk=0，輸出k，yk，x*。

注:取x0∈（-∞，+∞），定義域f（x0）=y0。

3.2 算法收斂性分析

證明 如圖1中，兩條下降曲線之間的距離是步長(zhǎng)λ0，設(shè)算法進(jìn)行K次迭代的步長(zhǎng)均為λ0，那么，若算法再經(jīng)過(guò)n步結(jié)束，為方便這里n將記為k，則有

所以，k→∞，λk≤ε，即

圖1 水平值下降搜索示意圖

定理3 yk是由算法所得到的迭代點(diǎn)列，則有

設(shè)算法經(jīng)K次迭代后，有zk=f（x）-yk=0無(wú)根，即λk=λ0，那么設(shè)算法此后又經(jīng)過(guò)n次迭代滿足終止條件，有

令K+n=k，所以

定理4 文中最后一步的求解過(guò)程采用牛頓法，令{xk}是由算法得到的序列，則該算法收斂。

證明:對(duì)

其迭代函數(shù)為

由于

假定 x*是 f（x）的一個(gè)單根，則由上式知φ′（x*）=0，于是依據(jù)定義3可以斷定，牛頓法在根x*的鄰近是平方收斂的。

3.3 數(shù)值算例實(shí)現(xiàn)

例1:求x4-3x3+4x的極小值。

圖2 例1圖

取精度為 ε=10-4，最后的迭代步長(zhǎng)為1.220 7e-004，最小值 x（n）=-2.999 8，迭代16步可找到最優(yōu)值。最優(yōu)解為-0.593 1。

4 結(jié) 語(yǔ)

文中算法具有大范圍收斂性，利用了多項(xiàng)式判別矩陣，使算法的整體復(fù)雜性降低。同時(shí)與其它算法的差別之處是先尋找最優(yōu)值的范圍，可以判斷出最優(yōu)值的范圍（yk-λk，yk），最后求得最優(yōu)解。由于其它所有函數(shù)都可以通過(guò)擬合等方法轉(zhuǎn)化為多項(xiàng)式函數(shù)求解，所以文中對(duì)多項(xiàng)式函數(shù)全局優(yōu)化問(wèn)題算法的研究可推廣到其它函數(shù)。另外，文中方法經(jīng)過(guò)技術(shù)轉(zhuǎn)換還可推廣到一般n維空間的全局優(yōu)化問(wèn)題中，這是后續(xù)工作。

[1] 陳冬芳，薛繼偉，張漫.全局最優(yōu)化算法及其應(yīng)用[J].大慶石油學(xué)院學(xué)報(bào)，2005（1）:89-93.

[2] Ge R P.The theory of filled function methods for finding global minimizes of nonlinearly constrained minimization porblems[J].Journal of Computation Mathematics，1987，5（1）:129.

[3] Cetin B C，Barhen J，Burdick J W，et al.Terminal repeller un2constrained subenergy tanneling（TRUST）for fast global opti2mization[J].Journal of Optimization Theory and Applications，1993，77（1）:97-126.

[4] 刑文訓(xùn)，謝金星.現(xiàn)代優(yōu)化計(jì)算方法[M].北京:清華大學(xué)出版社，1999:90-138.

[5] 彭拯，張海東，鄔冬華.一種無(wú)約束全局優(yōu)化的水平值下降算法[J].應(yīng)用數(shù)學(xué)，2007，20（1）:213-219.

[6] 彭拯，鄔冬華，田蔚文.約束全局最優(yōu)化的水平值估計(jì)算法[J].計(jì)算數(shù)學(xué)，2007，29（3）:293-304.

[7] 楊路，張景中.侯曉榮.非線性代數(shù)方程組與定理機(jī)器證明[M].上海:上?？萍冀逃霭嫔?，1996:160-163，144-145.