一种解决非光滑非凸优化问题的暂态混沌神经网络

喻 昕，汪炎林，徐柳明，伍灵贞

(广西大学 计算机与电子信息学院，南宁 530004)

1 前 言

在科学与工程应用中，优化问题作为一类重点问题在最近几十年内得到了广泛的关注与发展.在1986年，由Hopfield 和 Tank[1]提出一种Hopfield神经网络(Hopfield Neural Network,HNN)作为解决优化问题的并行计算模型，引起了大家的兴趣并开始广泛应用.Zhang等人[2]利用Lagarange乘子法创建了一个新的递归神经网络来处理凸光滑非线性优化问题，Xia等人[3]提出了基于投影方法的递归神经网络用以解决光滑凸(伪凸)优化问题.

不久后，应用范围从光滑问题发展到非光滑优化问题，如Li等人[4]在基于Clark次梯度的递归神经网络模型之中引入投影方法以解决n上闭凸子集的非凸非光滑优化问题.Liu等人[5]尝试投影方法建立递归神经网络模型解构线性等式和n上闭凸子集共同约束的非光滑非凸优化问题.Bian等人[6]也开始利用光滑递归神经网络来解决非光滑非凸的优化问题，使用光滑逼近技术即用一个与目标函数逼近的光滑函数构造光滑神经网络模型.Yu等人[7]基于微分包含的思想，建立了一个不依赖罚参数的神经网络模型用以解决非光滑非凸优化问题.

然而上述的模型的本质仍是基于“梯度”或“次梯度”下降的动力系统，无法避免“陷入”局部最优解.尤其是当优化的目标函数是非凸时会存在多处局部最优解，这将无法保证获得全局最优解.

为了解决这个问题，Aihara等人[8]受生物神经元混沌特性的启发，于1990年在HNN中增加一个自反馈项以引入混沌机制开创了混沌神经网络(Chaotic Neural Network,CNN).此后，Chen和Aihara[9]将模拟退火优化算法引入到CNN中提出了暂态混沌神经网络(Transiently Chaotic Neural Network,TCNN).TCNN的动力系统对自反馈链接权值敏感，它可以类比模拟退火算法中一直衰减的温度.当“温度”较大时，整个系统处于“粗搜索”阶段,搜索过程符合混沌动态的特性，会按照混沌轨道进行遍历，并且不受目标函数的限制，能克服陷入局部最优解；当“温度”开始减少并达到一定程度时，系统进入“细搜索”阶段，这时的自反馈权值对系统的影响变得很小，这时的神经网络类似于HNN，以粗搜索得到的解为初始点，根据HNN梯度下降机制在小范围进行搜索，并收敛到一个平衡点，最终TCNN会收敛到一个全局最优解.

TCNN提出后，不少学者对此展开研究.文献[10，11]分别将TCNN应用于解决组播路由和蜂窝信道分配等组合优化问题；Zhang等人[12]利用小波函数作为激活函数的TCNN来解决函数优化问题；Babak等人[13]利用TCNN改进了反应曲面法在函数优化问题中应用的性能.

借助脑电波的生物机制，分析不同频率的正弦信号叠加形成的脑电波模型,Hu等人[14]用变频正弦(Frequency Conversion Sinusoidal,FCS)函数与 Sigmoid 函数加权和作为混沌神经元的激励函数,建立了一个新的神经网络模型 —变频正弦混沌神经网络(Frequency Conversion Sinusoidal Chaotic Neural Network,FCSCNN)模型，并在文献[15，16]进一步分析和优化了这种新的模型.

综上，为了解决非凸非光滑优化问题，本文提出一个能收敛到优化问题关键点集的递归神经网络，并在此基础上构建了一个暂态混沌神经网络，用于实现非凸优化问题的全局寻优.

2 预备知识

考虑如下问题:

minf(x)s.t.g(x)≤0Ax=b

(1)

当x=(x1,x2,…,xn)T∈n，f:n→，目标函数是正则的，但可以是非凸的和非光滑的，g(x)=(g1(x),g2(x),…,gp(x))T:n→p是p-维向量值函数，gj(x)(j=1,2,…,p)是凸的，但可能是非光滑的，A∈m×n是满行秩矩阵，而且b=(b1,b2,…,bm)T∈m.我们假设优化问题(1)具有至少一个局部最小解.

定义：

