（运筹学与控制论专业论文）指数函数空间变换的互补问题的微分方程方法.pdf

大连理工大学硕士学位论文 摘要 本文主要研究非线性互补问题，提出了一个求解非线性互补问题的微分方程方法并 进行了相应的数值实现。 第一章介绍了互补问题的背景。研究互补问题，大致分为理论和算法两大方向。理 论方面主要是研究如何借助有关概念和思想来设计出各种类型的具体的求解方法，焦点 集中在互补问题解的存在性、唯一性等；算法方面，到8 0 年代后期提出了不动点法、 投影法和牛顿法。九十年代以后，人们又提出了很多有效的算法，例如光滑方程组法、 非光滑方程组法、可微无约束化法、内点法等等。后来，基于c h e n & m a n g a s a r i a n 磨光 技术，人们提出了非内点的研究。 第三章对求解非线性互补问题的微分方程方法进行研究，先将非线性互补问题补转 化为等价的不等式约束非线性规划问题，再利用空间变换，将不等式约束优化转化为等 式约束优化问题。然后构造了一个微分方程系统求解该优化问题，证明了非线性互补问 题的解与构造的微分方程系统的平衡点是等价的，并在此基础上建立了一个数值算法， 给出了该数值算法的收敛性证明。 第四章计算了互补问题的几个例子，数值结果表明它们对规模不是很大的问题是有 效的。 关键词：非线性互补；渐进稳定；微分方程方法；平衡点 指数函数空间变换的互补问题的微分方程方法 ad i f f e r e n t i a le q u a t i o n 印p r o a c h ，b a s e do nt l l es p a c e 仃a n s f o 彻a t i o no f e x p o n e n t i a l 如n c t i o n ，t oc o m p l e m e n t a 巧p r o b l e m s a b s t r a c t 1 1 1 i sp 印e ri sd e v o t e dt o 也es t i l d yo nn 啪e r i c a la l g 谢m m sf o rn o i l l i n e a rc o m p l e m e n t a r y p r o b l e m s np r o v i d e san e wd i 丘b r e n 矗a le q 眦t i o na p p r o a c hf o rn o n l i l l e a rc o m p l e m 肋t a r y p r o b l 锄sa n dr 印o r t sn u m e r i c a l 证l p l 锄e n t a t i o n s c h a p t e r1i m m d u c e st h eb a c k g r o u n do fc o m p 王e m t a r yp r o b l e m s t h e r ea r c 伽oa 酗e c t s o ft l l ep m b l e m s ：t h e o r i e sa n da l g o r n s h la c a d 咖i c 韶p e c t ，t l l er e s e 盯c hi sp r i m a m ya b o u t h o wt oi m r o d u c ed e f i n i d o n sa n di d e a st od e s i g nt 1 1 em 劬o d st or e s o l v e 也ec 伽叩l e m e m a r y p r o b l e m s i tf o c 璐e so nt h es 0 1 l n i o n se x i g t e n c ea n dl l n i q u e n e s s i nn l el a s to f1 9 8 0 s ，al o to f a c h i e v e m e n t si i la l g o 血h n l sh a v eb e e nm a d e f o re x 唧l e ，、v eh a v es 协d o n a r yp o i n tm e m o d s ， p m j o c t i o nm e m o d s ，a n dn e 州o nm e m d d s a 丘e r19 9 0 s ，s o m ee 虢c t i v ea 1 9 0 r i t l l m sh a v e b e e nc o n s t r i l c t e d f o rm s 协n c e ，s m o o t hd i 珏曲即t i a le q w 惦o nm e t h o d s ，0 n 锄o o me q 删o n m e t h o d s ，d i 髓。r e 埘a b l eu n c 伽鼬r a j 由e dm e 廿l o d s ，a n dm t e r i o rp o i n tm 葩l o d s r e c e n t l y ，b a s e d o nt h ep 0 1 i s l l i n gt e c 埘q u eo fc h e na n dm 趾g 嬲a r i a i l ，an o i l - i n t e r i o rp o i n tm e m o dh a sb e c n d e v e l o p e d c k r p t e r3i s t 1 1 em a i l lp a r to ft h i sd i s s 睨例0 1 1 ，w i l i c hs t l l d i e sd i 丘b r e 耐a le q 删o n a p p r o a c h e s f o r s o l 啊n gn o i l l m e a rc o m p l e m e i i t a r yp r o b l e m s w ec o n v e r tan o n l i i l e a r c o m p l e m e n t a r yp r o b l e i nt 0a l le q m v a l e n ti n c q l l a i i 够c o n s t r 豳e dn o n l i n e 盯p r o g r 锄m i n g ( n l p ) p r o b l e m 舳e r t l l 鸸c o n v e n 舭m q l l a l 畸咧曲a i n 甜n l pp r o b l 锄t o a n n l pp r o b l e m 丽t 1 1 e q l l i 母c o n s t r a d n tb ys p a c e 廿锄s f o n n a t i o n ad i 恐r e n t i a le q l l a t i o ns y s t e mi sc o l l s m 眈dt o s o l v et h en l p p r o b l e m s np r o v e st h a ts o l 埘o i l st ot l l en 0 i l l i l l e a rc o m p l e m e i l t a r yp r o b l e ma r e e q l l i l i b 商】h lp o i n t s t ot l l ed i 丘柏l t i a le q 删o ns y s t e m am m l e r i c a l 以g o r i 血m ，b a s e do n s o l v i n gt h ed i 行e r e 】砸a ls y s t e m ，i s 西v e n 鼬dp r o v e dt ob ec o n v e r g e m c h a p t e r4p m v i d e sn u m e r i c a ie x p e r i m e n t sb yt h ea l g o d m mf o rs e 、1 e r a le x 锄p l e so ft l l e n o n l m e a rc o m p l e m e n t a r yp r o b l c m s t h en u m e r i c a lr e s i l l t ss h o wm a tt l l ep r o p o s e da l g o m h m i se f f e c t i v ea tl e a s tt 0s o l v eo p e 瑚上i 、屯p r o b l e m sw i 吐lr e l 撕v es m a l ls c a l e s k e yw o r d s ：n o n i i n e a r m p l e m e n t a r y ；d i f f e r e n t i a ie q u a t i o a p p 阳a c h ；a s 呻p t o t i c a l s t a b i l n y ；e q u 丑i b r i m p o i 缸 独创性说明 作者郑重声明：本硕士学位论文是我个人在导师指导下进行的研究工 作及取得研究成果。尽我所知，除了文中特别加以标注和致谢的地方外， 论文中不包含其他人已经发表或撰写的研究成果，也不包含为获得大连理 工大学或者其他单位的学位或证书所使用过的材料。与我一同工作的同志 对本研究所做的贡献均已在论文中做了明确的说明并表示了谢意。 作者签名：丝日期：垫! 壹：! ：型 大连理工大学硕士研究生学位论文 大连理工大学学位论文版权使用授权书 本学位论文作者及指导教师完全了解“大连理工大学硕士、博士学位论文版权使用 规定”，同意大连理工大学保留并向国家有关部门或机构送交学位论文的复印件和电子 版，允许论文被查阅和借阅。本人授权大连理工大学可以将本学位论文的全部或部分内 容编入有关数据库进行检索，也可采用影印、缩印或扫描等复制手段保存和汇编学位论 文。 作者签名：丝蓬 导师签名 垫型年兰一月王日 大连理工大学硕士学位论文 引言 本论文研究如下形式的互补问题： 设f ) ：掣斗彤，f ( x ) = ( 五( x ) ，五( 工) ) 7 ，这里z ( x ) ：胄”_ 尺为二次连续可微 的。所谓的非线性互补问题( n c p ) 就是求解以下方程和不等式组 工o ，f ( x ) o ，x 7 f ( x ) = o ， 的一个解，或等价的求解 i o ，z ( 工) o 【z ( 功= o ，f _ 1 ，2 ，h 求解互补问题有许多有效的算法，如不动点法，同伦算法，投影法，光滑方程组法， 牛顿法，可微无约束优化方法和内点方法等。 本文通过基于指数函数空间变换的微分方程方法对互补问题进行研究。 大连理工大学硕士学位论文 1 绪论 文章概述了求解非线性互补问题的微分方程方法的研究历史及现状，并对本文所凭 借的主要理论工具微分方程的稳定性理论，给出了简要的介绍。 1 1 互补问题微分方程方法的研究进展 互补问题是一类重要的优化问题在实际应用中，它出现在工程物理、经济与交通 平衡等领域；同时，它也出现在约束优化的最优性条件中因此，对它的研究具有重 要意义 对互补问题的研究，一般分为理论与算法前者主要研究解的存在性、唯一性、稳 定性与灵敏度分析；后者则主要建立有效的求解方法及相应的算法分析我们在这里仅 介绍互补问题的求解方法 d e n t z i g 和c o t t l e 于1 9 6 3 年首先提出互补问题次年，c o t t l e 在他的博士论文中 第一次提出求解它的数学规划算法互补问题的出现，引起了当时人们的浓厚兴趣，许 多人纷纷参与这项研究到8 0 年代中后期，经过2 0 余年的努力，在算法研究方面取得 了丰硕成果：( i ) 对线性互补问题，有直接方法( 如l e r a k e 法，c o t t l e d e n t z i g 法) 和 迭代法( 如m a n g s a r i a n 法) ；( i i ) 对非线性互补问题，有不动点法，同伦法，投影法， n e w t o n 法等，其算法的特征是，在迭代中需要求解线性互补子问题，或者二次子规 划l e m k e 算法( 1 9 6 4 ) 是这一时期最著名的方法之一关于1 9 9 0 年以前的工作，可见 h a r k e r 和p a n g 的综述文献1 1 】也见优秀专著1 2 ，3 ”。 随着8 0 年代科技与经济的发展，互补问题变得越来越重要这就刺激了对其算法 的进一步研究出现了8 0 年代后期的研究高潮，至今未衰在这将近1 0 年的时间里， 人们提出许多有效算法，并且完善与丰富了算法的收敛性理论。下面介绍几种主要的算 法。 l 光滑方程法 这类方法就是把互补问题转化为一个与之等价的光滑方程组，然后用n e w t o n 类型 法求解m a n g a s a r i a n 于1 9 7 6 年首先提出此种方程组。 2 非光滑方程法 就是把互补问题转化为一个与之等价的非光滑方程组，然后用广义n e w t o n 类型法 求解。我们首先回忆非光滑分析中的几个概念。 3g l p 投影法 指数函数空间变换的互补问题的微分方程方法 就是基于g o l d s t e i n ，l e v i t i n p o l y a k 求解凸规划的梯度投影法思想，求解互补问题。 虽然这类方法最多只有线性收敛速度，但它运算量小，存储量小，保稀疏性因此近 几年又有新的发展，如南京大学的何炳生教授，建立了一类特殊类型的投影法一投影 收缩法【5 6 ”，揭示了已有的投影收缩法中的寻查方向，都是基于三个基本不等式的 不同组合。 4 内点法 这是把互朴问题转化为一个与之等价的非负约束方程组，然后用n e w t o n 类型法求 解。它的研究起源于k a r m a r k a r 的求解线性与凸二次规划的内点法，也是这种方法的 自然延伸。 5 磨光方程与非内点法 不难看出，非光滑方程法存在一个弱点，即方程日( z ) = o 中的j a c o b i 矩阵v 日( x ) 难 于计算。自然地，考虑用一个光滑函数日( x ，a ) 近似代替日( x ) ( 这里日( x ，口) 称为磨光函 数，称为磨光参数，日( x ，o ) = 日( z ) ) 转而求解日( x ，a ) = o ，这就是磨光方程法如果在 迭代过程中能调整到零，则称它为连续磨光方程；进一步，如果连续不断地压a 的值到 零，则称它为非内点法。后者具有路径跟踪法的主要特征，但它能取任何初始点及充分 选取步长。这恰能克服内点法的弱点。所以，自它自c h e n h a r k e r 旧于1 9 9 3 年提出来 后，吸引了众多学者的注意，并取得迅速发展。 6 微分方程方法 这是把互补问题转化为一个与之等价的可微无约束优化问题，然后用某种大范围或 n 鲫t o n 类型法求解由于无约束优化法较为成熟，因此，对这类方法的研究重心在 于如何转化上 m a n g a s a r i a n 和s o l o d o v 例又先于他人，给出一个可微的势函数 仲( - 口f ( 力+ + f 2 一肛8 2 + f ( 一口，( 砌+ i f 2 一| f h 功8 2 ，口 o ， ( 1 1 1 ) 称札，为隐l a g r a n g e 函数。中国科学院计算数学所青年学者彭积明给出了变分问题的可 微无约束优化再生。有趣的是，它恰是隐l a g r a n g e 函数在变分问题中的推广与此同 时，也带动了对其误差界的研究。误差界有两大用途：( i ) 算法迭代中的停止准则；( i i ) 分析算法的线性收敛速率。后用途是由l u o 和t s e n g 【i o j 发现的，具有开拓性。后来对 可微无约束优化再生的研究兴趣转向增加非负约束，因为实际计算表明，仅用无约束优 化求出的n c p ( f ) 的解并不理想。为此m o r e 给出一个可行的信赖域方 法；w a n g m o n t e i r o p a n g 提出一降势内点法。 大连理工大学硕士学位论文 1 2 优化理论的微分方程方法的研究进展 自求解最优化问题的微分方程方法问世以来，无论在理论研究还是算法研究上均取 得了一系列重要进展。该方法将最优化问题归结为求一个( 往往是自治的) 微分方程组 的平衡点的问题，从而将复杂问题( 特别是约束非线形规划问题) 的求解转化为较为成 熟的常微分方程组得数值求解，开辟了求解非线形最优化问题的一条新途径。另一方面， 求解最优化问题的微分方程系统往往是一神经网络模型，因此，最优化微分方程方法的 深入研究无疑会推动神经网络方法求解最优化问题的进展。 用微分方程的方法求解约束非线性最优化问题，最早由a r r o w 和胁f m f 篮叫提出， 他们考虑的是等式约束最优化问题( 既在n l p 中卅= o ) 。f i a c c o 和 和c o 瑚f c 硝”1 用微分 方程方法对约束规范。e v t u s h e n k o 和z l l a d a n ( 1 9 7 3 1 9 7 4 1 比较早得对等式约束问题进 行了研究。其后，n a s h j t a 【1 ”和办a d 锄f 1 5 1 6 1 7 川9 1 及，册f 2 0 1 对该方法进行了发展和完善。 特别是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 m p o i n t s ) 恰好是非线性规划问题的全局最优解、局部最优解或k u h n t u c k e r 点，将数值 算法的收敛性问题转化为微分方程平衡点的稳定性判别问题。 下面我们简要回顾一下该方法的研究情况。首先介绍非线性规划问题： m i n ，( 工) g ( 工) o j 1 2 ( x ) = o x r ” 其中函数厂：五”斗r 1 ，g ：舻寸r ”和 ：彤_ 掣都是二次连续可微的。这个问题定义为 ( n l p ) 。 为了叙述方便起见，记可y ( x ) 为函数，在x 处的梯度向量，v 2 ，0 ) 为函数，在x 处 的胁船e 阵。定义n l p 问题的函数为： 三( z ，“，v ) = ，( x ) 一“2 9 ( x ) + v 7 ( ， z 处的紧约束指标集为，( x ) = ( fg ，( z ) = o ，k 1 ，肌) 。 指数函数空间变换的互补问题的微分方程方法 对无约束优化问题( n l p 中，= o ，m = o ) ，b d 拈删捃【2 1 】与4 埘口哟2 2 1 用精确微分方程 方法对他进行求解，定义了下面的微分方程系统 譬= q ( x ) 一1 可( x ) ， 其中q ( x ) 是对称正定矩阵，在v 2 ，( x ) 正定的情况下，b o t s 耐s 证明了通过此微分方程系 统求得的解是优化问题的最优解；在可丁( x ) 的水平集是凸性的假设下，a m a y a z 证明了 收敛性定理。 关于等式约束问题( n l p 中脚= 0 ) ，也有许多学者利用微分方程方法对它进行了 求解。例如，b r o w n 和州 d z d m v e 一甄g 2 辅1 提出了含有罚函数的参数化相关的微分 方程系统， 睾= 一昙m ( v ) ， 出玉” 其中巾( x ，r ) = ，( x ) + ：。，砰( x ) 是外点罚函数，利用此系统仅能求得近似解并且r 不能 取得非常大，因而效果不是很好。 为了能够求得较精确的解，t 锄a b l e ( 1 9 7 4 ) ，h n a s 】1 i 切( 1 9 8 0 ) ，e v t u s h e n k o 和 z h a d a l l ( 1 9 7 4 ，1 9 8 5 ，1 9 9 4 ) 都利用l a g l l r 柚g e 函数，提出了不同的微分方程系统来求解极小 化问题。在v 啊( x ) ，f = 1 ，对任意的工彤均是列满秩的假设条件下，他们提出了所提 出的微分方程系统有定义。在此条件下，t 知a b e 等诸位学者分别给出了下述的各微分 方程系统。 t a n a b e 给出微分方程系统 譬= ( ，一q ( 艽) ) ( 一可o ) ) ， 见文献2 “，其中，q ( x ) ：= v 矗( x ) ( v ( x ) v h ( 工) 7 ) 一1 v ( x ) 。 y 砌a s h i 铽1 9 8 0 ) ，e v n 曲e n k o 和z h a d a i l ( 1 9 7 4 ，1 9 8 5 ，1 9 9 4 ) 定义了相似的系统 翌出7 威= 一( 耵( x ) + v 矗( 。) 7 “( z ) 眦1 ) d h ( z ) ，西= f 厅( 工) 、。 其中b ) r ”“是对称正定矩阵，f o 为常数，在系统( 1 _ 2 1 ) 中，若取f s l ，b ( x ) = 1 ， 则得到场懈砌卅的一个微分方程系统，研究表明系统( 1 2 1 ) 描述的轨迹在奇点x 附 近十分复杂，这是一个严重的缺陷。若取fsl ，曰( x ) = v ：( x ，耕( x ) ) ，则得到y a m a s 的牛顿系统，他克服了上述困难，使在z 附近的解变成： 工o ) 兰( x + x ( 0 ) 一x ) e 一， 大连理工大学硕士学位论文 并且该方法具有二阶收敛速度。由于收敛的区域被严格限制在稳定点的邻域内，于是 y 趴碰舡t a 利用迹连续的技术，扩大了收敛的区域。 若取b ( z ) ；，“，f 0 ，则得到e l l s l l e i l k o 和刀蝴妇，z 1 的微分方程系统，这一系统 被他们称为障碍投影法( b a i t i e rp r o j e c t i o nm e t h o d ) 。张立卫( 1 9 9 9 ) 2 6 1 对等式约束问题 ( n l p 中m = o ) 提出了下述微分方程系统 ( 歉，西2 一b ( x ) v ，l ( x ，“( x ) ) ， ，1 ，” d h ( x ) 卉= 妒( ( x ) ) ， l 1 2 。2 j 其中占( x ) r ，为正定矩阵，妒：r 1 _ r 7 满足条件 1 妒( ) 在r 7 的原点邻域u 上可微，雅可比矩阵v 。咖( ) 7 的所有特征值在u 上有负实部。 2 妒( ) 在u 上有唯一不动点，即庐( z ) = z 当且仅当：= o 成立。系统( 1 2 2 ) 概括了系 统( 1 2 1 ) ，是对系统( 1 2 1 ) 的推广。 e v t u s h e l l k o 和踟d 研【1 6 1 用微分方程方法对下列更一般的约束问题进行了研究 m i n 厂( x ) j x z ： x 引矗：吣拼 ( 1 删 其中p 为不等式约束，假设尸有非空的内部。 他们对问题利用空间变换技术，等价的转化为只有等式约束的问题，再通过逆变换， 得到如下微分方程系统 2 - g ( x ) v ，三( 训( x ) ) ， r ( z ) “( 功+ 1 鼢( 功g ( x ) 可厂 ) = f ( z ) ，( 1 2 4 ) x ( o ，孔) = 民p 逆变换的作用使得微分方程的右边被乘上一个矩阵g ( ，只要初始点位于p 内，以此 为初始点的轨迹就不会穿出p ，因此g ( x ) 起到了障碍作用。在此种空间变换的基础上， e 硼l s l l c n k 0 和z h a d a n 仅对户= 群的情况进行研究，通过分量空间变换一= 毒( y ) 和逆变 换，将( 1 2 4 ) 转化为： 豢= _ d ( x ) ) v ，三( 圳( 石) ) ， 其中臼( x ) = r ，口 0 ，d ( 日( z ) ) 为对角型矩阵，即使对这样简单的系统，它们的收敛性也 要在下述条件下得到证明：c 3 ：p ( 一) 当且仅当一= o ；百( 0 ) o 时成立。于是跏扣阳v 【2 7 1 提出了向量李雅普诺夫方法，在较弱的条件下，解决了收敛性问题。 指数函数空间变换的互补问题的微分方程方法 当处理混合约束问题( n l p 中z 0 ，m o ) 时，一个容易想到的方法就是通过引入 人工变量把不等式约束问题转化为等式约束问题。这一思想被历d “( 1 9 9 7 ) 及张立卫等 ( 2 0 0 0 1 陋1 利用，构造了求解混合约束优化问题的微分方程系统。 z 加甜【2 8 】通过引入松弛变量z ，将非线性规划问题转化为 m i n ，( y ) = ，( x ) s 工y s = y e r ”1 日c y ，= ( g 。x ；芝：，： = 。) ， 其中y = ( x ，z ) ，= 川璺= 0 ，f _ 1 ，所) 表示g ( x ) 的紧约束指标集，在梯度 v ( z ) ，w b ( 工) 与v & ( x ) ，fe ( x ) 线性无关的条件下，他提出了下述微分方程系统 麓孙p 竺拦玩h 剥，l 吃比毋l d ( 五) 九j i o j f 珊( x ) 出西 1r 一忍( z ) 、 l 审g ( x ) 出旃一d ( 鼻) 如出厂l g ( 功+ z 2 2 j 其中，d ( t ) = 凼曙( 毛，) 。 而张立卫( 2 0 0 0 ) 1 通过引入松弛变量j ，将非线性规划问题转化为 1 i l i n ，( z ) = ，0 ) “日( z ) = o ， 三五肿” 其中 酢，_ 搿加 抄卢w ， 与之相关的微分方程系统为 出，西= b ( 2 ) v ：上( z ，w ( z ) ) ， 船( z ) 出= o ( ( z ) ) ， 其中b ( ：) r ( ”) “”1 对称正定。m ：r ”卜r 州为满足下列条件的映射： 1 巾( ) 在u 上可微，u 是r ”7 空间的原点的一个邻域，并且中( ) 的雅可比矩阵 v 。中( ) 7 在u 上有负实部。 2 o 是中( ) 在u 上的唯一固定点，即中( z ) = z 成立当且仅当z = o 。 大连理工大学硕士学位论文 在文献【2 9 中仅需要梯度v 栩( x ) ，v ( x ) 与v g ，( x ) 是线性无关的即可，它不但具有不 需要初始点可行的优点，而且还能保持可行性，即如果当前点是可行的，则它的后续轨 迹( s u b s e q u e n t 蛔j e 咖r y ) 始终保持在可行域中。 另一方面，各种由微分方城系统描述的神经网络模型被提出求解非线性最优化问 题。自h o d 丘e l d 和t a i l l 【首次提出解线性规划的一个神经网络m o o ”以来，采用神经网 络求解最优化问题得到了相当深入的研究，已发展了多种不同形式的求解非线性最优化 问题的神经网络模型。 对无约束优化问题( n 】l p 中，o ，研o ) ，r o d r i g l l e z v a z q u e z ( 1 9 9 0 ) ，c i c h o c k i 和 u n h b e h a u e l l ( 1 9 9 3 ) ，提出了基于最速下降法的神经网络动态系统 譬：彤v ，( 功， 其中形是对称正定矩阵，他们证明了神经网络的平衡状态对应于问题的局部最优解。 o s o 哪她( 1 9 9 2 ) 【3 5 1 ，c i c h o c k i 和u i l l b c h a u 肌( 1 9 9 3 ) 对上述问题进行了进一 步的研究，基于n e w t o n 法提出了下列神经网络动态系统 譬= 研v ：，( x ) w ( z ) 虽然基于n e w t o n 法的神经网络系统具有较快的收敛性，但有时h e s s e 阵会出现奇异性 问题，因而o s o w 出( 1 9 9 2 ) ，c i c h o c l d 和u n h b e h a u ( 1 9 9 3 ) “1 对上述神经网络 进行了改革，提出了l e v e n b e r g m a r q l l a r d t 法的神经网络动态系统 譬：矿 v 2 ，( x ) + f ，】夥( x ) ， 其中，为单位矩阵，f 为一适当的正数。 对不等式约束问题( n l p 中z = o ) ，k e m e d y 和c h l l a ( 1 9 8 8 ) 1 利用梯度法和罚 函数法给出了下列神经网络动态系统 q 鲁一掣一喜掣，川 其中q 为正数，f ，= p ，( g ，( x ) ) ，并且有如下定义 f o ，v o ， 巧( ”j 5 1 上v v o ，由于f 近 似为o ，所以e ，又可以近似为乃= s 9 1 l ( 毋( x ) ) c 2 一c 2 。c i c h o c k i 和u n b e h a l l e n f l 9 9 3 ) 基于增广l a g r a n g e 函数 1mr1 “训囊) - 八功+ 捌专龇+ 眦) ) ) 2 卅i ， 给出了神经网络动态系统 。 鲁1 ( - 掣+ 酗m 删剖 ， 警= b 陋班钞s ， ，渊，棚， 其中一，砖和b 都是正的变量或常数，通常情况下，也与非常小，可以忽略，在增 广l a g u r a n g e 函数病态的情况下，c i c h i c k i 和u n b e h a u e l l ( 1 9 9 1 ) 矧在增广l a g m n g e 函 数中引入了正则化( r e 则a r i z a t i o n ) 项，以消除惩罚项造成的不稳定，给出了正则增广 l a g r a n g e 函数 大连理工大学硕士学位论文 三( x ，p ，七) = ，( x ) + 至i 雕毋( 跏一+ ；t ( 瞻( 瑚一) 2i 一等杰戽， j ll 山 j厶，= l 其中 吕o ) 一= m i n ( x ) ，一“t ) ，“s 0 ，a o 是正则化参数。c i c l l i c k i 和u n b e h a u e n ( 1 9 9 3 ) 对上述函数提出了神经网络系统对等式约束问题，和提出了规划神经网络 鲁一， _ 掣+ 如，嘲，掣 ，川，棚， 警= 只f s 咖) 一训，瑚，晰 对等式约束问题( n l p 中m = 0 ) ，z h a l l g 和c o n s t 明t i n i d e s ( 1 9 9 2 ) 提出了l a g 删1 9 e 规划神经网络 譬= 坷，上( x ，a ) ， ( 1 2 5 ) 譬= 一v 三( x ，a ) ， ( 1 2 6 ) 其中工( 工，九) = 厂( 茸) + a 7 ( x ) ，a 且4 为i a g r a n g e 乘子向量。方程( 1 2 5 ) 成为变量神经 元，它提供问题最优解，方程( 1 2 6 ) 称为乘子神经元，它使得网络收敛于可行域内。 但是，这一方法局部最优解的存在依赖于优化问题的结构凸性，即要求v ：三( z ，a ) 在动 态域内正定。针对这一缺陷，他们提出了基于增广l a g r 锄g e 乘子法的神经网络系统 鲁一善一言c - + 州砌誊， z h a l l g 等( 1 9 9 2 ) 4 0 1 又提出了二阶神经网络 拶v 跏绷十圳，iv ( 工) 7 o j l 以出jl 矗( x ) j 值得强调的是这一网络对h e s s e 阵v ：三( x ，a ) 在整个空间内无正定性要求。 对混合约束问题，m 够s m i c h a e l ( 1 9 9 2 ) 4 1 1 提出了一种两阶段优化神经网络，当 0 f 时，网络的动态系统为 等= 呵 ) 吖( v 矧功勖( 加珊( 踟( 瑚， 当f 时，网络的动态系统为 塑塑里塑窒塑壅垫笪里! ! 旦璧堕丝坌塑互垫 西c 国= 一1 咿( 砷一v g ，( 昭了+ _ “) 一v 向( 曲( 功+ a ) ， d 丸d f = 8 b 协， dl l d t = s 心g j ) ， 其中j ： f l g ， o 存在，使得下述条件成立 1 满足条件 p o l t 6 ， 的系统( 2 2 1 ) 的每一个解都有定义： 2 对这些解有不等式： 2 对这些解有不等式： ( 2 2 1 ) 表示为z = x o o ，0 。 指数函数空间变换的互补问题的微分方程方法 | | x ( x 。，f ) 一x ( z ，) 9 o ，有 三7 ，7 ( z + ) v ：( z ，”) j ( z ) 三 o 那么，z 是问题( 3 1 3 ) 的严格局部极小点。 应用点k 膪r 方法求解系统( 3 3 1 ) ，我们得到 缸“= 气一，( 气) 疗【g ：( 缸) j ( z 。) ，7 ( z ) 丘( z 女) + 町g ；( 缸) j ( 气) 】+ g ( z 。) )( 3 3 2 ) 下面证明微分方程系统( 3 3 1 ) 的渐近稳定性及迭代序列( 8 ) 的局部收敛性。 定理( 3 3 2 ) ：设z + 是问题( 3 1 3 ) 的一个稳定点，在z + 处二阶充分条件成立，那么当f o 时，微分方程系统( 3 3 1 ) 在z 点是渐近稳定的，且王 ，v o o 。 若露。= 0 ，那么专五( z ) = 扣r 5 ：岛1 ( z + ) 以z = 0 。) 。 将( 3 3 5 ) 式左乘等得 ；盥世颦终监 ol 汹1 一 f 2 ”6 因此a 1 = m i n 0 。 l s | s j 我们有a = 血n 兄，a ” 0 ，q 的每个特征值都是大于零的，所以由上卿“n d v 一阶 线性准则得，z 是系统( 3 3 1 ) 的渐近稳定平衡点，且l i m s u p 监堕三：! 型s 一旯。 设矗+ 2 寺，其中a + 2 懋 ，当步长o ( 峻 0 ，f o ，由爿删扣准则确定，选取初始点毛r “，令七= o ； 2 计算 气+ ，= & 一境，( ) 巧 ( 气) j ( & ) 】l ，7 ( ) 正( 2 ) + f 受( ) ，( 气) + g ( z 。) ) 3 如果0 t i i ：+ 怯( 毛) 1 1 ：s ，停止计算，否则令= i + 1 ，转步2 。 大连理工大学硕士学位论文 4 数值实验 4 1 求解非线- 胜互补问题微分方程方法的数值结果 我们在胁打口6 下，应用上面算法求解下面互补问题 例1 考虑。求x 满足 工0 ，( x ) 0 【薯z ( x ) = o ，f = 1 ，2 ，3 ，4 iz ( 并) = 3 彳+ 2 葺x 2 + 2 + 而+ 3 - 一6 其中j 五( x ) 2 2 彳+ 而+ x ；+ 1 0 为+ 2 _ 一2 l 五( x ) = 3 + 而而+ 2 霹+ 2 而+ 9 一9 l 工( x ) = 砰+ 3 + 2 毛+ 3 一3 最优解为x = ( 1 ，o ，3 ，o ) 7 和工= ( ，o ，o ，必) 7 ，由上面算法，当s = 1 o 1 0 _ 6 ，f = o 5 ， 取气= ( 1 ，0 ，3 0 0 ，o o l ，l ，1 ，1 ，1 ) 7 时，求得的近似解为( 1 o o ，o ，2 9 9 ，- o o l ，o ，3 0 9 ，o ，3 9 8 ) 7 ；当 s = 1 o l o 。，f = o 5 ，取= ( 1 ，1 ，1 ，1 ，5 ，1 4 ，8 ，6 ) 7 时，求得的近似解为 ( 1 2 2 4 8 ，o ，o ，o 5 ，o ，o 0 0 4 ，3 2 2 5 0 ，o o 0 0 4 ，0 0 0 0 矿； 例2 考虑三c p ( m ，g ) 其中 m = 3o一1 13一l 014 1一l一1 g = ( _ 2 ，3 ，_ 4 ，5 ) 7 。 三c p 的最优解为x = ( 1 ，0 ，1 ，o ) 7 ，由上面算法，当s = 1 0 1 0 _ 6 ，f = o 5 ，分别取 毛= ( 0 ，0 ，0 ，o ，o ，0 ，0 ，o )