基于動(dòng)力系統(tǒng)求非線性?xún)?yōu)化的局部最優(yōu)解

張 娜

(天津大學(xué) 理學(xué)院，天津 300072)

基于動(dòng)力系統(tǒng)求非線性?xún)?yōu)化的局部最優(yōu)解

張 娜

(天津大學(xué) 理學(xué)院，天津 300072)

根據(jù)目標(biāo)函數(shù)的拓?fù)浜蛶缀涡再|(zhì)求函數(shù)的多個(gè)局部最優(yōu)解，建立相關(guān)的梯度向量場(chǎng)，求梯度向量場(chǎng)的穩(wěn)定均衡點(diǎn)，穩(wěn)定均衡點(diǎn)就是相應(yīng)目標(biāo)函數(shù)的局部最優(yōu)解，通過(guò)退化點(diǎn)使梯度向量場(chǎng)跳出穩(wěn)定均衡點(diǎn)的穩(wěn)定域，在本文中對(duì)求退化點(diǎn)的算法進(jìn)行改進(jìn)，求非線性?xún)?yōu)化的多個(gè)局部最優(yōu)解.

梯度向量場(chǎng)；穩(wěn)定均衡點(diǎn) ；穩(wěn)定域；退化點(diǎn)

近年來(lái)隨著社會(huì)的高速發(fā)展，全局優(yōu)化問(wèn)題在社會(huì)上有很廣泛的應(yīng)用,它已經(jīng)融入我們的日常生活之中，對(duì)社會(huì)的高速發(fā)展有非常重要的作用.全局最優(yōu)化問(wèn)題廣泛存在于分子生物學(xué)、經(jīng)濟(jì)金融、數(shù)據(jù)挖掘與知識(shí)發(fā)現(xiàn)、環(huán)境工程、網(wǎng)絡(luò)運(yùn)輸、圖像處理與模式識(shí)別、化學(xué)工程設(shè)計(jì)、工業(yè)制造等眾多領(lǐng)域，因此受到人們的普遍關(guān)注，隨著全局最優(yōu)化問(wèn)題的廣泛應(yīng)用，在實(shí)際生活中，存在著很多的、非常有意義的全局優(yōu)化模型，然而，全局最優(yōu)化的困難主要在于，很難跳出當(dāng)前的局部最優(yōu)解，得到其全局最優(yōu)解.而傳統(tǒng)的非線性規(guī)劃方法卻很難應(yīng)用于全局優(yōu)化問(wèn)題，因此，全局最優(yōu)化成為了學(xué)者研究的熱點(diǎn)之一，隨著計(jì)算機(jī)技術(shù)的進(jìn)步，全局最優(yōu)化得到了快速的發(fā)展，許多全局最優(yōu)化的理論及算法也相應(yīng)地得到發(fā)展.

H·D·Chiang運(yùn)用目標(biāo)函數(shù)的拓?fù)浜蛶缀涡再|(zhì)求非線性函數(shù)的多個(gè)局部最優(yōu)[1]，這個(gè)方法構(gòu)造了相關(guān)的梯度向量場(chǎng)，用梯度向量場(chǎng)的多個(gè)穩(wěn)定均衡點(diǎn)作為目標(biāo)函數(shù)的局部最優(yōu)解，給定一個(gè)初始點(diǎn)數(shù)值積分梯度向量場(chǎng)求出一個(gè)穩(wěn)定均衡點(diǎn)，通過(guò)退化點(diǎn)跳出穩(wěn)定均衡點(diǎn)的穩(wěn)定域，然后沿著退化點(diǎn)的不穩(wěn)定流形的反方向運(yùn)動(dòng)到另一個(gè)穩(wěn)定均衡點(diǎn)，重復(fù)上述過(guò)程，找到多個(gè)穩(wěn)定均衡點(diǎn)，這些穩(wěn)定均衡點(diǎn)就是局部最優(yōu)解，在本文中對(duì)求退化點(diǎn)的算法進(jìn)行改進(jìn)，使算法更加簡(jiǎn)練易懂.

