劉勇為，胡劍峰，王平

（海南師范大學(xué)數(shù)學(xué)與統(tǒng)計(jì)學(xué)院，海南?？?71158）

基于投影神經(jīng)網(wǎng)絡(luò)求解凸規(guī)劃問(wèn)題的二分法

劉勇為，胡劍峰*，王平

（海南師范大學(xué)數(shù)學(xué)與統(tǒng)計(jì)學(xué)院，海南?？?71158）

將投影梯度神經(jīng)網(wǎng)絡(luò)方法和二分法相結(jié)合，提出了一種求解凸規(guī)劃的新算法，并證明了該算法的收斂性.

凸規(guī)劃；二分法；神經(jīng)網(wǎng)絡(luò)

近年來(lái)，用神經(jīng)網(wǎng)絡(luò)來(lái)解決優(yōu)化問(wèn)題已經(jīng)取得了很多重要的成果，其中很多已經(jīng)被應(yīng)用到優(yōu)化領(lǐng)域和工程控制中.

1985年，Tank和Hopfield[1]首次提出了一類神經(jīng)網(wǎng)絡(luò)模型來(lái)解決線性規(guī)劃問(wèn)題，但其平衡點(diǎn)不能保證收斂到線性規(guī)劃問(wèn)題的最優(yōu)點(diǎn).后來(lái)，Kennedy和Chua[2]提出了一類求解非線性規(guī)劃的神經(jīng)網(wǎng)絡(luò).該模型利用了罰函數(shù)，僅當(dāng)懲罰參數(shù)為無(wú)限大時(shí)，才有可能得到問(wèn)題的最優(yōu)解.為了避免使用罰參數(shù)，Zhang和Constantinides[3]基于Lagrange乘子法建立了求解約束優(yōu)化問(wèn)題的網(wǎng)絡(luò)模型，該模型在目標(biāo)函數(shù)是嚴(yán)格凸時(shí)能保證收斂到問(wèn)題的最優(yōu)解.

基于投影理論的投影神經(jīng)網(wǎng)絡(luò)最近被提出來(lái)用來(lái)解決一般凸規(guī)劃問(wèn)題，如：Liang[4]和Gao[5]建立了求解約束優(yōu)化問(wèn)題的投影神經(jīng)網(wǎng)絡(luò)模型；Yang[6]提出了凸規(guī)劃的投影神經(jīng)網(wǎng)絡(luò).本文在文獻(xiàn)[6]的基礎(chǔ)上，首先通過(guò)構(gòu)造Lyapunov函數(shù)和利用LaSalle不變?cè)?，給出了投影神經(jīng)網(wǎng)絡(luò)模型穩(wěn)定性和收斂性的一種新的證明過(guò)程；其次結(jié)合二分法的思想，提出一種求解凸規(guī)劃問(wèn)題的二分投影神經(jīng)網(wǎng)絡(luò)模型，并給出了算法的收斂性證明.

1 問(wèn)題和模型建立

考慮如下凸規(guī)劃問(wèn)題

其中，f

（x）和gi（x）（i=1，2，…，p）在Rn→R上是2階連續(xù)可微的凸函數(shù)，A∈Rm×n,b∈Rn和

對(duì)于問(wèn)題（1），考慮下面的子問(wèn)題[6]

和相應(yīng)的投影梯度神經(jīng)網(wǎng)絡(luò)

其中

2 投影神經(jīng)網(wǎng)絡(luò)穩(wěn)定性和收斂性分析

本節(jié)通過(guò)構(gòu)造Lyapunov函數(shù)和利用LaSalle不變?cè)?，給出了投影神經(jīng)網(wǎng)絡(luò)模型（3）的全局穩(wěn)定性和收斂性的一種新的證明過(guò)程.

證明令x*是問(wèn)題（2）的最優(yōu)解，考慮如下的Lyapunov函數(shù)

顯然V（x）是Ω上的連續(xù)可微的凸函數(shù)，并且對(duì)

根據(jù)投影理論和E（x，M1）是可微的凸函數(shù)，很容易得到

