一种解决分布式伪凸优化问题的神经网络模型

周顺, 喻昕, 黄镘潼, 覃海华, 李浩宇

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

0 引言

优化问题一直广泛存在于科学与工程应用中。自从1986年Tank等[1]首次提出求解非线性光滑优化问题后,神经网络的研究再一次在研究优化领域的学术界掀起巨浪。近年来,随着大数据和人工智能的发展,许多集中式的算法难以胜任大规模复杂的优化问题,因此,受机器学习[2]、智能电网[3]、云计算[4]等领域的启发,基于多智能体系统的分布式优化开始受到关注,其目标核心是设计一个分布式优化算法,使得多智能体系统中各个节点都能找到使得全局目标函数最小的点。上述领域的许多工程问题都可以通过建模转化为分布式优化问题,并进行求解,为此,工程师和科学家们开发了许多解决不同类型分布式优化问题的算法[5-12]。这些模型算法的局部目标函数往往都是凸的,意味着全局目标函数也具有凸性,因此研究一个凸性更弱的分布式优化算法是很有意义的。本文解决的优化问题全局目标函数仅具有伪凸性,伪凸是更一般的凸性,因此更具有普遍意义。

随着凸优化和微分包含理论的不断研究,针对实际应用中出现的非光滑和非凸的相关问题,学者们也提出了许多神经网络模型。对于集中式连续时间的神经网络算法,Liu等[13]也提出了一种基于罚参数思想的递归神经网络,该模型需要精确计算罚参数。Xue等[14]提出了一个可以解决非凸非光滑优化问题的算法,该算法依赖于精确的惩罚参数,意味着罚参数的计算准确性直接影响到算法的有效性。为了避免精确计算罚参数,Yu等[15]、Qin等[16]、Xu等[17]分别提出一个单层的神经网络算法解决伪凸优化问题,并且所提出的算法不需要精确计算罚参数。

对于分布式连续时间的神经网络算法,Wang等[7]提出了一种解决无约束分布式凸优化的连续时间算法。Liu等[10]设计了一种基于Karush-Kuhn-Tucker(KKT)条件和微分包含的连续时间算法,用于求解带有凸不等式约束仿射等式约束的凸分布式优化问题,并且证明了这个微分包含状态变量的轨迹在Slater约束规范的假设下将收敛于原分布式优化问题的最优解。Zeng等[18]提出了一种连续时间投影算法来求解具有一般集合约束的分布式非光滑凸优化问题。Lu等[19]提出了一种基于有向图通信网络、且局部目标函数受限于共同凸集的强伪凸分布优化问题的算法。Xu等[20]提出了一种基于有向图通信网络、且局部目标函数受限于共同凸集的强伪凸分布优化问题的算法。通过查阅文献[18-20]可知,目前针对于求解非凸问题的分布式连续时间算法的研究工作是十分有限的。

受上述所提算法的启发,提出了一种解决分布式伪凸优化问题的神经网络模型。

1 预备知识

1.1 记号说明

记Rn为n维的欧几里得空间,〈·,·〉和‖·‖分别为Rn空间上的內积和范数。用B(x,r)表示以x作为中心、半径为r的开球。符号⊗表示克罗内克积,Im表示m阶单位矩阵。对于x∈Rn和y∈Rm,记col(x,y)=(xT,yT)T,对x=(x1,x2,…,xn)T∈Rn,记向量x的对角矩阵为diag{x1,x2,…,xn}。

1.2 非光滑分析

下面给出相关的必要预备知识。

定义1若对于集合K⊂Rn上的任意点x,都存在一个非空集合F(x)⊂Rn,则称x→F(x)是K⊂Rn上的集值映射。若对于任意的开集E⊂F(x0),对x0都有一个相应的领域U,使得F(U)⊂E,则称集值映射F：K→Rn在点x0∈K处是上半连续的。

定义2设函数f：Rn→R在x∈Rn附近是Lipschitz连续的,f在x的广义方向导数定义为

时间t→0。另外,函数f在点x处的广义梯度定义为

∂f(x)={ξ∈Rn：f0(x,d)≥〈d,ξ〉,∀d∈Rn}。

命题1设函数f：Rn→R在x∈Rn附近是局部Lipschitz连续的,记Lipschitz常数为λ,那么有：

①∂f(x)是Rn上的非空紧凸集。

③∂f(x)在x处是上半连续的且∀ξ∈∂f(x),有‖ξ‖≤λ。

