时间依赖凸约束可行性问题的神经动力学方法

张宸宁，李国成

(北京信息科技大学信息与计算科学系，北京 100192)

0 引言

本文考虑如下时间依赖约束可行性问题：

(1)

这里x∈n为状态变量；F=(f1,f2,…,fm)T:+×n→m为m维向量值函数，其分量fi(t,x)关于变量x是凸函数(i=1,2,…,m)。对任意δ>0，存在Li(δ)>0，使得

t,s≥0，x1,x2∈B(0,δ)，其中B(0,δ)={x∈n:‖x‖<δ}是以0为中心δ为半径的开球。A∈r×n为具有行满秩系数矩阵，b是一个r维向量。问题(1)等价于找到x(t)∈C(t)，其中C(t)={x∈n:F(t,x)≤0且Ax=b}为问题(1)的可行集。令C1(t)={x∈n:F(t,x)≤0}，C2={x∈n:Ax=b}。显然，C(t)=C1(t)∩C2。在本文中，我们假定问题(1)至少有一个可行解x(t)∈C(t)(t≥t0)。

工程应用中的许多问题，如控制理论、信号处理、安全通信和图像重建，都可以归结为可行性问题，其中许多问题涉及时变环境，在很短的时间内提供解决方案是至关重要的。例如，机器人的实时运动规划和控制、非线性模型预测控制、用于多媒体数据安全性的快速信号加密、无线传感器网络中的定位、计算机断层摄影术中投影的图像重建以及使用鲁棒掩模波束成形的安全通信方案等。当需要实时获得可行解决方案时，特别是存在不确定性时，时间依赖约束可行性问题的难度明显增大。在这样的应用中，与传统的数值可行性算法相比，基于递归神经网络的神经动力学方法具有独特的优点：可以设计硬件实现。例如，超大规模集成电路(VLSI)、可重配置模拟芯片、光学芯片、图形处理单元(GPU)、现场可编程门阵列(FPGA)、数字信号处理器(DSP)等。新技术的产生使神经网络的设计和实现更合理、更可行。

基于递归神经网络的神经动力学方法在过去30年取得了巨大的成功，可参考文献[1-16]。其中，Tank等[1]率先采用神经动力学方法求解线性规划问题； Wang[3]提出了一种求解线性和非线性凸规划问题的确定性模拟退火神经网络；Kennedy等[5]等提出了解决非线性优化的递归神经网络，利用有限惩罚方法来逼近最优解；Forti等[6]引入了一种广义非线性规划电路(G-NPC)，它将文献[5]中的规划电路扩展到非光滑情形。G-NPC利用基于高增益非线性约束神经元实现非光滑爆破函数的精确罚函数法来优化不可微目标函数。对比文献[5]中的光滑电路，G-NPC的优势是滑模的存在，由于滑模的存在，网络状态轨道能够在有限时间内收敛到可行集。Ban等[8]进一步推进了Forti的工作[6]，提出了一种求解非凸优化问题的神经网络模型，并证明了对于一个足够大的惩罚参数，网络的状态轨道都可以在有限时间到达可行域，并在此之后停留在可行域中。实际上，已有的神经网络模型是在假设目标函数和约束不依赖于时间来设计的。在文献[8]中，Marco等首先提出了时间依赖非光滑神经网络模型，用于解决带有不等式约束的时间依赖可行性问题。

从文献 [8-9]得到启发，本文考虑了带有等式和不等式约束的时间依赖可行性问题，并提出了基于精确罚函数法设计的神经动力学模型。对于惩罚参数的适当值，证明了所提出的神经动力学模型的状态轨道在有限时间到达移动集，且随时间跟踪移动集。同时估计了惩罚参数和收敛时间的下界。

1 预备知识

在本节中，我们将介绍有关集值分析中的某些定义和性质，以及本文所需的凸分析的知识。读者可参考文献 [17-21]。

定义1Q:+×n→n称为集值映射。每个点(t,x)∈+×n，对应唯一非空集合Q(t,x)⊂n[17]。

定义2设Q是一个集值映射。如果∀ε>0,∃δ>0，使得∀(t,x)∈B(t0,δ)×B(x0,δ)，Q(t,x)⊂Q(t0,x0)×B(x0,ε)，则称Q在(t0,x0)∈+×n处是上半连续的(u.s.c)。若对任意(t0,x0)∈+×n都上半连续，则称Q为上半连续(u.s.c)。

设G⊂n是一个非空闭凸集，x∈n，则存在唯一的元PG(x)∈n满足‖x-PG(x)‖=miny∈G‖x-y‖，称PG(·)为G上投影算子。此外，m(G)=PG(0)表示G上取最小范数的向量。