由此，可以得到神經(jīng)網(wǎng)絡(luò)（3）對(duì)于任意的初始點(diǎn)是Lyapunov意義下穩(wěn)定的.

證明（i）先證存在唯一連續(xù)解.

（ii）再證Ω是神經(jīng)網(wǎng)絡(luò)模型（3）的不變集，即

從而

（iii）最后證明x（t）在[t0，T）上是有界的.

令x*是問(wèn)題（2）的最優(yōu)解.由V（t）的定義及V（t）沿著軌線x（t）是不增的，有

從而有

因此，x（t）是有界的，故T=+∞.

綜合（i）、（ii）和（iii）即得到定理2的證明.

定理3令Ωe為神經(jīng)網(wǎng)絡(luò)（3）的平衡點(diǎn)集，Ω*為凸規(guī)劃問(wèn)題（2）的最優(yōu)解集，則Ωe=Ω*.

證明x*是凸規(guī)劃問(wèn)題（2）的最優(yōu)解，即x*∈Ω*，等價(jià)于

上式又等價(jià)于

故Ωe=Ω*.

根據(jù)LaSalle不變?cè)恚谑怯邢率匠闪?/p>

令

又因?yàn)閂1（x）是連續(xù)的，故有

而

3 基于投影神經(jīng)網(wǎng)絡(luò)的二分法

基于上一節(jié)的投影神經(jīng)網(wǎng)絡(luò)模型，結(jié)合二分法的思想，給出了一個(gè)求解問(wèn)題（1）的二分投影神經(jīng)網(wǎng)絡(luò)模型，并給出了算法的收斂性證明.

定理5設(shè)Lk和Uk分別是問(wèn)題（1）的最優(yōu)值的下界和上界，即，將帶入子問(wèn)題（2），得到相應(yīng)的神經(jīng)網(wǎng)絡(luò)模型（3）的平衡點(diǎn).如果，則有如果，則有

根據(jù)上面的定理5，給出了求解問(wèn)題（1）的二分投影神經(jīng)網(wǎng)絡(luò)算法.

算法1

定理6令x*是凸規(guī)劃問(wèn)題（1）的最優(yōu)解，L0和U0分別是問(wèn)題（1）的最優(yōu)值的下界和上界，則基于投影神經(jīng)網(wǎng)絡(luò)求解問(wèn)題（1）的二分法得到的序列滿足

證明對(duì)任意k≥0，有

而

而

故有

即

[1]Tank D W,Hopfield J J.Simple‘neural’optimization network:an A/D converter,signal decision circuit and a linear programming circuit[J].IEEE Trans Circuits Syst, 1986,33:533-541.

[2]Kennedy M P,Chua L O.Neural networks for nonlinear programming[J].IEEE Trans Circuits Syst,1988,35:554-562.

[3]Zhang S,Constantinides A.Lagrange programming neural networks[J].IEEE Transaction on Circuits and Systems-II:Analog and Digital Signal Processing,1992,39(7):441-452.

[4]Liang X,Wang J.A recurrent neural network for nonlin-ear optimization with a continuously differentiable objective functions and bound constraints[J].IEEE Transactions on Neural Networks,2000,11(6):1251-1262.

[5]Gao X.A novel neural network for nonlinear convex programming[J].IEEE Transactions on Neural Networks, 2004,15:613-621.

[6]Yang Y,Cao J.A feedback neural network for solving convex constraint optimization problems[J].Appl Math Comput,2008,201:340-350.

責(zé)任編輯：畢和平

A Bisection Method for Convex Programming Based on the Projection Neural Network

LIU Yongwei，HU Jianfeng＊，WANG Ping
（College of Mathematics and Statistics，Hainan Normal University，Haikou 571158，China）

In this paper,a new algorithm for convex programming is proposed by combining projection neural network with bisection method.The convergence of the algorithm is proved.

convex programming；bisection method；neural network

O 221.1

A

1674-4942（2014）01-0015-03

2013-10-25

*通訊作者