S1={x:g(x)≤0}

S2={x:Ax=b}

则S=S1∩S2，S={x∈n:g(x)≤0,Ax=b}是优化问题(1)的可行域.

为便于后续的证明，首先给出下面两个假设：

这里:

J+(x)={j∈{1,2,…,p}:gj(x)>0}J0(x)={j∈{1,2,…,p}:gj(x)=0}

定义1.若对于集合E⊂Rn上的任意点x，都存在一个非空集合F(x)⊂Rn，则x→F(x)是E→Rn上的集值映射.若对于任意的开集V⊃F(x0)，都有一个相应的邻域U，使得F(U)⊂V，则称集值映射F:E→Rn在点x0∈E是上半连续.

定义2.如果存在正整数k，ε，对任意的x1,x2∈x+εB(0,1)，|f(x1)-f(x2)|≤k(x1-x2)成立，则称函数f:Rn→R在x∈Rn附近是Lipschitz的，如果f在其定义域每一个点的附近都是Lipschitz的，则称f为局部Lipschitz的.

定义3.如果f:Rn→R在Rn上是局部Lipschitz的，则f在点x沿方向v∈Rn的广义方向导数为：

如果f0(x;v)是有定义且有限的，f在x处的次微分可以定义为：

∂f(x)={ξ∈Rn:f0(x;v)≥,∀v∈Rn}

引理1(链式法则).

本文提出的神经网络动力学模型:

(2)

这里α是一个正比例罚参数，I是一个单位矩阵，P=AT(AAT)-1A.

函数β(t)是一个单调非减的函数，其形式如下：

tS2为进入可行域S2的时间上限.

3 收敛性分析

1)有限时间收敛到S2

定理1.若假设1,2成立，则从任意点x0∈Rn出发，神经网络(2)的状态向量将在有限时间收敛进S2，其后不再离开.

证明：令K(x)=‖Ax(t)-b‖1，则K(x)是正则函数且∂K(x)=ATh(Ax(t)-b).根据链式法则，存在ψ(t)∈h(Ax(t)-b)，θ(t)∈∂f(x)，σ(t)∈∂D(x)，使得:

由于A(I-P)=A-AAT(AAT)-1A=0,AAT是正定矩阵，则：

这里λm是矩阵AAT的最小特征值.由于A是行满秩矩，所以λm(AAT)>0.对于任意x(t)∉S2，根据函数h(x)的定义可知‖ψ(t)‖2≥1，因此:

(3)

若存在tS2

K(x(tS2))-K(x0)≤-λm(AAT)tS2

2)状态变量x(t)有界

证明：第1步：当t∈[0,tS2]，β(t)=0神经网络(2)可以写成:

(4)

根据链式法则，存在ψ(t)∈h(Ax(t)-b)，使得：

第2步：当t>tS2，由定理1可知，x(t)将在有限时间内收敛到S2，其后不再离开，且进入的时间上限为tS2.所以对t>tS2，有β(t)=1，x(t)∈S2，Ax(t)=b，神经网络(2)可以写成:

(5)

根据链式法则，存在θ(t)∈∂f(x)，σ(t)∈∂D(x)，使得:

当x(t)∈S2S1，因为‖(I-P)θ(t)‖≤‖θ(t)‖，结合引理2，有:

此外，因为神经网络(2)的右边部分是上半连续，且为非空紧凸值。因此在t∈[0,T)，对于初始条件x(0)=x0，神经网络(2)至少存在一个局部解x(t).

结合定理2和解的可扩展理论，局部解可以从t∈[0,T)扩展到t∈[0,+)，即神经网络(2)存在全局解.

3)有限时间收敛到S

因(I-P)2=I-P，(I-P)T=I-P，根据链式法则,存在θ(t)∈∂f(x)，σ(t)∈∂D(x)，使得:

将上式两边从tS2到t进行积分，得到:

D(x(t))≤D(x(tS2))-ε0(t-tS2)

(6)

当t≥D(x(tS2))/ε0+tS2时，D(x(t))≤0.

而D(x(t))≥0且有上界，结合{x:D(x(t))≤0}=S1，说明x(t)会在一定时间内进入S1，即进入可行域S.类似定理1，可证明神经网络的状态变量x(t)在进入S后，不再离开.综上，定理3证毕.

4)神经网络的精确性