设f:n→是一个凸函数，则f是局部Lipschitz连续的，但未必是可微的。我们可以引入f的次微分。

定义3设f:n→是凸函数，则f在x处的次微分定义如下：

∂f(x):=

{ξ∈n:∀y∈n,f(y)≥f(x)+〈ξ,y-x〉}

向量ξ∈∂f(x)称为f在x处的次梯度。映射x→∂f(x)具有非空紧凸集值，具有闭图像且局部有界[21]。因此，x→∂f(x)将n的紧集映成n的紧集。此外，如果f在通常意义下在x处是可微的，那么∂f(x)={f(x)}是单值的。

在本文中，我们将使用以下微分运算规则来描述凸函数的次微分。

1)设f1,f2,…,fm是从n到的m个凸函数，λ1,λ2,…,λm为正实数，则

2)设f1,f2,…,fm是从n到的m个凸函数，

f(x)=max{f1(x),f2(x),…,fm(x)}(x∈n)，I(x)={i:f(x)=fi(x)}表示指标集，则

∂f(x)=co{∪∂fi(x):i∈I(x)}

其中，co(G)表示集合G的凸包。

3)链式法则[22]。设V:n→是一个凸函数，x:+→n在+的任一紧区间上是绝对连续的，则，对几乎所有的t≥0，t→V(x(t))是可微的，且

Hausdorff距离：设G1,G2⊂n为非空闭集，G1和G2之间的Hausdorff距离定义为[20]]

dist(G1,G2)=

2 神经网络模型

在本节，提出了一个基于精确罚函数法的神经动力学模型来求解时间依赖凸约束可行性问题。

下面给出一些需要的符号和假设。对于给定的(t,x)∈+×n，令

I+(t,x)={i:fi(t,x)>0,1≤i≤m}

I0(t,x)={i:fi(t,x)=0,1≤i≤m}

I-(t,x)={i:fi(t,x)<0,1≤i≤m}

为(t,x)的指标集。

在本文中，需要以下假定。

假定1集值映射t→C(t)在Hausdorff距离下是连续的，并且存在R>0，使得C1(t)⊂B(0,R)及intC1(t)≠∅。

假定2存在一个选择s(t)∈intC1(t)∩C2，满足Lipschitz条件，Lipschitz常数Ls>0。

假定3存在ρ>0，使得对于任何t≥0，i=1,2,…,m，fi(t,s(t))≤-ρ。

由条件1知，C1(t)是非空紧凸的，则对于几乎所有t≥0，t→C1(t)在Hausdorff度量下存在Lipschitz选择s(t)∈C1(t)[20]。此外，由于intC1(t)≠∅，则s(t)∈intC1(t)[20]。如果“Steiner点映射”g满足g(C1(t))∈C2，或“重心选择映射”h满足h(C1(t))∈C2，则在假定2下存在Lipschitz选择，并且可以估计Lipschitz系数Ls[17-20]。

本节目的是设计一个神经网络模型，使得在t=0时，在C1(0)外面开始的任何状态在有限时间内到达移动集C(·)，并且此后保持在C(·)之内。为此，定义能量函数E:+×n→如下：

其中θ>0是一个待定常数。P=AT(AAT)-1A，AT是A的转置，c=AT(AAT)-1b。矩阵P称为投影矩阵。显然，对于任何t≥0，x→E(t,x)是凸的。

神经网络模型由如下微分包含方程给出：

(2)

其中σ>0是一个待选择的惩罚参数，对于几乎所有t≥0， ∂xE(t,x)是凸函数x→E(t,x)的次微分。∂xE(t,x)表示如下：

(3)

注意到，C2={x:Px=c}={x:Ax=b}。当x∉C2时，‖Px-c‖是严格可微的，其微分为∂‖Px-c‖=‖Px-c‖=PT(Px-c)/‖Px-c‖；当x∈C2时，∂‖Px-c‖={PTξ:‖ξ‖≤1,ξ∈n}。

给定x0∈n且t1>0，柯西问题(2)的解是一个绝对连续函数x(t)，满足x(0)=x0，且对几乎所有的

由假定1)，(t,x)→E(t,x)是局部Lipschitz连续函数，(t,x)→∂xE(t,x)是具有非空紧凸集值的上半连续集值映射[18]，且(t,x)→m(∂xE(t,x))是局部紧的，则对于任意x0∈n，对于初始条件x0，微分包含式(2)至少存在一个状态解[17]。

3 动态分析

