东北大学学报:自然科学版  2017, Vol. 38 Issue (2): 153-157  
0

引用本文 [复制中英文]

王占山, 康云云, 牛海莎. 一类求解优化问题的神经网络及其全局吸引性分析[J]. 东北大学学报:自然科学版, 2017, 38(2): 153-157.
[复制中文]
WANG Zhan-shan, KANG Yun-yun, NIU Hai-sha. A Class of Neural Networks for Solving Optimization Problems with Global Attractivity[J]. Journal Of Northeastern University Nature Science, 2017, 38(2): 153-157. DOI: 10.3969/j.issn.1005-3026.2017.02.001.
[复制英文]

基金项目

国家自然科学基金资助项目 (61473070,61433004);流程工业综合自动化国家重点实验室项目 (2013ZCX01)

作者简介

王占山 (1971-),男,辽宁抚顺人,东北大学教授,博士生导师。

文章历史

收稿日期:2015-10-18
一类求解优化问题的神经网络及其全局吸引性分析
王占山1, 康云云2, 牛海莎1    
1. 东北大学 信息科学与工程学院,辽宁 沈阳 110819;
2. 国网池州供电公司,安徽 池州 247100
摘要:构造了一个以微分包含形式给出的神经网络模型来求解带有等式约束和不等式约束的非线性最优化问题.通过在网络模型中引入含有加权矩阵的高阶补偿项,不仅提高了神经网络优化计算的收敛速度,而且改进了优化解从不可行域逐步收敛到稳定域的问题.理论上不仅证明了神经网络的解的全局存在性和唯一性,也证明了解的有界性以及在有限的时间内收敛到最优化问题所确定的最优解集中,并分析了神经网络的全局吸引性.通过三个数值例子验证了所提出的神经网络优化的有效性.
关键词神经网络    微分包含    神经计算    优化    全局吸引    
A Class of Neural Networks for Solving Optimization Problems with Global Attractivity
WANG Zhan-shan1, KANG Yun-yun2, NIU Hai-sha1    
1. School of Information Science & Engineering, Northeastern University, Shenyang 110819, China;
2. Chizhou Power Supply Company of State Grid, Chizhou 247100, China.
Abstract: A recurrent neural network in the form of differential inclusion was proposed for solving a class of nonlinear optimization problems, where the constraints were defined by a class of inequality and equality constraints. A higher-order compensation term was involved in the considered neural model, therefore, the convergence rate of the neural computation was significantly increased and the unstable problem of the optimal solution from infeasible domain to feasible domain was solved. In theory, it is proven that not only the solution of the proposed network exists globally and uniquely, but also the solution of the proposed network is bounded and is convergent to the optimal solution set of the optimization problem. Meanwhile, global attractivity of the neural network was analyzed. Three numerical examples were used to show the effectiveness and good performance of the proposed neural network.
Key Words: neural networks    differential inclusion    neural computation    optimization    global attractivity    

非线性优化可以广义地理解为带有等式和不等式约束条件的目标函数优化问题[1-11].在各种各样的科学与工程领域中都经常遇到这类最优化问题.目前,已经有很多方法可以解决这类问题,然而,在这些方法中,多数需要大量的计算,而且并不适合于解决实时或近似实时最优化的问题.神经网络方法为解决约束最优化问题提供了一个有效的发展方向,通过使用具有高度并行计算能力的神经网络体系结构,使许多复杂的最优化问题得到实时解决[2].

1982年美国物理学家Hopfield教授首次将优化问题与一类神经网络相联系[3],并利用能量函数的概念,使所设计的神经网络能够等解相应的优化问题.然而,因为网络中要用到目标函数和约束函数的梯度,所以大部分神经网络模型只适用于解决光滑凸优化问题;但在实际应用中,大部分优化问题都不具备光滑的凸性性质,所以设计适当的神经网络来解决非光滑凸优化和非光滑非凸优化问题是很必要的.

文献[4]构造了一个神经网络模型来求解非光滑凸优化问题,文献[5]建立了一个单层递归神经网络模型来求解带有线性等式约束条件的伪凸优化问题;然而文献[4-5]求解的都是只带有线性等式约束的非光滑凸优化问题,没有考虑不等式约束的情况.

文献[6]中不是任意的初始点都可以使神经网络收敛于优化问题的最优解.文献[7]中由于正增益的不同,神经网络的解是不一样的,很可能不收敛.无论待解决的最优化问题是否光滑,大部分的神经网络技术解决此类约束最优化问题都是带惩罚项的,而且只能给出近似解或有可能无法用电路实现.基于此,文献[9]提出了一种带有微分包含形式的神经网络模型来解决非光滑凸优化问题,克服了罚函数法引入的目标函数二阶导数不连续的缺点; 但是在优化计算时,仍存在收敛速度慢,需要可行域来确保神经网络的有效性,以及从不可行域逐步收敛到解的不足.

为克服上述文献中的缺点,本文通过在网络模型中引入含有加权矩阵的高阶补偿项,重新构造了一类优化神经网络,不仅对于任意的初始值,神经网络的解都能收敛到优化问题的最优解,而且不用确定收敛域来确保神经网络的有效性,收敛速度也得到了提高.

