（工程力学专业论文）互补问题算法研究及其在力学中的应用.pdf

摘要 互补问题的最显著特征是含有互补性条件，即要求两组非负变量对应分量的乘积为 零。3 0 多年以来，互补问题已经发展成为许多领域非常重要的数学工具，在数学规划、 经济、工程及其它学科具有非常广泛的应用。在经济领域中的应用主要有w a l r a s i a n 平 衡、空间价格平衡和对策论模型等；在工程中的应用有接触力学问题、断裂力学问题、 弹塑性问题、障碍和自由边界问题、流体弹性动态润滑问题、最优控制问题及交通平衡 问题等。也就是说，上述这些问题都可以模型化为互补问题，从而最终归结为互补问题 的求解。可以看出，在互补问题众多的应用中，经济和力学是互补问题应用的两个最大 的领域。 本论文的主要工作是互补问题的算法研究及其在力学中的应用，其主要动机为： 夺虽然互补问题已经有许多算法，但一些力学实际问题往往满足不了算法的限定条件， 因此需对某些算法做一些适应性改进。与此同时，也有必要针对力学问题进行一些 新算法的研究和探讨； 夺近年来，互补问题的力学应用远远落后于算法发展，把一些新的算法介绍到力学问 题求解，既有助于丰富力学问题的算法工具，也有助于扩充互补问题的应用背景。 在互补问题的算法研究方丽，主要针对近年来发展起来的两类重要方法：方程组方 法和内点方法，希望为力学问题求解提供一些可行的算法，特别希望能提供一些可求解 大型与非线性互补问题的算法。 第二章的四个算法均为方程组类方法，包括两个光滑牛顿型算法和两个光滑迭代算 法。前者借助n c p 函数把互补问题转化为等价的非光滑( 不可微) 方程组，再用带参数 的光滑( 连续可微) 方程组近似这些非光滑方程组最后用牛顿型方法求解所得到的光 滑方程组，希望通过光滑参数趋于零得到原来互补问题的解：后者基于等价不动点格式， 构造了一个光滑迭代算法和一个具有有限终止性质的算法，虽然这种迭代算法仅有线性 收敛速度，但由于其格式简单、存储量小、保稀疏性、非常易于计算机实现等特点，故 较适用于求解大规模稀疏问题。 第三章给出了两个新的内点算法。本论文从两个不同角度对原一对偶内点方法通常 使用的摄动方程组进行了变化。并据此建立了两个不同的内点算法。首先通过对中心化 方程船= 掣e 实施代数等价变换，得到了新的不同的摄动方程组。我们发现，通过幂变 换得到的摄动方程组，可给出彭积明等人提出的大步内点算法的牛顿方程，但代数等价 变换的思想要比彭等人算法的思想容易理解得多。在此基础上，我们建立了一个基于幂 大连理工大学博士学位论文 变换的内点算法。第二个算法利用极大极小( m i n - m a x ) 函数本身所具有的“均化”作 用，定义了一个新的邻近度量函数，并以其最优性条件代替中心化方程。这样，在摄动 方程本身建立了一种自调节机制，从而使牛顿方向能够根据上次迭代点的信息在各个互 补对之间做出自适应的调整。基于改造后的摄动方程组，建立了一个具有自调节功能的 内点算法。 第四章为弹性摩擦接触问题的数值求解及其算法应用。利用参变量变分原理和参数 二次规划法，离散后的接触问题可化为线性互补问题，之后，将第二、三章提出的互补 问题算法应用到接触问题的数值求解中。 在第五章，我们采用正交各向异性摩擦定律模型对三维弹塑性摩擦接触问题进行分 折，将正交各向异性的摩擦定律线性化后，将参变量变分原理和参数二次规划法应用到 这一复杂的力学问题中来，最终将问题化为线性互补问题模型。经验证，本论文提出的 算法对该互补模型仍然适用。另外在对接触实际例题的分析中，还注意比较了下面两 种情况：正交各向异性摩擦与各向同性摩擦的结果比较：正交各向异性弹性摩擦接触与 弹塑性摩擦接触的结果比较。 关键词互补问题：接触问题；弹塑性问题：内点方法：方程组方法：三维弹性摩擦接 触问题：正交各向异性弹塑性摩擦接触问题 摘要 a b s t r a c t t h e d i s t i n g u i s h i n g f e a t u r eo fa c o m p l e m e n t a r i t yp r o b l e m i s t h es e to f c o m p l e m e n t a r i t yc o n d i t i o n s ，w h i c hr e q u i r e t h a tt h e p r o d u c t o ft w o n o n n e g a t i v e q u a n t i t i e ss h o u l db ez e r o o v e rm o r et h a nt h i r t yy e a r s ，t h i sc l a s so fp r o b l e m sh a s b e c o m ei n c r e a s i n g l y p o p u l a r i n m a n yf i e l d s s u c ha sm 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 sa n de n g i n e e r i n ga p p l i c a t i o n sf r o mt h ef i e l do fe c o n o m i c si n c l u d eg e n e r a l w a l r a s i a n e q u i l i b r i u m ，s p a t i a lp r i c ee q u i l i b r i a ，a n dg a m e - t h e o r e t i c m o d e l si n e n g i n e e r i n g ，c o m p l e m e n t a r i t yp r o b l e m s a r i s ei nc o n t a c tm e c h a n i c s f r a c t u r e m e c h a n i c s ，e l a s t o p l a s t i cp r o b l e m s ，o b s t a c l e a n df r e e b o u n d a r yp r o b l e m s ， h y d r o d y n a m i cl u b r i c a t i o n ，o p t i m a lc o n t r o lp r o b l e m sa n dt r a f f i ce q u i l i b r i u mp r o b l e m s t h a ti s ，a l lt h ea b o v ep r a c t i c a lp r o b l e m sc a nb ef o r m u l a t e da sc o m p l e m e n t a r i t y p r o b l e m sa n ds o l v e db yp r o p e ra l g o r i t h m s ，e c o n o m i c sa n dm e c h a n i c sa r et h et w o m a j o r a r e a sa m o n gt h en u m e r o u sa p p l i c a t i o n so fc o m p l e m e n t a r i t yp r o b l e m s t h e p r e s e n t d i s s e r t a t i o ni s m a i n l y d e v o t e dt o s t u d y i n ga l g o r i t h m s o f c o m p l e m e n t a r i t yp r o b l e m sa n d t h e i ra p p l i c a t i o n si nm e c h a n i c s t h em o t i v a t i o no ft h i s t h e s i si sb a s e dt h e f o l l o w i n gc o n s i d e r a t i o n s ： p r a c t i c a lm e c h a n i c sp r o b l e m sm a yn o ts a t i s f yc e r t a i nr e s t r i c t i v ec o n d i t i o n sf o r s o m ee x i s t i n ga l g o r i t h m sf o rc o m p l e m e n t a r i t yp r o b l e m s ，t h o u g h 蜘e ym i g h tb e m e r ye f f i c i e n tf o rs o m em a t h e m a t i c a ip r o b l e m s ，t h e r e f o r e o no n eh a n d i t i s n e c e s s a r yt om a k eaf e wm o d i f i c a t i o n st os o m ee x i s t i n ga l g o r i t h m ss ot h a tt h e y a r es u i t a b l ef o rs o l v i n gm e c h a n i c sp r o b l e m so nt h eo t h e rh a n d w en e e dt o d e v e l o pa l g o r i t h m sd i r e c t l yo r i e n t e dt oc h a r a c t e r i s t i c so fm e c h a n i c sp r o b l e m s 夺a p p l i c a t i o n s o fm o d e r n a l g o r i t h m s i nm e c h a n i c s d r o p p e d f a rb e h i n dt h e a l g o r i t h m i cd e v e l o p m e n t s o fc o m p l e m e n t a r i t yp r o b l e m s w ew i s ht h ei n t r o d u c t i o n o fs o m en e wa l g o r i t h m st os o l v i n gm e c h a n i c sp r o b l e m ss h o u l dp l a yt h er o l eo f b o t h e n r i c h i n g t h es o l u t i o nt o o l so fm e c h a n i c sa n de x t e n d i n gt h er a n g e so f c o m p l i m e n t a r i t yp r o b l e m s ，w h e r e b ya r o u s i n gt h ef u r t h e ri n t e r e s to fr e s e a r c h e r s f r o mt h et w of i e l d s ， i nt h es t u d yo fc o m p l e m e n t a r i t ya l g o r i t h m s w er e s t r i c to u r s e l v e st ot w om a j o r c l a s s e so ft h e m ：e q u a t i o ns y s t e mb a s e da l g o r i t h m sa n di n t e r i o r - p o i n ta l g o r i t h m sw e w i s ht od e v e l o pe f f e c t i v ea l g o r i t h m sf o rp r a c t i c a lp r o b l e m si nm e c h a n i c s ，i np a r t i c u l a r l n 查堡墨三查兰! 主兰垡垦茎 k e e p i n gl a r g e s c a l ea n dn o n l i n e a rc o m p l e m e n t a d t yp r o b l e m si nm i n d t w os m o o t h i n gn e w t o n - t y p ea l g o r i t h m sa n dt w os m o o t h i n gi t e r a t i v e a l g o r i t h m s a r eg i v e ni n c h a p t e r2 ，i nt h ef i r s tt w oa l g o r i t h m s t h ec o m p l e m e n t a r i t yp r o b l e mi s r e f o r m u l a t e dt on o n - s m o o t h ( n o n d i f f e r e n t i a b l e ) e q u a t i o n su s i n g s o c a l l e d n c p - f u n c t i o n s a n dt h e ns o l v e db ya p p l y i n gn e w t o n - t y p em e t h o d st ot h es m o o t h e n e d e q u a t i o n st h et h i r da l g o r i t h mi sas m o o t hi t e r a t i v em e t h o db a s e do na ne q u i v a l e n t f i x e d p o i n tf o r m a to ft h ec o m p l e m e n t a r i t yp r o b l e mt h ef o r t ha l g o n t h mi st h es a m ea s t h et h i r do n ew i t ha na d d i t i o no ff i n i t et e r m i n a t i o n c r i t e r i a a l t h o u g ht h el a t t e rt w o a l g o r i t h m s h a v eo n l yl i n e a rr a t eo f c o n v e r g e n c e ，t h e ya r ee s p e c i a l l ys u i t a b l ef o r l a r g e s c a l e a n ds p a r s ep r o b l e m s ，w i t h 怡a t u r e so fs i m p l ef o r m u l a ，s m a l l s t o r a g e ， s p a r s i t yp r e s e r v a t i o na n de a s yi m p l e m e n t a t i o n t w oi m p r o v e di n t e r i o r p o i n ta l g o r i t h m sa r ep r o p o s e di nc h a p t e r3 t h e ya r e d e s i g n e db a s e d o nt h em o d i f i c a t i o n st ot h es t a n d a r dp e r t u r b e ds y s t e mo fp r i m a l d u a l i n t e r i o r - p o i n ta l g o r i t h m s f r o mt w od i f f e r e n t a n g l e s t h e f i r s tl sb a s e do nt h e a l g e b r a i c a l l ye q u i v a l e n t t r a n s f o r m a t i o nt ot h es t a n d a r dc e n t e r i n ge q u a t i o n x s = , u ew e d i s c o v e r e dt h a tt h en e w t o ne q u a t i o n su s e db yp e n gj i m i n ge ta 1 i nt h e i rl o n g s t e p i n t e r i o rp o i n ta l g o r i t h m sc o u l db ed e r i v e db yap o w e rt r a n s f o r m e dp e r t u r b e ds y s t e m o u r a p p r o a c ho fa l g e b r a i c a l l ye q u i v a l e n tt r a n s f o r m a t i o ni sm u c hs i m p l e rt h a nt h eo n e p r o p o s e db yp e n ge ta 1 i nt h e i ra l g o r i t h m s i n s p i r e db yt h i so b s e r v a t i o n ，a ni n t e r i o r p o i n ta l g o r i t h m b a s e do n p o w e r t r a n s f o r m a t i o ni s d e v e l o p e d a n o t h e r i n t e r i o r a l g o r i t h m i st o e m p l o yt h e “h o m o g e n i z i n g ”e f f e c to fm i n m a xf u n c t i o n w h e r et h e s t a n d a r dc e n t e r i n ge q u a t i o ni sr e p l a c e db yt h eo p t i m a l i t yc o n d i t i o no fan e w p r o x i m i t y m e a s u r ef u n c t i o n as e l f - a d j u s t i n gm e c h a n i s mi sa d d e dt ot h en e w p e r t u r b e ds y s t e m s u c ht h a tt h en e w t o nd i r e c t i o n s o fe a c hc o m p l e m e n t a r yp a i r sc a nb ea d j u s t e d s e l f - a d a p t i v e l ya c c o r d i n g t ot h ei n f o r m a t i o no fl a s ti t e r a t e s w e d e v e l o p a s e l f - a d j u s t i n gi n t e r i o rp o i n ta l g o r i t h mb a s e d o nt h em o d i f i e dp e r t u r b e ds y s t e m i n c h a p t e r4 w ec o n s i d e rf i n d i n gt h en u m e d c a is o l u t i o no ff r i c t i o n a ic o n t a c t p r o b l e m sa n dt h ea p p l i c a t i o n so ft h ep r o p o s e da l g o r i t h m s t h ed i s c r e t i z e df r i c t i o n a l c o n t a c t p r o b l e m s c a nb er e d u c e da s ai 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 mu s i n g p a r a m e t r i cv a r i a t i o n a lp r i n c i p l ea n dp a r a m e t r i cq u a d r a t i cp r o g r a m m i n gm e t h o d t h e n w ec a na p p l yt h ea l g o r i t h m sp r o p o s e di nt h i st h e s i st ot h es o l u t i o no ft h ec o n t a c t p r o b l e m s f nc h a p t e r5 w es t u d yt h r e ed i m e n s i o n a le l a s t o p l a s t i cf r i g i o n a lc o n t a c tp r o b l e m s w i t ho r t h o t r o p i cf r i c t i o ni a wp a r a m e t r i cv a d a t i o n a lp r i n c i p l ea n dp a r a m e t r i cq u a d r a t i c p r o g r a m m i n gm e t h o da r ea p p l i e dt oa n a l y z et h i s c l a s so fc o m p l i c a t e dm e c h a n i c s p r o b l e m s ，al i n e a rc o m p l e m e n t a r i t yp r o b l e mf c r m u l a t i o n i sd e r i v e d t h ep r o p o s e d a l g o r i t h m sa r ea l s os u i t a b l ef o rs o l v i n gt h i sf o r m u l a t i o nt h r o u g hc o m p u t a t i o n s w h a t s 摘要 m o r e ，f o rt h eg i v e ne x a m p l e si nt h i sc h a p t e r w eh a v eg i v e nac o m p a r i s o no fs o m e c o m p u t a t i o nr e s u l t sf o rd i f f e r e n tf r i c t i o n m o d e l sa n dac o m p a r i s o nb e t w e e ne l a s t i c c o n t a c ta n d e l a s t o - p l a s t i cc o n t a c t a sw e l l k e y w o r d sc o m p l e m e n t a r i t yp r o b l e m s ；c o n t a c tm e c h a n i c s ；e l a s t o - p l a s t i cp r o b l e m s i n t e r i o rp o i n tm e t h o d s ；e q u a t i o ns y s t e mm e t h o d s ；t h r e ed i m e n s i o n a l e l a s t i cf r i c t i o n a lc o n t a c t p r o b l e m s ；o r t h o t r o p i ce l a s t o - p l a s t i cf r i c t i o n a l c o n t a c tp r o b l e m s v 第一章绪论 本章首先介绍了互补问题的概念及其背景知识和应用领域。之后，将线性互补问题 当前的主要算法做了简要的总结，互补问题算法可以划分为以l e r a k e 算法为代表的经典 算法以及以内点法和方程组法为代表的现代算法。其中，前者面向中小型线性互补问题 的求解后者面向非线性互补问题和大规模问题的求解。接下来概括了互补问题在非线 性力学申的一些应用情况，如摩擦接触问题、弹塑性问题及结构优化问题等。另外，还 简单描述了文献上给出的几类重要力学问题的互补问题模型，将力学问题写成互补问题 模型具有双重魅力：一是使力学问题有更自然、更清晰的数学表达；二是可以考虑用互 补问题的有效的数值算法采求解。最后对本论文的研究动机及主要研究内容进行了总 结。尽管互补问题现在已经有许多有效的算法，但应用到具体的实际问题中不一定仍然 有效。所以结合力学问题时互补问题算法进行研究，探索和改进是非常有意义的_ r - 作。 11 引言 舅：补问题的最显著特征是含有互补性条件，即要求两组非负变量( 或变量的函数) 的对应分量的乘积为零。3 0 多年以来，互补问题已经发展成为许多领域非常受欢迎的工 具。互补问题在数学规划、经济、工程及其它学科具有非常广泛的应用，在经济领域中 的应辟j 主要有w a l r a s i a n 平衡、空间价格平衡和对策论模型等；在工程中的应用有接触 力学问题、断裂力学问题、障碍和自由边界问题、流体弹性动态润滑问题、最优控制问 题l 乏交通平衡问题等。也就是说，上述这些问题都可以模型化为互补问题，从而最终归 结为互补问题的求解。f e r r i s 和p a n g u 在1 9 9 7 年的综述性文献中给出了许多领域中已 有的互补问题数学模型，并给出了互补问题算法研究的许多文献。 可以看出，在互补问题众多的应用中，经济和力学是互补问题应用的两个最大的领 域，而前者的应用历史更长一些。 那么，什么是互补问题昵? 其一般的数学描述是：给定函数f ：r “- - 月”，求矢量 xer ”，使满足如下的方程和不等式条件 x 0 ，f ( x ) 0 ，x t f ( x ) = 0 式( 1 1 ) 等价于分量形式表达t 0 ，f ( x ) 0 ，x 。f ( x ) = 0 ；i = 1 ，2 ，n 。 大连理工大学博士学位论文 当f ( x ) 是线性函数，即f ( x ) = m x 十q ( m r ，q r ”) 时，上述问题为线性互 补问题。记为l c p ( m ，g ) ，否则为非线性互补问题，记为n c p ( f ) 。互补问题的名称来 臼于( 1 1 ) 中的第三个方程，称为互补条件，因此，互补对( x 。，f ( x ) ) ( i = l ，n ) 中， 至少有个变量为零。在实际问题中，变量z 一般是指决策变量或决策变量的函数，如 接触力学问题中的接触位移或接触力，经济问题中的商品价格或商品数量等。 追述互补条件的起源，其最早出现在k a r u s h 于1 9 3 9 年研究不等式约柬非线性规划 的最优性条件中，而这只是数学意义上的约束函数和拉各朗目乘子i 司的互补关系。在许 多实际问题中，互补问题被赋予了更广泛的意义，因为在经济和工程领域里的大量关于 平衡问题的研究，会自然地涉及到互补条件。比如，在经济学里的w a l r a s i a n 平衡问题 中，商品的价格和该商品的过量供应之间就是互补关系，当商品的供应过量时，则其价 格就会f 降，或者直到需求增加抵消这种过量供应，或者价格下降到零。另一个例子来 自于力学阃题，在接触力学中，两物体间的接触力和它们间的距离之间是互补关系，只 有两物体间的距离为零时才有可能产生接触力，否则接触力为零。 就对互补问题的研究而言，人们首先研究的是线性互补问题( l c p ) ，其最初动机 是由于线性规划和二次规划的k k t 最优条件构成一个l c p 。比较系统地对线性互补问 题的研究始于1 9 6 3 年，在h o w s o n 的博士论文阱及在l e m k e 和h o w s o n 的文章里i 2 j 把计 算双矩阵对策n a s h 平衡点的问题转化为一个线性互补问题，并提出了一个互补转轴算 法，即l e m k e 算法。而c o t t l e 和d a n t z i g 于1 9 6 8 年将线性规划、二次规划以及双矩阵 对策统一转化为线性互补问题，被视为一个重要突破，由此，对互补问题的研究进入了 一个兴旺时期。 继线性互补问题之后不久，c o t t l e 于1 9 6 4 年在他的博士论文里引进了非线性互补问 题( n c p ) ，其主要目的是计算非线性规划的驻点。丽对非线性互补问题的算法研究来 说，主要从2 0 世纪7 0 年代末期才开始。 对于互补问题的应用，人们起初主要是对经济和对策论的平衡问题进行计算，研究 计算平衡的最初动力来自于经验地分析一般平衡理论并用这种理论来研究税收、失业等 问题的需要。随着2 0 世纪8 0 年代科技与经济的飞速发展，工业上的更复杂的政策计划 模型需要更有效的方法来分析和计算经济及对策论模型。同时，互补问题的应用领域也 在不断拓宽，由经济问题发展到了工程方面的许多领域，这样，互补问题变得越来越重 要。 互补问题的广泛应用促使许许多多的数学工作者以极大的热情投入到算法的研究 线性互补问题的英文表达为l i n e a r c o m p l e m e n t a r i t yp m b l e m ；n o n l i n e a r c o m p l e m e n t a r i t y p r o b l e m 是非线性互补问题 的英文袭达。 第一章结论 中来。他们的目标是开发有效和强健的求解方法。因为对任何一个实际问题而言，只建 立了漂亮的互补模型是远远不够的，最终目的是将问题的解求出来。而互补问题本身是 由等式和不等式构成的，属于非光滑问题，探索其有效而强健的算法绝非轻而易举之事。 经过大量学者的不懈努力和潜心研究，在互补问题算法方面不断涌现出令人兴奋的 成果，如基于方程组的算法和内点类算法等。算法的发展又反过来激发人们将互补问题 格式应用到新的问题或新的领域。新问题可能会对算法提出更高的要求，所以互补问题 在应用和算法研究方面相互促进，共同发展。 本论文的工作主要分为两部分第一部分是互补问题算法研究，其动机是面向大规 模问题和非线性互补问题；第二部分是算法的力学应用。 1 2 互补问题的研究和应用 1 2 1 互补问题算法发展 对互补问题的研究是多方面的，理论方面主要包括研究解的存在性、唯一性、稳定 性、灵敏度分析：算法方面主要是建立有效的求解方法及相应的算法分析。因为互补问 题在经济领域、工程领域及其它学科中的广泛应用，寻求有效的求解方法一直是人们最 关注的问题，为此，这里将对一些重要算法的进展情况给予介绍。 互补问题的算法发展可以划分为这样两个时期：一是以l e m k e 算法为代表的经典算 法研究时期，其主要目标是面向中小型线性互补问题的求解；二是以方程组类算法和内 点法为代表的现代算法研究时搬主要是面向大型和非线性互补问题的求解。其中，方 程组类算法主要是基于m a n g a s a r i a n 的1 9 7 6 年的非常著名的工作，尽管这类算法的热 潮开始于2 0 世纪9 0 年代咀后；内点算法主要开始于1 9 8 4 年k a r m a r k a r 的具有开创性 的工作。 如果一个算法可以求出互补问题的一个解或能说明问题无解，则说这个算法能“处 理p r o g e s s ) ”这个问题。无论从“处理”情况还是从效率方面来说，几乎所有的算 法都依赖于问题，即对非线性互补问题n c p ( f ) ，取决于函数f ( x ) 的性质；对线性互补 问题l c p ( m q ) ，取决于矩阵m 和向量g 的性质，所以矩阵类别在线性互补问题的研究 中起着非常重要的作用。若对l c p ( m ，q ) 的数据不加任何限制，目前所知的唯能保证 “处理”线性互补问题的算法是枚举类算法( e n u m e r a t i v ea l g o r i t h r n s ) 。 互补问题有唯一解的条件非常苛刻，般是很难满足的，对非线性互补问题，要求 大连理工大学博士学位论文 在贮( r ：= x lx o ，ze r “) ) 上连续的函数f ( x ) 强单调2 ：对线性互补问题，要求矩阵m 为p 矩阵l 即各阶主子式都大于零的方阵) ，这时的g 可以是任何实数向量，显然正定 矩阵。为p 矩阵。对于不满足上述条件的函数或矩阵，互补问题有可能无解或有多个解。 在多解的情形，算法般只能求出一个解。 对于算法的收敛性，人们一般希望具备下列两点：( 1 ) 全局收敛；( 2 ) 局部快速收 敛，第一点的意思是不营初始点怎么选取算法都能确保求出问题的一个解；第二点的意 思是若一个算法为局部超线性收敛或二次收敛就被视为局部快速收敛。但是，要达到上 述两点屉要有一定条件的。 经过3 0 多年的研究，互补问题在算法方面取得了丰硕成果：对线性互补问题，有 直接方法( 如经典的l e m k e 算法【2 1 ) 和迭代法( 如h a n g a s a r i a n 川法) ：对非线性互补问 题，有不动点法、投影法、同伦法、方程组法( 光滑方程组法、非光滑方程组法) 以及 内点法等。当然，解非线性互补问题的方法也适合线性互补问题。文：4 - 6 是互补问题 的综述性文献，在文献、7 中，作者除对互补问题的主要算法做了简明的介绍外，还总 结了近期在互补问题算法方面的研究工作。 1 2 1 1 转轴类算法 这黾求解线性互辛卜问题的最早的类算法，其中最著名的当数b e m k e 算法。c o t t l e 、 p m l g 和s t o n e 的专著 8 1 中详细描述了其它转轴策略，在m u r t y 的专著i 9 1 中也有很多的描 述。当矩阵肘是半l e 定矩阵时几乎所有的转轴算法都能“处理”l c p ( m ，g ) ，因为这 时的线性g i q 问题与凸二次规划等价。转轴类算法对中小规模的问题是非常有效的，但 u r ty 于t 9 7 8 年证明了这些算法与求解线性规划的单纯形法一样属于指数型算法。对h 维单渊的线性互补问题( 即矩阵肼为半正定时的问题) ，在最坏的情形需要o ( 2 n ) 个转 轴步。 因该类算法特别是l e m k e 算法) 一般比较熟悉而且有很多现成的子程序可以套 用，在此不予介绍。 ：设集台k cr 一非空函数，： r “碧定若对任意的_ y k ，满足 f ( x ) 一，( y ) r ( 工一y ) o 则称f盘集合kf 一是单调的：若对任意的工，y k 存矗：口 0满足 f f ( z ) 一f ( ，) 。( 一一) - 口l l x 一一舻则称f 在集台k 上是强单调的a 、若对任意的x r n都有x 7 尬0 则称矩阵肼是半正定的；若对任意的工r “ 0 育x 。胧譬 0 刚称矩阵m 是酝定的注意这里井没有要求矩阵是对称的。( 专著( 8 】，p a g e 6 5 ) 4 第一章绪论 1 2 1 2 内点法 勺苣法是求解互补问题的另一类非常重要的方法。自从1 9 8 4 年k a r m a r k a r m 1 提出求 解线性姚划问题的内点法( i p m ) 1 以来，内点方法获得了非常迅猛的发展。上个世纪9 0 年代初达到高潮，目前内点算法无论从理论上还是算法实现上都趋于比较成熟。起初， 、们主要研究求解线性规划和二次规划的内点法，由于线性互补问题与线性规划及二次 规划的密切关系，求解互补问题的内点法可以看作是线性规划原一对偶内点法的一个 自然推广。求解线性互补问题的第一个内点法是由k o j i m a 、m 1z u n o 和y o s h is e 1 2 1 提出 的。许多学者为内点法的研究做出了重要的贡献，对此感兴趣的读者可参阅专著f 1 1 及 其中所引文献。 尽管人们研制出了许多性能比较好的内点算法，但目前最为成功的当数原一对偶内 点算法，该方法不但理论比较完善，而且算法的实际性能也很好。下面给出该方法的基 本思想。 一般地，将( 1 1 ) 式的互补问题写成下面的等价形式： f ( 。) - ( 】2 ) x s = 0 x 0 s 0 然后用牛顿法解下面的摄动方程组： ，f j ) = j x i $ = i = l ，2 ，n ( 1 3 ) ( x 0 ，s 0 ) 其中“ 0 为摄动参数。在上述公式里，之所以把两组变量t 5 0 的条件放在括号 内，是因为它们仅在迭代过程中起控制作用，而并不参与方程求解。随着“- 0 ，方程 组( 1 3 ) 的解( x ( ) ，s ( ) ) 描绘出一条通向互补问题的解集的曲线，即所谓的“中心路 径”。然而在实际算法中，对应某个固定的摄动参数值，并不需要精确求解，一般只进 行一个或者几个牛顿步，就调整参数a “1 = d ( 1 一口) ，其中目( o ，1 ) 为缩减系数。 内点法与转轴类算法比较起来具有两个显著的特点：从理论上说，内点法对单调的 互补问题具有多项式复杂界限，即算法的执行时间( 或运算次数) 在最坏的情况下为问 题规模的多项式函数；从算法实现上说，根据观察发现：相对于问题规模的增加幅度来 说其运算时间增加得比较缓慢【l3 1 。基于这个特点，在众多的算法中，内点算法被认为可 1 i p m ：l m e r l o rp o i n tm e t h o d s 茎堡墨三奎堂! ! 圭兰垡兰兰 以用来求解规模非常大的问题。 内点法不仅可以求解线性互补问题，也可以求解非线性互补问题。 1 2 1 3n c p 函数和方程组方法 藉助n c p 函数，可以将式( 1 1 ) 描述的非线性互补问题c j p ( ，) 转化为等价的非 线性方程组。所谓的n c p 函数是这样描述的：设函数妒：r 2 斗r ，若声( 口，b ) = o 等价于 a 2 0 ，6 0 ，a b = 0 ，则称函数是一个n c p 函数。下面是几个常用的n c p 函数： ( a ) 九( 口，6 ) = m i n ( a ，b 1 ( b ) 办w “l ，6 ) = a 2 + b 2 一d b f r ) ( 口，6 ) = 一日6 + ；m i n2 o n + 6 ( d ) ( “，6 ) = ( d - b ) 2 一a l l - b l b i ：b ) 叫f i s c h e r b u r m e i s t e r 函数，在点a = b = o 不可微( 非光滑) ；( c ) 和( d ) 是在 整个矗2 空间可微分( 光滑) 的函数，其中( d ) 来自于m a n g a s a r i a n l l 5 1 。 r 庐( x 。，f ( x ) ) 1 似班。k x o , x ) 3 i j n 4 ) 称中为对应于耷的方程算子，则x + 是非线性互补问题n c p ( f ) 的解的充要条件是x + 是非线性方程组畎x ) = 0 的鳃【1 6 1 。 显然，不同的n c p 函数会得到不同的方程组，若f 和n c p 函数$ 连续可微，则。也 连续可微( 比如，我们可以使用n c p 函数( d ) ) 这种情况下可用经典的n e w t o n 法解非 6 第一章绪论 线性方程绸叫z ) = 0 ，其迭代为 工+ 1 ：= ，一中( j ) - f 中( 工) ，k = o ，j 2 但是，基于可微n c p 函数的方程组有一个缺点：它在退化解x + 处( 互补问题( 1 1 j 的退化解工+ 是指对某些下标f ，有x ，+ = f ( x + ) = o ) 的雅可比矩阵m ( z + ) 是奇异的， 这样牛顿法的局部快速收敛性不再具备。而且，对所有可微的n c p 函数，都存在这种雅 可比矩阵的奇异性。所以在实际计算中，可微的n c p 函数并不受欢迎，一般都采用不可 微的n c p 函数，由此形成了两类方法：非光滑方程组法和光滑化法。 ( 】) 非光滑方程组法 列互补问题的算法来说，直接求解非光滑方程组是近些年数学规划领域非常活跃的 研究方向之。对其最早的研究可追溯到e a v e s ”1 。这种方法是直接解由不可微的n c p 函数得到的方程组中( x ) = 0 一以最小函数( a ) 为例，则o ( x ) = m i n ( x f ( x ) ) ) ，因为该方 程组是非光滑的，雅可比矩阵不存在这时就不能直接使用经典的牛顿法了需要用非 光滑( n o n s m o o t h ) 方程组的理论和算法。该方法求方向时，用方程 v d = 一中( x 1 来代替牛顿方程o ( ) = 一中( ) ，其中v 。是中( ，) 的c l a r k e 1 7 】次微分或b - 次微分剐 的一个元素b 是b o u l i