（运筹学与控制论专业论文）求解互补问题的微分方程方法.pdf

大连理工大学硬士学位论文 摘要 本文回顾了互补问题的发展历程提出了两种新的求解互补问题的微分方程方法， 包括求解线性互补问题和非线性互补问题的微分方程方法的理论及相应的数值实现。 1 互补问题是在六十年代二次规划中被提出的。它在数学物理，数理经济等领域有着 重要的理论研究价值；同时在一些实际问题当中也有着广泛的用途，例如，金融，交 通规划，电力系统，区域化经济发展等等。因此互补问题的研究受到越来越广泛的重 视关于这方面的研究，大致分为理论和算法两大方向。理论方面主要是研究如何引 进和借助有关技术，概念和思想来设计出各种类型的具体的求解方法，研究焦点集中 在互补问题解的存在性、唯性等；到80 年代后期，经过许多学者20 余年的辛勤 工作，在算法方面取得了丰硕的成果：例如不动点法、同伦法、投影法、牛顿法等都产 生于这个时期九十年代以后，人们又提出了很多有效的算法，例如光滑方程组法、 非光滑方程组法，可微无约束化法，内点法等等后来，基于c h e n m a n g a s a r i a n 磨光技术，人们提出了非内点的研究 2 本文的第3 章对求解线性互补问题的微分方程方法进行了研究。构造了一个新型的 解决线性互补问题的微分方程系统它的结构简单，易于计算在一定的条件下我们 证明了线性互补问题的解是该微分方程系统的平衡点，并且证明了微分方程系统的 稳定性和全局收敛性。最后我们还给出了五个数值算例证明了这种方法的有效性 3 本文的第4 章介绍了有关隐式互补问题的相关知识，并且利用投影算子建立了与之 等价的微分方程系统，这个微分方程系统的平衡点就是隐互补问题的解随后，我们 选取了能量函数，利用其证明了该系统的稳定性 关键词：微分方程系统；线性互补；收敛性；稳定性；隐互补 李阳；解决互补问题的微分方程方法研究 d i f f e r e n t i a le q u a t i o nm e t h o d sf o rc o m p l e m e n t a r i t yp r o b l e m s a b s t r a c t 眦p a p e rr e v i e w st h eh i s t o r yo fc o m p l e m e n t a r i t yp r o b l e m si tm a i n l yp r o v i d e st w o n e wd i f f e r e n t i a le q u a t i o nm e t h o d sf o rt h el i n e a ra n dn o n l i n e a rc o m p l e m e n t a r i t yp r o b - l e m s a n dt os h o wt h ev a l i d i t yo ft h e s em e t h o d s ，w ep r o v i d et h ec o r r e s p o n d i n gn u m e r i c a l e x p e r i m e n t s 1 c o m p l e m e n t a r i t yp r o b l e m sw a ss u g g e s t e di nq u a r t i cp r o g r a m m i n gi n1 9 6 0 s i th a s v e r yi m p o r t a n tv a l u e si nm a t h e m a t i c a lp h y s i c sa n dm a t h e m a t i c a le c o n o m yf i e l d s ； a tt h es a m et i m e ，i ta l s oh a sw i d e l yu 鼬粥ei nm a n yp r a c t i c a lp r o b l e m s s u c ha s ， f i n a n c e ，t r a n s p o r t a t i o np r o g r a m m i n g ，e l e c t i cs y s t e m ，r e g i o n a ld e v e l o p m e n t ，e c t t h u s t h er e s e a r c h e so fc o m p l e m e n t a r i t yp r o b l e m sa t t r a c tm o r ea n dm o r ea t t a i n t i o n a n d t h e r ea r et w oa s p a c t so ft h i sp r o b l e m ：t h e o r i e sa n da l g r i t h m s i na c a d e m i ca s p e c t ， t h er e s e a r c h ei sp r i m a r i l ya b o u th o wt oi n t r o d u c et h ec o r r e l a t i v et e c n i q u e s ，d e f i n i t i o n s a n di d e a st od e s i g nt h em e t h o d st or e s o l v et h ec o m p l e m e n t a r i t yp r o b l e m s i tf o c u s e s o nt h es o l u t i o n se x i s t a n c ea n du n i q u e n e s s i nt h el a s to f1 9 8 0 s ，w i t ht h et w e n t y - y e a rh a r dw o r ko fm a n ys c h o l a r s ，al o to fa c h i e v e m e n t so fi nt h i sf i e l d sa p p e a r f o r e x a m p l e s ，s t a t i o n a r yp o i n tm e t h o d ，h o m o t o p ym e t h o d ，p r o j e o t o nm e t h o d ，n e w t o n m e t h o da n ds oo i l a f t e r1 9 8 0 s ，s c h o l a r ss u g g e s ts o m eo t h e re f f e c t i v e 姆i t h s f o ri n s t a n c e ，s m o o t hd 丑；e r e n c i a le q u a t i o nm e t h o d ，n o n s m o o t hd i f f e r e n c i a le q u a t i o n m e t h o d ，d i f f e r e n c i a lu n c o n s t r a i n i z i n gm e t h o d ，i n n e rp o i n tm e t h o d r e c e n t l y , b a s e d o nt h eb u r n i s h i n gt e c n i q u eo fc h e na n dm a n g a s a r i a n ，s o m e o n eh a ss u g g e s t e dn o n - i n n e rp o i n tm e t h o d 2 i nc h a p t e r3o ft h i s p a p e r ，w ep r e s e n tad i f f e r e n t i a le q u a t i o ns y s t e mf o rs o l v i n g l i n e a rc o m p l e m e n t a r i t yp r o b l e mi nr e a lt i m e i tp o s s e s s e sav e r ys i m p l es t r u c t u r e f o ri m p l e m e n t a t i o ni nh a r d w a r e i nt h et h e o r e t i c a la s p e c t ，t h i ss y s t e mi sd i f f e r e n t f r o mt h ee x i s t e n t sw h i c hu s et h ep e n a l t yf i m e t i o u so rl a g r u n g i a n s w ep r o v et h a t t h ep r o p o s e dd i f f e r e n t i a le q u a t i o ns y s t e mc o n v e r g e sg l o b a l l yt ot h es o l u t i o ns e to ft h e p r o b l e ms t a r t i n gf r o ma n yi n i t i a lp o i n t i na d d i t i o n ，t h es t a b i l i t yo fi t i sa n a l y z e d a n df i v en u m e r i c a le x a m p l e sa r eg i v e nt ov e r i 母t h ev a l i d i t yo ft h ed i f f e r e n t i a le q u a t i o n s y s t e m 3 i nc h a p t e r4 ，w ei n t r o d u c et h ed e f i n i t i o no fi m p l i c i tc o m p l e m e n t a r i t yp r o b l e m sa n d s t r u c ta ne q u i v a l e n tp r o j e c t i o nd i f f e r e n t i a le q u a t i o ns y s t e m a n dt h e nw ep r o v et h e e q u i l i b r i u mp o i n to fs y s t e mi se x a c tt h es o l u t i o no ft h ei m p l i c i tc o m p l e m e n t a r i t y p r o b l e m a f t e rt h a t ，w ec h o o s ea ne n e r g l cf u n c t i o nt op r o v et h es t a b i l i t yo ft h e d i i i e r e n c i a le q u a t i o ns y s t e m 大连理工大学硬士学位论文 k e yw o r d s ：d i f f e r e n t i a le q u a t i o ns y s t e m ；l i n e a rc o m p l e m e n t a r l t y ；c o n v e r - g e n c e ；s t a b i l i t y ；i m p l i c i tc o m p l e m e n t a r i t y 独创性说明 作者郑重声明：本硕士学位论文是我个人在导师指导下进行的研究工 作及取得研究成果。尽我所知，除了文中特别加以标注和致谢的地方外，论 文中不包含其他人已经发表或撰写的研究成果，也不包含为获得大连理工大 学或其他单位的学位或证书所使用过的材料与我一同工作的同志对本研究 所做的贡献均已在论文中做了明确的说明并表示了谢意。 大连理工大学硬士学位论文 大连理工大学学位论文版权使用授权书 本学位论文作者及指导教师完全了解4 大连理工大学硕士、博士学位论文版权使用 规定”，同意大连理工大学保留并向国家有关部门或机构送交学位论文的复印件和电子 版，允许论文被查阅和借阅。本人授权大连理工大学可以将本学位论文的全部或部分内 容编入有关数据库进行检索，也可采用影印、缩印或扫描等复制手段保存和汇编学位论 文 作者签名： 互陛一 导师貅毽立乙导师签名：乏：j 董垒：至 大连理工大学硕士学位论文 引言 本论文研究如下形式的互补问题： 定义设f ：形一舻是连续可微的，所谓非线性互补问题就是以下方程和不等式组 的一个解，或等价的求解 。0 ，f ( x ) 0 ，z t f ( x ) = 0 z t 0 ，只( z ) 0 ，玎r ( z ) = 0 ，i = 1 ，2 ，n 记这个问题为n c p ( f ) 当映射是具有如下形式 f 扛) = m x + q 的仿射函数时，其中m 是个n n 的实矩阵，则此互补问题被称为线性互补问题，简记 为l c p ( m ，q ) 而隐互补问题是指求解。酽使得 g ( z ) 0 ，f ( z ) 0 ，g ( z ) t f ( z ) = 0 成立其中f ( z ) 和g ( z ) 是连续可微的单调映射；n 一彤定义为( i n c p ( f ，g ) ) 求解问互补题有许多有效的算法，例如，惩罚函数法，障碍函数法，增广l a g r a n g e 函数法，内点法，序列二次规划方法和信赖域法等 本文通过微分方程方法对互补问题进行研究。 大连理工大学硕士学位论文 1 绪论 文章概述了求解互补问题的微分方程方法的历史及研究现状，并对本文所凭借的主 要理论工具一微分方程的稳定性理论，给出了简要的介绍。 1 1互补问题微分方程方法的研究进展 在r i c h a r dc o t t l e 的博士论文卟n o n l i n e a rp r o g r a m sw i t hp o s i t i v e l yb o u n d e dj a c o b i a a s ” 中首次出现了互补问题。后来在c o t t l eh a b e t l e t r 和l e m k e 整理的文献1 2 】q u a & a - t i cf o r m s s e m i - d e f i a i t eo v e rc o i i v e xc o i l e s ”中才被真正称为互补问题。 非线性互补问题是在六十年代二次规划中被提出在数学物理，数学经济等领域有 着重要的研究价值；同时在一些实际问题当中也有着广泛的用途。例如，金融，交通规 划，电力系统，区域化经济发展等等。因此对非线性互补问题的研究受到越来越多的重 视 关于互补问题的研究，大致分为理论和算法两大方向，理论方面的研究焦点集中与 互补问题解的存在性、唯一性等；通过研究如何引进和借助有关技术，概念和思想来设计 出各种类型的具体的求解方法到80 年代后期，经过许多学者20 余年的辛勤工作， 在算法方面取得了丰硕的成果：例如不动点法、同伦法、投影法、牛顿法等九十年代以 后，人们又提出了很多有效的算法，例如光滑方程组法、非光滑方程组法，可微无约束 化法，内点法等等。近来，基于c h e na n dm m a g a s a r i a n 磨光技术，人们提出了非内点的研 究如r u r k ej 、f e r r i s m c ，h a r k e rp t 和x i a o b 、p a n gjs 、s o a r e s 等( i ) 对缵陛 互补问题，有直接方法( 如l e m k e 点法，c o t t l e - d e n t z i g 法) 和迭代法( 如m a n g a s a v i a n 法) ；( i i ) 对非线性互补问题，有不动点法，同伦法，投影法，牛顿法等90 年代后， 人们又提出许多有效的算法，如光滑方程组法，非光滑方程组法，可微无约束优化法， 内点法等。后来人们又提出了外点法。 下面简要介绍几种解互补问题的重要思想： 1 可微的无约束优化方法：就是把互补问题转化为一个与之等价的可微无约束优化问 题，然后用某种大范围或n e w f o n 类型法求解其重点在于互补问题的转化上。 2 g l p 投影法：这种方法是基于g o l d s t e i n - l e v i t i n p o l y a k 求解图规划的梯度投影法思想 来求解互补问题。它的优点是计算量小，存储量小，保稀疏性 3 李阳：解决互补问题的微分方程方法研究 3 内点法：这是把互补问题转化为一个与之等价的非负约束方程组，然后用n e w t o n 类 型法求解互补问题。它起源于k a x m a r l a x r 求解线性与凸二次规划的内点法，也是这种 方法的自然延伸。 4 微分方程方法：将非线性互补问题转化为等价的优化问题或光滑的方程组，然后利用 微分方程方法进行求解 ( 钆n ( z ) ) 1 g 。：2 【。，- 。，j 妒( o ，6 ) = e ( 1 a b 1 ) 一e ( a ) 一目( 6 ) ( 1 1 1 ) ( 1 1 2 ) 这里r ( z ) 是f ( x ) 的第i 个分量， = 1 ，2 ，n ；o ( t ) ：r r 是个严格递增的函数， 满足日( o ) = 0 。称庐( o 扣) 为n c p 函数或势函数在文献【目中，m a n g a s a r i a a 证明了非线 性互补问题n c p ( f ) 的解与方程组( 1 1 1 ) 解的等价性基于n c p 函数( 1 1 2 ) ，k a n z o w ( 4 】 考虑下面阶方程组： 日( o ，y ) = 掣一f ( 嚣) 曲( 0 1 ，y 1 ) 毋( 研。，执；) = 0 ( 1 1 3 ) 他给出了矩阵在的非解点出存在逆的几个充分条件t s e n g s l 则把( 1 1 3 ) 变成方程 e p ( z ，y ) = ( y f ( g ) p 庐( z 1 ，可1 ) ( z n ，3 h ) = 0 ，p 0 ，( 1 1 4 ) 进而研究l i h i i 和i l 正例的增长行为 由于n c p 函数并不是处处光滑的，光滑滑函数方法求解n c p 问题成为学者们研 究的重要课题文献中已经给出了多个光滑函数，例如神经网络函数【6 】，c h e n - h a x k e r - k a n z o w - s m a l e ( c h k s ) 光滑化函数f 7 一，g a b r i e l 和m o r e 9 提出的光滑化西毂族等。 最为常见的n c p 函数有： ( 1 ) f i s h e r - b u r m e i s t e r 函数【1 0 】：舒hr 五，定义为： 它具有下述几个性质 曲( n ，b ) = 石巧面一。一b 1 曲( o ，b ) = 0 当且仅当d 0 ，b 0 ，a b = 0 4 大连理工大学硕士学位论文 2 ，州o ，的的平方是连续可微的； 3 妒除原点外都是二次连续可微的。 ( 2 ) 最小值函数m j n # ，f ( z ) ) 利用n c p 函数就可以将互补问题等价于一个微分方程组，进而进行求解当然，现 在已经发现的n c p 函数很多，在此不一一列举了 1 2 优化理论的微分方程方法的研究进展 自求解最优化问题的微分方程方法问世以来，无论在理论研究还是算法研究上均取 得了一系列重要进展该方法将最优化问题归结为求一个( 往往是自治的) 微分方程组 的平衡点的问题，从而将复杂的优化问题( 特别是约束非线性规划问题) 的求解转化为 较为成熟的常微分方程组得数值求解，开辟了求解非线性最优化问题的一条新途径另 一方面，求解最优化同题的微分方程系统往往是一神经网络模型，因此，最优化微分方 程方法的深入研究无疑会推动神经网络方法求解最优化问题的进展 用微分方程的方法求解约束非线性最优化问题，最早由a r r o w 和h u r w i c z “】提出， 他们考虑的是等式约束最优化问题( 既在n l p 中m = 0 ) f i a c c o 和m c c o r m i c k 1 q 用微 分方程方法对约束规范e v t u s h e n k o 和z h a d a n ( 1 9 7 3 - 1 9 7 4 ) 1 3 1 比较早得对等式约束问题 进行了研究。其后，y a m a s h i t a i z 4 和z h a d a a 1 5 , 1 6 , 1 7 , 1 8 , 1 9 及p 对该方法进行了发展 和完善特别是e v t u s h e n k o 和z h a d a n 从1 9 7 3 年开始，利用微分方程的稳定性理论，对 n l p 问题以及一般闭集上的约柬问题( 这样个抽象的模型) 的微分方程方法做了大量的 研究，丰富了非线性规划问题的微分方程方法，形成了系统的理论 非线性规划微分方程方法的主要思想是：将一个数值优化算法与一个微分方程系统 相关联，所构造的这个微分方程系统具有这样的性质：它的平衡点( e q u i l i b r i u mp o i n t s ) 恰 好是非线性规划问题的全局最优解、局部最优解或k u b n - t u e k e r 点，将数值算法的收敛 性问题转化为微分方程平衡点的稳定性判别问题 下面我口】简要回顾一下该方法的研究情况首先介绍非线性规划问题： m i n ，( z ) 8 t ， 口渖) 兰0 ( ) = 0 印 其中函数，：r n r 1 ，g ：邪一j 和h ：舻一r i 都是二次连续可微的这个问题 定义为( n l p ) 为了叙述方便起见，记v f ( z ) 为函数，在z 处的梯度向量，v 2 ， ) 为函数，在z 处的h e s s e 阵。定义n l p 问题的函数为； 工扛，“， ) = ，0 ) 一u 勺扛) + t ) 。处的紧约束指标集为，( z ) = 矧吼( z ) = 0 ，i = 1 ，m ) 5 李阳：解决互补问题的微分方程方法研究 对无约束优化问题( n l p 中f _ 0 ，m = 0 ) ，b o t s 鲥g 【2 1 】与a m 炉 2 2 用精确微分方程 方法对他进行求解，定义了下面的微分方程系统 a ， 等= 一o ( z ) 一1 v ，( ) ， 其中口( z ) 是对称正定矩阵在v 2 f ( x ) 正定的情况下，b o t s a f i s 证明了通过此微分方程 系统求得的解是优化问题的最优解；在v ，( z ) 的水平集是凸性的假设下，a m a y “证明 了收敛性定理 关于等是约束问题( n l p 中m = 0 ) ，也有许多学者利用微分方程方法对它进行了求 解例如，b r o w n 和b a r t h o l o m e w - b i g g s 2 3 ，驯提出了含有罚函数的参数化相关的微分方程 系统， 面2 一瓦虫忙，7 ) ， 其中圣( 。，r ) = ，( 。) + ； = l ( 茹) 2 是外点罚函数，利用此系统仅匏求得近似解并且r 不能 取得非常大。因而效果不是很好 为了能够求得较精确的解，t a n a b l e ( 1 9 7 4 ) ，y a m a s h l t a ( 1 9 8 0 ) ，e v t u s h e n k o 和z h a d a n ( 1 9 - 7 4 ，1 9 8 5 ，1 9 9 4 ) 都利用l a g u r a n g e 函数，提出了不同的微分方程系统来求解极小化问题在 v k 0 ) ，i = l ，f 对任意的z 舻均是列满秩的假设条件下。她们阐述了所提出的微分 方程系统有定义。在此条件下，t a n a b e 等诸位学者分别给出了下述的各微分方程系统 t a n a b e 给出微分方程系统 署= ( i 一口( z ) ) ( 一v ，( z ) ) ， 见文献f 2 5 】，其中，q ( $ ) - 一v h ( x ) r ( v h ( x ) v h ( x ) t ) 一1 v y a m a s b l t a ( 1 9 8 0 ) ，e v t u s h e n k o 和z h a d a a ( 1 9 7 4 ，1 9 8 5 ，1 9 9 4 ) 定义了相似的系统 b ( 茁) d 2 出= 一( v ，( 嚣) + v h 扛) t u 扛) ) ， ( 1 2 1 ) d h ( x ) d t = 一他( z ) 其中b ( z ) 静“是对称正定矩阵，7 0 为常数在系统( 1 2 1 ) 中，若取r ；1 ，b ( z ) i j ， 则得到y a m 鹅l l i t a f l q 的个微分方程系统，研究表明系统( 1 2 1 ) 描述的轨迹在奇点矿附 近十分复杂，这是一严重的缺陷若取r - - 7 - - 1 ，b ( z ) = v l l ( 。，u ( 。) ) ，则得到y a m a s h i t a 的 牛顿系统，他克服了上述匿难，使在矿附近的解变成： z ( t ) 窒! 茹+ + ( 茁( o ) 一z ) e 一， 并且该方法具有二阶收敛速度由于收敛的区域被严格限制在稳定点的邻域内，与是y 靠 m a s h i t a 利用迹连续的技术，扩大了收敛的区域 若取b ( x ) ；p 一，r 0 ，则得到b v t l l 日h e n k o 和z h 8 d 8 n 【1 5 】的微分方程系统，这一系 统被他们称为障碍投影法( b a r r i e rp r o j e c t i o nm e t h o d ) 张立卫( 1 9 9 9 ) 2 6 】对等式约束问题 ( n l p 中m = 0 ) 提出下述微分方程系统 d x d t = 一b ( z ) v z 工( z ，“( $ ) ) ， f l f 2 2 ) d h ( x ) d t = ( h ( z ) ) ， 其中b ( x ) r n 为正定矩阵，：r 一剜满足条件 6 大连理工夫学礤士学位论文 1 庐( ) 在剜的原点邻域u 上可微，雅可比矩阵v 西( ) t 的所有特征值在u 上有负实 部 2 垂( ) 在u 上有唯一不动点，即( z ) = z 当且仅当z = 0 成立。系统( 1 2 2 ) 概括了系统 ( 1 2 1 ) ，是对系统( 1 2 1 ) 的推广。 e v t u s h e n k o 和z h a n d a n ( 1 9 9 4 ) 1 q 甩微分方程法对下列更一般的约束问题进行了研究 篓二邛m l h ( 。) - 0 鲫 ( 1 2 3 ) z x = z ) 等o z ，。p 、。 其中p 为不等式约束，假设p 有非空的内部 他们对问题利用空间变换技术，等价的转化为只有等式约束的问题，再通过逆变换 得到如下微分方程系统 如斑= 一g ( x ) v = l ( x ，u ( z ) ) ， f ( $ ) t ( z ) + v ( 。) g ( z ) v ，( z ) = r h ( z ) ，( 1 2 4 ) z ( o ，o ) = 知p 逆变换的作用使得微分方程的右边被乘上一个矩阵g ( x ) ，只要初始点位于p 内，以此为 初始点的孰迹就不会穿出p ，因此g 0 ) 起到了障碍作用在此种空间变换的基础上， e v t u s h e n k o 和z h a d a n 全面研究了障碍投影法和障碍牛顿法的收敛性和收敛速度方便起 见，e v t u s h e n k o 和z h a d a n 仅对p = 啦的情况进行研究，通过分量空间变换一事( 扩) 和逆变换，统( 1 2 4 ) 可转化为： 豢；一d ( 俐v 。三。，u 扛) ) 其中日p ) = 矿，n 0 ，d ( 口( z ) ) 为对角型矩阵即使对这样简单的系统，它们的收敛 性理论也要在下述条件下得到证明：c 3 ：( ) 当且仅当一= 0 伊( o 0 时成立于 是s m i r n o v 2 日提出了向量李雅普诺夫方法，在较弱的条件下，解决了收敛性问题 当处理混合约束问题( n l p 中z 0 ，m 0 ) 时，一个容易想到的方法就是通过引入 人工变量把不等式约束问题转化为等式约束问题这一思想被z h o u ( 1 9 9 7 ) 2 8 及张立卫等 ( 2 0 0 0 ) 1 2 9 利用，构造了求解混合约束优化问题的微分方程系统 z h o u 【2 8 1 通过引入松弛变量z ，将非线性规划问题转化为 m 讥 f ( g ) = ，0 ) s t v s = y e 舻十”1 日c 们= ( ：高一。，。) = 。) ， 其中9 = 0 ，z ) ，j = 矧虫= o ，t = l ，m 表示9 ) 的紧约束指标集，在梯度 v h l ( z ) ，v ( z ) - qv m ( z ) ， j ( z ) 线性无关的条件下，他提出了下述微分方程系统 ( 鼬b m d 。脑出) + v h ( z ) a i + 勖。风) = ( ) 7 李阳：解决互补问题的微分方程方法研究 ( 咐v h ( z ) d x d t d x d t o ( z ；) d z d t ) = ( 裂+ z 2 2 ) ，趵( 。) t 一 一9 0 ) + 其中，d ( ) = d i a g ( z l ，) 而张立卫( 2 0 0 0 ) 2 9 i 通过引入松弛变量g ，将问题非线性规戈f f 问题转化为 r a i n ( z ) = ，0 ) s t h ( z ) = 0 ， z r “+ 其中 日( z ) = ( 9 。) - ( 。d ) ”9 ) ，：= ( z ，f ) 与之相关的微分方程系统为 d z d t = 一日( z ) v 二l ( z ， ( z ) ) ， d h c z ) d t = 圣( 日( z ) ) ， 其中b ( z ) 冠( n + m ) x ( n + m ) 对称正定。圣：口忡一舻州为满足下列条件的映射： 1 由( ) 在u 上可微，u 是舻州空间的原点的个邻域，并且垂( - ) 的雅可比矩阵v 日垂( ) t 在u 上有负实部。 2 0 是垂( ) 在u 上的唯一固定点，即壬( z ) = z 成立当且仅当z = 0 在文献| 嚣】中仅需要梯度v h z ( x + ) ，v h d x + ) 与v g t ( x + ) 是线性无关的即可它不但具有 不需要初始点可行的优点，而且还能保持可行性，即如果当前点是可行的，则它的后续 轨迹( s u b s e q u e n tt r a j e c t o r y ) 始终保持在可行域中 另一方面，各种由微分方程系统描述的神经网络模型被提出求解非线性最优化问题 自h o p f i e l d 和t a n k 首次提出解线性规划的一个神经网络 3 0 , 3 1 , 3 2 以来，采用神经网络求 解最优化问题得到了相当深入的研究，已发展了多种不同形式的求解非线性最优化问题 的神经网络模型 对无约束优化问题( n l p 中f 0 ，m 0 ) ，助d r i g u 协v a z q l l ( 1 9 9 0 ) 删，c i c h o c k i 和 u n h b e h a u e n ( 1 9 9 3 ) a 4 ，提出了基于最逮下降法的神经网络动态系统 塞= 一w v f ( 吐 其中是对称正定矩阵，它们证明了神经网络的平衡状态对应于问题的局部最优解 o s o w s k i ( 1 9 9 2 ) 3 5 ，c i c h o c k i 和u n h b e h a u e n ( 1 9 9 3 ) a a 对上述问题进步进行了研究， 基于n e w t o n 法提出了下列神经网络动态系统 詈= 一 v 2 ，( z ) j - 1 v ，0 ) 虽然基于n e w t o n 法的神经网络系统具有较快的收敛性，但有时h e s s e 阵会出现奇异性问 题，因而c i c h o c k i 和u n h b e h a u e n ( 1 9 9 3 ) s 4 对上述神经网络进行了改革，提出了l e v e n b e r g - m a r q u a r d t 法的神经网络动态系统 等= 一w v 2 ，( z ) + 调_ 1 v ，( z ) ， 8 大连理工大学硬士学位论文 其中j 为单位矩阵，7 为一适当的正数 对不等式约束问题( n l p 中1 = 0 ) ，k e n n e d y 和c h u a ( 1 9 8 8 ) 3 6 利用梯度法和罚函数 法给出了下列神经网络动态系统 盘警= 一掣一；= 乳1j 型o z i ，n ， 其中c 为正数，弓= p j 渤( z ) ) ，并且有如下定义 咖) ：n ” 0 【击 o 庐l ” l0 ，否则 l i l l o 等( 1 9 9 3 ) 3 7 对k e n n e d y 和c h u a ( 1 9 9 8 ) s 6 的非线性最优化神经网络给出了进一 步的分析，指出k e n n e d y 和c h u a 的神经阿络本质上是基于罚函数方法，在电路实现时， 罚系数不能任意大。从而降低了神经网络求解的准确性针对这些问题，l i l l o 等提出了 神经阿络动态系统 鲁= 一水月( j 酗掣) + 岛等 ， 其中鼠，口是饱和函数& ，口在拐点。= 一卢和。= 卢处经过光滑处理后的非线性函数， = 睢 品a = 品，且。 7 ，廊= s i ( 毋( 。) ) ，8 ；c ( g j c x ) ) 2 m i n o ，8 矗渤( 甸) ，c 0 ，由于e 近似 为0 ，所以西，又可以近似为西= s 卵( 渤( 。) ) c 2 一c 2 c i c h o c l d 和u n b e h a u e n ( 1 9 9 3 ) 1 s 4 1 基于增广l a g r a u g e 函数 砸，小) = 他) + 互1 j m 兰。l 丢( 删邮，脚+ 酬瑚) 2 一詹l ， 给出了神经网络动态系统 垫d t = 一q o 呐f ( x ) + 墨 s ：f 帆+ 缸肌( 瑚掣 ) ，= ，n ， 警= 胁陋矿眚( 1 - 最) i ，i _ 1 ， l m ， 9 李阳：解决互补问题的微分方程方 姗究 其中脚，如和店都是正的变量或常数，通常情况下，一脚他非常小，可以忽略在增广 l a g u r a n g e 函数病态的情况下，c i c h o c k i 和u n b e h a u e m ( 1 9 9 1 ) 3 8 在增广l a g r a n g e 函数中引 入了正则化( r e g u l a x i z a t i o n ) 项，以消除惩罚项造成的不稳定，给出了正则增广l a g r a n g e 函数 工( z ，p ，k ) ：，( z ) + 曼沁西( $ ) 】- + ；h ( 甑( z ) 】一) 2 】一芸萋卢 ，工 ，p ，) = ，扛) + ，汕 西( $ ) 】一+ 言h ( 【仉( z ) 】一) 2 】一吾曼卢 ， j = zzj = i 其中味( z ) 】_ = m 讯妇( z ) ，一脾风) ，胁s0 ，口0 使正则化参数 c i c h o c k i 和 u n b e h a u e n ( 1 9 9 3 ) 8 t 对上述函数提出了神经网络系统对等式约束问题，和提出了规划神 经网络 鲁一q ( 掣+ 薹p c 删掣 ) im 百d l z l = 以嗡毋( 。) 一a 地】 = 1 ，m 对等式约束问题( n l p 中m = 0 ) ，z h a n g 和c o n s t a n t i n i d e s ( 1 9 9 2 ) s 9 提出了l a g r a n g e 规划神经网络 等= - v 。工( z ，a ) ， ( 1 2 5 ) 等= 一v 牡( z ， ) ， ( 1 2 6 ) 其中三( 毛a ) = ，( z ) + a t h ( x ) ， r t 为l a g r a n g e 乘子向量方程( 1 2 5 ) 成为变量神经 元，它提供问题的最优解，方程( 1 2 6 ) 称为乘子神经元，它使得阿络收敛于可行域内 但是，这一方法局部最优解的存在依赖于优化问题的结构凸性，即要求v 工( z ，a ) 在动 态域内正定针对这一缺陷，他们提出了基于增广l a g r a n g e 乘子法的神经网络系统 警= 一差一，i 。( + 啦( 瑚鲁，t - l i z h a n g 等( 1 9 9 2 ) 4 0 1 又提出了二阶神经网络 蔫骱0 缸 驯d m 出d t - v 篙砷 【v ( ) tj 【jl ( 士) j 值得强调的是这一网络对h e s s e 阵吧工( z ，a ) 在整个空间内无正定性要求 对混合约束的问题，m a s s 和m i c h a e l ( 1 9 9 2 ) 1 4 1 】提出了一种两阶段优化神经网络，当 0 t s t l 时，网络的动态系统为 等= - v f ( z ) 一s ( v 加( ) 酊( z ) + v 危( 。) ( z ) ) ， 当t t 1 时，网络的动态系统为 d x d t = - v f ( = ) 一v g ，( s g 了+ 肛) 一v h ( s h ( x ) + a ) d d t = e 扣 ) ， d 卢d t = e ( s 盯) ， 1 0 大连理工大学硬士学位论文 其中j = i b 0 则称f 在集合耳上是严格单调的； 若对于任意的蜀y k ，存在a 0 ，使得f 满足： 【f ( 动一f ( 口) 】r ( 霉一y ) a | | z y i i “ 则称f 在集合k 上是强单调的； 若对于任意的y k ，z y ，f 满足 “限( z ) 一只( 妁】扛t 一坎) o 则称f 为集合上的p 一函数； 若对于任意的2 ，口k ，z y ，f 满足 m 竽陬( $ ) 一最( ) 】( 而一非) o 则称f 为集合k 上的岛一函数； 若对于任意的毛y k ，存在a 0 ，使得f 满足 m 争x 最( 。) 一日0 ) 】( 戤一鼽) 口| | z yf i ；， t 李阳：解决互补问题的微分方程方法研究 则称f 为集合耳上的一致p 一函数； 定义( 2 1 2 ) ：一个矩阵w 胛被称作 p o 一矩阵，如果矩阵的所有主子式均非负； p 一矩阵，如果矩阵w 的所有主子式均为正； 从上面可以知道，一致p 一函数是p 一函数，尸一函数是p 0 一函数，单调函数是蜀一 函数，严格单调函数是p 一函数，强单调函数是一致p 一函数此外，每个连续可微的 p 0 一函数的雅可比矩阵是p 0 一矩阵 定义( 2 1 3 ) ：如果对于任意的z ，o n 曼舻有下列 i f f ( ) 一f ( y ) | | 5 工i i 。一y 成立，其中l 0