于金金，呂一兵

(長江大學(xué)信息與數(shù)學(xué)學(xué)院，湖北 荊州 434023)

極大極小問題是一類重要的不可微優(yōu)化問題，許多工程設(shè)計(jì)問題都可以轉(zhuǎn)化這一問題[1～3]，因此，研究極大極小問題的有效解法具有非常重要的理論和實(shí)用價(jià)值。

目前，國內(nèi)外許多研究者已經(jīng)設(shè)計(jì)了求解極大極小問題的可行算法。C.Charalambous和A.R.Conn[4]提出了直線搜索法，其思路是將極大極小問題轉(zhuǎn)化為與之等價(jià)的非線性約束優(yōu)化問題，然后計(jì)算2個(gè)搜索方向(水平方向和垂直方向)，并在較強(qiáng)的條件下證明了算法的全局收斂性。文獻(xiàn)[5]每步通過求解2個(gè)QP子問題，并結(jié)合非單調(diào)直線搜索，克服了Maratos效應(yīng)，得到了全局收斂性和兩步超線性收斂的算法。文獻(xiàn)[6]采用信賴域和SQP方法相結(jié)合的技術(shù)將文獻(xiàn)[5]的方法推廣到了約束極大極小問題。A.Vardi[7]采用有效集策略，將極大極小問題轉(zhuǎn)化為與之等價(jià)的非線性等式約束優(yōu)化問題，并結(jié)合信賴域方法設(shè)計(jì)了相應(yīng)的求解算法，同時(shí)證明了算法的下降性，但缺少完整的全局收斂性證明。

神經(jīng)網(wǎng)絡(luò)具有大規(guī)模并行處理及快速收斂的特性，這為優(yōu)化問題的算法設(shè)計(jì)提供了一種新的思路。自J.J.Hopfield提出神經(jīng)優(yōu)化的思想以來[8,9], 用其求解優(yōu)化問題受到了越來越多學(xué)者的關(guān)注。文獻(xiàn)[10]基于罰函數(shù)求解約束優(yōu)化問題的神經(jīng)網(wǎng)絡(luò)模型，當(dāng)罰函數(shù)足夠大時(shí)，可以獲得原問題的可行解或近似最優(yōu)解；文獻(xiàn)[11]基于Lagrange乘子法建立了求解約束優(yōu)化問題的神經(jīng)網(wǎng)絡(luò)模型，該模型總能收斂于一個(gè)可行解；文獻(xiàn)[12]基于最優(yōu)性充要條件建立了神經(jīng)網(wǎng)絡(luò)模型，并通過構(gòu)造Lyapunov函數(shù)，證明了神經(jīng)網(wǎng)絡(luò)的穩(wěn)定性。但采用神經(jīng)網(wǎng)絡(luò)方法求解極大極小問題的文獻(xiàn)目前還不多見，為此，筆者考慮利用神經(jīng)網(wǎng)絡(luò)方法求解極大極小問題：將極大極小問題的數(shù)學(xué)模型轉(zhuǎn)化為相應(yīng)的神經(jīng)網(wǎng)絡(luò)模型，分析神經(jīng)網(wǎng)絡(luò)模型的穩(wěn)定性和收斂性。

1 非線性極大極小問題

考慮如下非線性極大極小問題：

(1)

式中：fi(x)為光滑實(shí)值函數(shù)；φ(x)稱為最大值函數(shù)。

因?yàn)棣?x)在函數(shù)的交點(diǎn)處具有不連續(xù)一階導(dǎo)數(shù)，因此問題(1)是一個(gè)不可微的無約束優(yōu)化問題。由文獻(xiàn)[4]、[13]和[14]可知，問題(1)等價(jià)于如下非線性規(guī)劃問題：

(2)

式中：z是一個(gè)引進(jìn)的新的獨(dú)立變量；gi:Rn→Rm為連續(xù)可微函數(shù)。

2 神經(jīng)網(wǎng)絡(luò)模型的構(gòu)造

采用Lagrange乘子法構(gòu)造問題(2)的神經(jīng)網(wǎng)絡(luò)模型。

定義1 令I(lǐng)(x*,z*)={i|gi(x*,z*)=0,i=1,2,…,m}，如果梯度▽gi(x*,z*)線性無關(guān),i∈I(x*,z*), 則稱點(diǎn)(x*,z*)為問題(2)的正則點(diǎn)。

記問題(2)的Lagrange函數(shù)為：

L(x,z,u)=z+uΤg(x,z)u

式中：u∈Rm是Lagrange乘子。

注：為避免不等式約束額外增加變量，定義的Lagrange函數(shù)將不等式約束的乘子取為u2。

定理1 假設(shè)(x*,z*)是(2)的局部極小點(diǎn)，且(x*,z*)是正則點(diǎn)，則存在u*使得：

且對(duì)任何y≠0,y∈Y(x*,z*)，Y(x*,z*)={y|yΤ▽gi(x*,z*)=0,i∈I(x*,z*)}，有：

