（应用数学专业论文）互补问题的算法研究.pdf

摘要 摘要 受：静弼越是一裳非常重癸的优化闽题，窀在工裰，经济与交通平衡等领堞有广 泛的应膈因诧，对互补阎题游法瓣磷究其育霞荽意义本论寒着重磷究了韪粪互褥 问题的几种非内点算法，并详细分析了所给算法的收敛性 全文共分瞪章，麓一章穰述了戛羚滔题瓣备稃形式及其巍工程、经济翻运筹掌 中的成用，同时分类介绍了求解互补问题的几种主裂方法最后，介绍了本文的内容 安簿， 第二章给出了一种求解p o 线性互补问题的一步非内点连续方法，证明了算法 奚骞全两线瞧渡敛瞧装嚣蕺二次毅敛槎+ 渡方法在每次逮裁辩镁需要求磐一个线链 方稷组，执行次步长搜索 第三章曹先霹p 驴蠡数嚣线性曩耠薅黧烩窭了耱羲髂校燕j # 内点算法，该冀 法遗代产生的序列疑c a u c h y 列，它全局线糗襁局部= 次收敛子互补嘲题的解；其次 黠擎灏l # 线性互羚润题绘戡了一零孛步裴起藤连续宠法藏方法是部二次收敛往的 建立不需甍柱解处满足严格匿补条件；最屠，对非辘健互 间题给啦了一种序列二 次规划方法，弗详绑矜辑了算法豹收敛性。 第四章讨论了类广义夏补闯繇静一释簿光滑方程缓鞯法，详魏分橱了簿法懿 全蛹线性收敛性和局部超线性、局郏= 次收敛性 关键词：线性甄补问题非线性互补问避广义互补问题 a b s t r a c t a b s t r a c t c o m p l e m e n t a r i t yp r o b l e m s a r ea n i m p o r t a n t b r a n c hi nt h em a t h e m a t i c a l p r o g r a m m i n gf i e l d w h i c hf i n dw i d ea p p l i c a t i o n si nm a n y f i e l d ss u c h8 se n g i n e e r i n g , e c o n o m i c sa n dt r a f f i c e q u i l i b r i u mp r o b l e m t h e r e f o r e 。i ti ss i g n i f i c a n t t os t u d yt h e a l g o r i t h m s f o rs o l v i n gc o m p l e m e n t a r i t y p r o b l e m s t h et h e s i s m a i n l yd e a l s w i t ht h es t u d i e so fn o n - i n t e r i o r a l g o r i t h m s f o r c o m p l e m e n t a r i t yp r o b l e m s ，a n da n a l y z e s t h e i rc o n v e r g e n c e p r o p e r t i e s t h ew h o l et h e s i sc o n s i s t so f f o 撖c h a p t e r s d i f f e r e n t f o r m u l a t i o n so f c o m p l e m e n t a r i t yp r o b l e m sa r e i n t r o d u c e di n c h a p t e ro n e , a l o n gw i t h t h e i rv a r i o u s a p p l i c a t i o n si ne n g i n e e r i n g ，e c o n o m i c sa n do p e r a t i o n sr e s e a r c l l ，t h e n ，s o m ee x i s t i n g a 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 a r ed e s c r i b e d + f i n a l l y , t h eo r g a n i z a t i o no f t h i s t h e s i si so f l b r e db r i e f l y i n c h a p t e rt w o ，ao n e s t e p n o n i n t e r i o r p o i n tc o n t i n u a t i o na l g o r i t h m s f o r p 0 一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 i s g i v e n ，w l l i e h s o l v e so n e s y s t e m o fi i n 宴a r e q u a t i o n sa n d c a r r i e so u to n l yo n el i n es e a r c ha te a c hi t e r t t t i o n f u r t h e r m o r e ，i ti ss h o w n t h a tt h ep r o p o s e da l g o r i t h mc o n v e r g e st ot h es o l u t i o no fc o m p l c m e n m r i t yp r o b l e m g l o b a l l yl i n e a r l ya n dl o c a l l yq u a d r a t i c a l l y i nc h a p t e rn l r e e a p r e d i c t o r - c o r r e p t o ri n f e a s i b l e n o n i n t e r i o rp o i n tc o n t i n u a t i o n a l g o r i t h mf o rp 0 - f u n c t i o nn o n l i n e a rc o m p t e m e n t a r i t yp r o b l e mi sp r e s e n t e df i r s t l y t h e i t e r a t i v es e q u e n c e sg e n e r a t e db yt h ea l g o r i t h m ，w h i c h a r e c a u c h ys e q u e n c e s ，a r es h o w n t oc o n v e r g et ot h es o l u t i o no fc o m p l e m e n t a r i t yp r o b l e t hg l o b a ! l yl i n e a r l ya n dl o c a l l y q u a d r a t i c a l l y s e c o n d l y , w ep r e s e n t a n i n f e a s i b l e o n e - s t e p n o n - i n t e r i o r p o i n t c o n t i n u a t i o n a l g o r i t h m f o rm o n o t o n en 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 ，w h i c h c o n v e r g e st ot h es o l u t i o no fc o m p l e m e n t a r i t yp r o b l e mw i t h o u tt h ea s s u m p t i o no fs t d t c o m p l e m e n t a r i t ya t t h es o l u t i o n f i n a l l y , as e q u e n t i a lq u a d r a t i cm e t h o df o rs o l v i n g c o m p l e m e n t a r i t yp r o b l e mi sg i v e n b a s e do nar e f o r m a t i o no ft h ec o m p l e m e n t a r i t y p r o b l e m a sam i n i m i z a t i o n p r o b l e m w i mn o n n e g a t i v ec o n s t r a i n t s u n d e r p r o p e r c o n d i t i o n s ，t h eg l o b a lc o n v e r g e n c e 。l o c a ls u p g r - i n e a ra n dl o c a lq u a d r a t i cc o n v e r g e n ，| c e a a r ep r o v e dr e s p e c t i v e l y i n c h a p t e rf o u r , a n o n - s m o o t h e q u a t i o n sa l g o r i t h m f o ra g e n e r a l i z e d c o m p i e m e n t a r i t yp r o b l e m i sd i s c u s s e d ，w h o s e g l o b a lc o n v e r g e n c e ，l o c a ls u p e r l i n e a ra n d l o c a lq u a d r a t i cc o n v e r g e n c e sa r cp r o v e dr e s p e c t i v e l y k e y w o r d s ：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 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 g e n e r a lc o m p l e m e n t a r i t yp r o b l e m 戗额性声溺 本人声明骈呈交的论文燕我个人夜导师捂释下进行的研究工作及取得的研究 成果尽我所知，除了文中特别加以标泣和致谢中所罗列的内容以外，论文中不包 含其他人已经笈表或撰髯过的礤究成聚：也不镪含为获褥西安电子科技大学袋其 它教育机构的学位或证档而使用过的材料，与我一向：七侄的同志对本研究所做的任 髂贡献均已在论文中徽了瞬礁戆说密并袭示了谢意 本人签名： 毒永堂 f 期： 望婴盘 关于论文使用授权的说瞬 本人完全了解西安电子科披大学有关保留和使用学位论文的溉定，即：学校有 权僳塑送交论文的复印件，允许查阅和借阅论文；学校可以公和论文的全部或部 分内容，可以允许采用影印、缩印或其他复铆手段保存论文( 保密的涂文在解密 后遵守此规定) 本大签名：童垂坌一 嚣瓤翊! 导师签名： 窒! l 至堡旦 日期 搽章绪论 第一章缝论 点补问题建一奥璧要的优化问题，它在工程、缎涝和交道平衡等领域都霄广泛 蘸藏薅“一奉章酋庇介绍了幕补网趱跨各辩幂菇移式及英农运筹擎和一鎏量程阏 题中的应用，然后对求解凰孙问题的各种算法作了简单介始，最后一节对本文所 敲工锋散了楚煎酶溉述+ 本文约定r “”氧示全体n x n 阶裳矩阵的袋合，r ”表示套体 雏实向量的檠合， r 量表示登体，l 维实旗向量的集合 1 1 曩朴问蹶凝其推广 线丝戛叠i 回壁( l c p ( m ，q ) ) 是聪补问题中最简单的，也楚应用最广泛、研究最 深入静一类阕蘸，京竣番孬悬运筹警孛一粪嫠零秘簸英一敖影式是 给定m g 采“，g e r ”，球x e r ”，y r “且满足 y ；m x + q ，x 芝0 ，y 0 ，x y = 0( 1 1 ) 线淫蔓棒游蘧懿攘广影彗：寄 ( 1 ) 撼盒线挞亘i b 闷越( m l c p ) ，其一般形式是：给愆a 量r “”，b er “”， c 若霖8 ，d 暑r “”，f r ”程b r ”，寐x 等熹”，y 蠢”，$ 盂“譬满足 匆+ b x + c = 0 + b y + e x + f 一0( 1 2 ) j x 0 , s k x ”s # 0 在( 1 2 ) 战中，游a 为非奇异矩阵，则y * - a 。( b x + c ) ，( 1 2 ) 式町述一涉表述 梵线幢互羚趣踅l c p ( e d a 。b , f - d a 4 砖) 。 2 ) 零星缝蛙嚣整翘薤( 翻羚，其一般形式楚；绘寇剪毫嚣“。，q 嚣“，拓基震， 求x 彤，s r ”且满足 互羚惩趱瓣冀法鹾究 l a 4 x + n s + q = 0 ( 1 - 3 ) i x o , s ( x x 7 s = 0 若n = ，时，( 1 3 ) 式郫为标凇的线髋置补问题 著为非奇异矩陴，贝w l ( 1 3 ) 式等蛰予线蛙互 瓣莲l c p ( 一n 。m , - n 。孽； ( 3 ) 垂鏖线丝垦b 照壁( v l c p ) ，即绘定时拦尺”，碍gr “且、 m ：f 肼4 ，m * 】7 ，哼* 【窜，口* j 7 ，掰峰霞8 ”，q e 霁斗，i 。1 ，2 ，疗，妻棚，。m - ! 惑鬻芒满是 ， 鲋x 譬t 橐避芹毽篆交a g + 譬。j = 逡i 一 ，嚣霹 l 感 j - t 转) 缝焦蹩蹙垂签坦蓬( s d l c p ) ，s ，”，s ? 分裂表黎全然拜嚣黔嬖澍称筵 l j | = 、实对称半正定矩阵以及实对猕正定矩辫的集合；r r ( x ) 表示矩阵爿的迹，对 爿，y s “一逡义两襁石y * 硪并妁弼线性矩薄鬣郡河麟的一觳解式是 衷善。y 毫s 一+ 捷羹瀵跫下瀵最系式 j 7 ；( r ) + 9 ，x k o , y k o , x y 。0( 1 5 其中q s “”，l ：s ”一s ”为线性算子- 抄表示z 芒f ，0 为零矩阵 ( 5 ) 一问石却= 划神。小肌 稼群蠹l o r e n t s 锭，l o r e m s 镪主裁线髓互替溺题翡一般形式惩 求点，y 嵌r ”且满足 y = m 譬+ 窜，z ，y 暑芷，x7 ，= 0 ( 1 6 ) 其中m 芒囊”，孽蠢”，趸秃l o z 味t s 黼。 姆线攮聂饕翊鼹终广副# 线悭瞎形，w 敷褥捌瑟一娄霪要熬嚣耱簿趱一蓥鍪 世基i 回壁c n c p ( f ) ) ，其一般形式疑 绘定嚣激f ：秽- 争r ”；求善咎露嚣，尹g r 4 置辚鼹 煞一章绪论 y = ( x ) ，x 0 ，y 0 ，x r y 一0 显见，当为，仿射函数m x + q 时，( 1 7 ) 式退纯为线髓互补阀趱( 1 1 ) 对菲线性互孙阏题做遴步推广，可褥到望金豆赴回避( m c p ) ，即： j r ：r “一r ”，f r u 哪j ”，“ r u + o o ”，且f 材，求 x e r ”，w r ”，v r ”满足下茂 1厂( 并) 一w + v = 0 x - - ，2o ，w o ( x 一，) 7 w = 0 i u j f o ，v o ，( “一x ) 7 v = 0 当，；0 0 ，“= + 。o 时，混合互 b 问题( 1 8 ) 式就是方程缀苁z ) ；0 ( 1 7 ) 给定函数 ( 1 8 ) 当f = 0 ，甜= 辩，混合互补瓣题( 1 8 ) 式就是黪线性受害 问题( 1 。7 ) 将非线性互补问题以及混合甄补问题做更进一步推广，可得到鸾盆丕笠式 v 1 p ( k ，) ，帮：给定函数f ：r 。- - t , r ”，妒k e r ”，求z 暑r 8 ，且满足 v y k ，( 对7 一力0( 1 9 ) 当k = x l x 怠0 ) 时，( 1 9 ) 式退化为非线性互补问题( 1 7 ) 当k 为矩形联；兀：i “。】，( - o o ，蜥s 4 0 0 ，f = l ，抖) 时，( 1 9 ) 式称为箱约束变分 不等式( b v i 玢，显然姥甜( 1 就是溜含互补鞫题( 1 。8 ) 。 以上撮剿的互补问题都是变最和函数点间的互补关系，将其推广到两个函数 之翔懿互补关系，靼可得到竖鬣盐回罄( g n c p ) ，其一般形式为：给定函数 f ：r ”斗r ”。g ：r ”峥r ”，求x 量r “使得 f ( x ) k ，g ( x ) k 。，( 工) 7 g ( x ) = 0( 1 1 0 ) 其中，足是r ”中一菲空闼凸锥，爱。是世的对偶锥，即： k o = y e r ”i y r x 2 0 , x 芒k ) 以上各种互* b l q 题的推广都是猩h 维实数空间r ”上进行的，还可以将匿补问 题推广到一些籀象空翔上，稠如： 假设曰是一实的b a n a c h 空间，k c 古是一个闭凸锥，露是b 的对偶空间，k 耍 | 蠢蘑救舞法硪突 为定彭l 对镁锥，t ：k - - 2 矿是点到集台熬映射，其中2 矿是b + 的所毒非空子集缀 成的集合。扩展广。义互补问题即是 求x k ，及样7 缸) n k ，侵褥t t t x = 0 ( 。| 1 ) 假设描是实躲h i t b e r t 空阕，k 匕h 是一个闭凸壤，足楚髟的对偶锥，砸 定义以下一类广义互补闯题 求# k ，使餐g ) 毫k ，r 姆) k ，g 国) 7 r g ) 一0 f 1 1 2 ) 1 2 运雾挚单酌置静问禳 互补条件广泛存在乎运筹学中。它主要体现在备类翅划问题激优性条件中 1 2 1 线健囊翻l 骛 线经嫂划嬲般形式戈； m l nc 7 z 5 t a x ；6( 1 1 3 ) x 0 其最优性条件为： f a x = b 一7 y + ，一口= 0( i 1 4 ) l x 0 ，j o , x 7 j = 0 显见，( 1 1 4 ) 式为个混合线性g * b j h - j 题( m l c p ) 1 2 2 = 次藏麓渊 考虑二次烂划； r a i n g t x + 圭x r h x s j - a 。x b ( 1 1 5 ) 工0 不赡求得( 】_ 1 5 ) 的k u h n t u c k e r 条伟为： g h x 兰a 1 + a ，a ”x = 6 + ，五镀瓴x o ，r 0 ( 1 1 6 ) 第一犟绪论 褥定义掰= 瞄诤= 阱w = 盼铸眦删： w m z = g ，律0 ，：0 ，w 7 z = 0 鲑然，( 1 1 7 ) 式为线性互毒卜问题 ( i 1 7 ) 3 互程中的美补阏趱 互补阔簇在工稷等领域中宵广泛的应麓，其中一个重要鲍原嗣楚工程中装统 平鼹豹辍念等同子数学主互章 豹橛褰。文献瑟】申辩藏俸了详鬃豹讨谂，本文绘爨两 个实铡采筒擎豹说秘一下。 4 1 3 。1 兰维接皴翊蘧4 ”3 考虑三缨接触翊题，设接触系鲮幽两令糖体q ，始：组戏，假定小变形、小转 动，两个物髂黝接簸嚣嚣，1 巳静鬻接遴，嚣：，群：，貅；是蠢姆= l ，2 ) 上耱链移活穗瓣q ： 体外法向h 和两个糨嚣囊誊的切向a , b 方向盼分基，为接触嚣之阐的韧始闽陬， 设或= 群：一矫2 + 岛，= 豁：一，螺= 域一西分粼为黪体间惦戤垂方向静籀对接触位 移，露，p ；，藏为t 在墩强b 方随接缴力，设法淘接触穗力为蠢三，剐满避库会麟攘 定德的接魅袋馋霹魍结为； 。 髂翻力裁发作搦力簸理；或= p ：= 蠢，p 。p ：一露，p 。= 癍；露 ( 1 。l s ) 凡髓协谲条悻；m i n d , ，热，一0疆1 9 ) 摩擦条传：( d 。，d b = 一孟( 段，p b ) ( 1 2 0 ) m i n 瓣隅一蠢曩霸= 0 ( 1 2 t ) 豇蠹摩擦系数 蠢予m i n a ，舂 = 0 盆，b o ，a b = 0 ，淡戳( 1 + l 鳓、l ，2 1 ) 势爨罄髻 予一鞫瘦 的互补条件。 互祷辐嚣鹊舞法硪究 1 3 2 交避平豁阍惩 考虑由：侮点集合和弧续集台a 所定义的交通运输网络，交通堵塞问题豹模 戳靛是躅泉预测阚络在稳定狡悉下靛交遗流量 设给定弧线格名的费用怒总流量囱爨，瓣非线幢涵数c 。，其中f 的分爨 为 ，6 a ，记c ( f ) 是巍气( ) 国固稳戒的赞溺岛羹遁常将= 雾点集会划分为 麓点集含0 弱终点集会p 瘫；煮一终熹( 0 一o ) 点辩懿集会渺c 0 d 蹩绘定鹣+ 设 w w 表示出麓点到终点的运输爨需求， 对绘建静替芒w ，令p 。烫连接。一务熹瓣w 豹掰豢潞径熬黎会；令p 为嬲终 中p 。舱嶷合：设如为路径p 户上的流爨：令流爨f 的函数。留) 表示耜成路径的 流量费翔定义援线一爨径关联矩阵厶，英元素敬为： ； ：菪鼹融删弧泡a 嚣然，窃筝之翔溅怒关系f * 矗筝，警缓设链条鼯强p 勰蕊爨厶g ) 铃予绣程p 迓过的弧线的花费。称该模型为加法黧模型；最恁，定义点对w 毒闽纳最小运费 嬲变量r ，。在嗣路径擒逡豹模黧中，用函数d 。( r ) 表示淼鼹w 瓣豹运辕嚣求，游舔 个d 。( r ) 都取为常数，刘臻泼模型为溜定霞拣摸囊，惩一般浆摸裂经常被拣为撵 稍? 需求横夔下面在w a r d r o p 平衡意义上建立交通礴缭的交通堵塞模型 w a r d r o p 乎辫准戴为；每一经镯祝在每一鼹起点一终点阗选取花费最小的潞径。 按照浚准剩，被逸定豹潞径靛藏赞是鞭等豹，蠢凑予豢夸芯赞的鼹径将没套淡鬃。 数学上，该准则可以筒洁的表述为：对予v w e ，p 兑， f ，o ，勺( f ) 一f ，0 ，且f ，辑( 力一f 。) ；0 ( i 2 2 ) 蓑e 蟊d ，c r ) ，v w 妊成立，鬟# 濮嫩上述要浓+ 囊要求零乖佘量辩，平衡条件可以滚述为：对予v we ， r 。0 ，靠一d ，( f ) 2 0 ，藏( 知一以( f ) ) o ；0( 1 2 3 ) 纛然t l 。2 2 ) 霹( 1 。2 3 ) 定义了变爨( 筝，f ) 瓣一个蛰线瞧豆钤阏怒。 第一章绪论 1 4 互补问题的研究现状 对互补问题的研究，一般可分为理论与算法两方面前者丑三要研究其解的存在 性、曦一性、稳定性与灵敏发分析；后者煲l 生要建立其有效豹求解方法及糖盛的 收敛性分析本节主要介绍互补问题算法的研究进展，熟主要成槊为： 1 内赢法 求解互於溺趣的内点法起源于k a r m a r k a r 求解线性与凸二次规划瓣内点泼，它 是这种方法的自然推广内点法的基本思想是： 令y = ，( ，则嚣於闯磁n c p ( f ) e - j 转他为 h ( x , y ) 。l y - ：o ，j j 。x ，y o( 1 ， l 一2 一，2 0 0 2 4 ) 毒中x 。y = ( 苫l y l ，x 2 y 2 ，x 。y 。) 融经证明，当，协) 是p 。函数时，d a c o b i a n 矩阵v h ( x ，y ) 是非奇异的给定 4 ，y 。) 尺黑，内点法的一般迭代格式为 嵇“，y “) = = ，y ) 十五( ，d ：)( 1 。2 5 ) v h ( x k , y ) d = - _ - 7 ( x ，y ) ，d = ( d ：，d ：)( 1 2 6 ) 这最西( 工，y ) 是i t ( x ，y + ) 的一个微小扰动，其目的是调节迭代的收敛遮度； 以 0 为步长，它的选取要便下一次迭代点秘“1 ，y “) 足2 苴价值隧数有一定量 的下爨若在迭霞过程串能够保证y * f ( x ) ，k = 0 , 1 ，则称为可行内点法，否则 称为不可行内点法 凌点法静主要缺錾是：慰予可移海点法，盛须攀先得到勰题的一严格碍劳内 点，不可行内点法虽可以问题的任一内点为初始点，但两者都要求迭代点列严格 大予零，这在缀大程发上影酾了这搴巾方法应攮豹广泛性。关予内点法的最薪研究成 果可见何尚潦博士论文 1 2 1 2 光淆方程法 这类方法就是将稼互补闷题转纯麓一个求艇光滑方程组辔牡) = 0 豹问题，然 l ： 。 兰整塑壁墼篷i 型篓一 焉刹嗣牛顿法二或广义牛顿法求解m a n g a s a r i a r l 在1 9 7 6 年苕先提出炫瓣方程族， 蛳，怩8 1 0 l ( x ) j z ， 国( 石) = ； i | _ ( 1 2 7 ) l 妒( z 其中，( ) 是，( z ) 翡第f 个分量，i = l ，狞，占( 磅：r 甘霆是一个满足疗( o ) ；0 的 严格递增函数由( 1 、2 8 ) 式定义的( d ，6 ) ：r x 显_ r 褥作n c p 函数或势函数( 1 2 8 ) ( 1 ) 将n c p ( f ) 转化为一个 # 光滑方程组m ( ：= l ； i = o ； l 妒( 毛。五( x ) l ( k ，( x ) j ( 3 ) 为了褥到舞法的全羁收敛瞧，用一缍搜索去掇小纯会遁鲢徐值函数， ( 如。( x ) n 归( z ) 4 ) ，选取合适的步长因子 定义1 4 。t 设国：r ”_ r ”是l i p s e h t i z 连续的，d 辔是零豹全体霉微的点 集合，定义巾在工处的b - 次微分为：n ( x ) ； 爿：了缸 ，工d - ，碧墨v 中o ) = 咖在x 处c l a r k e 次微分为：静( 苫) = c o ( o r 参。( ) 这里踟表示榘合的凸包， r 。三器。， 鼢 ( v h e 穴”) 存在 第一章绪论 定义1 4 3 假定m 在xe r ”半光滑，若v h + d ) ，d _ 0 下式成立 h d 一巾( x ；，) = o ( i i d02 ) 则称中在x r ”强半光滑 有关算法及收敛性结果参见文献 t 5 - 1 6 非光滑方程法的一个主要缺点是，方程o ( x ) = 0 中的j a c o b i a n 矩阵v 巾( x ) 难于 计算为此人们研究了下面一类算法 4 磨光方程与非内点法 针对非光滑方程法的缺陷，一种自然的想法是：用一个光滑函数h ( x ，a ) 近 似代替非光滑函数( z ) ，转而求解h ( x ，口) = 0 ，这就是磨光方程法其中t t ( x ，口) 称 为磨光函数，口称为磨光参数，h ( x ，0 ) = ( x ) 这类方法自c h e n h a r k e r m l 于1 9 9 3 年提出来后，吸引了众多学者的注意并取得迅速发展( 【3 】， 1 8 2 1 】) 这类方法的主要优点是它能以任意点作为初始迭代点及充分选取步长，并且 不要求中间的迭代点是内点，因此，它比内点法更具适应性，便于数值计算但是， 为了得到此类方法的全局收敛性和局部收敛速度。通常在一次迭代中需求解两个 线性等式组，执行两次步长搜索。从而，研究每次迭代只需求解一个方程组的一 步非内点连续方法是人们普遍关注的问题【2 l 】 5 优化方法 这类方法主要是将原互补问题转化为一个与之等价的极小化问题m i n 0 ( x ) ，即 在一定的研究范围内其全局极小解同原互补问题的解保持一致目标函数口为互补 问题的价值函数。互补问题中价值函数的构成形式直接关系到它的求解状况，有关 这方面的详细工作见博士论文【2 2 】及综述性文献【2 3 】 理论分析和实际计算表明1 2 4 l 。有时仅用无约束极小化问题去求解互补问题并不 理想，人们转而考虑用带有非负约束的极小化问题去求解互补问题 这类方法的缺点是明显的，由于对一个极小化问题，一般只能得到其稳定点，这 就需要建立一系列正规性条件去保证极小化问题的稳定点是原互补问题的解 ! !兰! ! 塑壁堕簦鲨婴塑 ：， 1 5 鸯奏肉墨瀚安碡 互补问题在运筹学、工程等领域中有着广泛的应用，研究互补问题的求解方 法不但在理论上具有重要价值，两且有广泛的应用前景本文的主要内容安排如下： 第二章给出了一种求解p 。线性互补问题的一步非内点连续方法，该方法在每 次迭代时仅需求解一个线性方程组，执行一次步长搜索，同时证明了算法具有全局 线性收敛性和局部二次收敛性 第三章首先对p 。函数非线性互补问题给出了一种预估校正非内点算法，该算 法迭代产生的序列是c a u c h y 列，它全局线性和局部二次收敛于互补问题的解；其次 对单调非线性互补问题给出了一种一步非内点连续方法，该方法局部二次收敛性的 建立不需要在解处满足严格互补条件：最后对非线性互补问题给出了一种序列二 次规划方法，并详细分析了算法的收敛性 第四章着重讨论了一类广义互补问题的一种非光滑方程组算法；最后对本文 的工作进行了总结，并对今后的工作做了展望 第二章线性互补问题 第二章线性互补问题 线性互补问题是互补问题中最常见、应用最广泛的一类互补问题人们针对单 调线性互补问题设计出了有效的内点算法，它可在多项式时间内求解，k o j i m a 等 人通过例子说明了p o 矩阵线性互补问题是n p 一难问题【2 5 】，即不存在求解p o 矩阵 线性互补问题的多项式时间算法本章对p 0 矩阵线性互补问题给出了一个基于 c h c n h a r k e r - k a n z o w s m a l e 光滑函数的非内点连续算法，该算法在每次迭代时只 需求解一个线性方程组，执行一次步长搜索，在适当的条件下，证明了算法的全 局线性收敛性和局部二次收敛性 本章约定：8 表示向量或矩阵的一范数，r + = 似o ，卢r ) ，表示单位矩 阵，v h 表示日的j a c o b i a n 阵的转置吼= p ( 反) 若以寸0 , 1 i m s u p a i 以 0 ， 则称m 为p 矩阵，而相应的互补问题( 2 1 ) 称为p 矩阵线性互补问题 定义2 1 3 若对任一非零向量x r ”，存在七( 1 s 七s 玎) 使其满足( 缸) 0 j l x 女+ ( 胁) 。0 ，则称m 为p 。矩阵，而相应的互补问题( 2 1 ) 称为po 矩阵线性互 补问题 显见，p 。矩阵互补问题是p 矩阵互补问题和单调线性互补问题的推广 1 2 互於润麓懿算法疆究 2 a 一步毒 内点蕊续篝法 裁蠲c h e n h a r k e r - k a n z o w - s m a l e 竞懑遮数丸婊醇。格+ 鑫一- , ( a - b y + 4 , a i ， 其中( a ，b ，a ) r3 ，对v z 。( z ，j ，) r2 ”，令 一m x - 汹y + p 吖力。院卜1 m x x - y + 力q j ， 州悄m ，v 甜v h ( p , z ) = f v 誓v - 尹iv h 摄然：丸( 口，6 ) 掌0 口2 0 , b o ，a b = 0 ， 屯( 4 ，玉) = o 尝口o ，6 d ，口6 掌2 ， 鞭照，扛) = 0 静：是l c p ( q ，掰) 静辩 从而，求解l c p ( q ，槲) 可通过求够一系列参数化了的光滑方程z ( ) = o 去邂 近非光滑方程h o ( 2 ) = 0 ，直至口趋于零 同文【2 6 】，对l c p ( q ，m ) 定义中心路径 p ：= 秘薅r 2 。：戤( 2 ) = 瓴芦 0 n ( f l ，芦) 游 ：e r 轴：磊乐一y + 窖= o ，l 零。( z ) i i s 露鑫 贝u 中心路径邻域可取为n ( f 1 ) = u n ( f l ，) 对函数谚，0 ，有以下主要性质( 文【2 l ，引理2 - 2 j 。文臻7 引理2 j ) 引理2 2 i ( i ) 九( 口，在任意( 啦b ，) r ( o ，o o ) 连续可微； 2 5 对经意霸，2 。翻口，努若霖2 ，寿| 屯( 口，矗) 一屯( 取b ) l 0 ，有l | 审2 丸0 ，b ) l l v u ； ( ) 对往意( 口，b ，z u ) r 2x r + ，九( 口 6 ) 是强半光滑的，卵： 对任意y e o o ( a + a a ，b + a b ，+ 奶和( 和，z l b ，啼0 肖： 第二黎线缝要替溷趣 丸+ 舡犯+ 幽；6 + g 妨一九b b ) - v 7 ( 如，肋，印一0 ( i | ( 觚4 6 ，印娜) 其中黝怒c l a r k e 意义下酌广义方痢导数。 雾法2 2 ( 步翡国点连续算法) 步骤0 选取吼e ( o ，l 】，口；畦( o ，1 ) i m l , 2 ，任取= 。= 。，y o ) 苣r 2 ”和e 崔( o ，) ，选 取p 0 使褥缸。，y 。) 薅n ( f l ，腧) 鬻露洋o ： 步骤1 蓉斑= o ，则终业，蓦主是l c p 婚嬲) 豹勰，孬刚，转多戮2 ； 步骤2 蓑辔挑；) = 0 ，鬣z “i - z 4 ，转步骥4 ，磷则，令触= 触，每) 垲r “ 是以下方稳组的解： v 丑i ) 7 血。= - h 。( ( 2 2 ) 步骤3 令是；m a x i ，强，掰? ，且满足以下关系式： | | 由。( ：+ 织) 捶( 1 一吼太) 8 蛰鲰0 。郑 ( 2 0 ) 鬻：。+ 攀十以舭； 步骤4 令以= m a x l ，群2 ，球；，；鼓濑跫器下关系戎： # 心1 懒凇0 “) 1 1 s d ( 1 一疗2 双 敝 ( 2 4 ) 鬣越+ l ：= f l a 2 “敝t k 津k + l ，遨回步骤l 。 注：1 ) 由母掰为p o 矩痒，j a c o b i a n 镩v 耳。( z ，对所有z _ g 鬟抽，弘 0 都非奇滓 晃 丈强8 ，定蠖3 。5 】) ，从而螺( 2 ，2 ) 焱确定的牛顿方向怒唯一的； ( 2 ) 劳m 。) = 0 ，期算法幂需要拳解方缎纽( 2 2 ) t 也琴需要律践搜索拯。3 ) ； ( 3 ) 由于初始点满足矿= m x 。+ 窜，跌而y 。m x 。+ 譬 若葬滚迷戎嚣定爻) 类似文 2 7 1 ，绘l c p ( q 。磊”强躺螺下絷传： e l ：对绘定髂 0 编 o ，存在c 0 ，使得对经意露o 段蒜穗硒】，暑| 攥n 蹶棘) ， 有 v h 。( z ) 一貉c 下露诞秘箨法2 ，2 是有定义豹。 萼i 理2 2 。2 设 o ，z 芒n ( ，纯) ，段 锈条件e l 成立，剐以”f 结论成吏； 互补问题的算法研究 ( i ) 若m m ( z ) 0 ，则九旯，a = 口l 因此，步骤3 中的( 2 3 ) 式有限终止其 一二| = i z = m i n 1 ，( 1 一盯) 肛2 ( i i ) y 女，y = m i n 1 ，盯；口2 y + 因此，步骤4 中的( 2 4 ) 式有限终止其中 y + = 吼劲( 2 + ) 证明( i ) 设& r 2 ”由( 2 2 ) x - - 铲l - l ，首先对f n = 1 ，2 ，”) ，五 0 ，1 由 t a y l o r 展式， c u ( z ，+ a a z ) = 九( 毛) + 五v 九( ：，) 7 缸，+ ( a 2 2 ) & z , r v 2 九( - ) & ， = ( 1 一a ) 吮( z ，) + ( 五2 2 ) h ，, r v 2 九( i j z ， 其中，i = z + 彳& ，0 s 爿1 ，利用引理2 2 1 有， i 哆( 毛十尬，) 喀( 1 一五) l 九( 毛) j + ( 2 ) l z ，审2 九( 刁z ，i ( 1 一旯) i 九( z 川+ ( 矛2 ) i i 止，7i i i i v 2 九( 动i i i i z ，i i ( 1 一五) i 九( z ，) l + ( ) 8 z ，i i 2 从而，i i m ，i ( z + 五= ) f i s ( 1 - a ) l l o m ( z ) 0 + ( 五2 u , ) 1 1 a z 8 2 s ( 1 - j t ) i i o “( z ) i i + ( 岔儿i ) c 2i i o “( z ) 1 12 ( 由c i 及( 2 3 ) 式) ( 1 - a ) i i o 。( ：) 1 1 + ( 以) c 2 励。| | m 。( z ) j | = ( 1 一丑) i j 中，。( z ) 1 1 + 刀c 2 f o 。( z ) 1 1 容易证明当五( 1 一口) 肛2 时， ( 1 一, z ) i i 。0 ) i i + 旯2 c 2 卢i i 中m 0 ) i i - 0 ；( i i ) v h ( z + ，菲奇髯 c 2 中骢( i ) 表骥嚣在：辫避是越徽鲍，鞭越审以z 。，群在，迸褥a 9 0 ，耱 退化为 v h ( z ，o ) ) ，( i i ) 表明对所有的v e o h ( z 。0 ) 都非奇异从而在c 2 条件下。 利用文【2 9 】中命磁2 6 ，容易证嘲以下绪论成立 引理2 3 。2 假设c 2 成立。由算法2 2 产生的序列 ，熊) ) 收敛到( z ，o ) ， 敞五嗣前所定义则( = ，o ) 是h ( z ，。0 的解，且有， ( i ) 存在常数q 0 茸珏s a o ，使得对所有的( z , u ) e c c z ) ，v h ( z ，释奇异，辫 鬟1 v h ( z ，n ) 。l 墨c 1 其中，c ( z 。) = ( 毛) ：| | ( z ，) 一：，o ) l i - 0 和盈 0 ，使得对所有的( ：，) n ( z ) ， | ( z ，z ，) ( ：，0 ) 峪岛”h ( z ，) ” 箕中n ( z + ) = ( ：，) ：| | 0 ，) 一( = + ，o ) 1 1 - 岛 ： 定理2 3 。3 设 0 k ，熊) 是由磐法2 2 产生的摩歹且牧敛至( 。，o ) 。象彳譬e 2 成 立，刚m = o ( g ) 证明 由定理2 3 1 ，z 是l c p ( g ，m ) 酌一个解，首先说明当k 充分大时 ：“= = 。+ 地。定义帮( ：+ ，嚣) = ( ：，力瓴力一扛，q ) 1 1 - n 是一常数由定理 2 3 i ，k 0 0 ，”q “( z ) | | _ 0 ，所以tk 叶0 0 ，h & f 卜o 。由引理2 1 1 ，妒在矗2x 心 上强半光滑，园谢栉在r 2xr + 上强半光滑则当k 充分太时， | | 犀m ( = + 越) 一南0 ( z ) 一9 南= ) 触| | 第二章线性互补问题 = 1 1h ( z + a z ，“) 一h ( z ，女) 一v h ( z ， ) 7 ( 址，0 ) j | = i l h ( z k , ) 一h ( z 。+ 暑，f l