1 神经网络模型与理论分析 1.1 预备知识

首先给出非线性规划的一般形式:

(1)

式中:为目标函数,可以是非光滑非凸函数,在本文中假设f是有界的;gi(i=1, 2, …, m):RnR是不等式约束函数,可以是非光滑非凸函数;ARm×n是一个行满秩矩阵;b0Rm.

如果fRnRRn上是局部Lipschitz的,则fx点沿方向vRn的广义方向导数定义为

引理1 [9]如果VRnRx(t) 是正则函数且x(t) 对t是可微的,且在t附近是Lipschitz的,则

1.2 构造神经网络

满足所有约束条件的点集 (可行域) 可表示为

为解决问题 (1),构造如下神经网络模型

(2)

I是单位矩阵,P=AT(AAT)-1A.

(3)

式中bd (·) 为边界域,int (·) 为内部域.

1.3 主要结果

下面给出本文的定理及其证明过程.在进行分析时首先要满足一些假设条件.

假设条件1:存在r>0,有int (S1)∩S2,其中.

假设条件2:目标函数f(x) 在可行域S上是凸函数且在上是Lipschitz有界,不等式约束gi(x) 在S2上是凸函数.

说明1:从假设条件1中可知可行域S是有界的,而且int (S1)∩S2是非空的,而文献[4]~文献[8]中的假设条件不等式约束可行域S1是有界的,相比这些文献,本文所提的假设条件更弱,更具一般性.

定理1 当假设条件1和假设条件2满足时,构造的神经网络 (2) 的解全局存在且唯一.

证明 由于神经网络 (2) 是一个非空紧凸值的上半连续集值映射,因此,对任意,神经网络 (2) 存在一个局部解x:[0, T)→Rn,其中[0, T) 是神经网络 (2) 的解存在的最大区间.由于f在可行域S上是凸函数,||(t)||具有非增性,所以对神经网络的两个解x(t),y(t)∈S时,有

可推出

(4)

h∈[0, T) 使y0=x(h),则

x(t) 在[0, T) 有界推出它可被扩展,这与[0, T) 是神经网络 (2) 存在最大区间的解相矛盾,所以神经网络 (2) 的解是全局存在,而且通过式 (4) 可以看出当初始点为x0时,解是唯一的.

定理2 当假设条件1和假设条件2满足时,对任意初始点,神经网络 (2) 的解有界并且在有限时间内收敛到可行域中.

证明 首先构造Lyapunov能量函数

(5)
(6)

由式 (6) 和可行域S有界可知V(x(t), t) 是非增的.

(7)

其中为神经网络的最优解,由于V(x, t) 在可行域S上为凸函数,所以当xS且结合式 (7),可以得到

(8)
(9)

由式 (9) 结合V(x, t) 的非增特性得

(10)
(11)
(12)

由式 (12) 可得

(13)
(14)

因为可行域S有界,x(t) 在[0+∞) 是有界的,即||x(t)||≤γ,并且神经网络 (2) 的解收敛到式 (1) 可行域S,即.

说明2:定理2的结论对int (S1)=∅时仍然有效,上面证明了最后收敛到可行域.下面进一步说明可在有限时间内收敛到可行域.

由于A(IP)=0,所以当xRn\S2时,.

又因为,所以

(15)

由式 (15) 知,当t=L(x(0))/λmin(AAT) 时,L(x)=0,x(t) 收敛到S2,其中λmin为矩阵的最小特征值.

当进入到S2时,Pẋ=0,=(I-P)

(16)

其中, lf是一个正常数.

由于当x(t)∈S2\S1时,存在β满足||(IP)ζ2||≥,可知当时到达可行域S1,因为,所以一定存在一个t,当tt时到达可行域S1.

定理3 当假设条件1和假设条件2成立时,对任意的初始点,神经网络 (2) 的解收敛到式 (1) 的最优解集.

定理4当假设条件1和假设条件2成立时,对任意初始点,,即神经网络具有全局吸引的性质.

说明3:定理1给出了神经网络解的存在性及唯一性,定理2证明了神经网络的解在有限的时间内是收敛到可行域的,定理3证明了神经网络的解能收敛到优化问题的最优解集中,最后,定理4证明了本文所提出的神经网络具有全局吸引的性质.

2 仿真分析

例1光滑非凸优化问题:

ε(t)=1/(t+1)1/3,从图 1可以看出神经网络 (6) 的解均能收敛到优化问题的最优解,即=(-1, 2)T.这里引用的是文献[6]中的例子,文献[6]中以 (7/2, -5/2)T和 (-3/2, 5/2)T为不同的初始点,网络的轨道分别收敛于 (2, -1)T和 (-1, 2)T,但只有 (-1, 2)T是能达到其在可行域上的最小值.但本文中提出的网络轨道能以不同的初始点都收敛到可行域上的最小值,更具优势.

图 1 任意10个初始点的状态轨迹仿真图 Fig.1 Properties of (x1, x2)Twith any ten initial points

例2非光滑优化问题:

