一类半无限规划问题的神经网络算法

昌吉学院 数学系，新疆 昌吉 831100

昌吉学院 数学系，新疆 昌吉 831100

半无限凸规划的一般形式为：

其中 x=(x1，x2，…，xn)T∈Rn，A∈Rm×n(m≤n)，b∈Rm。 g和fi(i∈I)是 Rn上的凸函数，I为无限集。为求解问题（1），作如下假设：问题（1）存在有限解x*∈Rn。

半无限规划问题是数学规划的一个重要分支。它应用于许多领域，如控制系统设计、分散系统的资源配置、信号处理中的滤波器设计等。此外随着近代工业技术的快速发展，由于要不断提高对产品性能的期望，还要受到环境和资源等条件的诸多限制，使得许多实际问题都可以建立成半无限规划的数学模型。所以研究半无限规划问题就显得很重要。但是在半无限规划问题中，由于其约束条件的个数是无限的，这就给数值求解带来比较大的困难，使现有的许多算法都比较复杂，而且不容易被人们所掌握。所以如何求解半无限规划问题就具有非常重要的实际价值和理论意义。目前，在很多科学技术和工程领域，经常需要实时求解（1）。然而基于电路实现的神经网络，具有大规模并行处理，分布式存储和高度的纠错能力等许多优点，成为一些领域求解大规模优化问题的有效方法。此外运用神经网络求解优化问题也已得到广泛的研究，并取得较好成果[1-4]。基于上述考虑，为实时并行求解问题（1），本文根据其结构特点，构造了求解它的一个神经网络模型，并严格证明该神经网络模型是Lyapunov稳定的，还收敛于问题（1）的精确解。数值实验表明该模型不仅是可行的，而且是有效的。为叙述方便，用‖·‖表示欧氏范数。

1 极大熵函数的提出及其性质

对于半无限规划问题（1），由于它的约束条件的个数是无限多的，不易于求解。文献[5]中证明：当所考虑问题是凸规划时，可用下述问题（2）逼近问题（1）。即问题（1）的最优解可以通过问题（2）的最优解获得。因此本文应用极大熵方法，提出了求解问题（1）的一个神经网络模型。

考虑下述问题：

min g(x)

因此问题（1）的最优解可由问题（3）的最优解来逼近。

由于极大值函数F(x)是不可微的，则问题（3）就是不可微优化问题。因此借助最大熵原理导出一族一致逼近F(x)的可微函数（称之为熵函数），定义如下[6]：

其中 p＞0是控制参数。从而问题（3）可进一步地转化为如下光滑问题：

其中Fp(x)由式（4）定义。因此可以根据定理2，通过求解p充分大时的问题（5）的最优解去逼近原问题的最优解。

为应用方便，下面介绍熵函数Fp(x)的一些性质：

性质1[7]若 fi(x)(i=1，2，…，l)都是凸函数时，则对∀p＞0，Fp(x)也是凸函数。

定理1[7]对∀x∈Rn，p＞0，有：

定理2[7]当x∈Rn，p→+∞时，Fp(x)一致收敛于F(x)。

定理3[7]设 x*是式（1）的解，xp是由极大熵函数法求的近似解，则有：

2 神经网络模型

为建立求解式（5）的神经网络，首先问题（5）满足slater’s条件，即存在 x′∈Rn，使得：

作为构建网络的理论基础，给出其解的充要条件：

定理4 x*是式（5）的最优解当且仅当存在 λ*∈R，μ*∈Rm，使得：

证明显然问题（5）的拉格朗日函数为：

它是定义在C=Rn×R×Rm。

由于问题（5）是凸的，且满足Slater条件，根据凸规划KKT条件知：x*是问题（5）的最优解，当且仅当存在λ*∈R，μ*∈Rm，使得 (x*，λ*，μ*)是 L(x，λ，μ)在 C 上的鞍点，即

由式（7）左边：

进而对 ∀(λ，μ)∈R+×Rm，有：

再对 ∀x∈Rn，且 x≠x*，可知 x*+t(x-x*)∈Rn，∀t∈(0，1)，那么由式（7）右边得：

令t→0，并取极限，就有：

下面引入记号，标记 z=(xT，λT，μT)T，z*=((x*)T，(λ*)T，(μ*)T)T∈Rn+m+1。

其中 F(z)是从Rn+m+1到Rn+m+1的连续映射，C是Rn+m+1上的非空闭凸子集，∇g(x)是g(x)的梯度。于是定理4等价于如下定义的变分不等式VI(C，F)：

又根据射影定理〔8〕和定理4，可进一步推出如下结论：

引理1 x*是问题（5）的最优解当且仅当存在 λ*∈R，μ*∈Rm，使得：

成立。

引理1说明通过求解系统（8）可以得到问题（5）的最优解。为方便，记 λ~＝[λ-Fp(x)]+，根据以上分析和论述，可以得到求解（5）的神经网络，即

其中k＞0是设计参数。接下来根据引理1，可以得到如下关于式（8）的解和式（9）的平衡点这两者之间的关系的结论，即

推论1 令 C*={z∈Rn+m+1|z是式（8）的解}，则 z∈C*当且仅当z是神经网络（9）的平衡点。

3 稳定性分析

为了讨论网络（9）的动力行为，先给出如下引理。

引理2 令 z*=((x*)T，λ*，(μ*)T)T∈ C*是有限的，则