定義2 滿足定理1的點(diǎn)(x*,z*,u*)稱為問題(2)的Kuhn-Tucker點(diǎn)。

定理2 假設(shè)(x*,z*)滿足約束條件，且存在u*使得:

且滿足嚴(yán)格互補(bǔ)性條件，即u*≠0，?i∈I(x*,z*)，如果對(duì)任何y≠0，y∈Y(x*,z*)有：

則(x*,z*)是問題(2)的局部嚴(yán)格極小點(diǎn)。

定理1與定理2的證明與文獻(xiàn)[15]類似定理的證明相同，這里不再重復(fù)。

定義3 如果對(duì)任何x∈Rn,u∈Rm,z∈Rm有：

L(x*,z*,u)≤L(x*,z*,u*)≤L(x,z,u*)

則稱Lagrange函數(shù)L(x,z,u)在(x*,z*,u*)具有鞍點(diǎn)性質(zhì)，且(x*,z*,u*)稱為L(x,z,u)的鞍點(diǎn)。

構(gòu)造問題(2)的神經(jīng)網(wǎng)絡(luò)模型如下:

(3)

按照求解過程中的作用不同，可將神經(jīng)網(wǎng)絡(luò)的神經(jīng)元分為變量神經(jīng)元x、z和Lagrange神經(jīng)元u。從網(wǎng)絡(luò)的狀態(tài)方程可以看出，沿著神經(jīng)網(wǎng)絡(luò)的軌跡Lagrange函數(shù)總是隨x、z減少,隨u增加。當(dāng)網(wǎng)絡(luò)演化到穩(wěn)態(tài)時(shí)，有：

也就是說神經(jīng)網(wǎng)絡(luò)的漸近穩(wěn)定點(diǎn)(x*,z*,u*)是Lagrange函數(shù)的鞍點(diǎn)。

定義4 如果(x*,z*,u*)滿足：

▽xL(x*,z*,u*)=0 ▽zL(x*,z*,u*)=0 ▽uL(x*,z*,u*)=0

則稱(x*,z*,u*)是神經(jīng)網(wǎng)絡(luò)的平衡點(diǎn)。

3 穩(wěn)定性分析

定理3 設(shè)(x*,z*,u*)是神經(jīng)網(wǎng)絡(luò)(3)的平衡點(diǎn)，且(x*,z*)是正則點(diǎn)，則(x*,z*,u*)是神經(jīng)網(wǎng)絡(luò)的漸近穩(wěn)定點(diǎn)。

證明 神經(jīng)網(wǎng)絡(luò)(3)的能量函數(shù)定義為：

能量函數(shù)E對(duì)時(shí)間t的微分為：

4 數(shù)值試驗(yàn)

首先將其轉(zhuǎn)化為一般的非線性規(guī)劃問題，其Lagrange函數(shù)為：

然后，構(gòu)造相應(yīng)的神經(jīng)網(wǎng)絡(luò)模型，采用四階Runge-Kutta法求解相應(yīng)的常微分方程組，得到最優(yōu)解(x1,x2)=(0.5,-2.0). 變量x1和x2隨迭代次數(shù)的變化情況如圖1所示。

首先將其轉(zhuǎn)化為一般的非線性規(guī)劃問題，其Lagrange函數(shù)為：

然后，構(gòu)造相應(yīng)的神經(jīng)網(wǎng)絡(luò)模型，采用四階Runge-Kutta方法求解相應(yīng)的常微分方程組，得到最優(yōu)解(x1,x2)=(1,1). 變量x1和x2隨迭代次數(shù)的變化情況如圖2所示。

圖1 算例1變量隨迭代次數(shù)的變化情況 圖2 算例2變量隨迭代次數(shù)的變化情況

上述2個(gè)算例表明，利用神經(jīng)網(wǎng)絡(luò)方法可以有效地求解極大極小問題。另外，在利用Runge-Kutta方法求解相應(yīng)的神經(jīng)網(wǎng)絡(luò)模型時(shí)，初始值的選取對(duì)算法的收斂性起著關(guān)鍵作用。初始值選擇恰當(dāng)，則可以較為迅速的收斂到最優(yōu)解。

5 結(jié)語

利用神經(jīng)網(wǎng)絡(luò)方法求解極大極小問題，采用Lagrange乘子法得到了一種非線性規(guī)劃神經(jīng)網(wǎng)絡(luò)模型，該神經(jīng)網(wǎng)絡(luò)的優(yōu)點(diǎn)在于可直接處理不等式約束，不用增加松弛變量。該方法可較為有效地減少神經(jīng)網(wǎng)絡(luò)的復(fù)雜度，數(shù)值試驗(yàn)結(jié)果表明了該方法的可行性。此外，筆者提出的神經(jīng)網(wǎng)絡(luò)模型只是具有漸進(jìn)穩(wěn)定性的特征，如何設(shè)計(jì)具有全局收斂性的神經(jīng)網(wǎng)絡(luò)模型，還值得進(jìn)一步研究。