随机线性互补问题算法的研究.pdf
《随机线性互补问题算法的研究.pdf》由会员分享,可在线阅读,更多相关《随机线性互补问题算法的研究.pdf(59页珍藏版)》请在淘文阁 - 分享文档赚钱的网站上搜索。
1、西安电子科技大学 硕士学位论文 随机线性互补问题算法的研究 姓名:黄亚魁 申请学位级别:硕士 专业:应用数学 指导教师:刘红卫 20100101 摘要 摘要 互补问题是数学规划中的热点课题之一,在工程和经济等领域有很多的应用。 经过几十年的研究,互补问题的理论和算法都得到了极大的发展而趋于成熟。由 于理论和实际方面的需要,近年来人们开始关注含有随机变量的互补问题,如随 机线性互补问题、随机非线性互补问题和随机变分不等式问题等。这些随机问题 通常不存在满足全部约束条件的解,为了得到合理的解,人们提出了一些再定式 将随机互补问题转化为确定的问题,并从理论上提出了求解算法。随机线性互补 问题是随机互
2、补问题中的基本问题,其理论和算法的研究对随机非线性互补问题 和随机变分不等式问题等有重要的参考意义,因此,我们关注随机线性互补问题。 本文主要研究一类特殊的随机线性互补问题,即离散型随机线性互补问题。 首先,简单介绍了互补问题的理论和算法的发展以及随机线性互补问题的研究现 状,分析了现有模型和算法并提出了需要研究的问题,给出了本文所需的基本概 念。然后,利用著名的F i s c h e r B u r m e i s t e r 函数,将随机线性互补问题转化为半光 滑方程组,并进一步转化为约束极小化问题,给出了约束极小化问题解集有界的 条件。针对约束极小化问题,分别提出了可行半光滑牛顿算法和部
3、分投影牛顿算 法,证明了算法的全局和局部二次收敛性。数值结果表明提出的算法是有效的。 最后,分析了算法的优缺点,总结了本文的工作。 关键词:随机线性互补问题可行半光滑牛顿算法部分投影牛顿算法 A b s t r a c t T h ec o m p l e m e n t a r i t yp r o b l e mi so n eo ft h eh o ts u b j e c t si no p t i m i z a t i o n I th a sa w i d er a n g eo f a p p l i c a t i o n si ne n g i n e e r i n ga
4、 n de c o n o m i c s I nas p a no ff o u rd e c a d e s ,t h e s u b j e c th a sd e v e l o p e di n t oav e r yf r u i t f u ld i s c i p l i n ei nt h ef i e l do fm a t h e m a t i c a l p r o g r a m m i n g T h ed e v e l o p m e n t si n c l u d ear i c hm a t h e m a t i c a lt h e o r ya n
5、 dah o s to f e f f e c t i v es o l u t i o na l g o r i t h m s S i n c es o m ee l e m e n t sm a y i n v o l v eu n c e r t a i nd a t ai nm a n y p r a c t i c a lp r o b l e m s ,t h es t o c h a s t i cv e r s 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 sa n dv a r i a t i o n a I i
6、n e q u a l i t yp r o b l e m sh a v ed r a w nm u c ha t t e n t i o ni nt h er e c e n tl i t e r a t u r e W ec a n n o t g e n e r a l l ye x p e c tt h a tt h e r ee x i s t sav e c t o rs a t i s f y i n ga l lt h ec o n s t r a i n t s T h e r e f o r e a n i m p o r t a n ti s s u ei nt h e
7、s t u d yo fs t o c h a s t i cc o m p l e m e n t a r i t yp r o b l e m sa n ds t o c h a s t i c v a r i a t i o n a li n e q u a l i t yp r o b l e m si st op r e s e n ta na p p r o p r i a t ed e t e r m i n i s t i cf o r m u l a t i o no f t h ec o n s i d e r e dp r o b l e m A n ds e v e r
8、 a lr e f o r m u l a t i o n so ft h e s ep r o b l e m sh a v eb e e n p r e s e n t e dt oo b t a i nr e a s o n a b l es o l u t i o n s T h es t u d yo ft h e o r i e sa n da l g o r i t h m so f s t o c h a s t i cl 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 ( S L C P ) h a si m p o
9、 r t a n tr e f e r e n c ev a l u et o s t o c h a s t i cn 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 sa n ds t o c h a s t i c v a r i a t i o n a li n e q u a l i t y p r o b l e m s S ow ef o c u so nt h eS L C E I nt h i st h e s i s ,w ec o n s i d e rac l a s so fS L C Pw i t
10、hf i n i t e l ym a n yr e a l i z a t i o n s F i r s t l v w ei n t r o d u c e b r i e f l yt h ed e v e l o p m e n t so ft h ec o m p l e m e n t a r i t yp r o b l e m sa n dt h e r e s e a r c hs t a t u so fS L C P T h e n ,w ea n a l y z et h ee x i s t i n g r e f o r m u l a t i o n sa n
11、d a l g o r i t h m so f S L C Pa n dp r e s e n tt h eb a s i cd e f i n i t i o n sa n dc o n c l u s i o n sn e e d e d B ye m p l o y i n gt h e f a m o u sF i s c h e r B u r m e i s t e rf u n c t i o n , w ef o r m u l a t et h ec o n s i d e r e dp r o b l e ma st w o s y s t e m so fs e m i
12、 s m o o t he q u a t i o n sw h i c hw e r ef u r t h e rf o r m u l a t e da sc o n s t r a i n e d m i n i m i z a t i o np r o b l e m s ,r e s p e c t i v e l y W ep r e s e n tt h ec o n d i t i o n sf o rt h es o l u t i o ns e t so f t h ec 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
13、 e m st ob eb o u n d e d T h e nw ep r o p o s eaf e a s i b l e s e m i s m o o t hN e w t o nm e t h o da n dap a r t i a lp r o j e c t e dN e w t o nm e t h o dt os o l v et h e s e c 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 eg l o b a la n dl o c a lq u a d r a t i c c o n
14、 v e r g e n c er e s u l t s o ft h ep r o p o s e da l g o r i t h m sa r ep r o v e du n d e rm i l dc o n d i t i o n s M o r e o v e r , n u m e r i c a l r e s u l t sa r er e p o r t e dt os h o wo u rm e t h o d sa r e p r o m i s i n g F i n a l l y , w ea n a l y z et h e a d v a n t a g e
15、 sa n dd i s a d v a n t a g e so fo u ra l g o r i t h m s K e y w o r d s :s t o c h a s t i cl 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 e a s i b l es e m i s m o o t h N e w t o nm e t h o d p a r t i a lp r o j e c t e dN e w t o nm e t h o d 西安电子科技大学 学位论文独创性( 或创新性) 声明 秉承学校严谨的学风和优良的
16、科学道德,本人声明所呈交的论文是我个人在 导师指导下进行的研究工作及取得的研究成果。尽我所知,除了文中特别加以标 注和致谢中所罗列的内容以外,论文中不包含其他人已经发表或撰写过的研究成 果;也不包含为获得西安电子科技大学或其它教育机构的学位或证书而使用过的 材料。与我一同工作的同志对本研究所做的任何贡献均已在论文中做了明确的说 明并表示了谢意。 申请学位论文与资料若有不实之处,本人承担一切相关责任。 本人签名: 西安电子科技大学 关于论文使用授权的说明 本人完全了解西安电子科技大学有关保留和使用学位论文的规定,即:研究 生在校攻读学位期间论文工作的知识产权单位属西安电子科技大学。学校有权保 留
17、送交论文的复印件,允许查阅和借阅论文;学校可以公布论文的全部或部分内 容,可以允许采用影印、缩印或其它复制手段保存论文。同时本人保证,毕业后 结合学位论文研究课题再撰写的文章一律署名单位仍然为西安电子科技大学。 ( 保密的论文在解密后遵守此规定) 本学位论文属于保密,在年解密后适用本授权书。 日期坐! ! :! :f 丛牡一学 名 名 签 签 人 师 本 导 第一章绪论 第一章绪论 本章首先简单回顾了互补问题的理论和算法的发展。然后,介绍了随机线性 互补问题的研究现状,引出了需要研究的问题,给出了本文所需的基本概念。最 后,简要介绍了本文的工作。 1 1 互补问题 1 9 6 3 年美国的R
18、W C o t t l e 首先提出了互补问题的模型,次年,C o t t l e 在其博 士论文中第一次提出求解互补问题的数学规划算法。互补问题提出以后很快就受 到了研究者的重视,成为数学规划中的热点之一。经过几十年的研究,互补问题 的理论和算法都得到了极大的发展而趋于成熟。 互补问题可以简单的分为线性互补问题和非线性互补问题,经过多年的发展, 互补问题的形式向许多方向进行了推广和延拓。线性互补问题的推广形式有:混 合线性互补问题、竖直线性互补问题、水平线性互补问题、广义竖直线性互补问 题和广义水平线性互补问题等。非线性互补问题的推广形式有:混合非线性互补 问题、隐互补问题、竖直互补问题、半
19、定互补问题等。线性互补问题是互补问题 里的最基本和最重要的问题,有关线性互补问题的一些结论可以相应的推广到其 他的互补问题上,因此,线性互补问题的研究十分重要。C o t t l e 和D a n t z i g 曾指出, 线性规划与二次规划是线性互补问题的特例。线性互补问题还包括双矩阵对策问 题、最优停止问题和市场均衡问题等。一般非线性规划的K K T 条件是混合互补 问题的特例。因此,互补问题在交通、经济、金融和控制等领域有广泛的应用。 有关互补问题可解性、解集的拓扑性质、稳定性、误差界及不同类型互补问题的 算法研究都有了很多结果,国内外出版了一些优秀论文和的专著【1 1 引。下面我们 给
20、出线性和非线性互补问题的标准形式f 1 3 】。 线性互补问题为:寻求解X R ”,满足 X 0 ,M x + q 0 ,X r ( M x + q ) = 0 ,( 1 1 ) 其中M R “”是一个r xn 的实矩阵,q R ”是一个,l 维向量。记该问题为 L C P ( M ,q ) 。 非线性互补问题为:寻求解x R ”,满足 X 0 ,F ( x ) 0 ,x r F ( x ) = 0 ,( 1 - 2 ) 其中F :R ”jR ”是由尺”到R ”的映射。记该问题为C P ( F ) 。当F ( x ) = M x + q 时, 2 随机线性互补问题算法的研究 非线性互补问题退化
21、为线性互补问题L C P ( M ,q ) 。 线性互补问题和非线性互补问题解集的有界性、解的存在性等已经有了较好 的结果,人们提出了很多有效的算法【l 。下面我们简要介绍几种常见算法的主要 思想。 1 投影法 投影法是求解互补问题的一类重要的方法,它基于G o l d s t e i n - L e v i t i n P o l y a k 求解凸约束规划的投影梯度法,包括外梯度法、逐点逼近法、矩阵分裂法等。 给定尺”的一个非空闭凸子集X ,定义一点Y R ”到X 上的投影为 兀x ( y ) - - a r g m i n x - y ,x 椰。 若x = 掣= x R ”,x O )
22、,则兀霹( y ) = m a x ( 0 ,y ) 。以下简记兀成( ) 为 】+ 。 投影法的基本迭代公式为 “= 【一a F ( x ) 】+( 1 3 ) 这里a 0 为步长。为了改进迭代( 1 3 ) 的收敛性结论,K o r p e l e v i c h t 4 1 提出了外梯度 法,其迭代公式为 岳嚣慕没 c 川 协:一a F ( 尹) 】+ u 叫 投影法已有许多其他的形式和改进【1 捌。 2 非光滑牛顿法 非光滑牛顿法把互补问题转化为一个等价的非光滑方程组,然后用广义牛顿 型方法求解该方程组,从而得到互补问题的解。非光滑牛顿法包括:半光滑牛顿 法、正则化牛顿法等。 互补问题
23、转化为非光滑方程组需要借助一类特殊的函数- N C P 函数,下面我 们给出N C P 函数的定义。 定义1 1 函数9 :R 2 一R 称为N C P 函数,若对任意的( 口,b ) R 2 ,妒( 口,b ) = 0 当且仅当口0 ,b 0 ,a b = 0 。 常用的N C P 函数有【1 5 l t p l ( a ,b ) = m i n a ,舛, 仍( 口,6 ) = 口+ 6 一口2 + 6 2 ,( F B 函数【6 】) 仍( 口,6 ) = 【妒2 ( 口,6 ) 】+ ) 2 + a 【( 口6 ) + 】2 , a 0 , 吼( 口,6 ) = Z i p 2 ( a
24、 ,6 ) + ( 1 一九) 【口】+ 【6 】+ ,( 惩罚F B 函数【1 7 1 ) 允( O ,1 ) 。 第一章绪论 3 体( 口,6 ) = ( 仍( 口,6 ) ) 2 + a ( 【口】+ 6 】+ ) 2 ,a 0 , a P 6 ( a ,6 ) = ( 仍( 口,6 ) ) 2 + a ( 动】+ ) 2 ,a 0 , 吣,拦 m 5 , 这里F O ) 为F ( x ) 的第f 个分量,i = l ,押。 然后用一列光滑函数唾。( x ) 去逼近( x ) ,再用牛顿型方法求解光滑化方程组 1 2 随机线性互补问题 由于理论和实际方面的需要,近年来人们开始关注含有随机
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 随机 线性 互补 问题 算法 研究 钻研
限制150内