（计算数学专业论文）两类非线性问题的计算方法研究.pdf

两类非线性问题的计算方法研究 白 颉 摘要非线性互补问题( c p ) 与二阶锥规划( s o c p ) 问题是两类重要的优 化问题它们广泛出现于科学与工程技术领域，因此研究它们的求解方法具有一 定的理论价值与现实意义 互补问题与非线性规划、极大极小、对策论、不动点理论、变分不等式等数学 分支紧密联系，并广泛应用于力学、经济、交通等领域，因此受到广泛关注，并在 其理论与算法方面取得了丰硕成果其中，通过构造光滑函数，用光滑牛顿法求 解n c p 是近年来的研究热点之一本文第二章考虑了一类p o 一映射n c p ( f ) 首先，引入一个新的光滑函数，将e p ( f ) 等价转化为一个光滑方程组，并建 立了求解它的光滑牛顿法其次，证明了由该算法产生的无穷序列的任一聚点均 为原问题的解，并且当c p ( f ) 的解集非空有界时，迭代序列有界然后，当 n c p ( f ) 有一个局部惟一解且满足一个非奇异条件时，证明了该算法具有局部超 线性收敛性和二次收敛性最后，用五个例子的数值实验说明了该算法可行且有 效与已有方法相比，本文提出的方法不需要假设搜索方向有界，不需要严格互 补条件，而且通过特殊的设计牛顿方程及线性搜索步，可以控制光滑参数以合适 的速度收敛 s d c _ p 问题是一类重要的凸优化问题它不但广泛应用于工程技术领域， 而且许多其它的优化问题可以转化为它，因此其求解方法一直是人们关注的焦点 问题目前，有许多方法可以求解s o c p 问题，但它们基本上属于传统的迭代 法由于计算时间依赖问题的规模、结构以及所采用的算法，因而很难满足实时 性要求与传统数值方法相比，由于内在的并行分布处理信息的特点及电路实现 的潜能，神经网络具有许多计算上的优势和实时性的应用自提出h o p f i e l d 神经 网络，并将其成功应用于优化问题后，用神经网络求解优化问题得到了相当深入 的研究，并取得了许多重要的成果本文第三章考虑了一类s d c p 问题利用两 个光滑函数分别将二阶锥约束转化为光滑的凸约束，从而将s o c p 问题近似转 化为两类凸优化问题，并根据射影理论建立了求解它们的两个新神经网络然后 运用l y a p u n o v 稳定性理论和l a s a l l e 不变原理证明了提出的神经网络在适当的 条件下是l y a p u n o v 稳定的，且能以任意精度收敛到原问题的解最后数值实验 表明这些网络不仅可行，而且有效 关键词：光滑函数；非线性性互补问题；牛顿法；神经网络；收敛 性；稳定性；二阶锥规划 s t u d yo fc o m p u t i o n t i a lm e t h o d sf o rt w o k i n d so fn o n l i n e a rp r o b l e m s b a ij i e a b s t r a c t ：t h en 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 ( g p ) a n dt h es e c o n d o r d e rc o n ep r o g r a m ( s o g p ) p r o b l e ma r et w ok i n d so ft h ei m p o r t a n to p t i m i z a t i o n p r o b l e m s t h e ya r i s ew i d e l yi ns c i e n c ea n de n g i n e e r i n gf i e l d s ，t h u sh o wt os o l v e t h e mi ss i g n i f i c a n ti nb o t ht h e o r ya n da p p l i c a t i o n t h ec o m p l e m e n t a r i t yp r o b l e m sa r ec l o s e l yr e l a t e dt om a n yf i e l d si n c l u d i n gt h e n o n l i n e a rp r o g r a m m i n g ，t h em i n m a xp r o b l e m ，g a m et h e o r y ，f i x e dp o i n tt h e o r y ， v a r i a t i o n a li n e q u l i t ya n ds oo n ，a n dh a v ew i d ea p p l i c a t i o n si nm e c h a n i c s ，e c o n o m i c s c i e n c e ，t r a n s p r o t a t i o ns c i e n c ef i e l d s t h u st h e yh a v ed r a w ng r e a ta t t e n t i o n ，a n d g r e a ta c h i e v e m e n ti nb o t ht h e o r ya n da l g o r i t h mh a sb e e nm a d e r e c e n t l y , t h e r eh a s b e e na ni n c r e a s i n gi n t e r e s ti ns o l v i n gn cpb yu s i n gs o - c a l l e ds m o o t h i n gn e w t o n m e t h o d i nc h a p t e r2 ，w ec o n s i d e r g p ( f ) w i t hp o m a p p i n g f i r s t ，w ec o n - v e r te q u i v a l e n t l y c p ( f ) i n t oas m o o t h i n gs y s t e mo fe q u a t i o n sb yd e f i n i n gan e w s m o o t h i n gf u n c t i o n ，a n dp r e s e n tas m o o t h i n gn e w t o nm e t h o df o ri t s e c o n d ，w e p r o v et h a tt h es e q u e n c ep r o d u c e db yi t e r a t i o ni sb o u n d e da n di t se v e r ya c c u m u l a - t i o np o i n ti sas o l u t i o no f c p ( f ) w h e nt h es o l u t i o ns e to f g 尸( f ) i sn o n e m p t y a n db o u n d e d t h i r d ，w h e nn c p ( f ) h a sa u n i q u es o l u t i o n ，t h ec o n v e r g e n c er a t ei s p r o v e dt ob el o c a l l ys u p e r l i n e a ra n dq u a d r a t i cu n d e rt h em i l dc o n d i t i o n s c o m p a r e d w i t ht h ee x i s t i n gm e t h o d s ，t h ep r o p o s e dm e t h o dh a sn or e q u i r m e n t so ft h eb o u n d - e d n e s so fs e a r c hs t e pa n dt h es t r i c tc o m p l e m e n t a r i t y , a n di t sc o n v e r g e n c er a t ec a n b ec o n t r o l l e db yd e s i g n i n gn e w t o ne q u a t i o na n dl i n es e a r c h f i n a l l y , i l l u s t r u c t i v e e x a m p l e sd e m o n s t r a t et h ef e a s i b i l i t ya n de f f i c i e n c yo ft h ep r o p o s e dm e t h o d s o cpp r o b l e mi sa l s oo n eo ft h ei m p o r t a n t l yc o n v e xo p t i m i z a t i o np r o b l e m s n o to n l yd o e si ta r i s ew i d e l yi ne n g i n e e r i n gf i e l d s ，b u ta l s om a n yo p t i m i z a t i o np r o b - l e m sc a nb ec o n v e r t e dt oi t ，t h u sh o wt os o l v ei t i saf o c u s a sw ek n o w ，m a n y a l g o f i t h m sf o rs o c pp r o b l e ma r ed e v e l o p e d b u tt h e ya l m o s ta l la r et h et r a d i t i o n a l i t e r a t i v em e t h o d s ，a n dm i i g h tn o to b t a i nt h es o l u t i o ni nr e a l - t i m ed u et os t r i n g e n t r e q u i r m e n to i lc o m p u t a t i o n a lt i m e d i f f e r i n gf r o mt h et r a d i t i o n a la l g o r i t h m s ，t h e n e u r a ln e t w o r kh a sm a n ya d v a n t a g e so nc o m p u t a t i o na n dr e a l t i m ea p p l i c a t i o n sd u e i i i t oi t si n h e r e n tm a s s i v ep a r a l l e l i s ma n de l e c t r i cc i r c u i ti m p l e m e n t a t i o n s i n c eh o p - f i e l dp r o p o s e da r t i f i c i a ln e u r a ln e t w o r ka n di ti sa p p l i e ds u c c e s s f u l l yt oo p t i m i z a t i o n p r o b l e m s ，t h et h e o r y , m e t h o d o l o g ya n da p p l i c a t i o no fn e u r a ln e t w o r kh a v e b e e n w i d e l yi n v e s t i g a t e d ，a n dm a n ys i g n i f i c a n tr e s u l t sh a v eb e e na c h i e v e d i nc h a p t e r3 ， w ec o n s i d e rs o cpp r o b l e m b yu s i n gt w os m o o t hf u n c t i o n s t h es e c o n d o r d e rc o n e c o n s t r a i n t sa r ec o n v e r t e di n t os m o o t h i n gc o n v e xo n e 8 t h u s s o c pp r o b l e mc a n b ec o n v e r t e da p p r o x i m a t e l yi n t ot w oc o n v e xo p t i m i z a t i o np r o b l e m s ，a n dt w on e u r a l n e t w o r k sf o rt h er e s u l t i n gp r o b l e m sa r ep r e s e n t e db yu s i n gp r o j e c t i o nt h e o r y t h e p r o p o s e dn e u r a ln e t w o r k sa r es h o w nt ob es t a b l ei nt h es e n s eo fl y a p u n o vu n d e r s o m em i l dc o n d i t i o n sa n dc o n v e r g et oa no p t i o n a ls o l u t i o no ft h eo r i g i n a lp r o b l e m w i t ha n ya c c u r a c y f i n a l l y , i l l u s t r u c t i v ee x a m p l e sd e m o n s t r a t et h ef e a s i b i l i t ya n d e f f i c i e n c yo ft h et w on e u r a ln e t w o r k s k e yw o r d s ：s m o o t h i n gf u n c t i o n ；n 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 ； n e w t o nm e t h o d ；n e u r a ln e t w o r k ；c o n v e r g e n c e ；s t a b i l i t y ； s e c o n d - o r d e rc o n e p r o g r a m i v 学位论文独创性声明 本人声明所呈交的学位论文是我在导师的指导下进行的研究工作及取得的研 究成果。尽我所知，除文中已经注明引用的内容外，论文中不包含其他个人已经 发表或撰写过的研究成果，也不包含为获得陕西师范大学或其它教育机构的学位 或证书而使用过的材料。对本文的研究做出重要贡献的个人和集体，均已在文中 作了明确说明并表示谢意。 作者签名：暨兰鱼日期：b 0 7 、箩，仂 学位论文使用授权声明 本人同意研究生在校攻读学位期间论文工作的知识产权单位属陕西师范大 学。本人保证毕业离校后，发表本论文或使用本论文成果时署名单位仍为陕西师 范大学。学校有权保留学位论文并向国家主管部门或其它指定机构送交论文的电 子版和纸质版；有权将学位论文用于非赢利目的的少量复制并允许论文进入学校 图书馆、院系资料室被查阅；有权将学位论文的内容编入有关数据库进行检索； 有权将学位论文的标题和摘要汇编出版。 作者签名：鱼! 1日期：塑! ：三：兰 第一章绪论 1 1互补问题 优化问题广泛地出现在经济计划、工程设计、生产管理、交通运输、国防等 重要领域，它与信号处理，系统识别、滤波设计、函数逼近、回归分析和自动控 制等科学技术领域密切相关研究优化问题的特性和寻求其解的计算方法是许多 学者和工程技术人员普遍关心的问题，也是最优化这门学科主要解决的问题【1 一 互补问题足运筹学与计算数学的一个交叉研究领域它与非线性规划、极大 极小、对策论、不动点理论、变分不等式等分支紧密联系，在力学、工程、经济、 交通等许多实际部门有广泛应用这使得互补问题成为数学规划中十分热门的研 究课题 互补问题作为一类新的数学模型，首先由著名运筹学家、数学规划的创始人 g b d a n t z i g 和他的学生r w c o t t l e 于1 9 6 3 年提出次年，c 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 n s ”中第一次提出 求解它的非线性规划算法这一数学问题在初期曾被称为。拼合问题”、“基本问 题”或“互补转轴问题”等文f 3 】曾指出：线性规划与二次规划是线性互补问题 的特例文【4 】指出：双矩阵对策问题也是线性互补问题的特例线性互补问题 还包括了最优停止问题和市场均衡问题等非线性互补问题、混合互补问题和隐 互补问题包括了更多的数学问题，如一般的非线性规划的k k t 条件是混合互补 问题的特例互补问题是从线性规划和非线性规划推广而形成的，因此它很快引 起当时运筹学界和应用数学界的广泛关注和浓厚兴趣关于它的研究一般分为理 论与算法两方面，前者主要研究解的存在性、唯一性、解的拓扑性质、稳定性与 灵敏度分析，以及不同类型互补问题与其它数学问题的联系等；后者主要建立有 效的求解方法和相应算法的理论分析至2 0 世纪8 0 年代中后期，经过2 0 余年 的努力，在理论与算法方面已取得了比较丰硕的成果由于互补问题与最优化、 变分不等式、平衡问题、对策论、不动点理论等数学分支紧密联系，以及它在科 技与经济方面的广泛应用，因此出现了2 0 世纪9 0 年代以来的研究高潮在这十 余年的时间里，人们不仅改进和丰富了互补问题的理论研究，而且还提出了多种 有效算法 1 1 1互补问题的数学模型 互补问题是指它包含的两组决策变量之间满足一种“互补关系”根据问题中 变量所满足的不同条件及互补关系的不同形式，它可分为下列几种数学形式f 5 】 1 1 1 线性互补问题( t h el 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 ) 令m 酽“，q 形，线性互补问题( l c p ( m ，g ) ) 为；找z 舻，使 z 0 ，m x + q 0 ，x t ( m x + q ) = 0 l c p 的基本来源是线性规划与二次规划任一二次规划的k k t 条件、凸二次规 划及线性规划都等价于l c p 1 1 2 竖直线性互补问题( t h ev e r t i c a ll 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 ) 令m ：= ( ( 舰) r ，( ) t ，( ) t ) r ，q ：= ( ( q 1 ) t ，( 匏) t ，) t ) r ，其中尬 n r m 一“，吼j p 令m ：= m i ，竖直线性互补问题( v l c p ( m ，q ) ) 为：找z 舻， i = l 使 - m 0 z 0 ，尬z + 哦20 ，x i ( 必万+ 吼b = 0 j = l 显然若m i = 1 ，i = 1 ，2 ，n ，则v l c p ( m ，q ) 化为l c p v l c p ( m ，q ) 是c o t t l e 和d a n t z i g 于1 9 7 0 年提出的，它应用于非线性网络、对策论和经济学等方面一 般的y 三g j p 已不是三g j p 1 1 3 广义竖直线性互补问题( t h ee x t e n d e dv e r t i c a ll 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 ) 广义竖直线性互补问题是v l c p ( m ，q ) 的推广令m ：= m o ，尬，尥) ， q ：= q 0 ，q l ，q k ，其中舻“，吼舻，i = 0 ，1 ，尼，广义竖直线性互补问 题( e v l c p ( m ，口) ) 为；找z 酽，使 ， i m i x + a 0 ，i = 0 ，1 ，k ， i 兀( m i z + 吼) = 0 ，歹= 1 ，n 1 1 4 水平线性互补问题( t h eh o r i z o n t a ll 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 ) 令矩阵m o ，m 1 尼“，q 酽，水平线性互补问题( h l c p ( m o ，m 1 ，g ) ) 为， 找z ，y 舻，使 z 0 ，y 0 ，m o y = m l z + q ，x t y = 0 当 如是单位矩阵时，h l c p ( m o ，m 1 ，q ) 化为l c p 1 1 5 广义水平线性互补问题( t h ee x t e n d e dh o r i z o n t a ll i n e a rc o m p l e m e n t a r i t y p r o b l e m ) 2 令m ：= ，m ，慨) ，q ：= q 0 ，9 1 ，一，q k + 1 ，其中尬舻“，吼 i t ，i = 0 ，1 ，k ，且当k 2 时，岱 0 ，i = 1 ，k 一1 广义水平线性互补 问题( e v l c p ( m ，g ) ) 为：找x o ，茁1 ，舻，使 f 墨20 ，i = 0 ，1 ，k m o x o = q o + m j 巧，z 和1 = 0 l j = l 【q j 一巧0 ，( q j 一巧) t 巧+ 1 ，j 1 ，k 一1 ，七22 当k = 1 时，e h l c p ( m ，q ) 化为l c p e h l c p ( m ，q ) 由r s z n a j d e r 和m s g o w d a 提出，它可应用于力学、统计学和库存问题 1 1 6 广义线性互补问题( t h ee x t e n d e dl 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 ) 令尬，m 2 r ”，pcr ”为一多面体，广义水平线性互补问题( e l c p ( m 1 m 2 ，尸) ) 为：找z ，y 形，使 z 20 ，y 0 ，m l z m 2 y p x t y = 0 当m = n ，且p = g ) ，即多面体退化为一点q 时，e l c p ( m a ，m 2 ，p ) 转变 h l c p ( m o ，q ) 1 1 7 非线性互补问题( t h en 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 ) 令映射f ：舻- r f l ，相应的非线性互补问题( n c p ( f ) ) 为；找z 形，使 z 0 ，f ( x ) 0 ，x r f ( x ) = 0 ，( 1 1 1 ) 当映射f ( x ) = m x + 口时，n c p ( f ) 化为l c p ( m ，g ) 1 1 8 广义非线性互补问题( t h ee x t e n d e 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 ) 令g ，h ：形一舻是两个映射，广义非线性互补问题( c p ( g ，h ) ) 为；找 z 毋，使 g ( x ) 0 ，日( z ) 0 ，g ( z ) 7 f ( z ) = 0 1 1 9 混合非线性互补问题( t h em i x e 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 ) 令g ：j p t r n 。_ + r m 和h ：舻- r “。- - + 舻：是两个映射，混合非线性互 补问题( m n c p ( g ，日) ) 为：找u 舻1 ，t ，t 2 ，使 ig ( “， ) = 0 ， i ”0 ，日( u ，u ) 0 ，1 3 t 日( u ， ) = 0 1 1 1 0 隐互补问题( t h ei 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 ) 3 令映射f ：r 2 n + ”- r l ，隐互补问题( i c p ( f ) ) 为：找z ，y j p ，。舻，使 f ( x ，y ，z ) = 0 ， z 0 ， y 0 ，x t y = 0 隐互补问题的一个重要应用是在力学和物理的自由边界问题方面 1 1 1 1 竖直互补问题( t h ev e r t i c a lc o m p l e m e n t a r i t yp r o b l e m ) 竖直互补问题是v l c p 的推广令映射p ：j p 叶，j = 1 ，k ，竖直互 补问题( y c p ( f 1 ，胪) ) 为t 找z j p ，使 if j ( z ) 0 ，j = 1 ，k ， i 兀( f t ( z ) ) j = 0 ，i = 1 ，m lj = l 除了上述互补问题的模型外，还有其它互补问题模型，其相互关系见【5 】 1 1 2互补问题的发展及研究现状 随着科技经济的快速发展，以及互补问题在理论与实践中的广泛应用，求 解互补问题变得越来越重要，这就刺激了对其算法的进一步研究至今，已提出 了许多有效求解方法( 如光滑方程法、非光滑方程法、可微的无约束优化法、摄影 法、内点法、磨光方程与非内点法) ，并且不断完善和丰富了算法的收敛性理论 1 1 1 2 光滑方程法 光滑方程法的基本思想是把互补问题转化为一个与之等价的光滑方程组，然 后用n e w t o n 类型法求解文【6 】首次引入n c p 函数t 妒，b ) = o ( 1 a 一6 1 ) 一o ( a ) 一p ( 6 ) ，( 1 1 2 ) 其中e ( t ) ：r 斗r 是一个严格递增函数，且o ( o ) = 0 ，将互补问题化为光滑方程 组，并用牛顿法求解在所给条件下，算法在解附近具有超线性收敛性为了保 证大范围的收敛性，文f 7 】建立了一个同伦法文【8 】则提出一个带阻尼因子的 g a u s s - n e w t o n 法文【9 】用非单调线性搜索技术改进文 8 】中的迭代格式，得到 好的数值结果文【1 0 】证明了当f ( x ) 连续可微时，文【8 】中的算法是大范围收敛 的，在文【6 j 的条件下，其点列局部超线性收敛基于n c p 函数( 1 1 2 ) ，文1 1 1 】 考虑了光滑方程组 h ( x ，y ) = ( y f ( z ) ，妒( z 1 ，y 1 ) ，妒( z 。，) ) t = 0 ， 并给出了v h ( x ，y ) 在n c p ( f ) 的非解点处非奇异的几个充分条件显然算法的 大范围收敛性与水平集 工( z o ，y o ) = ( z ，y ) r 2 nil i 王t ( z ，y ) | i l i h ( x o ，y o ) 0 ) 4 的有界性密切相关对此，文【1 1 】也做了研究 虽然这类方法有一定的优越性，但缺点是，即使一个l c p ，转化后的方程往 往是非线性的，且非线性程度较高，这导致了理论与计算的复杂化 1 1 1 3 非光滑方程法 非光滑方程法就是把互补问题转化为一个与之等价的非光滑方程组，然后用 广义n e w t o n 类型法求解众所周知，光滑方程的n e w t o n 法在解点附近的超线性 收敛性是建立在该点的j a c o b i a n 矩阵非奇异基础之上r o b i n s o n 1 2 】把这一结果 推广到变分不等式与互补问题中，即引进正则解概念后来又提出r - 正则解、 b 正则解、c d 一正则解等概念，它们都服务于广义n e w t o n 法的超线性收敛性 分析文 1 3 通过引入n c p 函数妒( n ，b ) = m i n a ，6 ) ，建立了一个带有非精确线 性搜索的广义n e w t o n 法，并在某种正则条件下，证明了算法的大范围收敛性及 局部超线性收敛性在1 9 9 2 年，f i s c h e r 引入一种结构简单而又奇特的i v g p 函 数( 又称f i s c h e r - b u r m e i s t e r 函数) 妒( 口，b ) = 、石丁；1 i a b ， 建立的n e w t o n 法可取任何初始点，并表现出良好的理论与数值结果1 1 4 】这引起 众多学者的极大兴趣，并围绕这一n c p 函数做了大量工作，但它们不能处理单 调n c p 其原因在于不能保证水平集有界后来c h e n - c h e n k a n z o w 1 5 】做了进 一步的研究，并得到一系列漂亮的理论与数值结果 1 1 1 4 可微的无约束优化法 这一方法就是把互补问题转化为一个与之等价的可微无约束优化问题，然后 用n e w t o n 类型法求解由于无约束优化法较为成熟，因此对这类方法的研究重 心在于如何转化上文【1 6 】引进一个光滑函数，使得以该函数为目标函数的无约 束最优化问题的全局最优解为n c p ( f ) 的解文【1 7 】证明了当f 在尼中强单 调时，文【1 6 中的无约束优化问题的任一稳定点均为e 尸( f ) 的解文【1 8 】提出 了几种将c p ( f ) 转化为无约束优化问题的新方法在设法构造n c p 函数的 同时，也带动了其误差界的研究，误差界是一个特殊的n c p 函数近来，对可 微无约束最优化再生的研究兴趣转向增加非负约束因为实际计算表明，仅用无 约束优化问题求出的解并不理想为此文【1 9 】给出了一个可行的信赖域方法 1 1 1 5g l p 投影法 投影法就是基于g o l d s t e i n - l e v i t i n p o l y a k 求解凸规划的梯度投影法思想求解 互补问题基本迭代格式为 z “：= k a f ( x ) l + ， 5 其中a 0 为步长然而它的收敛性要求f 强单调为此，k o r p e l e v i c h 提出外 梯度法，它的收敛性仅要求f ( x ) 单调且解集非空文 2 0 】应用a r m i j o 搜索技术 得到当f ( z ) 伪单调且解集非空时，迭代点列收敛到解集虽然这类方法最多只 有线性收敛速度，但它运算量小、存储量小且保持稀疏性，因此近年来又有新的 发展，如文 2 1 】建立了一类特殊的投影法一一投影收缩法文【2 2 】推广了文 2 1 】 的投影收缩法，并在相当弱的条件下，证明了其算法有大范围的线性收敛性 1 1 1 6 内点法 内点法是把互补问题转化为一个与之等价的非负约束方程组，然后用n e w t o n 类型法求解互补问题它的研究起源于k a r m a r k a r 求解线性规划与凸二次规划的 内点法其研究高潮在1 9 9 0 年前后。至今已取得了丰硕成果文【2 3 】证明了求 解l c p 内点法的迭代点列的收敛性文【2 4 】提出了求解n c p 的长步内点法， 它仅用一次n e w t o n 步可得到局部二次收敛性文f 2 5 】借用非内点法的思想改进 中心路径邻域，并引进积极约束策略，使算法的局部超线性收敛性不需要严格互 补条件 1 1 1 7 磨光方程与非内点法 在非光滑方程法中，互补问题被转化为非光滑方程组h ( x ) = 0 基于j a - c o b i a n 矩阵v h ( x ) 难于计算，用一个光滑函数h ( x ，0 1 ) 近似代替日( z ) ( 这里 h ( x ，o ) 称为磨光函数，a 称为磨光参数，h ( x ，0 ) = 日( z ) ) ，转而求解h ( x ，o ) = 0 ， 这就是磨光方程法若在迭代过程中能调整a 到零，则称它为连续磨光方程；若 连续不断地压缩d 的值到零，则称它为非内点法后者具有路径跟踪法的主要特 征，但它能取任何初始点及充分选取步长，这恰能克服内点法的弱点所以自文 【2 6 于1 9 9 3 年提出以来，吸引了众多学者的注意，并取得迅速发展文【2 7 】用磨 光法研究带有平衡约束的优化问题数值结果表明磨光算法优于l e m k e 法和内 点法基于磨光法的好的局部收敛性【2 8 及文【2 9 】的大范围线性收敛性的非内点 法，文【3 0 】提出了求解n c p 非内点法，它具有文【2 8 】和【2 9 】中方法的优点文 【3 1 】提出了一个求解单调n c p 的带有积极约束策略的非内点法，它能在较大范 围内选取初始点，并在无严格互补的条件下，具有局部二次收敛性文【3 2 】提出 了一个求解单调l c p 的预估一校正非内点法，其初始点很容易被选取同时， 连续磨光法也有很大进展，这种算法的迭代形式简单、收敛性强( 局部二次收敛 性不要求严格互补条件) 且数值效果好 1 2二阶锥规划问题 6 二阶锥规划( s o c p ) 问题是一类重要的凸优化问题它包括线性规划( l p ) 、 凸二次规划( q p ) 、凸二次约束二次规划( q c q p ) 等优化问题，同时又是一类 特殊的半定规戈d ( s d 尸) ，因此s o c p 问题是介于l p q p 和s d p 之间的一类 重要优化问题和l p 、q p 问题一样，s o c p 问题可在多项式时间内用内点法求 解，且内点法比将s o c p 问题作为s d p 问题求解更有效另外，许多其它优化 问题，如鲁棒线性规划问题、范数和及范数最大化问题、矩阵分式优化问题、含 有凸双曲约束的最优化问题、回归问题等也可化为s o c p ，而且它在滤波设计、 天线设计、衍架设计，机器人抓取力最优化设计等工程技术领域有广泛的应用 在许多工程和科技领域，特别足高科技领域中，往往要求实时求解大规模与 超大规模优化问题基于数字计算机的传统方法，由于计算时间依赖于问题的规 模与结构，因而很难满足实时性要求由于神经网络足一种自组织、自适应、自 学习的非线性网络，它具有大规模并行处理、分布式存贮和高度的纠错能力，其 算法具有极快的收敛速度和很好的稳定性因此神经网络被认为是求解大规模与 超大规模的线性与非线性优化问题的一个非常有效的途径 1 9 8 4 年j j h o p f i e l d 提出著名的人工神经网络模型| 1 】 并于1 9 8 5 年应用于 求解优化问题【2 】他的开创性的研究不但有力地推动了神经网络的研究，而且开 拓了神经网络优化计算的新途径，因此引起了许多学者的关注 目前，优化神经网络主要围绕能否求出原问题的精确解、是否全局收敛和结构 简单便于电路实现三大问题研究因此从硬件实现来讲，一个较好的神经网络， 其结构应相当简单；从计算性能来讲，一个较好神经网络应该是渐近( 或全局) 稳 定的，不含变量参数而且其平衡点是精确或近似最优解；从数学观点来说，这些 特性与设计网络模型所采用的优化技术密切相关 通常，建立神经网络的方法有两种： 第一种是先构造适当的能量函数，使能量函数的最小值点恰为所求问题的 勰，然后让网络为能量函数的负导数( 梯度) 第二种是先构造适当的网络，然后选择适当的能量函数，使能量函数的最优 点恰为网络的平衡点 1 - 3 预备知识 定义1 3 1 令f ：艘一舻为一映射，相应的互补问题( c p ( f ) ) 为：找 z 彤，使 z o ，f ( x ) 0 ，( 1 3 1 ) t t f ( x ) = 0 ( 1 3 2 ) 7 称满足不等式( 1 3 1 ) 的点为c p ( f ) 的可行点，满足不等式x 0 ，f ( z ) 0 的点 为c p ( f ) 的严格可行点，满足式( 1 3 1 ) 与( 1 3 2 ) 的点为c p ( f ) 的解 定义1 3 2 设f ：形_ 舻为一映射若对v x ，y 舻，有 0 一可) t ( f ) 一f ( ! ，) ) 0 ， 则称映射f 是研中的单调映射若v x ，y 形，y ，有 扛一f ) t ( f ( z ) 一f ( ! ，) ) 0 ， 则称映射f 是舻中的严格单调映射 定义1 3 3 设f ：酽_ 形为一映射，f = ( ，2 ，厶) r 若v x ，y 舻，z y ，3 i ( 1 i n ) ，使得 x i y i ，( 一雏) ( ( z ) 一 ( 9 ) ) o ( o ) ， 则称映射f 是舻中的晶一映射( p 一映射) 定理1 3 4 s l 设f ：，p - 彤为一映射 ( a ) f 是单调映射，则f 是岛一映射； ( b ) f 是严格单调映射，则f 是p 一映射 定义1 3 5 设矩阵a 舻“，若v x 舻，x 0 ，了以0 ，使得 x i ( a x ) i o ( o ) ， 则称a 为r 一矩阵( p 一矩阵) 显然半正定矩阵必为蜀一矩阵，正定矩阵必为p 一矩阵，所以r 一矩阵与 p 一矩阵分别是半正定矩阵与正定矩阵的推广 定理1 3 6 1 5 1 设矩阵a 舻“，则有下面的等价关系： ( a ) a 是r 一矩阵 ( b ) a 的所有主子式均为非负 ( c ) 垤 0 ，a + e i 是p 矩阵，其中j 是n 阶单位阵 定理1 3 7 【5 】设矩阵a 舻“，则a 为p 一矩阵的充要条件是；a 的全部 主子式均为正值 定理1 3 8 【5 】设f ：形- r n 为一可微映射，则f 为舒中的r 一映射的 充要条件是：对任意的z 彤，v f ( x ) 为r 一矩阵 下面考虑非线性自治系统： 鲁= m ) ，z 兄”或卫g o _ 舻，t o ，( 1 3 _ 1 ) 8 其中i ( o ) = 0 ，f ( x ) 连续且满足初值问题解的存在惟一性定理的条件为方便， 不失一般性，假定石= 0 是系统( 1 3 1 ) 的平衡点 记系统( 1 3 1 ) 的满足初值条件x ( t o ) = 。oo t o ) 的解为z ( t ；t o ，z o ) 定义1 3 9v e 0 和t o20 ，若存在6 = 6 ( t o ，e ) 0 ，使得当l i z o i l o ( 0 为光滑参数，则咖有如下性质 引理2 2 1设函数西：舒r + 由式( 2 2 2 ) 定义，则下列结论成立： ( i ) 对任意( 胁d ，r + + r 2 。l i + m 。咖( p ，。，6 ) = 妒( n ，6 ) ( i i )在日斗r 2 上连续可微，且 州刖= ：孥絮羞 蜘，归 m l + p 一- - 雾a - b 卜l a - 牝b l 1 2 撕，驴l + p - i , , - b 了卜l a - - 牝b _ _ p ( i i i ) 对任意的肛 0 ，札，钆，c b 0 由引理2 2 1 ，( p ，a ，b ) 在r + + xr 2 上l i p s c h i t z 连续 令2 = ( p ，z ) r + + x p ，定义h ：r + + xr ，l ， 日c 。，：= 日c 肛，z ，= ( 垂乞，) 其中垂( z ) = ( 妒( p ，x ，f l ( z ) ) ，咖( 肛，z 。，r ( z ) ) ) 丁，妒( 肛，z 。，r ( z ) ) ( i ( 2 2 2 ) 定义，则求解( 1 1 1 ) 等价于求解非线性方程组 日f z ) = 0 ( 2 2 3 ) n ) 由式 ( 2 2 4 ) 弓l 理2 2 2设，( z ) = i nli x i 一只( 。) l 0 ，故d 1 ( z ) 和d 2 ( z ) 均为正定矩阵 因此 ( d i l ( z ) d i ( z ) + f ，( z ) ) ! ，= 0 ， 即 ( f ( z ) 可) t = 一( d i l ( z ) d ( z ) ) i 从而 鼽( f ( z ) 童， = 一玑( 2 ) f 1 ( z ) d 1 ( z ) x 0 ，中( 肛，z ，f ( 茁)