1 定義和概念

本文用一個(gè)系統(tǒng)的方法求非線性?xún)?yōu)化的多個(gè)局部最優(yōu)解，它在本質(zhì)上是確定性方法.給定一個(gè)目標(biāo)函數(shù)，建立這個(gè)函數(shù)相關(guān)的向量場(chǎng)，使得向量場(chǎng)的軌跡收斂到相應(yīng)的局部最優(yōu)解.

考慮下面的無(wú)約束全局優(yōu)化問(wèn)題

min{f(x):x∈Rn}

(1)

其中：f∈C2.假設(shè)函數(shù)f(x)是有下界的使得函數(shù)的全局極小值點(diǎn)存在并且局部極小值點(diǎn)的個(gè)數(shù)是有限的.

建立與目標(biāo)函數(shù)f(x)相關(guān)的梯度向量場(chǎng)[2]

(2)

考慮如下非線性動(dòng)力系統(tǒng)

(3)

其中：動(dòng)力系統(tǒng)的向量x(t)屬于歐幾里得空間Rn，函數(shù)f:Rn→Rn滿(mǎn)足解存在性和惟一性的充分條件，稱(chēng)系統(tǒng)(3)在t=0時(shí)刻的解曲線x為軌跡，表示為Φ(x,·)：R→Rn.

雙曲穩(wěn)定均衡點(diǎn)xs的穩(wěn)定域表示為：

穩(wěn)定域A(xs)的邊界稱(chēng)為xs的穩(wěn)定邊界，用?A(xs)表示.實(shí)用穩(wěn)定域(practical stability region)是穩(wěn)定域一個(gè)子集，實(shí)用穩(wěn)定域在求多個(gè)局部最優(yōu)解中有非常重要的應(yīng)用，穩(wěn)定均衡點(diǎn)xs的實(shí)用穩(wěn)定域表示為Ap(xs)，它是開(kāi)集intA(xs)，退化點(diǎn)是在實(shí)用穩(wěn)定邊界上的1類(lèi)型均衡點(diǎn).

2 系統(tǒng)的方法

由上節(jié)的內(nèi)容可知函數(shù)f(x)的局部最優(yōu)解和(2)的均衡點(diǎn)是等價(jià)的，系統(tǒng)的求多個(gè)局部最優(yōu)解的方法包括如下幾步：

1)找到一個(gè)局部最優(yōu)解.

2)從局部最優(yōu)解出發(fā)，沿著函數(shù)值增加的方向移動(dòng)到一個(gè)退化點(diǎn).

3)沿著退化點(diǎn)的不穩(wěn)定流形的反方向移動(dòng)并且下降到另一個(gè)局部最優(yōu)解.

第一步可以由下降法求解，第二步非常有挑戰(zhàn)性，在下一節(jié)中有詳細(xì)的介紹，第三步涉及到負(fù)梯度系統(tǒng)的數(shù)值積分.

基于理論的觀點(diǎn)，上述的方法可以建立一個(gè)圖G描述局部最小點(diǎn)和退化點(diǎn)的聯(lián)系，需要下面的元素：

算法1：求多個(gè)局部極小值點(diǎn)

第1步：初始化數(shù)據(jù)

步驟1：令Vmin=Vd=v=φ

步驟2：找一個(gè)初始點(diǎn)x0

步驟3：令ε充分小

第2步：找第一個(gè)局部極小值點(diǎn)

第3步：建立相應(yīng)的圖G

WhileV≠φdo

Begin

選擇x∈V,令V=V{x}

Else

計(jì)算J-▽f(x)的不穩(wěn)定特征向量Eu，數(shù)值計(jì)算負(fù)梯度-▽f(x)初始點(diǎn)分別為x+εEu和x+εEu直到它們達(dá)到穩(wěn)定均衡點(diǎn)y1和y2

令V=V∪({y1,y2}Vmin)