定理5 若∇g(x)、F′p(x)在 Rn上局部Lipschitz连续，则对任意的 z0∈Rn+m+1，神经网络（9）在 [0，+∞)上存在唯一的以 z0为初值的连续解 z(t)(z(t0)=z0，∀t≥t0)(z(t)∈C*)。

类似文献[9-10]中的证明，对网络（9）有如下稳定性结论。

定理6 若∇g(x)、F′p(x)在 Rn上局部Lipschitz连续，则神经网络（9）是Lyapunov稳定的。并且∀z0∈Rn+m+1，对应轨线z(t)(z(t0)=z0，∀t≥t0)在有限时间内收敛于C*中的一个点。特别地，若C*={z*}，则神经网络（8）全局渐近稳定。

4 数值模拟

在pc机上对如下实例用ODE23模拟实验验证神经网络（9）的有效性和上章理论正确性。

例 考虑如下半无限规划问题：

根据上一章的分析，

由极大熵函数法，问题（11）等价于：

其中 p＞0是控制参数。该问题有最优解(x*)′=(-0.191 4，-1.277 3，1.729 2)。易知 (x*)′也是问题（10）的最优解。

用神经网络（9）求解该问题。所有模拟结果表明，对于任意给定的初始点，神经网络（9）总收敛于该问题的精确解。例如，图1显示了k=500和任取30个初始点时网络（9）的轨线性态。

图1 k=500和任取30个初始点时网络（9）的轨线性态1

其中 p＞0是控制参数。该问题有最优解(x*)″=(-0.191 4，-1.277 7，1.729 7)。易知 (x*)″也是问题（10）的最优解。

用神经网络（9）求解该问题。所有模拟结果表明，对于任意给定的初始点，神经网络（9）总收敛于该问题的精确解。例如，图2显示了k=500和任取30个初始点时网络（9）的轨线性态。

图2 k=500和任取30个初始点时网络（9）的轨线性态2

其中 p＞0是控制参数。该问题有最优解(x*)‴=(-0.191 4，-1.277 5，1.729 4)。易知 (x*)‴也是问题（10）的最优解。

用神经网络（9）求解该问题。所有模拟结果表明，对于任意给定的初始点，神经网络（9）总收敛于该问题的精确解。例如，图3显示了k=500和任取30个初始点时网络（9）的轨线性态。

图3 k=500和任取30个初始点时网络（9）的轨线性态3

5 结论

从上述过程可以看出，所提出的新模型不仅可行而且有效。

[1]Gao X B.A neural network for a class of extended linear variational inequaities[J].Chinese Journal of Electronics，2001，10（4）：471-475.

[2]Xia Y S.A new neural network for solving linear programming and quadratic programming problems[J].IEEE Trans on Neural Networks，1996，7：1544-1547.

[3]Xia Y S，Wang J.A general methodology for designing globally convergentoptimization neuralnetworks[J].IEEE Transon Neural Networks，1998，9：1311-1343.

[4]Bouzerdorm A，Pattison T R.Neural network for quadratic optimization with bound constraints[J].IEEE Trans on Neural Networks，1993，4：293-304.

[5]Karney D F.A pathological semi-infinite convex programs and their finite subprograms[J].Math Prog，1963，27：75-82.

[6]Kreisseloneier G，Steinhauser R.Systematic control design by optimizing a vector performance index[C]//Proc of IFAC Symp on CAD of Contor Sys，1979：113-117.

[7]李兴斯.一类不可微优化问题的有效解法[J].中国科学：A辑，1994，24（4）：371-377.

[8]Kinderlehrer D，Stampacchia G.An introduction to variational inequalities and applications[M].New York：Academic，1980.

[9]Gao X B，Liao L Z，Qi L Q.A novel neural network for variational inequalities with linear and nonlinear constraints[J]. IEEE Trans on Neural Network，2005，16（6）：1305-1317.

[10]Gao X B.A novel network for nonlinear convex programming[J].IEEE Trans on Neural Network，2004，15（3）：613-621.

一类半无限规划问题的神经网络算法

杨红梅

YANG Hongmei

Department of Mathematics,College of Changji,Changji,Xinjiang 831100,China

The paper considers the semi-infinite problem with inequalities and equality constraints.By using maximal entropy method,it converts many constraints problem into single constraint nonlinear programming.Then it proposes a new neural network for solving it.It is shown to be Lyapnuov stable,and convergent to an exact solution of the problem in finite time.Illustrative examples show the feasibility and efficiency of the network.

semi-infinite convex programming;maximal entropy function method;neural network

考虑了一类带有不等式和等式混合约束的半无限规划问题。通过运用极大熵方法，将多个约束条件的问题转化为单个约束条件的非线性规划模型，并提出了求解它的一个神经网络模型，严格证明了该模型是Lyapunov稳定的，并且在有限时间内收敛到原问题的一个精确解。数值实验表明，新模型不仅可行而且有效。

半无限凸规划；极大熵函数法；神经网络

A

O221.2

10.3778/j.issn.1002-8331.1203-0551

YANG Hongmei.Neural network model for solving semi-infinite problem.Computer Engineering and Applications, 2013,49（11）：38-40.

昌吉学院科研基金（No.2010YJYB008）；昌吉学院运筹学与最优化研究群体（No.2011YJQT001）。

杨红梅，女，讲师，研究方向：神经网络、最优化理论与算法。E-mail：20813524@qq.com

2012-03-23

2012-06-04

1002-8331（2013）11-0038-03

CNKI出版日期：2012-07-19 http://www.cnki.net/kcms/detail/11.2127.TP.20120719.1112.002.html