ε(t)=4/(t+1)1/2,从图 2可以看出,神经网络 (6) 最终均收敛于优化问题的最优解,即.这里引用的是文献[7]中的例子,从仿真图中可以看出,任意初始点时仍能收敛到可行域中,并且不用确定罚参数.但是在文献[7]中,正增益σ不同时,神经网络的解不一定是优化问题的最优解.所以,本文提出的神经网络效果更好,更具优势.

图 2 任意10个初始点的状态轨迹仿真图 Fig.2 Properties of (x1, x2, x3, x4)T with any ten initial points

例3非光滑凸优化问题:

ε(t)=1/(t+1)1/3图 3是神经网络 (6) 以 (0, 0, 0)T为初始点的状态轨迹仿真图,最终收敛于最优解.

图 3 以 (0, 0, 0)T为初始点的状态轨迹仿真图 Fig.3 Properties of (x1, x2, x3)T with zero initial points

图 4是神经网络 (6) 以 (0, 0, 0)T为初始点的目标函数和约束条件的状态轨迹仿真图.图 5是任意10个初始点的目标函数的状态轨迹仿真图.

图 4 以 (0, 0, 0)T为初始点的目标函数和约束条件的状态轨迹仿真图 Fig.4 Properties of f (x) and with initial point (0, 0, 0)T
图 5 任意10个初始点的目标函数的状态轨迹仿真图 Fig.5 Properties of f with any ten initial points

将本文结果与文献[9]的结果作了对比,从仿真结果可以看出,本文所提出的神经网络的收敛速度更快,并且增加了任意初始点时目标函数f的仿真图.

3 结语

本文构造了一类新的具有微分包含的神经网络模型来解决一些非线性优化问题,通过引入ε(t) 的高阶补偿项及相应的加权矩阵,使得神经网络具有全局吸引的性质,并且不用确定罚函数,这使得提出的神经网络模型对解决非线性优化问题更有效.与现有的文献进行对比,本文所提出的神经网络可以用电路实现,对任意的初值,神经网络的解都能使目标函数取得最小值,并且本文不需要先找到可行域就能确保神经网络模型的有效性.通过三个数值例子验证了本文方法的有效性.

参考文献
[1] Bazaraa M S, Sherali H D, Shetty C M. Nonlinear programming:theory and algorithms[M]. Hoboken: John Wiley & Sons, 2013: 1-21.
[2] Cichocki A, Unbehauen R. Neural networks for optimization and signal processing[M]. Hoboken: John Wiley & Sons, 1993: 1-20.
[3] 季策, 张化光. 一类具有时滞的广义Hopfield神经网络的动态分析[J]. 东北大学学报 (自然科学版), 2004, 25(3): 205–208.
( Ji Ce, Zhang Hua-guang. Dynamic analysis of a class of generalized Hopfield neural networks with hysteresis[J]. Journal of Northeastern University (Natural Science), 2004, 25(3): 205–208. )
[4] Liu Q S, Wang J.A one-layer recurrent neural network for non-smooth convex optimization subject to linear equality constraints[M]// Advances in Neuro-Information Processing.Heidelberg:Springer Berlin, 2009:2-30.
[5] Guo Z S, Liu Q S, Wang J. A one-layer recurrent neural network for pseudoconvex optimization subject to linear equality constraints[J]. IEEE Transactions on Neural Networks, 2011, 22(12): 1892–1900. DOI:10.1109/TNN.2011.2169682
[6] Bian W, Xue X P. Subgradient-based neural networks for nonsmooth nonconvex optimization problems[J]. IEEE Transactions on Neural Networks, 2009, 20(6): 1024–1038. DOI:10.1109/TNN.2009.2016340
[7] Liu Q S, Wang J. A one-layer recurrent neural network for constrained nonsmooth optimization[J]. IEEE Transactions on Systems, Man, and Cybernetics, 2011, 41(5): 1323–1333. DOI:10.1109/TSMCB.2011.2140395
[8] Li G C, Song S J, Wu C. Generalized gradient projection neural networks for nonsmooth optimization problems[J]. Science China:Information Sciences, 2010, 53(5): 990–1005. DOI:10.1007/s11432-010-0110-0
[9] Bian W, Xue X P. Neural network for solving constrained convex optimization problems with global attractivity[J]. IEEE Transactions on Circuits and Systems I:Regular Papers, 2013, 60(3): 710–723. DOI:10.1109/TCSI.2012.2209735
[10] 耿平, 刘静, 曾梅光. 多变元非线性复杂系统的优化模拟退火算法[J]. 东北大学学报 (自然科学版), 2002, 23(3): 270–272.
( Geng Ping, Liu Jing, Zeng Mei-guang. Multivariate nonlinear complex system optimization and simulated annealing algorithm[J]. Journal of Northeastern University (Natural Science), 2002, 23(3): 270–272. )
[11] 王占山. 复杂神经动力网络的稳定性和同步性[M]. 北京: 科学出版社, 2014.
( Wang Zhan-shan. Stability and synchronization of complex neural dynamical networks[M]. Beijing: Science Press, 2014. )