Vmin=Vmin∪{y1,y2}

E=E∪{(x,y1),(x,y2)}

End

我們建立函數(shù)相關(guān)的反射梯度系統(tǒng)，通過(guò)一階反射梯度系統(tǒng)求退化點(diǎn)，一階反射梯度向量場(chǎng)F1(x)[4]使f(x)局部極小值點(diǎn)鄰域內(nèi)的點(diǎn)收斂到它穩(wěn)定邊界上的1類(lèi) 均衡點(diǎn).可以用下面的方式檢驗(yàn)1類(lèi)均衡點(diǎn)是否是退化點(diǎn)：沿著1類(lèi)均衡點(diǎn)的Jacobian矩陣的不穩(wěn)定特征向量的兩個(gè)方向積分準(zhǔn)梯度系統(tǒng)，如果收斂到兩個(gè)不同的均衡點(diǎn)，則這個(gè)1類(lèi)均衡點(diǎn)是退化點(diǎn).

算法2：求退化點(diǎn)

第一步：初始化數(shù)據(jù)

步驟2：選擇一個(gè)充分大的迭代區(qū)間T

步驟3：令ε充分小

第二步：找退化點(diǎn)

Forj=1 topdo

步驟3：檢驗(yàn)負(fù)梯度向量場(chǎng)-▽f(x)=0均衡點(diǎn)的類(lèi)型：

如果nj是1類(lèi)均衡點(diǎn)，計(jì)算J-▽f(x)(nj)的不穩(wěn)定特征向量Eu，數(shù)值積分負(fù)梯度系統(tǒng)(2)，初始點(diǎn)為nj+εEu和nj-εEu直到它們分別到達(dá)均衡點(diǎn)y1和y2

如果y1≠y2,D=D∪{nj}，

End

3 數(shù)值檢驗(yàn)

用上述算法求下例的局部極小點(diǎn)

相關(guān)的負(fù)梯度系統(tǒng)為：

算法結(jié)束后，我們發(fā)現(xiàn)目標(biāo)函數(shù)有6個(gè)局部極小值和7個(gè)退化點(diǎn)，結(jié)果在表2中，比較局部極小值點(diǎn)的函數(shù)值，可以得到函數(shù)的全局極小值點(diǎn)為和，全局極小值為-1.0316.

表1 每次迭代的變量值

步驟初始點(diǎn)新的頂點(diǎn)VVminVd1(0．5，0．5)x1s=(-0．0899，0．7126)x1cx1c?2x1sx1d=(0，0)x2d=(1．2961，0．6051)x1d，x2d，x3dx1sx1d，x2d，x3d3x1dx2s=(0．0898，-0．7126)x2s，x2d，x3dx1s，x2sx1d，x2d，x3d4x2sx4d=(1．1092，-0．7683)x5d=(-1．12961，-0．6051)x2d，x3d，x4d，c5dx1s，x2sx1d，x2d，x3d，x4d，x5d5x1dx3d=(1．6071，0．5687)x3s，x3d，x4d，x5dx1s，x2s，x3sx1d，x2d，x3d，x4d，x5d6x3sx6d=(1．6381，0．2287)x3s，x4d，x5d，x6dx1s，x2s，x3sx1d，x2d，x3d，x4d，x5d，x6d7x3dx4s=(-1．7036，0．7961)x4s，x5d，x6d，x4dx1s，x2s，x3s，x4sx1d，x2d，x3d，x4d，x5d，x6d8x4dx5s=(-1．6071，-0．5687)x5d，x6d，x4s，x5sx1s，x2s，x3s，x4s，x5sx1d，x2d，x3d，x4d，x5d，x6d

續(xù)表