定义3设函数f：Rn→R在x∈Rn附近是局部Lipschitz连续的,若函数f满足：

②对任意的d∈Rn,f0(x;d)=f′(x;d) 成立,那么称函数f在x处是正则的。

命题2如果fi在x处正则,那么有

命题3如果V(t)：Rn→R在x(t)处正则并且x(t)：[0,+∞)→Rn在[0,+∞)的任意紧集上是绝对连续的,那么V(x(t))是几乎处处可微的且对几乎所有的t≥0,如下等式都成立：

定义4设K⊂Rn是一个非空凸集,称函数f：K→R为集K上的伪凸函数,则对于任意的x,y∈K,若有η∈∂f(x),满足η(y-x)≥0,则必有f(y)≥f(x)。

1.3 代数图论

2 问题描述与模型构建

设G为由m个智能体组成的无向网络,网络中的每个结点都能与它的邻接点相互通信,考虑建立如下的在无向网络G上的分布式优化问题：

(1)

为了解决优化问题(1),首先引入如下假设。

假设1G是连通的无向网络。

引理1[21]在假设1成立的条件下,分布式优化问题(1)等价于如下优化问题：

(2)

其中

L=LN⊗Im,x=col{x1,x2,…,xm},g(x)=col{g1(x1),g2(x2),…,gm(xm)}。

由引理1可得,当通信网络是连通的无向图时,设x*∈Rn是优化问题的(1)的一个最优解,那么有x*=col{x*,x*,…,x*}∈Rmn是分布式优化问题(2)的一个最优解。为了解决分布式优化问题(2),基于引理1,将构造一个连续时间的分布式算法。这里为了方便,首先引入惩罚函数,

因此对于第i个智能体,它的不等式可行域可以表示为

Si={x∈RnGi(x)≤0},

那么优化问题(2)的不等式可行域可以表示为

S={x∈Rmn：g(x)≤0}。

经过分析,可以得到

其中

引理3[22]如果假设3成立,则可选取充分大的常数ri>0,满足

并且对于任意的x∈Rn和x∉Si,本文有如下式子成立：

定义5在X⊆Rn上的连续时间的集值动力系统被定义为如下的微分包含：

其中t∈R+且Ψ：X⊆Rn→Φ(Rn)是一个集值映射。任意一个解x：[0,T]→X是一个绝对连续函数,并在几乎处处意义下满足上述微分包含。

基于上文的分析,为了解决分布式优化问题提出了如下的分布式神经网络模型：

(3)

(4)

σ=max{‖∂fi(x)‖：x⊆B(0,R),i∈{1,2,…,m}},

(5)

这里ε(t)：[0,∞)→(0,∞)为一个函数,满足如下性质：

①ε(t)在其定义域内是非增的。

3 收敛性分析

定理1在假设3成立的条件下,∀xi0∈RnSi,对于几乎所有的时间t∈[0,T),满足xi(t)∉Si,分布神经网络模型的状态解是有界的。

证明考虑如下能量函数：

式中i∈{1,2,…,m}。

(6)

根据式(4)、(5),有

若假设3成立,根据引理3,可得

(7)

根据式(6)、(7),得到

(8)

定理2若假设3成立,对任意初始点x0,分布式神经网络模型的轨迹xi(t)将会在有限时间内进入到各自的可行域Si,并永驻其中,即存在时间T1>0,在t∈[T1,∞)时,有xi(t)∈Si。

Vg(t)=Gi(xi(t))。

根据命题3,对所有时间t>0,存在可测函数ηi(t)∈∂fi(xi(t)),βi(t)∈∂Gi(xi(t)),有

(9)

意味着xi(t)将会在在有限时间内进入Si中。

下面证明xi(t)在进入可行域Si后会永驻其中。

使用反证法对其进行证明。假设存在时间t2>t1>T1,当t∈(t1,t2]时,有xi(t1)∈Si和xi(t2)∉Si。将不等式(9)两边从t1到t2进行积分,有

与xi(t2)∉Si,Gi(xi(t2))>0相矛盾,因此分布式神经网络在初始点为x0的轨迹都会在有限时间进入到可行域当中,且永驻其中。

接下来需要推导出各智能体的状态解将会在可行域内达成一致。

定理3若假设1和假设3成立,设x(t)=col{x1(t),x2(t),…,xm(t)}是过初始点x0的分布式神经网络模型的状态解,则

(10)

即分布式神经网络模型的状态解最终会达成一致。

证明使用反证法证明。假设式(10)不成立,由于L是半正定的,那么有