定义4.优化问题的关键点集合C为C={x∈S:0∈∂f(x)+NS(x)}，其中NS(x)是x在可行域S上的法锥.

证明：由定理3可知，x(t)会进入S，并停留其中，不妨令x0∈S，则x(t)∈S，Ax(t)=b，β(t)=1，∂D(x(t))=0.

(7)

其中θtn∈∂f(xtn)，σtn∈∂D(xtn).

因为∂f(x)，∂D(x)是上半连续的集值映射，可知:

那么，可以得出:

(8)

(9)

综上，神经网络(2)的任一聚点都是优化问题(1)的关键点，定理4得证.

5)收敛到C

证明：在定理4证明过程中得到，对于x0∈S，S有界，则f(x(t))有界.

假定:

对任意x(t)∈W，有0∉κ(x(t)).因为κ(x(t))是紧凸集，则在W上存在最大值于最小值，分别表示为：

对任意时间间隔t∈[tn,tn+τ]，x(t)∈W，有0≤τ≤k/(4MW)，结合式(7)，有:

4 暂态混沌神经网络

若假设1,2成立，在神经网络(2)的基础上，引入文献[14]的FCSCNN模型，提出一种解决非光滑非凸优化问题的暂态混沌神经网络.

(10)

yi(t+1)=kyi(t)+λ(t){-(I-P)[∂f(x)+α‖∂f(x)‖∂D(x)]-ATh(Ax-b)}-zi(t)(xi(t)-I0)

(11)

zi(t+1)=(1-β1)zi(t)

(12)

(13)

(14)

S2(yi(t),ε2)=A(0)·exp(-u1|yi(t)|)· sin(yi(t)/(ε2·exp(-u2|yi(t)|)))

(15)

其中：

yi(t)为神经元内部状态；

xi(t)为神经元输出；

zi(t)神经元自反馈连接权值；

ω是输出比例系数，控制着函数的输出范围；

ε1为 Sigmoid 函数的陡度参数，ε2为FCS函数的陡度参数；

k为神经隔膜的阻尼因子；

λ(t)为正值缩放因子；

I0为正值参数；

β1为z(t)的退火衰减因子,β2为λ(t)的退火衰减因子.

相对于神经网络(2)，暂态混沌神经网络可以看成在神经网络(2)的单层神经网络基础上扩展成多层神经网络，所以对应的输入输出函数会有相应的调整.

式(11)表示神经元内部状态，同时也是神经网络的输入层,其中大括号内的部分为递归神经网络，参数定义与神经网络(2)相同。由于暂态混沌神经网络的特性，初始点的选取范围是n，即从神经网络(2)的扩展到无限制，这对神经网络的性能来说是一个提升.

式(12)是神经元自反馈连接权值，控制着神经网络的混沌状态的发生与结束.

式(13)是神经网络(2)的系数，控制着递归神经网络对混沌的影响.λ(t)一般需要一个较大的初始值保证足够的影响.由于考虑的优化问题是非凸的，为了防止输出变量的波动，所以需要让系数逐步缩小以保证能最终收敛到最优点，所以用β2为退火衰减因子来控制λ(t)的缩小.

式(15)表示FCS函数，表示的是不同频率正弦信号叠加的脑电波模型.将Sigmoid函数(式(14))与FCS函数的加权和作为混沌神经元的激励函数(式(10))，作用是非单调化激励函数，得到更丰富的混沌特性，并且让激励函数更加接近真实生物神经元的激活抑制模型同时还能满足脑神经不同活跃状态的特点.yi(t)为函数自变量,表示脑电波活动的强弱;A(0)为正弦函数的幅值;ε2为正弦函数的陡度参数,控制着正弦函数频率;u1,u2均为正值参数；ε1为Sigmoid函数的陡度参数，c为FCS函数的比例系数(c≥0).令ε1=10，A(0)=0.8，ε2=0.02，u1=6，u2=1，c=0.5，S1(t)与x(t)的函数图像如图1所示.

图1 Sigmoid和Sigmoid+0.5FCS激励函数曲线对比Fig.1 Comparison of excitation function curves between sigmoid and sigmoid + 0.5FCS

图1(a)为Sigmoid函数，图1(b)为Sigmoid+0.5FCS函数，通过图1的对比能看出，相对于最常见的激励函数Sigmoid函数，加入FCS函数后的激励函数不仅有着很强的非单调性，还表现出了Sigmoid函数的生物学特性，这意味着新的暂态混沌神经网络的神经元动力特性更好，混沌的程度更高，这决定了新的神经网络模型具备更好的全局寻优能力.