步驟初始點(diǎn)新的頂點(diǎn)VVminVd9x4s?x5d，x6d，x5sx1s，x2s，x3s，x4s，x5sx1d，x2d，x3d，x4d，x5d，x6d10x5d?x6d，x5sx1s，x2s，x3s，x4s，x5sx1d，x2d，x3d，x4d，x5d，x6d11x5sx7d=(-1．2961，-0．6051)x6d，x7dx1s，x2s，x3s，x4s，x5sx1d，x2d，x3d，x4d，x5d，x6d，x7d11x6dx6s=(1．7036，-0．7961)x6s，x7dx1s，x2s，x3s，x4s，x5s，x6sx1d，x2d，x3d，x4d，x5d，x6d，x7d13x6s?x7dx1s，x2s，x3s，x4s，x5sx1d，x2d，x3d，x4d，x5d，x6d，x7d14x7d??x1s，x2s，x3s，x4s，x5sx1d，x2d，x3d，x4d，x5d，x6d，x7d

表2 局部極小值點(diǎn)和退化點(diǎn)

局部最小值點(diǎn)f(·)退化點(diǎn)x1s=(-0．0898，0．7126)-1．0316x1d=(0．0)x2s=(0．0898，-0．7126)-1．0316x2d=(1．2961，0．6051)x3s=(1．6071，0．5687)2．1403x3d=(-1．1092，0．7683)x4s=(-0．7036，0．7961)-0．2155x4d=(1．1092，-0．7683)x5s=(-1．6071，-0．5687)2．1403x5d=(-1．2961，-0．6051)x6s=(1．7036，-0．7961)-0．2155x6d=(1．6381，0．2287)x7d=(-1．2961，-0．6051)

4 結(jié) 語(yǔ)

在本文中，用動(dòng)力系統(tǒng)求非線性函數(shù)的多個(gè)局部極小值點(diǎn)，在算法1中的第二步，本文中用擬牛頓法求局部極小值點(diǎn)，相比以前積分的方法更簡(jiǎn)單精確度更高，在算法2中，本文求的零點(diǎn)，這個(gè)方法更直觀便于理解，通過(guò)準(zhǔn)梯度系統(tǒng) 和反射梯度系統(tǒng)之間的轉(zhuǎn)換可以求出多個(gè)局部極小值點(diǎn)和退化點(diǎn)，通過(guò)比較局部極小值點(diǎn)的值可以得到全局極小值點(diǎn).最后需要進(jìn)一步改進(jìn)的是如何得到所有的退化點(diǎn).

[1] ALBERTO L F C, CHIANG H D, Characerization of stability region for general autonomous nonlinear dynamical systems [J]. IEEE Tran. Automat Contr, 2012, 57(6): 1564-1569.

[2] DEMARCO C I. Approximating power system dynamics and energy functions by quasi-gradient models [J]. Intern. Sympos. on Circuits and Systems, 1989, 2: 1966-1969.

[3] HIRSH M W, SMALE S. Differential equation, dynamical systems and linear algebra [M]. New York：Academic.1974.

[4] JONGEN H T, JONKER P, TWILT F. Nonlinear optimization in RN [M]. Verlag Peter Lang, 1986. 102-103

[5] 嚴(yán)太山,崔杜武.求解無(wú)約束優(yōu)化問(wèn)題的知識(shí)進(jìn)化算法及其收斂性分析[J]. 控制理論與應(yīng)用, 2010, 27(10): 1376-1382.

Obtaining local optimal solutions of nonlinear programming problems based on gradient system

ZHANG Na

(School of Science, Tianjin University, Tianjin 300072, China)

According to the topological and geometric properties of the objective function the multiple local optimal solutions were solved, and relevant gradient vector field of the function was established. The stable equilibrium of the gradient vector field was the local optimal solution of the corresponding objective function. Through degradation point of gradient vector field seeks for the stable equilibrium. This paper improved the method of degradation point algorithm and solve nonlinear optimization of multiple locally optimal solutions.

stable equilibrium point; gradient vector field; stability region; degradation point

2014-12-04.

張 娜(1991-)，女，碩士，研究方向：動(dòng)力系統(tǒng)與優(yōu)化.

O224

A

1672-0946(2015)06-0744-04