根据上极限的定义,那么就存在常数δ0>0与一个趋于无穷的数列{tn}⊂[T1,∞),使得

x(tn)TLx(tn)≥δ0,

(11)

当t∈[T1,∞)时,定义如下能量函数：

根据命题3和式(4)对所有t∈[T1,∞),本文有ηi(t)∈∂fi(xi(t)),βi(t)∈∂Gi(xi(t)),则

(12)

值得注意的是

(13)

根据函数ε(t)的性质和定理1,可以推断出存在一个时间T2′≥T2,在t∈(T2′,∞)时,满足

(14)

根据式(11)—(14),对不等式(12)两边从T2′到t进行积分,有

定理4若假设1、2、3成立,分布式神经网络模型的状态解x(t)=col{x1(t),x2(t),…,xm(t)}最终将会收敛于问题(2)的一个最优解x*。

证明设x*是优化问题(1)的一个最优解,定义如下能量函数：

根据命题3和定理2,存在函数ηi(t)∈∂fi(xi(t))、βi(t)∈∂Gi(xi(t))和η(t)∈∂f(x(t)),对几乎所有时间t>T1,满足

(15)

这里可以逐项分析,有

-〈x*,xi(t)-xj(t)〉)。

(16)

式中x(t)=col{x1(t),x2(t),…,xm(t)}。

根据式(15)、(16),可以得到

(17)

(18)

(19)

(20)

根据ε(t)的性质和引理2,有

和

意味着存在一个时间数列{tn},满足

(21)

式中η(tn)∈∂f(x(tn))。

又存在另一个时间数列{tnk}⊆{tn},满足

(22)

根据定义4和 式 (17)—(22),本文最后有

构造另一个能量函数

类似上述证明可知

即分布式神经网络模型的状态解最终将会收敛于问题(2)的最优解。

4 仿真实验

通过2个仿真实验来验证本文所提出的分布式神经网络模型的收敛性和准确性。

实验1考虑如下的分布式全局函数求和是严格伪凸的优化问题[19]：

式中x=[x1,x2]T。该问题的局部目标函数为

图1 实验1的状态解运动轨迹Fig.1 Trajectories of state solution for Example 1

图2 实验1的一致项函数‖xi-x*‖的轨迹Fig.2 Trajectories of consensus function ‖xi-x*‖ for Example 1

实验2考虑如下的二次型分布式伪凸优化问题[20]：

式中x=[x1,x2]T。该问题的局部目标函数为

式中

该问题局部凸不等式约束分别为g11=-2-x1,g21=x1-2,g31=1-x2,g41=x2-5,通过分析可知全局函数f(x)在其可行域内是伪凸的,且该问题的最优解为x*=(-0.73,1)T。选取函数

初始状态量为x1(0)=(-4,-3)T,x2(0)=(-1,0)T,x3(0)=(1,2)T,x4(0)=(3,4)T。实验2的通信拓扑结构是由4个智能体构成的全连通图,使用分布式神经网络模型对该问题进行求解,实验2智能体状态解的运动轨迹如图3所示。从图3可见, 4个智能体的状态解最终收敛于原问题的最优解x*=(-0.73,1)T。一致项函数‖xi-x*‖,

图3 实验2智能体状态解的运动轨迹Fig.3 Trajectories of state solution for Example 2

i∈{1,2,…,4}的轨迹如图4所示。从图4可见,智能体xi(t)的轨迹最终收敛到x*,并达成一致,说明实验2支持了本文中得出的理论成果。

图4 实验2的一致项函数‖xi-x*‖的轨迹Fig.4 Trajectories of consensus function ‖xi-x*‖ for Example 2

5 结语

本文旨在解决一类普遍出现的带有不等式约束条件的非光滑分布式伪凸优化问题,基于罚函数的思想和微分包含的理论提出了一种新型的分布式神经网络模型,通过罚函数来确保分布式神经网络的状态解收敛到可行域中。本文中所提模型的优势有：①不同于所研究的凸分布式优化算法[5-13],本文中所解决的分布式优化的目标函数是伪凸且不一定可微,意味着本文中提出的算法可以解决的问题范围更大。②与固定罚参数的算法[14-15]不同,本文提出的模型不需要精确计算罚参数,意味着本文提出的分布式神经网络模型更具有实用性。本文中提出的分布式神经网络模型都是建立在无向图的网络上的,具有一定的局限性,未来的工作可以着眼于设计一种解决带等式约束和凸不等式约束的非平衡有向图上的分布式优化算法。