在本节中，首先研究在初始条件下，问题(2)状态解的有界性和唯一性。然后我们证明，通过适当选择惩罚参数σ，在初始条件x(0)∉C1(0)时，问题(2)的任意状态解x(·)在有限时间th到达移动集合C(·)。换言之，x(th)∈C(th)，其中th可根据网络参数估计。在到达移动集C(·)后，状态解能够跟踪移动集，即对于任何t≥th，x(t)∈C(t)。

3.1 状态解的有界性与唯一性

本节给出主要结果之前，首先需要引入如下2个引理。

引理1若假定1～3满足，那么，对于任何t≥0，x∈n，x∉C1(t)，有

〈z,x-s(t)〉≥ρ∀z∈∂xV(t,x)

(4)

其中，t→s(t)在假定2中定义，并且

证明固定t≥0，x∉C1(t)，则I+(t,x)≠∅。由定义3，有

0<-fi(t,s(t))<-fi(t,s(t))+fi(t,x)≤

〈zi,x-s(t)〉 ∀zi∈∂xfi(t,x)

其中i∈I+(t,x)。如果I0(t,x)≠∅，则

0<-fi(t,s(t))<-fi(t,s(t))+fi(t,x)≤

〈zi,x-s(t)〉 ∀zi∈∂xfi(t,x)

其中i∈I0(t,x)。则对任意z∈∂xV(t,x)，有

引理2若假定1～3满足，则对任意的x∈n，z∈∂‖Px-c‖，有

(5)

证明若x∈C2，则Px-c=Ps(t)-c=0。对任意的ξ∈n使得‖ξ‖≤1，有

〈PTξ,x-s(t)〉=〈ξ,Px-Ps(t)〉=0

如果x∉C2，则

∂‖Px-c‖=‖Px-c‖=PT(Px-c)/‖Px-c‖

〈PT(Px-c),x-s(t)〉/‖Px-c‖=‖Px-c‖

证明首先 证明状态解的有界性。为此，定义如下Lyapunov函数：

其中选择s(t)在假设2中定义。

由于

σ(∂xV(t,x(t))+θ∂x‖Px-c‖)

σθ〈x(t)-s(t),z2(t)〉-

根据引理1～2，如果x(t)∉C1(t)，‖x(t)-s(t)‖≤2R，那么

(6)

对于任意t≥0，x→E(t,x)是凸的，则x→-σ∂xE(t,x)是极大单调算子[17]，类似文献 [23]中性质3的证明，可以得到结论：对于初始条件x(0)∈B(0,R)，问题(2)存在唯一状态解x(t)。

3.2 到达阶段

下面的结果表明问题(2)的状态解在有限时间到达随时间移动的可行集。

注意到s(t)∈intC1(t)∩C2，则

‖x(t)-s(t)‖2<

‖x(0)-s(0)‖2-2RLst，

0

因此，对于任意t∈[0,te)，x(te)∈C(te)，存在te≤Te使得x(t)∉C1(t)。

3.3 跟踪阶段

在本节中，我们将证明：问题(2)的状态解达到移动集合C(·)后，它将保持在移动可行集内。为此，构造问题(2)的Lyapunov函数如下：

在证明主要结果之前，需要以下引理。

(7)

其中z(t)∈∂xE(t,x(t))。

由链式法则，可以得到

另一方面，由于|E(t+τ,x(t+τ))-E(t,x(t+τ))|=|V(t+τ,x(t+τ))-V(t,x(t+τ))|，‖x(t)‖<3R，可得

证明对于初始点x(0)∈B(0,R)C1(0)，x(t)是问题(2)的状态解。由定理1可知，存在te使得x(te)∈C(te)。

下面证明x(t)∈C(t)，t≥te。

采用反证法。

一方面，当x(t)∉C1(t)时，由式(4)、(5)可知，对于任意z(t)∈∂xE(t,x(t))有〈z(t),x(t)-s(t)〉≥ρ，那么

由式(7)得

另一方面，当x(t)∈C1(t)C2(t)时，选择W(x(t))=θ‖Px(t)-C‖作为问题(2)的Lyapunov函数，那么，对于任何v(t)∈∂xV(t,x(t))，有

σ‖W(x(t))‖·‖v(t)‖-

-σθ<0

4 结束语

本文提出了一个基于精确罚函数法的神经动力学模型来求解时间依赖凸约束可行性问题。首先研究了问题(2)状态解的有界性和唯一性。基于此，通过适当选择惩罚参数σ，在初始条件x(0)∉C1(0)情形下，问题(2)的任意状态解x(·)在有限时间th到达移动集合C(·)，即x(th)∈C(th)，其中th可根据网络参数估计。此外，证明了状态解能够跟踪移动集合，即t≥th，x(t)∈C(t)。