（计算数学专业论文）非线性互补问题的derivativefree下降方法与同伦方法研究.pdf

非线陛互补问题的d e r i v a t i v e f r e e 下降方法与同伦方法研究 摘要 非线性互补问题( n c p ) 最早是1 9 6 4 年c o t t l e 在他的博士论文中提出的， 1 9 6 6 年h a r t m a n 和s t a m p a c c h i a 将非线性互补问题( n c p ) 与变分不等问题( v i p ) 联系在一起。到了七十年代末和八十年代初，关于非线性互补问题的研究 蓬勃发展起来。 非线性互补问题在许多领域都有着广泛的应用，诸如数学规划( m a t h e m a t i c a lp r o g r a m m i n g ) ，经济均衡模型( e c o n o m i e se q u i l i b r i u mm o d e l s ) ，决策论( g a m e s t h e o r y ) 等( 【加】，【1 6 ， 2 4 】e t c ) 。 在本篇论文中，我们从两个方面考虑非线性互补问题的解决方法，一个 是利用原始问题的极小化等价变形，给出了求解约束极小化问题的d e r i v a t i v e f r e e 下降算法；另一个是利用方程形式等价变形，构造了新的同伦方程并给 出了相应的算法。整篇论文的主要内容如下： 第一章，我们介绍了互补问题的起源以及各种互补问题的定义，并且列 出了一些本文要用到的定义、引理等预备知识。 第二章，我们集中讨论了原始的非线性互补问题在经过m e r i t 函数的极 小化变形之后的解决方法。利用m e r i t 函数的极小化变形可分为无约束和约 束两种类型。无约束极小化变形的研究比较多，已经有了很多种算法，理 论上也相对完备，但对于约束极小化变形，据作者所知，至今还没见过这 方面的算法。我们在这一章里就考虑了n c p ( f ) 的约束极小化变形，通过限 制的n c p 函数来构造n c p 问题的m e r i t 函数，将原始的问题n c p ( f ) 转化为 毗上的约束极小化问题，并构造相应的d e r i v a t i v e f r e e 下降算法。 在证明了所构造的d e r i v a t i v e - f r e e 算法的合理性以及整体收敛性之后，我 们将所构造的算法与以前已经存在的无约束型的d e r i v a t i v e f r e e 算法进行了比 较。所做的数值模拟都表明，我们的算法在迭代次数上具有明显的优势， 而且，我们的算法对于初始点的变化以及问题维数的增加显示了很强的适 应能力。 第三章，我们考虑了利用原始问题方程形式的等价变形，来解决非线性 互补问题的方法我们首先总结了这一类等价变形中的几种主要的方法， 并给出了一些数值模拟实例，然后我们考虑了解决非线性互补问题的同伦 方法。通过建立一个新的同伦方程，将n c p ( f ) 的求解问题转化为同伦方程 的求解问题。在不需要非线性映照f ( z ) 的j a e o b i a n 矩阵v f ( z ) 正则或非奇异 的限制下，我们证明了所构造的同伦方程有一条从( ”( m ，1 ) 出发的有界的解 曲线，而其终点就是我们要求的n c p ( f ) 的解。最后，我们建立了相应的同 伦算法以及解其中微分方程初值问题的曲线跟踪法，具体的实验例子也证 实了我们所提出方法的有效性。 第四章，我们总结了全文，并提出了一些研究的展望。 关键词：非线性互补问题( n c p ( f ) ) ，m e r i t 函数，d e r i v a t i v e f r e e 下降算 法，整体收敛性，同伦方程，正则值，曲线跟踪法。 s o m er e s e a r c ho nd e r i v a t i v e f r e e d e s c e n tm e t h o da n dh o m o t o p y m e t h o df o rn o n l i n e a r c 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 i n1 9 6 4 ，c o t t l ef i r s t l y p r e s e n t 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 s ( n c p ) i nh i s p h d sa r t i c l e i n1 9 6 6 ，h a r t m a na n ds t a m p a e c h i ar e l a t 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 s ( n c p ) w i t hv a r i a b l ei n e q u a l i t yp r o b l e m s ( v i p ) f r o m t h ee n do f7 0 1 sa n dt h eb e g i n n i n g o f8 0 s r e s e a r c h e sa b o u tn 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 sh a v eb e e n d e v e l o p e dr a p i d l y n o n l i n e a re o m p l e m e n t a r i t yp r o b l e m sh a v em a n ya p p l i c a t i o n si nal o to ff i e l d s s u c ha s m a t h e m a t i c a lp r o g r a m m i n g ，e c o n o m i c se q u i l i b r i u mm o d e l sa n dg a m e st h e o r y , a n ds oo n ( 1 0 ， 1 6 】， 2 4 e t c ) i nt h i sa r t i c l e ，w ec o n s i d e rt h em e t h o d sf o rs o l v i n gn 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 f r o mt w o a s p e c t s ：o n ei st h ee q u i v a l e n tf o r m u l a t i o no fm i n i m i z a t i o n ，t h eo t h e ri st h ee q u i v a 1 e n e ef o r m u l a t i o no fe q u a t i o n t ot h ef o r m e r ，w eg i v ean e wd e r i v a t i v e - f r e ed e s c e n ta l g o r i t h m b a s e do nc o n s t r a i n e dm i n i m i z a t i o nf o r m u l a t i o n ，t ot h el a t e r ，w ec o n s t r u c tan e wh o m o t o p y e q u a t i o na n dg i v ei t sa l g o r i t h m t h ew h o l ea r t i c l ei so r g a n i z e da sf o l l o w s i nc h a p t e r1 ，w ei n t r o d u c et h eo r i g i no fc o m p l e m e n t a r i t ya n dd e f i n i t i o n so fk i n d so f c o m p l e m e n t a r i t yp r o b l e m s m o r e o v e r w ep r e s e n ts o m ed 曲n i t i o n sa n dl e m m a sw h i c l la r e n e e d e dl a t e ri no u ra r t i c l e i nc h a p t e r2 w ed i s c u s st h em e t h o df o rs o l v i n gn o n l 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 s w i t h t h ee q u i v a l e n tf o r m u l a t i o no fm i n i m i z a t i o nb a s e do nm e r i tf u n c t i o n w i t hm e r i tf u n c t i o n ， t h eo r i g i np r o b l e mc a nb ec o n f o r m e dt ou n c o n s t r a i n e do rc o n s t r a i n e dm i n i m i z a t i o np r o b - l e m s t h e r eh a v eb e e nm a n ys t u d ya b o u tt h eu n c o n s t r a i n e de q u i v a l e n tf o r m u l a t i o n m a n y a l g o r i t h m sa n dt h e o r i e sh a v eb e e nc o n s t i t u t e da b o u tt h i sk i n do ff o r m u l a t i o n b u tt ot h e c o n s t r a i n e de q u i v a l e n tf o r m u l a t i o n it h e r ei sn oc o r r e s p o n d i n ga l g o r i t h m ，i nt h i sc h a p t e r 。w e c o n s i d e rt h em e t h o do fc o n s t r a i n e de q u i v a l e n tf o r m u l a t i o nw eu s et h em e r i tf u n c t i o nb a s e d o nt h er e s t r a i n e dn c pf u n c t i o na n dc o n v e r tt h eo r i g i np r o b l e mn c p ( f ) t om i n i m i z a t i o n p r o b l e mw h i c hc o n s t r a i n e do n 虢2 w e c o n s t i t u t et h ec o r r e s p o n d i n gd e x i v a t i v e - f r e ed e s c e n t a l g o r i t h m a f t e rw ep r o v e dt h ew e l l d e f i n i t i o na n dg l o b a lc o n v e r g e n c eo fo u rd e r i v a t i v e - f r e ed e s c e n t a l g o r i t h m ，w ec o m p a r eo u ra l g o r i t h mw i t hs o m e e x i s t e n td e r i v a t i v e - f l e ed e s c e n ta l g o r i t h m s b a s e do nu n c o n s t r a i n e dm i n i m i z a t i o nf o r m u l a t i o n a l lt h en u m e r i c a ls i m u l a t i o n ss h o wt h a t 3 o u ra l g o r i t h mi s p r e d o m i n a n to ni t e r a t i v et i m e so v e ro t h e ra l g o r i t h m sm o r e o v e r ，o u ra l - g o r i t h mr e p r e s e n tw e l la d a p t i v ec a p a c i t yo nt h ec h a n g eo fs t a r t i n gp o i n ta n di n c r e a s eo f d i m e n s i o n s i nc h a p t e r3 ，w ed i s c u s st h em e t h o df o rs o l v i n gn o n l 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 s w i t h t h ee q u i v a l e n tf o r m u l a t i o no fe q u a t i o n f i r s t l y ，w es u m m a r i z et h em a i nm e t h o d sa b o u tt h i s k i n do ff o r n m i a t i o ea n dm a k es o m en u m e r i c a l s i m u l a t i o n s ，s e c o n d l y ，w ed i s c u s st h eh o m o t o p y m e t h o df o rs o l v i n gn o n l i n e a rc o m p l e m e n t a r i t yp r o h l e m s t h r o u g hc o n s t i t u t i n ga p p r o p r i a t e h o m o t o p ye q u a t i o n ，w ec o n v e r tn c p ( f ) t os o l v i n gt h eh o m o t o p ye q u a t i o nw i t h o u ta s - s u m p t i o no fr e g u l a ro rn o n s i n g u l a r i t yf o rv f ( x ) ( w h i c hi st h ej a c o b i a uo ff ( z ) ) ，w ep r o v e t h a tt h eh o m o t o p ye q u a t i o nh a sab o u n d e ds o l u t i o nc u r v es t a r t i n gf r o m ( ( ，1 ) ，a n di t s e n dp o i n ti st h es o l u t i o no fn c p ( f ) f i n a l l y , w ec o n s t i t u t eah o m o t o p ya l g o r i t h ma n dt h e p a s s 。f o l l o w i n gm e t h o df o rs o l v i n gt h ed i f f e r e n t i a le q u a t i o ni nt h eh o m o t o p ya l g o r i t h m t h e e x m n p l ea l s os h o w st h ev a l i d i t yo fo u rh o m o t o p ym e t h o d i nc h a p t e r4 ，w es u m m a r i z et h ew h o l ea r t i c l ea n dp r e s e n ts o m e r e s e a r c h i n ge x p e c t a t i o n k e y w o r d s ： n o n l 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 s ( n c p ( f ) ) ，m e r i tf u n c t i o n ，d e r i v a t i v e f r e ed e s c e n tm e t h o d ，g l o b a lc o n v e r g e n c e ，h o m o t o p y e q u a t i o n ，r e g u l a rv a l u e ，p a s s - f o l l o w i n g m e t h o d 4 南京航空航天大学硕士论文 第一章绪论 1 1互补问题的起源以及各种互补问题的定义 早期的线性互补问题( 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 ( l c p ) ) 来源于线性和 二次优化问题的k k t 条件，但是有关互补问题的系统研究最早还是出现在 1 9 6 3 年h o w s o n 的博士论文以及l e m k e 和h o w s o n 的文章( 3 6 】中，他们说明了计 算b i m a t r i xg a m e 中的n a s h 均衡点问题可以转化为线性互补问题( l c p ) ，并且发 展了一种求解线性互补问题的简单有效的方法( c o m p l e m e n t a r yp i v o tm e t h o d ) 。 1 9 6 8 年，c o t t l e 和d a n t z i g 给出了线性与二次规划问题以及b i m a t r i xg a m e 在线 性互补问题( l c p ) 表述下的统一形式，这大大促进了对互补问题的研究。关 于线性互补问题的研究可参见文献 1 0 】， 4 5 】。 非线性互补问题( n c p ) 是1 9 6 4 年c o t t t e 在他的博士论文中首先提出的， 1 9 6 6 年h a r t m a n 和s t a m p a c c h i a 将非线性互补问题( n c p ) 与变分不等问题( v i p ) 联系在一起。虽然非线性互补问题( n c p ) 的引入只比线性互补问题晚了一 年，但关于非线性互补问题的研究却直到7 0 年代末才开始。非线性互补问 题与变分不等问题的研究可参见文献 2 4 】 线性与非线性互补问题在许多领域都有着广泛的应用，诸如数学规划 ( m a t h e m a t i c a lp r o g r a m m i n g ) ，经济均衡模型( e c o n o m i c se q u i l i b r i u mm o d e l s ) ，决策论 ( g a m e st h e o r y ) ，工程( e n g i n e e r i n g ) 以及力学( m e c h a n i c s ) 等( 【1 0 】， 1 6 ，f 2 4 】e t c ) 。 下面我们给出一些互补问题具体的定义。 最简单和研究最广泛的互补问题仍然是线性互补问题。线性互补问题 的一般形式为：给定m 蹰一“，q 精n ，寻求向量u = ( w 。) 舻以及 。= ( z ，) 渺，使得 w = m z + q ；w ，：0 ；w 7 。= 0 ( 1 1 ) 我们一般记形如( 1 1 ) 的线性互补问题为l ( q ，m ) ，只包含不等式约束的二次 规划问题的一阶优化必要条件便是一个l ( q ，m ) 由( 1 1 ) 的最后两个条件可 以看出，对任意的江1 ，n ，变量对( 引中至少有一个为0 ，( 盈) 被 称为问题l ( q ，m ) 的第i 个互补对。若矩阵m 为正半定矩阵，线性互补问题 l ( q ，m ) 称为单调的。 线性互补问题的一个简单的推广是所谓的混合线性互补问题( m i x e dl c p ， 或简记为m l c p ) ：给定a 卯一，b 妒“，c 卯m ，d 驼”“，d 豌n ，6 咿， 寻求向量u 豫“，”孵”，使得 n + u + c v = o ；b + d u + b y 0 ；u 20 ；u t ( 6 + d u + b y ) = 0 ( 1 2 ) 非线陛互补问题的d e r i v a t i v e f r e e 下降方法与同伦方法研究 混合线性互补问题( m l c p ) 是线性互补问题与关于变量”的线性方程系统 的混合。同时包含等式和不等式约束的二次规划问题的一阶必要条件便是 一个混合线性互补问题。在( 1 ，2 ) 中，若 是非奇异的，则向量“可具有形 式：u = 一a 一，( n + c v ) ，这样，混合线性互补问题( 12 ) 就变成线性互补问题 ( b - d a - l a , b d a 一- e ) 混合线性互补问题( 1 2 ) 称为单调的，若矩阵f g db 为正半定的。 线性互补问题的另外一个推广是所谓的水平线性互补问题( h o r i z o n t a l l c p 或简记为h l c p ) ：给定n 舻x n ，m 邢一，q 卯，寻求向量w 骑，z 妒， 使得 n w = m 。+ gw ，。0 ， 铆t 。= 0 f l3 ) 当n = j 时，水平线性互补问题( h l c p ) ( 1 ，3 ) 成为标准的线性互补问题，当非 奇异时，水平线性互补问题( h l c p ) ( 1 3 ) 等价于线性互补问题( q ，n m ) 。 水平线性互补问题( h l c p ) ( 1 3 ) 称为单调的，若任意满足n w = m z4 - g 的向量 对( 1 ，= 1 ) 和( 舻，z 2 ) 有：( 1 一u 2 ) 7 ( 。1 一。2 ) 0 。 对任意的饽1 ，n ，设m 。为正数，m = ：，m ；，线性互补问题的另 一种推广形式一一垂直线性互补问题( v e r t i c a ll c p ，或v l c p ) 的定义如下。 设矩阵m 。舻。，。妒具有形式m ：f m ；1 1 ，。：f 1 1 1 ，其中对任意 m ”矿 的诘1 ，n ，尬扩m ，q l 邺垂直线性互补问题( v l c p ) 就是寻求向 量z = ( ) 虢”满足 q + m z 0 ， = 0 ，五il ( 矿+ m z ) j = 0 ， i = 1 ，一，n ( 1 4 ) 广义互补问题( g e n e r a l i z e dl c p 或g l c p ) 的定义如下：对于矩阵a ，b 瓣“，g 渺。以及向量q 乳m ，寻求向量z 妒，s 跣“，。剌使得 。4 z + b s4 - c z = 口， 缸，s ，2 ) 0 ， z t 8 = 0 ( 1 5 ) 下面我们给出线性互补问题的非线性推广，也是本文所研究的主要内 容一一非线性互补问题( 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 c p ) ；给定 映射f ( ：) ：卯一跪n ，寻求向量。扩使得 ：0 ，f ( ：) 0 ，z t f 0 ) = 0( 1 6 ) 显然若f 为线性函数，则( 1 6 ) 即为线性互补问题。 南京航空航天大学硕士论文 非线性互补问题( n c p ) 的进一步推广是变分不等问题( v i p ) ：给定映射 f ( 。) ：蹰n 一咿，以及o k c 舻，寻求向量。+ k 使得 上述变分不等问题( v i p ) 记为v i ( k ，f ) 事实上，若k = z ：z 兰0 ) ，则变分不 等问题v i ( k ，f ) 的解矿也是非线性互补问题( n c p ) ( 1 6 ) 的解；若k = z ：= 0 ) 且f 为线性函数，变分不等问题v i ( k ，f ) 成为线性互补问题；若耳为矩形 区域，k = 兀翟1 。】1 - 一o os ， 1 ) 6 ) e r a = a b + 0 2 a ) ( a a 纠；一n 2 ) ( n 1 ) ； 7 ) s ( 。，6 ) 竺n 【纠 + f 一6 】车， 其中5 ) 亦称为隐l a g r m u g i a n 型n c p 函数 我们令f ( 。) = 限( z ) ) ，定义： ( 轧f 1 ( z ) ) 吣) - l ! j ( z 。，f n ( z ) ) 非线性互补问题的d e r i v a t i v e - f r e e 下降方法与同伦方法研究 显然，互补问题( 1 6 ) 的解等价于非线性方程中( z ) = 0 的解。我们还可以 将互补问题( 1 6 ) 化为如下的极小化问题： m i n 坼) = 扣吣) i i 2 ( 1 1 1 ) 其中中( 。) 定义如( 1 1 0 ) 。 因此，我们就可以利用解非线性方程或解极小化问题的方法来解决各 种各样的互补问题。在本文中，我们就分别从这两个方面考虑非线性互补 问题的解法。 1 2 预备知识 我们考虑n c p 问题( 1 6 ) ，为了以后的方便，在这一节中，首先给出一 些定义、引理以及预备知识。 定义1 2 映射f ： 一r n ，设，= 1 ，2 ，n ， 艰若对任意的z ，g ”，z 9 ，存在i f ，使得岛叭且( z 。一9 。) 【f i ( z ) 一日( 9 ) 】 0 ，称f 为p o 函数； 纠若对任意的z ，y r “，y ，存在i j ，使得戤y ；且x 。一们) 限( 。) 一只( g ) 】 0 ，称f 为p 函数； 圳，若存在p 0 ，对任意的z ，y r “，z y ，使得辫c ( q 一执) 限( z ) 一r ( y ) 】 圳z 一圳2 ，称f 为一致p 函数 定义1 3 若矩阵 厶。的每个主子式都非负，即任意的。0 ，z r r , ，存 在i j ，使得8 0 且q 【m z 】l 0 ，则称m 为p 0 矩阵； 剀若矩阵慨。的每个主子式都为正，即任意的z 0 ，。r n ，存在i j ， 使得瓤0 且以 m z 】； 0 ，则称m 为p 矩阵 关于p 0 函数与p 0 矩阵，有如下的引理： 引理1 4 映射f ：”一舻连续可微，则f 为p o 函数当且仅当任意的z r n ， f 在z 处的j a c o b i a n 矩阵j f ( x ) 为p 0 矩阵。 而对于一致p 函数，则有如下的结论： 引理1 5 映射f ：鼢一”连续可微，且f 为一致p 函数，则问题n c f ，倒有 唯一解。 定义1 6 映射f ：r n 一卯， 叫如果对任意的z ， ，( 9 一z ) 7 ( f ( y ) 一f ( 圳0 ，则称f 为单调函数； 缈如果对任意的z ，y 舻，( y z ) 7 ( f ( f ) 一f ( z ) ) 0 ，则称f 为严格单调函 数： 南京航空航天大学硕士论文 副如果存在口 0 ，对任意的z ，y 舯，0 一。) 7 ( f ( y ) 一f ( z ) ) 硎一z l l 2 ，则 称f 为强单调函数； 钞如果存在l 0 ，对任意的z ，y r “，有i i f ( y ) 一f ( x ) l i l i i x 一训，则称f 为l i p s c h i t z 连续函数 定义1 7 ( 正则性定义) 设j = 1 ，2 ，n ) ，函数：豫2 一豫，令 型! ! ! 幽：惮鱼墨蚴曼垒鱼- w ，型- 业 【 a l乩 d nl 型! 苎：兰堕2 ：型堕! 墨堕2 ! 尘( 垒! 墨魁州 a 6 l扔 a 6 l 以及 ，= 0 学 0 ) m ，= 卜学= 0 ) 帅，= 0 盟掣 0 ，z n 0 ，z n 0 ( 1 1 3 ) 称点z r n 为严格正则点。 注意：如果v f ( x ) 为p 0 矩阵，则z 为正则点；进一步地，如果v f ( 。) 为 p 矩阵，则。为严格正则点此外，z 为正则点一定也为严格正则点 定义1 8 对于n c p 问题r 矽， 如果存在2 0 使f ( ) 0 ，则称一6 ) n c p 严格可行； 纠设i 为口纠的一个解，即i2o ，f ( i ) o ，i 7 f ( i ) = 0 ，如果对任意的i ， 磊与e ( i ) 不同时为零俨pi + f ( i ) o j ，则称解i 为似纠的非退化解。 定义1 9 假设n 元函数，：舻一翁，如果，能够建立与n c p ( 1 纠等价的极小 化问题，即，( z ) 的整体极小解就是n c p ( 1 酬的解，则称，( 。) 为n c p ( 1 甜的 一个m e r i t 函数 5 非线性互补问题的d e r i v a t i v e f r e e 下降方法与同伦方法研究 求解n c p 比较关注的方法就是把原始的n c p 通过m e r i t 函数等价变形为 求解最小化问题，使得最小化问题的整体最小解恰好就是n c p 的解。大多 数的m e r i t 函数都用一个n c p 函数：r 2 一r 且( 。，b ) = 0 甘o 0 ，b 0 ，b ：0 来构造，例如隐l 呼a n g e 函数( i m p l i c i tl a g r a n g i u n ) ( ( 4 3 】) ，二次f i s c h e r b u r m e i s t e r 函数( 【2 9 ) ，距离函数( t h eg a pf u n c t i o n ) ( 4 】) ，正则化距离函数( t h er e g u l a r i z e d g a pf u n c t i o n ) ( 【2 1 】) 都是由n c p 函数构造的一种m e r i t 函数 对于( 1 6 ) 的n c p 函数毋：铲一精，一般使函数非负，并且常常满足以 下的若干性质： ( 1 ) a 0 ，b 0 ，a b = 0 ( o ，6 ) = 0 甘v ( n ，6 ) = 0 ； ( 2 ) 对任意的( n ，6 ) 7 瓣2 ，! 警i 铲兰0 ； ( 3 ) 对任意的( 口，6 ) 7 跪；，! 铲0 ； ( 4 ) 对任意的b 骑，! 为铲= 0 ，! 社s0 ； ( 5 ) 口二次可微且在任意严格互补向量( o ，b ) t 虢。的领域内有l i p s c h i t z 连续 的二阶导数； ( 6 ) 的二阶偏导数满足 ( i ) 对任意的b 0 ，蠹( o ，6 ) 0 ， ( i i ) 对任意的o 0 ，韶( o ，o ) 0 ， ( i i i ) 对任意的a mb ，黥( n 6 ) 裳( o ，6 ) = 0 ( 7 ) 勉掣盐掣= 0 锌p b ( o ，6 ) = 0 其中，( 5 ) 中的严格互补向量( 口，b ) 7 噼满足。0 ，b 0 ，a b = 0 且n 帅 0 ，明显 地，对于n c p 的非退化解i ，( 最( z ) ) 就是严格互补向量( v i ，= 1 ，n ) ) 。 一般地，任何一个n c p 函数都必须满足条件( 1 ) 和( 2 ) ；同时满足条件 ( 1 ) ，( 2 ) ，( 5 ) ，( 6 ) 的n c p 函数为正定n c p 函数例如，隐l a 香z a n g e 函数( i m p l i c i t l a g r a n g i a n ) ( 【4 3 】) 中使用的n c p 函数( 记作m s ) 满足了条件( 1 ) ( 2 ) ；二次 f i s c h e r b u r m e i s t e r 函数( 2 9 】) 中使用的n c p 函数( 记作f 且) 满足条件( 1 ) ，( 2 ) ， ( 7 ) ，并且f b 在精2 上连续可微，v 毋f b ( o ，0 ) = ( 0 ，o ) 然而，在文献【4 1 】中，l u o 和t s e n g 提出的m e r i t 函数并非基于n c p 函数 构造的。 值得注意的是，基于n c p 函数的那些m e r i t 函数，必须同时在f 强单调 ( 或f 为一致p 函数) 且fl i p s c h i t z 连续的条件下，才能具有整体误差界， 而l u o 和t s e n g 的m e r i t 函数( 【4 l 】) 仅在f 强单调的条件下就能具有整体误差 界l u o 和t s e n g 的m e r i t 函数为 n ，：瞬“一跪，( z ) = 讥( ( z ，f 扛) ) ) + 砂i ( - x i ，一只( 。) ) ， ( 1 a 4 ) i = 1 南京航空航天大学硕士论文 其中，母o ：虢一【0 ，+ o 。) ，1 f l 。：艉2 一l o ，+ 。) ，i = 1 ，n 为连续函数且只在负象限 上值为零。该m e r i t 函数具有如下性质： 1 ) 如果f 强单调，则，具有整体误差界； 2 ) 如果( z ，f ( z ) ) ，一最( z ) ，f _ 1 ，n 都为关于。的凸函数，则，也为舻上的 凸函数。 在文献【3 0 】中，采用了如下的m e r i t 函数： n 1 “r ，一 12 ，k y f 扛) = 中( 甄r 扛) ) + i i 、z ；+ r o ) 2 一吼一r 扛) i ( 1 1 5 ) 这是对l u o 和t s e n g 的m e r i t 函数的一种改造，它保留了 4 1 中m e r i t 函数的 所有性质，只是f 为p 函数。 此外，如果( 1 1 4 ) 中的如( 一一只( z ) ) = ； 杉可再丽一跏一日( z ) 2 ，则可 以定义如下新的m e r i t 函数： ，( z ) = 粕( ( 。，f o ) ) ) + j 1 l 以? + r o ) 2 一戤一只扛) l 2 ( 1 1 6 ) n r r 一 1 该新的m e r i t 函数具有如下的性质： 1 ) 如果f 单调，则，的任意稳定点是n c p 的解； 2 ) 如果f 单调，则，有整体误差界； 3 ) 如果f 单调且n c p 严格可行，则，的水平集有界 显然，保留了厶y f ( z ) 所有好的性质( ) ，且进一步地，比屈v r ( z ) 还多了至少两个优点： 1 ) ，在n c p 的每一个退化解处都二次连续可微，而f k y ，( z ) 在n c p 的任意 解处都非二次连续可微； 2 ) ，正如二次f i s c h e r b u r m e i s t e r 函数一样，都在n c p 解的附近起作用。 正因为有了性质2 ) ，可以构造一个解决n c p 的混合方法： s t e p1 ：对m i n ，用最速下降法； s t e p2 ：对由f i s c h e r b u r m e i s t e r 函数导出的方程组用牛顿方法。 这样，最速下降法确保了整体收敛性，而牛顿方法又保证了快速局部收 敛性 大家都知道，许多研究者致力于对m e r i t 函数误差界和水平集的深入研 究，这是由于误差界对解决迭代方法收敛性方面起着至关重要的作用，而 一个m e r i t 函数的水平集有界就能确保由一个下降算法产生的序列至少存在 一个聚点( 【3 0 j ) 非线性互补问题的d e r i v a t i v e f r e e 下降方法与同伦方法研究 1 3 本文的主要内容 在本文中，我们从两个方面考虑解非线性互补问题的方法，一种是将非 线性互补问题转化为极小化问题，并利用新的m e r i t 函数和d e r i v a t i v 。f r 。下 降算法来解决单调的非线性互补问题；另外一种是将非线性互补问题转化 为非线性方程的求解问题，通过建立同伦方程的方法来解这个问题。 南京航空航天火学硕士论文 第二章单调非线，陛互补问题的d e r i v a t i v e f r e e 下降算法 将非线性互补问题转化为极小化问题，是解决非线性互补问题的最常 见的方法( 见1 1 9 】，1 2 0 】，【4 3 】等) ，但往往由于涉及到求m e r i t 函数的梯度等计算 量非常大的运算，而很难获得快的收敛速度。近年来，在 6 5 ，【4 4 】，【5 0 】等文 献中出现了一种新的下降算法：d e r i v a t i v e f r e e 下降算法。这种算法由于避免 了求m e r i t 函数的梯度，立刻引起了诸多研究者的兴趣。 在这一章里，我们考虑了一种新的d e r i v a t i v e f r e e 下降算法，它采用了以 前算法中未用过的m e r i t 函数，实际上是一种基于限定n c p 函数的m e r i t 函 数，将非线性互补问题转化为约束优化问题，利用它我们建立了d e r i v a t i v e - f r e e 下降算法，来解决单调的非线性互补问题。 2 1非线性互补问题极小化变形后的解法简介 解决非线性互补问题最常用的方法之一就是将其转化为无约束或约束 的极小化问题，关于这方面已经出现了许多种成熟的和正在发展的解决方 法，我们首先对其中几个比较有代表性的方法做简单介绍 1 传统的算法。 传统的算法包括b f g s 算法，n e w t o n 方法，拟n e w t o n 方法以及阻尼 n e w d o n 法等它们基本上都是利用非线性映照f ( z ) 的梯度来构造下降算 法。例如在文献【4 7 】中证明了这样的结论：矿为n c p ( f ) 的非退化解，如 果f ( z ) 在矿点二次可微，v f ( z ) 在矿附近连续且 v f ( z ) 倒， 耳) 线性 独立，其中zk 分别为使得f ( x + ) 和矿分量为零的指标集；则对于m e r i t 函数定义的n e w t o n 方法： v m ( x 2 ，o ) + v 2 m ( x i , o ) ( 。件1 一) = 0 是超线性收敛的 2 d e r i v a t i v e f r e e 下降算法 由于传统的算法基本上都是利用非线性映照f ( z ) 的梯度来构造下 降算法，而当问题的维数比较高时，m e r i t 函数以及f ( 。) 的梯度的计算 量是非常大的，因此，近年来大家的主要研究目标都集中到构造不需要 求m e r i t 函数以及f ( z ) 梯度的算法上，也就是所谓的d e r i v a t i v e 。f r e e 方法。 在文献 6 7 】中采用了隐l a g r a n g e 型的m e r i t 函数，并使用了如下的搜 非线性互补问题的d e r i v a t i v e f r e e 下降方法与同伦方法研究 累方向和迭代规则： 驴= 一警( x a , f ( 幽) 一声尝p ，即呦， z k + 1 = z + 7 1 k d k 其中f k 为满足如下a r m i j o t y p e 线性搜索规则的最小的整数f ： 帆( z + 7 1 d ) m o ( x ) 一j 卸( ij r ( z ) 1 1 + p l l s ( x ) i i ) 2 文章中证明了该算法在f ( z ) 可微且强单调的意义下的整体收敛性。 在文献| 4 4 】中则同样考虑了隐l a g r a n g e 型的m e r i t 函数，而且使用了 和文献【6 7 1 一样的搜索方向和迭代规则，只是采用了不同的a r m i j o t y p e 线性搜索规则： m a ( x k ) 一m c , ( x k + 7 l d k ) 7 7 2 1 惜( x k , f ) ) 十警( x k , f x k 在这篇文章中则证明了该算法在，( z ) 可微且强单调的意义下的整体线 性收敛性 文献 5 0 和【65 中利用了二次f i s c h e r b u r m e i s t e r 函数型的m e r i t 函数来 构造d e r i v a t i v e - f r e e 下降算法。文献【5 0 】中的n c p 函数为 坼，5 ) = ；( 侮再一。一6 ) 2 搜索方向和a r m i j o - t y p e 线性搜索规则分别为： 扎一警p ，f ( x k ) ) ， 皿0 + 卢m d ) 皿( z ) 一阳mj d | 1 2 此文中证明了该算法在f ( z ) 光滑单调的意义下算法所生成点列的聚点 为n c p ( f ) 的解。 文献 6 5 】中的n c p 函数为 撕，6 ) = 弘) ；+ ；( 佰再一。一6 ) 2 搜索方向为可调整的搜索方向，定义为： 以萨) = 一警( 一脚锄一眇警( 一砷锄， 其a r m i