新的暂态混沌神经网络与HNN的优化机制类似，将优化问题的目标函数当做能量函数，之后的神经网络的动力学演化过程便是能量函数的全局寻优过程，当神经网络最终能收敛到一个稳定点时，与之相对神经元的输出结果就是优化问题的(最优/次优)解.

表1 与现有神经网络性能对比Table 1 Performance comparison with existing neural networks

通过表1可以看出，本文不需如文献[5]一样初始点受限，虽然本文可行域有界，但是本文有着其他参考文献不具有的全局寻优能力，且可行域有界是全局寻优能力的保障.

接下来将通过仿真实验来验证本文提出的暂态混沌神经网络的全局寻优能力.

5 仿真实验

为了验证本文提出的神经网络的性能，在Matlab2012a平台上，用仿真实验来验证神经网络(2)和本文提出的暂态混沌神经网络的表现.

例1.

minf(x)=-0.25x12+1.2x22+0.1x1x2+2x1-2x2s.t.g1(x)=-x1+x2-2≤0g2(x)=x1-2x2-2≤0g3(x)=-x1x2≤0x1+2x2=3

(16)

在例1中，f(x)和g3(x)非凸，但把x1=-2x2+3带入后，f(x)和g3(x)在可行域上为凸函数，且可行域有界，那么优化问题(16)有唯一全局最优点x*=(0,1.5)T且能用神经网络(2)解决.

图2 神经网络(2)在优化问题(16)的运行轨迹图Fig.2 Transient behaviors of neural network(2)in optimization problem(16)

例2.

(17)

容易看出优化问题(17)中，可行域有界，且在可行域上，f(x)非凸，并有着多个关键点.

令步长l=0.001，α=3，选取2个不同的初始点(-3,5)T，(-3,-1)T，神经网络(2)最终分别收敛到(-2.9839,2.9859)T，(0.001,0.001)T，收敛轨迹如图3、图4所示.

图3 神经网络(2)在初始点为(-3,5)T的轨迹图Fig.3 Transient behaviors of neural network (2) with initial point (-3,5)T

从图3、图4可以看出，神经网络(2)在非凸优化问题上有着一定的收敛能力，但是缺乏全局寻优能力.同样的问题在文献[5-7]的模型上也存在，选初始点(-3,5)T，文献[7]的模型的轨迹图如图5，能看出这个模型也没有全局寻优能力.那么，在优化问题(17)上对本文提出的暂态混沌神经网络进行测试.

对例2，在本文提出的暂态混沌神经网络中选取参数如下：

图4 神经网络(2)在初始点为(-3,-1)T的轨迹图Fig.4 Transient behaviors of neural network (2) with initial point (-3,-1)T

图5 文献[7]的模型在初始点为(-3,5)T的轨迹图Fig.5 Trajectories of the model in [7] at the initial point (-3,5)T

选神经网络(2)未能收敛到最优点的初始点(-3,5)T，令z1(1)=z2(1)=3,λ(0)=0.5.运行结果见图6，最终收敛到点(2.372×10-4,2.372×10-4)T，可以看成收敛到全局最优点.

图6 Fig.6

通过图6(a)，图6(b)可以看出，神经网络的输出值x1,x2在前期的“粗搜索”过程中体现了明显的混沌搜索的遍历性，伪随机性的特点，在160步时已收敛到最优解附近，而图6(c)则展示了神经网络的能量函数f(x)在经过前期的混沌搜索后，约在同时收敛到最低点附近，并且马上稳点在最低点.这种准确，快速的寻优效果很好的证明了本文提出的暂态混沌神经网络在函数优化方面的全局寻优能力.

图7 Fig.7

6 总 结

本文提出了一种新型的递归神经网络方法，用来解决带有不等式约束以及等式约束的非光滑非凸优化问题.对神经网络的准确性与收敛性进行了严谨的理论分析，并通过仿真实验验证了神经网络的性能.为实现神经网络的全局寻优，在递归神经网络的基础上构建了一个新的暂态混沌神经网络，并放开了递归神经网络对初始点的限制.通过仿真实验，验证了当可行域有界时，暂态混沌神经网络具有一定的全局寻优能力.