一种求解非线性极大极小问题的神经网络方法

于金金，吕一兵

(长江大学信息与数学学院，湖北 荆州 434023)

极大极小问题是一类重要的不可微优化问题，许多工程设计问题都可以转化这一问题[1～3]，因此，研究极大极小问题的有效解法具有非常重要的理论和实用价值。

目前，国内外许多研究者已经设计了求解极大极小问题的可行算法。C.Charalambous和A.R.Conn[4]提出了直线搜索法，其思路是将极大极小问题转化为与之等价的非线性约束优化问题，然后计算2个搜索方向(水平方向和垂直方向)，并在较强的条件下证明了算法的全局收敛性。文献[5]每步通过求解2个QP子问题，并结合非单调直线搜索，克服了Maratos效应，得到了全局收敛性和两步超线性收敛的算法。文献[6]采用信赖域和SQP方法相结合的技术将文献[5]的方法推广到了约束极大极小问题。A.Vardi[7]采用有效集策略，将极大极小问题转化为与之等价的非线性等式约束优化问题，并结合信赖域方法设计了相应的求解算法，同时证明了算法的下降性，但缺少完整的全局收敛性证明。

神经网络具有大规模并行处理及快速收敛的特性，这为优化问题的算法设计提供了一种新的思路。自J.J.Hopfield提出神经优化的思想以来[8,9], 用其求解优化问题受到了越来越多学者的关注。文献[10]基于罚函数求解约束优化问题的神经网络模型，当罚函数足够大时，可以获得原问题的可行解或近似最优解；文献[11]基于Lagrange乘子法建立了求解约束优化问题的神经网络模型，该模型总能收敛于一个可行解；文献[12]基于最优性充要条件建立了神经网络模型，并通过构造Lyapunov函数，证明了神经网络的稳定性。但采用神经网络方法求解极大极小问题的文献目前还不多见，为此，笔者考虑利用神经网络方法求解极大极小问题：将极大极小问题的数学模型转化为相应的神经网络模型，分析神经网络模型的稳定性和收敛性。

1 非线性极大极小问题

考虑如下非线性极大极小问题：

(1)

式中：fi(x)为光滑实值函数；φ(x)称为最大值函数。

因为φ(x)在函数的交点处具有不连续一阶导数，因此问题(1)是一个不可微的无约束优化问题。由文献[4]、[13]和[14]可知，问题(1)等价于如下非线性规划问题：

(2)

式中：z是一个引进的新的独立变量；gi:Rn→Rm为连续可微函数。

2 神经网络模型的构造

采用Lagrange乘子法构造问题(2)的神经网络模型。

定义1 令I(x*,z*)={i|gi(x*,z*)=0,i=1,2,…,m}，如果梯度▽gi(x*,z*)线性无关,i∈I(x*,z*), 则称点(x*,z*)为问题(2)的正则点。

记问题(2)的Lagrange函数为：

L(x,z,u)=z+uΤg(x,z)u

式中：u∈Rm是Lagrange乘子。

注：为避免不等式约束额外增加变量，定义的Lagrange函数将不等式约束的乘子取为u2。

定理1 假设(x*,z*)是(2)的局部极小点，且(x*,z*)是正则点，则存在u*使得：

且对任何y≠0,y∈Y(x*,z*)，Y(x*,z*)={y|yΤ▽gi(x*,z*)=0,i∈I(x*,z*)}，有：

定义2 满足定理1的点(x*,z*,u*)称为问题(2)的Kuhn-Tucker点。

定理2 假设(x*,z*)满足约束条件，且存在u*使得:

且满足严格互补性条件，即u*≠0，∀i∈I(x*,z*)，如果对任何y≠0，y∈Y(x*,z*)有：

则(x*,z*)是问题(2)的局部严格极小点。

定理1与定理2的证明与文献[15]类似定理的证明相同，这里不再重复。

定义3 如果对任何x∈Rn,u∈Rm,z∈Rm有：

L(x*,z*,u)≤L(x*,z*,u*)≤L(x,z,u*)

则称Lagrange函数L(x,z,u)在(x*,z*,u*)具有鞍点性质，且(x*,z*,u*)称为L(x,z,u)的鞍点。

构造问题(2)的神经网络模型如下:

(3)

按照求解过程中的作用不同，可将神经网络的神经元分为变量神经元x、z和Lagrange神经元u。从网络的状态方程可以看出，沿着神经网络的轨迹Lagrange函数总是随x、z减少,随u增加。当网络演化到稳态时，有：

也就是说神经网络的渐近稳定点(x*,z*,u*)是Lagrange函数的鞍点。

定义4 如果(x*,z*,u*)满足：

▽xL(x*,z*,u*)=0 ▽zL(x*,z*,u*)=0 ▽uL(x*,z*,u*)=0

则称(x*,z*,u*)是神经网络的平衡点。

3 稳定性分析

定理3 设(x*,z*,u*)是神经网络(3)的平衡点，且(x*,z*)是正则点，则(x*,z*,u*)是神经网络的渐近稳定点。

证明 神经网络(3)的能量函数定义为：

能量函数E对时间t的微分为：

4 数值试验

首先将其转化为一般的非线性规划问题，其Lagrange函数为：

然后，构造相应的神经网络模型，采用四阶Runge-Kutta法求解相应的常微分方程组，得到最优解(x1,x2)=(0.5,-2.0). 变量x1和x2随迭代次数的变化情况如图1所示。

首先将其转化为一般的非线性规划问题，其Lagrange函数为：

然后，构造相应的神经网络模型，采用四阶Runge-Kutta方法求解相应的常微分方程组，得到最优解(x1,x2)=(1,1). 变量x1和x2随迭代次数的变化情况如图2所示。

图1 算例1变量随迭代次数的变化情况 图2 算例2变量随迭代次数的变化情况

上述2个算例表明，利用神经网络方法可以有效地求解极大极小问题。另外，在利用Runge-Kutta方法求解相应的神经网络模型时，初始值的选取对算法的收敛性起着关键作用。初始值选择恰当，则可以较为迅速的收敛到最优解。

5 结语

利用神经网络方法求解极大极小问题，采用Lagrange乘子法得到了一种非线性规划神经网络模型，该神经网络的优点在于可直接处理不等式约束，不用增加松弛变量。该方法可较为有效地减少神经网络的复杂度，数值试验结果表明了该方法的可行性。此外，笔者提出的神经网络模型只是具有渐进稳定性的特征，如何设计具有全局收敛性的神经网络模型，还值得进一步研究。