基于動力系統求非線性優化的局部最優解

張 娜

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

基于動力系統求非線性優化的局部最優解

張 娜

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

根據目標函數的拓撲和幾何性質求函數的多個局部最優解，建立相關的梯度向量場，求梯度向量場的穩定均衡點，穩定均衡點就是相應目標函數的局部最優解，通過退化點使梯度向量場跳出穩定均衡點的穩定域，在本文中對求退化點的算法進行改進，求非線性優化的多個局部最優解.

梯度向量場；穩定均衡點 ；穩定域；退化點

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

H·D·Chiang運用目標函數的拓撲和幾何性質求非線性函數的多個局部最優[1]，這個方法構造了相關的梯度向量場，用梯度向量場的多個穩定均衡點作為目標函數的局部最優解，給定一個初始點數值積分梯度向量場求出一個穩定均衡點，通過退化點跳出穩定均衡點的穩定域，然后沿著退化點的不穩定流形的反方向運動到另一個穩定均衡點，重復上述過程，找到多個穩定均衡點，這些穩定均衡點就是局部最優解，在本文中對求退化點的算法進行改進，使算法更加簡練易懂.

1 定義和概念

本文用一個系統的方法求非線性優化的多個局部最優解，它在本質上是確定性方法.給定一個目標函數，建立這個函數相關的向量場，使得向量場的軌跡收斂到相應的局部最優解.

考慮下面的無約束全局優化問題

min{f(x):x∈Rn}

(1)

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

建立與目標函數f(x)相關的梯度向量場[2]

(2)

考慮如下非線性動力系統

(3)

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

雙曲穩定均衡點xs的穩定域表示為：

穩定域A(xs)的邊界稱為xs的穩定邊界，用?A(xs)表示.實用穩定域(practical stability region)是穩定域一個子集，實用穩定域在求多個局部最優解中有非常重要的應用，穩定均衡點xs的實用穩定域表示為Ap(xs)，它是開集intA(xs)，退化點是在實用穩定邊界上的1類型均衡點.

2 系統的方法

由上節的內容可知函數f(x)的局部最優解和(2)的均衡點是等價的，系統的求多個局部最優解的方法包括如下幾步：

1)找到一個局部最優解.

2)從局部最優解出發，沿著函數值增加的方向移動到一個退化點.

3)沿著退化點的不穩定流形的反方向移動并且下降到另一個局部最優解.

第一步可以由下降法求解，第二步非常有挑戰性，在下一節中有詳細的介紹，第三步涉及到負梯度系統的數值積分.

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

算法1：求多個局部極小值點

第1步：初始化數據

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

步驟2：找一個初始點x0

步驟3：令ε充分小

第2步：找第一個局部極小值點

第3步：建立相應的圖G

WhileV≠φdo

Begin

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

Else

計算J-▽f(x)的不穩定特征向量Eu，數值計算負梯度-▽f(x)初始點分別為x+εEu和x+εEu直到它們達到穩定均衡點y1和y2

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

Vmin=Vmin∪{y1,y2}

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

End

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

算法2：求退化點

第一步：初始化數據

步驟2：選擇一個充分大的迭代區間T

步驟3：令ε充分小

第二步：找退化點

Forj=1 topdo

步驟3：檢驗負梯度向量場-▽f(x)=0均衡點的類型：

如果nj是1類均衡點，計算J-▽f(x)(nj)的不穩定特征向量Eu，數值積分負梯度系統(2)，初始點為nj+εEu和nj-εEu直到它們分別到達均衡點y1和y2

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

End

3 數值檢驗

用上述算法求下例的局部極小點

相關的負梯度系統為：

算法結束后，我們發現目標函數有6個局部極小值和7個退化點，結果在表2中，比較局部極小值點的函數值，可以得到函數的全局極小值點為和，全局極小值為-1.0316.

表1 每次迭代的變量值

步驟初始點新的頂點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

續表

步驟初始點新的頂點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 局部極小值點和退化點

局部最小值點f(·)退化點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 結 語

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

[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] 嚴太山,崔杜武.求解無約束優化問題的知識進化算法及其收斂性分析[J]. 控制理論與應用, 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-)，女，碩士，研究方向：動力系統與優化.

O224

A

1672-0946(2015)06-0744-04