（运筹学与控制论专业论文）不确定线性互补问题的鲁棒解.pdf

河南大学硕士学位论文 中文摘要 本文研究不确定线性互补闯题，我们采用鲁棒优化技术探讨当输入数据元素为 不精确或不确定，属于某一不确定集的线性互补问题的求解以及鲁棒解的存在性等 性质不确定线性互补问题是数学规划中的一个全新领域，它与互补理论、鲁棒优化 技术以及随机线性互补问题等数学分支紧密相联，并在科技和经济方面有着广泛应 用，是一个十分吸引人的研究课题 互补问题是运筹学与计算数学的一个交叉研究领域作为一类新的数学模型，互 补问题首先是由著名运筹学家、数学规划的创始人g b d 锄t z i g 和他的学生r w c 0 t t l e 于1 9 6 3 年提出，并很快引起了当时运筹学界和应用数学界的广泛关注和浓厚兴趣， 许多人参与了这类问题的研究由于与最优化、变分不等式、平衡问题、对策论、不 动点理论等分支的紧密联系，以及在力学、工程、经济、交通等许多实际部门的广 泛应用，互补问题越来越显示其重要性，这激励了人们对其理论与算法的进一步研 究，出现了2 0 世纪9 0 年代以来的研究高潮在这十余年的时间里，人们不仅改进和丰 富了互补问题的理论研究，而且还提出了多种有效算法 但是，在几乎所有的文献中，互补问题模型，均是以确定性问题出现，即人们认 为输入的数据是精确已知的，等于某一额定值然而，我们知道，在许多实际情况中， 一些数据是很难已知或精确测量的如果我们忽视数据的不精确性或不确定性。就 可能出现约束条件被违背，由额定数据而获得的最优解不再是最优的，甚至是不可 行的情况因此，我们在研究互补问题的同时，应当考虑到输入数据元素的不确定 性 在本文中，我们主要探讨不同不确定集下的线性互补问题目前，在此方面，唯 一可借鉴的研究来源于m a s a 0f u l 【u s i l i m a 和x i a o j l l i lc h e n ( 文献【2 3 】) ，m a s a of u 【u s l l i m a 和x i 删吼c h e n 是以随机规划的角度出发，探讨不确定线性互补问题但是，随机规 划处理不确定问题，具有必须已知不确定数据的随机概率分布，以及它允许解违反 约束条件，从而不能保证某些硬性约束成立等特点鉴于此，我们采用鲁棒优化技 河南大学硕士学位论文 术_ 目前处理不确定问题十分流行的一类技术，进行研究 在第二章中，我们先引入了不确定线性互补问题鲁棒解的概念而且，我们证 明：如果不确定二次规划问题的r o b u 8 tc o 咖由e 印a r t ，这一鲁棒优化问题的最优解存 在矿，z + 舻，并且最优值为o ，那么矿就是不确定线性互补问题的鲁棒解由此，我 们得到了一种求解不确定线性互补问题的方法：将半无限规划模型r o b l l s tc o u n t e r - p a r t 转化为一有限的显示的优化问题然后，令优化问题的最优值为零，从而得到不 确定线性互补问题鲁棒解的充要条件根据以上方法，我们围绕着不确定集为未知 有界的、随机对称分布、简单椭球、以及有限个椭球的交这四种典型形式展开了对 不确定线性互补问题的讨论 首先，第二章的第二节，我们讨论未知有界不确定集下的线性互补问题我们利 用鲁棒理论：无论输入数据元素在不确定集中的真正取值是什么，约束条件必须满 足这一特点，把鲁棒优化模型转化为一二次规划问题，从而得到不确定线性互补问 题鲁棒解的充要条件，即：不确定集u 为未知有界时，z 为不确定线性互补问题的鲁 棒解当且仅当z 满足不等式组( 2 9 ) 并在此基础上，我们通过构造下标集合j 和引入 分块矩阵类里，将其转化为一类线性互补问题，借助于已有的互补理论，我们探讨了 不确定线性互补问题的可行性、鲁棒解的存在性，从而得到了一些新的结果 接下来，在第二章的最后一节，我们讨论当不确定集为随机对称分布时，线性互 补问题的求解与前一节方法的不同之处在于不确定集中含有随机变量，所以，对于 约束条件，应从以往确定性的满足转变为在概率意义下的满足由此，我们引入不确 定线性互补问题a l i n o s tr e l i a b l e 鲁棒解的概念，并得到了z 为a l z r 瑚tr e l i a b l e 鲁棒解的充 要条件 第三章为椭球不确定集下的线性互补问题椭球不确定集在鲁棒优化理论中 具有十分重要的地位在本节中，我们利用著名的l e 眦n 粥半无限规划模型r o b u s t c o u n t e r p 叭转化为一半定规划问题，并且我们推出，如果z 可以扩展为一非线性互补 问题的解，则z 是不确定线性互补问题的鲁棒解 第四章，我们采用了两种不同的鲁棒优化方法来探讨含有椭球交不确定集的线 i i 匝南大学硕士学位论文 性互补问题这两种方法，从一个侧面，体现了鲁棒优化技术的发展方向所有这些 结果都是以前所没有的，本文的结论丰富了不确定互补问题的研究 关键词：不确定线性互补问题；互补问题；鲁棒优化技术；不确定集合；鲁棒解 i i i 河南大学硕士学位论文 a b s t r 西砖 hn l i 8p a p 盱，w e8 t l l d y 珈暇t a i nl i n e a rc ( 如叩l k m 舳土撕锣p r o b l e m 8f b rw h i c ht h e 以t ai s 球) ts p e c 谪e d 旺a c t l yo r 硼胱r t a i n ，柚di ti so n l y 蛔仞mt ob e l o n gt oag i 、，e nu n o e r t a i 移s e t w ea d o mr c i b u 8 乞o p t i 玎1 i 默l t i o nt 戗h 埘董l o 留t od i 8 c u 鹃h o wt o8 0 l v eu n 僦咖 l i n e 甜c ( m l p l l e 加e n t a r i 锣p 】b i l e m s a n dc o n d i t i o i 璩b 量t h e 仞d s t e n o eo fa 加i b l 坶ts 0 1 u t i o na n d o n u n c e r t a i l ll i n e 盯c o m p l e m 鲫七a r t 哆p r o b l e i 璐a r eb 啪d - n e w 丘e l di nn l a t h e m a t i c a l p r o 酗明d n 岛w 比c hh a v l ec h ec o 玎e l a t i o 璐w i t hc o m p k 】n e n t 盯i 锣t h e o 吼r o b u s to p t i - m i z a t i o nt 池l o g y 8 t o c ：h 鹪t i ch 舱趾c o m p l e m e n t a r i t yp r o b k m 8 缸do t h e rm a t h e m a t i c 8 b r a n c h 嘴，1 0 r e o v i 嚣，h a v ew i d e g p r e a da p p h c a 七i o 璐i nt h e8 c i 衄c e 觚dt e 盘n o l o g ya n dt h e e o d n o m i c a ld o m 撕璐，a n d 棚_ e 如l u d ha t t r a c t i v er 铭e a r 6 ht 0 肺铝 t h ec o m p l e i n e i l t a r i 锣p r o b l e mi sai n t 删i i l g 确圉e a r c l ia r 铭b e t w 傥no p e r a t i o i l s r 髓e a r c h 蛐dc o 硼【p u t a t i o n a lm a t h e m a 七i c s a sak n do fn e wm a t l l 咖a 七i c a lm o d e l ，t h e c o m p l 伽n t 甜i t yp r o b l e mw 嬲p r o p e d 丘r s r t l yb yt h er e 玳唧n i e d 叩e r a t i o ns c i e n t i s t ，m a t h - 锄a t i c 8p r o 鲈甜m n i n gf o u n d e rg b d 锄t z i g 眦dl l i ss t u d e n tr w c o t t l e ，i n1 9 6 3 ，a n d v e 巧q u i d 心yc 瓤嘲订丽d 鹤p r e a da t t e n t i o 珊舡m8 t r o n gi n 乞e r e s t 8 丘d mt 伽 1 p o r a lo p e r a t i o 珊 r e a u r c ha ：n da p p h e dm a t h 咖a 土i c s 扣e a 8 ，a i l dm a n yp e o p l ep a r t i c i p a 七ei nt h i 8r e 8 e a r c h f b r h a 们n gc l o 舱r e l a t i o i l sw i t ho p t i i i l i z a t i o n ，u i a t i o n a l i n i e q u a l l i t y je q u i l i b r i u 】mp r o b l e m ，g a m e t h e o 姒嬲w e l la sm 【e dp o i n tt h e o r ya n ds 0o n ，r n o r e o v e r ，p o s s e s s i n gw i d e s p r e a d 印p l i c a t i o 璐i nm 瓤l ya c t u a ld 印a n n l e n t ss u c ha sm e c h a n i c s ，p r o j e c t ，e c o n o m 弘a n dt r a l l s p o r t 加 t i o n ，t h ec o i n p l e l n e n t 龃i t yp r o b l e ms h 响帕dm o r ea n di n o r ei m p o r t a n c e ，a n dd r i v e nf 证t h e r r e s e 缸c ht oi t 8t h e o 巧a n d 劬g o r i t h m ，w h i c hc a u s e dr e s e a r c hu p s u r g es i n c et h e1 9 9 0 s i nt h e 跎m o r et h a nt e ny e a 瑙，p e o p kn o to n l yh a v ei m 娜da n de r u r i c i l e df u n d a m e n t a l r 船e a r c ho ft h ec o m p l e m e n t 撕t yp r o b l e m ，b u ta l s op r o p ( 培e dm a r l ye n e c t i v ea l g o r i t h m s b u t ，i nn e a u r l ya l ll i t e r a t u r e ，c o m p k m e n t a r i t yp r o b l e i 璐，觚ed e t e r m i n i s t i ch l o d e l s w 王l i c ht h ei n p u td a t ai 8u s u a l l ya s s u m e dt ob ek n o w n p r e c i s e l y a n de q u a l st os o m en o m i n a l 、，a l u e h 陀v e r ，w e jk n o w ，i nn u m e r o u ss i t u a t i o i l s ，t h ed a t ai sn o tn e a r l yk n o w no rp r e c i 8 e l y 河南大学硕士学位论文 m 髓8 l 鹏d w ei g n o r et h 8 tt h ed a t ai 8i 刀旧国c to r1 m o e r t a i n ，p o s s i b i l ya p p e a r sn l a tr e s t r a l i n t c o 舡a i l 】妇舢陀、，i o l a t e l i ，趿dt h a tt h eo p t i m a l8 0 l u t i w e0 1 ) 毛a i nb yt h en i 础a 王d a t an o l o n g 甜i so 】蛳瑚l a l ，e v e ni 8 七h ei n f e 删e t h e r e f 0 舱，w k ms 乞u d yc 【m l p l 明n 跚l t a 矗妙p m b l e l s ， w e 加瑚tc c m s i d e r 珈1 0 e r t a j n l 哆0 f 付帕i n p u td a t a i nt h 熏8p a p e t ，w em a i l d yd i 8 c 1 峪sl i n e 解c o m 】p l e ：蚴t 龃i t yp r o b l e m s 诵t hd i & r e n tl m i c e r t a i n t y t 8 a tp r 锫e n t ，i nt h i sd o m a i 屯r e a r c hw 鲢d ho l 灯w em a yp r o 矗tf | r o mo r i g i - n 8 七铭6 0 mm 够n l k i l 8 b j m a 柚dx i a o j t l nc h 吼( t h e1 i t 凹g 妇ef2 3 】) m 够a 0n l k l l s l l i m a a n dx i a o j l mc h e n ，a c c o r d i d gt os t o 啦雒沌i cp r o 旷毗m 劬略，p 】o b ei n t ou l l c e r t a i nl i n e 甜c o l n p i e 】删a r i 哆p r o b i e m 8 h 仞陀v 凹，8 t o c b 8 s t 记牌锄吡n i n gr e q i l i r 铅o n et om a k e 弱s l l m p t i o n sa b o u t 址i ep r o b a b i l i 锣d i 8 t r i b u t i 吼o ft h eu n c e n 8 i nd a t aw h i c hm a yn o tb ea p p 妁 p 畦a t e ，m o r v e r ，a ：u o w 8 m t i o n st o 、，i o l a l 两t h ec o n s t r a i n t 8 赶f e c t e db y 恤c e r t a i n t y ，t l m s c 锄0 t 目i 舢铷啦e 鹤8 a t i s f 砬t i o no fc e r t a j nl l a 盯dc 0 璐t r a i n t 8 ，w h i 6 hi 8r e q u j r e di n8 伽p r a o - t i c a ls e t t i n g 舄i n 啊e wo ft t l i 8 ，w eu 8 er o b 岫s to p t i d z a t i o nt e ( 盘i l o l 0 固，- _ am u l c hp 0 i ) u l 射 l 【i n do ft 洳1 0 j 醪t od e a l 丽t h 眦e r t a i np r o b l e j 璐，t 0i n q i l i r ei n t ou n c e r t a i n 妇c o m p l 锄衄t a r i 够p r o b l e m 8 i nt h es e c o n dc h a p t e r ，w ei n t 加d u c et h en o t i o no fr 0 饥l s t l i l t i o no fu n c e r t a i nh n e a r c o m p l e l 矾m 缸i t yp r o b l e i 瑚，矗r s t l y b 髑i d e s ，w i ep r o v et h a t ，i fr o b u s tc o u n t 唧甜tt ou n c e r t a i nq u a d r a t i cp r o 铲龇i 瑚 1 i n 分一ar o b u s t0 p t i 血z a t i o np 】o b l e m ，h a sao p t i m a ls o l u t i o n ， z 。，z 幸j 汐，a n dt h eo p t i 功_ u 刀】、，a l u ee q u a l 8t oz e r o ，t h e nz 幸i st h er o b u s ts o l u t i o no ft h e m l c e r t a l i nl i i l e a rc o m p l e m e n t a r i t yp r o b l 唧i nt h el i g h to fi t ，w eo b t a i nan e wm e t h o do f s o l v i n gu n c e r t a i nl i l l e a rc o m p l e m e n t a r i t yp r o b l e 妇够：r e p 嘲e i l ts e m i i i l f i n i t ep r o g r m n m i n g m o d e l - r o b u s tc o u 】吐e r p a n ，t oas i n 舀em l i t ea n d 【p l i c i to p t i m i z a t i o np r o b l 锄w h e r 争 a 矗e r ，w el e to p t i m a lv a l u ee q u a lt oz e r o ，a c c o r d i n g 堍g e ts u 伍c i e i l ta n dn e c e s s 踟了c o n d i - t i o 璐o fr 6 b u s ts o l u t i o no fu n c e r t a i nl i n e a rc o m p l e l n e 毗盯i 锣p r o b l e 脚a c c o r d i n gt ot h e a b o v em e t h o d ，w ed i s c u 鹪u n c e r t a i nl i n e a rc o m p l 栩n e n 乞鲥t yp r o b l e r i l sw i t hu n c e r t a i n 乇y s e t sw h i c ha r eu n k n o w n - b u t - b o u n d e du n c f 晚a i n t y r a n d o ms y m m e t r i cu n c e r t a i n t s i m p l e v 河南大学硕士学位论文 e 懿删a l 瑚_ 优代a 泌时a n di n 白嘣蝌砸唧呻细州d 81 1 卫l c e r t 蜘f o 毗匆m c a r 妇 f i 瑙t l y ，i nt h es e c o n dp a 吼t h es e 0 0 n dc ! h a p t e r ，w ep 硒b ei 咖珊【o e r t 咖l i 北a r c 【m l p k 瑚【诚a 曲p r 0 1 曲哪8w i t h 曲m 仞哪b l l t 矗吼m d e d 瑚毗西i y 呵1 陀1 1 8 er 0 1 ) l l s to p t i - m i z a t i 0 i n 蚀u e o 珂：w h a t e 、n 盱t h ea c t i l a l 舶面i z a t i 衄i nu l l c 凹t 昌i i n 匆8 e ti 8 ，0 0 珈北r a i n t sm u s t b es 砒i s 丘e d w er e p 】e s e n 七r ( ，1 负l s to 供i m i z a 七i o n 瑚目i i e lt oaq u 纵h a l 施p 沁秽羽m n i n g ，a n d g e ts l l 伍c i e 】1 ta n di l e = ( ：e 黯a 哆c o n m t i o 璐o fr o b i l s ts o l u t i o no fu n c e r t 山l i n e 缸c o m p l e m e n _ t a l r i t yp r o b l e i 璐：w h e nl l 】删a i l l 姆8 e tu i 8al l | 1 】j m o 帅b u t i b d l 加d e d 珊删a i n t | y ，t h a 上万 i sr o b 璐t8 0 l u t i a no ft h e1 1 1 1 0 e r t 8 j nn l 硷a rc o m p l e m 蜘t 嘶p 加b l e mh o l d si fa n do n l yi fz s a t i s 丘t h ei n e q u 础t yg r o u p ( 2 9 ) o nt h eg r o u n d0 fi t ，碡r eo o n s t r i l c 七s i i b s c r i p ts e tj 锄d 砒r o d u c eb l o c km a t r i ) 【出螂皿，a n dt r 柚8 f o i mt h ei n e q l l a 吐t yg r o u p ( 2 9 ) i l l t oak i n do f n n e a rc o m p l e m e n t 撕锣p 】- o b l e i 璐r 崩y 证g0 nc 0 瑚l p l e m 衄t a 哟rt h e o q0 nh a n d ，w e 出8 c u 韶 f e a s i 砌t yo fu n i c e r t a i nl i n e a rc o 如【p l e m e n t 撕t yp r o b l e m s ，a n de x i 8 t e m 弛o fr o b u 8 t8 0 1 u t i o n ， t h u 8o b t a i n8 0 i n en e wr e s u l t s hl a s tp a r to ft h e8 e 砌d l a p t e r ，u n d e rar a n d o m 町如删c 珈删越n t | y ，w e8 t u 匆 u n e a rc o i n p k m e n t a r i t yp r o b l 伽峪o 咖叩a r e dw i t ht h ef b m e r ，d i 觑煳i nm e t h o d sl i e s i nt h eu n c e r t 撕n t ys e ti n c l u d i n gr a n i d o m 、，a u r i a b l 昭，t h e r e f o r e ，i tm a ：k 陷n 舱t op a s s 丘o m t h ed e t e r m i n i s t i cr e q u i r e m e n tt oi t 8p r 龇i h s t i cv e r s i o n 。a c c o r d i n g 坟w ei n t r o d u c ec o n c e p t i o no fa h n o s tr e l i a b l er o b l l s ts o l u t i o n ，a n do b t a i ns u m c i e n ta n dn e o e s s a r yc o n d i t i o n s o fa l m o s tr e l i a b l er o b u s ts o l u t i o n t h et h i r dc h 印t e ri sl i n e 盯c o m p l e m e n t 撕t yp r o b l e n 玛丽t h8 i l p l ee 1 1 i p s o i d a lu n c e r t a i n t y i nr o b u s to p t i m i z a t i o nt h e o r _ y ，t h es i m p l ee 1 1 i p s o i d a lu n c e r t a i n t yp o s s e s s e si i n p o r t a n ts t a t l l s i nt h i sc h 印t e r ，w eu s ef 轴1 1 ss - l e m m a ，r e p r e s e n ts e m i i m i t ep r o g r a m m i n g m o d e lt oas e n l i d e 缸i t ep r o g r a l i n i n gp r o b l 咖，a n d r es h o l wt h a ti fzc a nb ee x t e n d e d t oas 0 1 u t i o no fs o m 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 i e m ，t h e nzi sr o b u s ts o l u t i o no f u n c e r t a i nl 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 i nt h ef o u r t hc h a p t e r ，w ea d o p tt 帆rk i n d so fd i f r e r e n tm e t h o do fr o b u s to p t i m i z a t i o n 河南大学硕士学位论文 t o 饱融i n t ot h el i m a ro o m p l e m e n t a r i t yp r o b l e mi n c l u d i l l gj n t e 鹅e c t i o n - 畦e l h p s o i d 8 l 删a i n t y t h e s e t w om e t h o d s ，h d mt h eo t h e rh a 皿d ，m a n i l b s td e v e k ) p 】n e n td i r e c t i o n so f r o b u 8 to p t i n l i z a t i o nt e c h i l o l o 粤阢a no ft h e r 姻u l t 8a | - en o tk 1 1 0 帆p r e 访o i l s l y c o n c l t l 8 i 鲫s w ed b t a i nh a se n r i c h e d 1 0 e r t 越n 锄p l e 砒n t a r i 锣p 】b l e 螂 k e l y o r d 戤u n c e r t a i nl i n 铋r 瑚l p l e m e i i t a r i t yp “b l e 虹培；c o 瑚【p l 锄e n l 隐r i t y p r o b l e n 塔；r 0 1 ) u 8 to p t i m i z a t i o nt e c h 枷) l o 斛；u 功弛r t a i n 锣舱t ；r o b u s t l u t i o n i 关于学位论文独立完成和内容斜蕞薛声咀 本人向河南大学提出硕士学位申请。本人郑重声孵：厩至交的学位论文是 本人在导师的指导下独立完成的，对所研究的课题有新解见解。据我所知，除 文中特别加以说明、标注和致谢的地方外，论文中不包轻其他人已经发袁或撰 写过的研究成果，也不包括其他人为获得任何苏育。辩研机构的擘住或证书而 段保存、汇编学位论文( 纸质文奉和屯子文奉) 。 ( 涉及保密内容的学位论文在解密后适用本授权书 学位获得者( 学住论文作者) 鍪名：堡兰盎 2 咎。群6 月f 臣 学住论文指导教师签名：羔盥銎 20 9 乒年f 月fb 第一章绪论 1 1互补问题 互补问题是运筹学与计算数学的一个交叉研究领域，他与非线性规划、极大极 小、对策论、不动点理论等分支有紧密联系，在力学、工程、经济、交通等许多实际 部门有广泛的应用这使得互补问题成为数学规划中的一个十分热门的研究课题 互补问题首先是由著名运筹学家、数学规划的创始人g b d a n t z i g 和他的学生r w c 0 t t l e 于1 9 6 3 年提出次年，c 0 砌e 在他的博士论文f 2 5 】中第一次提出求解它的非线 性规划算法，并且指出：线性规划与二次规划是线性互补问题的特例线性互补问题 还包括了双矩阵对策问题、最优停止问题和市场均衡问题等非线性互补问题、混 合互补问题和隐互补问题也包括了许多的数学问题，如一般非线性规划的k k t 条 件就是混合互补问题的一特例互补问题是从线性规划与非线性规划的推广而形成 的，所以，其算法研究与可解性研究一样，受到了研究者的重视，前者主要建立有效 的求解方法及相应的算法理论分析：后者则主要研究解的存在性、唯一性、稳定性 与灵敏性分析，以及互补问题与其它数学问题的联系等经过2 0 余年的努力，互补问 题己取得了比较丰硕的成果 互补问题是指这样的问题，它包括的两组决策变量之问满足一种“互补关系” 线性互补问题 令m 舻跏是一n n 实矩阵，g 舻是一佗维向量，线性互补问题是：寻求 解z 舻，满足 z 0 ，m z + 口0 ，z t ( m z + g ) = 0 ( 1 1 ) 线性互补问题被记为l c p ( m ，垡) 如引入向量! ，舻，掣= m z + g ，则变量砍与现满足 条件兢o ，蛳o ，甄们= o ，i = 1 ，2 ，n 这表明了两组变量忍与玑满足互补关系 1 河南大学硕士学位论文 线性互补问题的基本来源是线性规划和二次规划考虑二次规划问题( q p ) ： m 兢= 如+ 妻，伽 ( 1 2 ) 8 t a 茹b ，霉o 、 其中q 舻期为对称矩阵，a 妒跏如q = o ，二次规划即退化为一线性规划 设$ 是二次规划问题( q p ) 的一局部最优解，根据k 壮u 如k 1 l b n m l d 姘最优性定理， 存在l a 铲蛐g e 乘子矢量，满足k k - t 条件： 忙：茳三苌蔷= 划 n 3 ， i 移= 一6 + a z o ，妙o ，r t ，= o 如q 是半正定矩阵，则q ( z ) 是凸函数，条件( 1 3 ) 也是( q p ) 的全局最优解的充分条 件：定义 。 m ：= ( 兰一) ，g ：= ( ，三) c 1 4 ， 条件( 1 。3 ) 即转化为一线性互补问题三卯( m ，尽) ，其中包含的矩阵m 是一双对称矩阵 所以任意一个二次规划的k - k - t 条件等价于一线性互补问题，而且凸二次规划与线 性规划等价于线性互补问题 非线性互补问题 令f ：舻一彤是由彤到舻的一映射，相应的非线性互补问题是：求向量z 俨，满足 z o ，f ( z ) 0 ，z t f ( z ) = o ( 1 5 ) 非线性互补问题被记为c p ( f ) 混合非线性互补问题 令g ：舻- 形z 斗舻- 和日：形z 俨。形：是两个映射，混合非线性互补 问题是：求u 舻- ，钉舻。，满足 翁芸啦帅慨一 6 ， i 口o ，丑( ，口) o ，口1 月( u ，秒) = o 河南大学硕士学位论文 m和 n f 1 7 ) s t 魏= 1 ， z2o 。 s t 珊= 1 ， o 、7 m ：= ( 三二：) ，口：= 一( ：) c 1 8 ， 乏三；f二二si乏ji二二。 c 1 9 ， 1 ( ：) tf m ( ：) + g ：。 l 印 河南大学硕士学位论文 “n 勰h 均衡 ，其中 = 杀，= 杀等和秽一2 丽 双矩阵对策可以推广为个局中人的多矩阵对策，多矩阵对策的“h 均衡? 问题 也可以转化为线性互补问题 v u 数学物理中许多障碍问题可以导致为线性互补问题障碍问题的研究目的之一 是确立“自由边界 ，互补问题中的互补条件可密切地关连到自由边界文献佟5 】中 对于障碍b r a t u 问题、障碍v o nk 锄孤问题以及非线性弹性梁问题中某些有关问题 已通过互补问题来研究另外，力学结构中的接触问题、最优停止问题和市场均衡问 题等均可转化为线性互补问题 当然，非线性互补问题也有许多应用，如经济方面的具有生产和投资的经济均 衡问题、一般的经济价格均衡问题；交通方面的静态交通流均衡问题；以及现在管 理、运输方面十分热门的供应链问题都可以通过转化为非线性互补问题来研究 互补问题在某些情况下也可以等价于其他的数学问题，如方程组和最优化问题 等在转化为方程组时，最常用的手段就是利用n c p 函数 随着互补问题越来越显示其重要性，人们不断提出并改进了多种有效算法投 影法是求解互补问题的一类基本而又重要的计算方法，它源于g o 地t e i n 和l 嘶t h 卜 p 0 l y a k 的求解凸约束优化问题的投影梯度法，包括著名的外梯度法、逐点逼近法、 矩阵分裂法等特别是近年出现的几个加速技术，涌现出了s o l o d o 卜s 嘲t e r 的逐点逼 近n e w t o n 法，y a m a s h i t a f u k u s l l i m a 的一步逐点逼近法，x i u - z h 锄g 的外梯度加速法等 优秀的方法对于线性互补问题，内点法也不失为一个好的算法，它的基本思想是把 互补问题转化为一个与之等价的非负约束方程组，然后用毗0 n 类型法求解常用 的内点法有：路径跟踪法、势缩减法、预测一校正法、不可行内点法等还有随着人 们对非光滑研究的不断深入，迅速发展的非光滑牛顿法，以及具有稳定性和有效性 的光滑牛顿法均是互补问题的常用方法 4 ， 河南大学硕士学位论文 1 2 鲁棒优化技术及应用 在经典的优化模型中，人们通常认为输入的数据是精确已知的，等于某一额定 值，但是，在许多情况下，部分或全部数据，是不精确或不确定的例如：数据n 在z 的 值确定之前是未知的，像z 表示产品，而。表示未来的需求或市场价格；或是数据是很 难测量计算的，像遥远地方的压强、气温如果我们忽视数据对于额定值的偏离或 扰动，就可能出现约束条件被违背，由额定数据而获得的最优解不再是最优的，甚至 是严重不可行的情况因此，人们自然就产生了一种需求，设计一些求解的方法，使 其对数据的不确定性是免疫的，即它们是鲁棒的 为了阐明鲁棒性在实际应用中的重要性，我们引用b e n _ 呻n e 旧1 i r o v 幽在2 0 0 0 年 的线性规划问题中所举出的例子该例子来自于著名的n e t l m1 i b r a 够这是个拥 有1 0 0 0 个变量和4 l o 个约束条件的线性规划问题第3 7 2 个约束条件为： n 三 一1 5 7 9 0 8 l z 8 2 6 8 5 9 8 8 1 9 z 舵7 一1 8 8 7 8 9 z 眈8 1 3 6 2 4 l 死啪一1 5 2 6 0 4 鸵8 3 0 o 0 3 1 8 8 3 2 8 4 9 2 8 7 2 5 5 5 5 2 8 5 0 1 0 7 9 2 0 6 5 2 8 5 1 一o 1 9 d ( 8 5 2 2 7 5 7 1 7 6 茁8 5 3 1 2 2 9 0 8 3 2 2 8 5 4 + 7 1 7 5 6 2 2 5 缸b 5 5 0 0 5 7 8 6 5 z 黜一3 7 8 5 4 1 仡8 5 7 7 8 3 0 6 6 l 茁8 5 8 一1 2 2 1 6 3 0 5 5 2 8 5 9 6 4 6 6 0 9 嬲6 0 o 4 8 3 7 l z 懿1 0 6 1 5 2 6 4 2 8 6 2 1 3 5 3 7 8 3 2 8 6 3 8 4 6 4 4 2 5 彻8 6 4 一1 2 2 4 5 9 0 4 5 2 8 6 5 4 3 1 5 5 9 3 z 蝴一1 7 1 2 5 9 2 z 8 7 0 0 4 0 1 5 9 7 2 8 7 1 + z 8 8 0 一0 9 4 6 0 4 9 2 8 嬲一0 9 4 6 0 4 9 跏1 6 6 三2 3 3 8 7 4 0 5 ， 求得的解如下： z 2 6 = 2 5 5 6 1 1 2 7 8 7 1 8 1 1 0 8z 2 7 = 6 2 4 0 4 8 8 9 1 2 2 3 2 1 0 0 z ；2 853 6 2 4 6 1 3 3 2 4 0 9 8 9 6 1z ；2 95 1 8 2 0 2 0 5 0 6 5 2 8 3 2 5 9 ( 1 1 0 ) z 缸9 = 1 7 4 3 9 7 0 3 8 9 5 7 3 0 3 7z 7 0 = 1 4 2 5 0 0 0 1 7 6 6 8 0 9 0 0 z 7 1 = 2 5 9 1 0 0 0 7 3 1 6 9 2 1 7 8z = 1 0 4 9 5 8 3 1 9 9 2 7 4 1 3 9 在机器的精确范围中，以上的最优解满足上述不等式观察( 伤7 2 ) 中的大部分系数， 我们有理山推断这些系数表示着某一技术设计或过程，因此他们很难是精确的假 5 河南大学硕士学位论文 设额定值n 为真实值石的o 1 的近似，即叼h 弓= ( 1 + 白) 叼白在卜。舢1 ，o 脚1 】独立 均匀分布可得( 动t 矿一b 一1 0 4 9 ，换句话说，用额定数据得到的矿，在【岛7 2 ) 处，约 束的违背是右端值的4 5 0 由此可见，对于不确定问题；解的鲁棒性是至关重要的 敏感性分析和随机规划是解决不确定问题的两种传统方法前者只提供了在额 定数据周围的局部信息；后者则要已知不确定数据的随机概率分布，而这显然是不 合适的随机规划方法常常导致大规模的规划问题，而且他并不能保证某些硬性约 束的成立，这在许多应用中是要求的 目前解决带有不确定集的优化问题，十分流行的方法就是鲁棒优化技术鲁棒 优化，其目的就是求得这样一个解，对于可能出现的所有情况，约束条件均满足，并 且使得最坏情况下的目标函数值最优，在此方向上，踏出第一步的是s o y s t e r 和l 柚 1 9 7 3 年，s 0 咿妇首先考虑了如下的一类含不确定输入数据的线性优化问题： n l n a x c t 叫五巧 6 ，z o ( 1 1 1 ) j 一1 其中z 舻，c 妒，6 冗m ，彳胛忭，且矩阵的每一列向量五属于凸集玛他提出 了一个踟r 8 忱a 8 e 的模型，并且指出这个问题等价于 m 孤 c t 叫盈厶，z o ) ( 1 1 2 ) 其中页中每个元素奶满足= s u 黝，确( 硒) 这个模型给出了确保最坏情况出现时 候的解，但是过分保守鲁棒优化领域，重要的发展分别由b e n 附和n e m i r o v s k i 【5 ，6 ， 7 ，8 ，1 0 ，1 1 ，1 2 】，d b e r t i m 嬲【1 7 ，1 8 】，e 1 g h a o u i 和l e b r e t 【2 9 ，3 0 】推动 考虑如下不确定优化问题模型： (p)miilc t 茁 s t f ( z ，e ) k ( 1 1 3 ) z x 其中，z 舻为决策变量，e 为不确定输入数据元素 6 河南大学硕士学位论文 确定一个不确定元素集合uc 只咿，构造优化问题： ( p ) m i nc t z s t f ( z ，c ) j ( 矽 ( 1 1 4 ) z x 我们称( p ) 的可行解为不确定优化问题( p ) 的鲁棒可行解，称( p ) 的最优解( 最 优值) 为不确定优化问题( p ) 的鲁棒最优解( 鲁棒最优值) 问题( p ) 就称为问题( p ) 的 r o b 璐tc o l i n t e r p a r t ，记为( 冗c ) 。 鲁棒优化问题须满足以下特点： 仅知道不确定元素的取值范围：移 无论( u 真正的取值是什么，约束f ( z ，( ) k 必须满足 t h er o b 璐tc o u n t e 印a r t 必须在计算上容易实现 由上可知，不确定优化问题( p ) 的d 0 b u s tc o u n t e r p a r t 是一个半无限规划问题我们 知道，半无限规划问题，即使是凸的，在数值上也不能被有效的求解，特别是无法利 用一些先进的算法，如内点方法来解决因此，应用鲁棒优化技术，其首要的任务就 是把一般形