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

摘要 摘要 互补问题是数学规划中的热点课题之一，在工程和经济等领域有很多的应用。 经过几十年的研究，互补问题的理论和算法都得到了极大的发展而趋于成熟。由 于理论和实际方面的需要，近年来人们开始关注含有随机变量的互补问题，如随 机线性互补问题、随机非线性互补问题和随机变分不等式问题等。这些随机问题 通常不存在满足全部约束条件的解，为了得到合理的解，人们提出了一些再定式 将随机互补问题转化为确定的问题，并从理论上提出了求解算法。随机线性互补 问题是随机互补问题中的基本问题，其理论和算法的研究对随机非线性互补问题 和随机变分不等式问题等有重要的参考意义，因此，我们关注随机线性互补问题。 本文主要研究一类特殊的随机线性互补问题，即离散型随机线性互补问题。 首先，简单介绍了互补问题的理论和算法的发展以及随机线性互补问题的研究现 状，分析了现有模型和算法并提出了需要研究的问题，给出了本文所需的基本概 念。然后，利用著名的f i s c h e r b u r m e i s t e r 函数，将随机线性互补问题转化为半光 滑方程组，并进一步转化为约束极小化问题，给出了约束极小化问题解集有界的 条件。针对约束极小化问题，分别提出了可行半光滑牛顿算法和部分投影牛顿算 法，证明了算法的全局和局部二次收敛性。数值结果表明提出的算法是有效的。 最后，分析了算法的优缺点，总结了本文的工作。 关键词：随机线性互补问题可行半光滑牛顿算法部分投影牛顿算法 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 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 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 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 es 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 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 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 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 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 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 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 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 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 西安电子科技大学 学位论文独创性( 或创新性) 声明 秉承学校严谨的学风和优良的科学道德，本人声明所呈交的论文是我个人在 导师指导下进行的研究工作及取得的研究成果。尽我所知，除了文中特别加以标 注和致谢中所罗列的内容以外，论文中不包含其他人已经发表或撰写过的研究成 果；也不包含为获得西安电子科技大学或其它教育机构的学位或证书而使用过的 材料。与我一同工作的同志对本研究所做的任何贡献均已在论文中做了明确的说 明并表示了谢意。 申请学位论文与资料若有不实之处，本人承担一切相关责任。 本人签名： 西安电子科技大学 关于论文使用授权的说明 本人完全了解西安电子科技大学有关保留和使用学位论文的规定，即：研究 生在校攻读学位期间论文工作的知识产权单位属西安电子科技大学。学校有权保 留送交论文的复印件，允许查阅和借阅论文；学校可以公布论文的全部或部分内 容，可以允许采用影印、缩印或其它复制手段保存论文。同时本人保证，毕业后 结合学位论文研究课题再撰写的文章一律署名单位仍然为西安电子科技大学。 ( 保密的论文在解密后遵守此规定) 本学位论文属于保密，在年解密后适用本授权书。 日期坐! ! ：! ：f 丛牡一学 名 名 签 签 人 师 本 导 第一章绪论 第一章绪论 本章首先简单回顾了互补问题的理论和算法的发展。然后，介绍了随机线性 互补问题的研究现状，引出了需要研究的问题，给出了本文所需的基本概念。最 后，简要介绍了本文的工作。 1 1 互补问题 1 9 6 3 年美国的r w c o t t l e 首先提出了互补问题的模型，次年，c o t t l e 在其博 士论文中第一次提出求解互补问题的数学规划算法。互补问题提出以后很快就受 到了研究者的重视，成为数学规划中的热点之一。经过几十年的研究，互补问题 的理论和算法都得到了极大的发展而趋于成熟。 互补问题可以简单的分为线性互补问题和非线性互补问题，经过多年的发展， 互补问题的形式向许多方向进行了推广和延拓。线性互补问题的推广形式有：混 合线性互补问题、竖直线性互补问题、水平线性互补问题、广义竖直线性互补问 题和广义水平线性互补问题等。非线性互补问题的推广形式有：混合非线性互补 问题、隐互补问题、竖直互补问题、半定互补问题等。线性互补问题是互补问题 里的最基本和最重要的问题，有关线性互补问题的一些结论可以相应的推广到其 他的互补问题上，因此，线性互补问题的研究十分重要。c o t t l e 和d a n t z i g 曾指出， 线性规划与二次规划是线性互补问题的特例。线性互补问题还包括双矩阵对策问 题、最优停止问题和市场均衡问题等。一般非线性规划的k k t 条件是混合互补 问题的特例。因此，互补问题在交通、经济、金融和控制等领域有广泛的应用。 有关互补问题可解性、解集的拓扑性质、稳定性、误差界及不同类型互补问题的 算法研究都有了很多结果，国内外出版了一些优秀论文和的专著【1 1 引。下面我们 给出线性和非线性互补问题的标准形式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 随机线性互补问题算法的研究 非线性互补问题退化为线性互补问题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 ) ，则兀霹( 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 非光滑牛顿法 非光滑牛顿法把互补问题转化为一个等价的非光滑方程组，然后用广义牛顿 型方法求解该方程组，从而得到互补问题的解。非光滑牛顿法包括：半光滑牛顿 法、正则化牛顿法等。 互补问题转化为非光滑方程组需要借助一类特殊的函数- 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 ，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 随机线性互补问题 由于理论和实际方面的需要，近年来人们开始关注含有随机变量的互补问题。 设( q ，芦，p ) 为概率空间，q gr ”。假设概率分布7 9 已知，随机线性互补问题【1 蛇3 】 ( s l c p ) 为：寻求x r ”，满足 m ( o g ) x + g ( ) 0 ，x 0 ，x 。( m ( ) x + g ( ) ) = 0 ，q ，( 1 6 ) 其中m 细) r “一，q ( o ) r ”为随机矩阵和随机向量。若q 只有一个点，( 1 6 ) 退化 为标准的线性互补问题( 1 1 ) 。 通常不存在z 使得对所有的q ，( 1 6 ) 都成立。为了得到( 1 6 ) 的合理的解， 人们提出了几种再定式。其中有三种比较重要：g f i r k a n 、o z g e 和r o b i n s o n 1 9 1 提 出的求解随机变分不等式的期望值模型( e v ) 。c h e n 和f u k u s h i m a t 2 0 1 提出的求解 s l c p 的期望残数极小化模型( e r m ) 。l i n 和f u k u s h i m a 2 1 】提出的求解随机非线 性互补问题的带有均衡约束的随机规划模型( s m p e c ) 。下面我们简单介绍这三 种再定式。 1 期望值模型【1 9 1 ( e v ) 4 随机线性互补问题算法的研究 令f ( x ，) = m 徊) x + g ) ，厨= e m ( c o ) 】，虿= j 8 i k ) 】，b 为期望。e v 为： 寻求解x r ”，满足 f ( x ) = i e i 【f ( x ，c o ) 】= 岔+ 虿0 ，x 0 ，x 1 f ( x ) = 0 。 ( 1 - 7 ) 2 期望残数极小化模型( e r m ) e r m 为：寻求解x 殿，满足 m 。艘i n f ( x ) - e 【i l ( ，) 1 1 2 】，( 1 - 8 ) 其中：r ”xq j r ”为 。国，：，妒“m x g ”l ，一 。 。9 ， l 妒( ( 4 ( 国) x + g ( 国) ) 。，毛) j 这里舻：r 2 斗r 是n c p 函数。 3 带有均衡约束的随机规划模型【2 l 】( s m p e c ) 引入松驰变量z ( c o ) 0 ，s m p e c 为： r a i nn d 7z ) s t x 0 ，f ( x ，) + z ( c o ) 0 ， ( 1 一l o ) x 7 ( f ( x ，) + z ( ) ) = 0 ， z ( ) 0 ，q ，a e ， 其中a e 表示几乎处处成立，d 是分量为正的权重向量。 有关s l c p 解的存在性、解集的有界性等已经有了一些结果r 在对s l c p 解 集性质的分析中，随机r 矩阵是十分重要的概念，我们给出其定义。 定义1 2 【冽称矩阵肘( ) 为随机r 矩阵，若 x 0 ，m ( c o ) x 0 ，x r m ( c o ) x = 0 ，a e = ，x = 0 。 f a n g ，c h e n 和f u k u s h i m a l 2 2 】研究了s l c p 的e r m 模型解集的性质。证明了 m ( ) 为随机r 矩阵是e r m 模型解集非空有界的充分必要条件。给出了m ( ) 为随 机风矩阵的s l c p 的局部和全局误差界。c h e r t ，z h a n g 和f u k u s h i m a l 2 3 1 研究了期 望矩阵为半正定矩阵的s l c p ，即单调s l c p 的解的性质。证明了若e v 模型的解 集非空有界则e r m 模型的解集非空有界。l i n g 掣2 4 】研究了由仍定义的e r m 模 型的s c l 特性。l u o 和l i n 2 5 j 利用正则化间隙函数把e r m 推广到随机变分不等式， 并给出了一种拟m o n t ec a r l o 方法。a g d e p p 如y a m a s h i t a 和f u k u s h i m a l 2 6 利用正则 化间隙函数和d 间隙函数，研究了随机仿射变分不等式的e r m 模型，他们证明 第一章绪论 5 了所得模型的凸性，并将其运用到交通均衡问题。随机互补问题近年来已经成为 国际优化界最为活跃的研究课题之一1 2 7 。4 】。l i n 和f u k u s h i m a t 2 8 1 有关随机变分不等 式和随机互补问题的综述文章及其中的参考文献详细介绍了该课题的研究现状。 1 3 问题提出 z h o u 和c a c c e t t a 2 7 1 研究了只包含有限个点的离散型s l c p 。令 q = c o l ，咤9 o 9 ) ，问题为：寻求解x r ”，满足 x 0 ，f ( x ，q ) = m ( q 弦+ g ( 皑) 0 ，x r f ( x ，q ) = 0 ， 假设岛= p q q ) 0 ， 其中 i = l ，2 ，m ，m 1 。( 1 1 1 ) f ，纯( ( 砝+ 孙葺) 1 以功荨k 砝纛吒) ji 吼( ( 坛+ 虿) 。，吒) 厨：羔只m ( q ) ，虿：芝只g ( q ) ，吼( 口，6 ) ：口+ 6 一以万+ a 口】+ 【6 】+ 且仅0 。引入松弛变量y r m ，若( 1 1 1 ) 有解，它等价于 啪，- ( 0 曼y ) = o ，- 删。 m 其中m = 【m ( q ) r ，m ( ) 7 r ，q = g ( q ) r ，9 ( ) r 】7 。 令z = ( x ，y ) ，( 1 1 2 ) 的价值函数为 臼( z ) = 吉1 1 h ( z ) 1 1 2 。 若( 1 1 1 ) 有解，( 1 1 2 ) 等价于求下列问题的全局极小点 m i n 日( z ) 2 刳日( z ) 1 1 2 ，( 1 - 1 3 ) s t z 0 。 文献【2 7 】中给出了求解( 1 - 1 3 ) 的可行半光滑牛顿算法，该算法是文献【1 8 】中算 法的直接应用，其搜索方向是投影梯度方向与投影牛顿方向的凸组合，即文中的 渐进牛顿方向。该算法的二次收敛性依赖于方程组系统h ( x ，y ) = 0 有解及h ( x ，y ) 的一些正则性假设。若h ( x ，y ) = 0 无解， 导致渐进牛顿方向更接近投影梯度方向， 则迭代得到的牛顿方向可能不精确，这 其二次收敛性不能保证成立。我们在数 值试验中发现，对一些可能无解的例子，该算法的数值表现较差。基于以上原因， 6 随机线性互补问题算法的研究 本文主要研究问题( 1 1 1 ) ，我们提出两种新的算法解决了问题无解时文献【2 7 】中的 算法收敛较慢的问题。 由于( 1 6 ) 通常无解，研究如何得到( 1 6 ) 的合理的解十分必要，c h e n ，z h a n g 和f u k u s h i m a t 2 3 1 给出了判定s l c p 解的最优性及可行性的度量。 r ( x ) = 只【1 l i l l i n ( o ，m ( q ) x + g ( q ) ) l l + x 丁【m ( q h + g ( q ) 】+ 】，x 霹。( 1 - 1 4 ) i = l 令 印( x ) = b ( ，【m ( q 弦+ g ( q ) 】+ ) ，xe 群， ( 1 - 1 5 ) 屁( x ) = p ，i l m i n ( o ，m ( q ) x + g ( q ) ) 0 ，x 群。 ( 1 - 1 6 ) z = l 函数印( x ) 是解的最优性的度量，而凡( x ) 是解的可行性的度量。y e ( x ) 的值 越小，则x 的安全性越高。在后面的章节中，我们将用这些函数来衡量我们的算 法得到的解的优劣。 1 4 基本概念 本节给出本文用到的符号和基本概念。 文中我们用下面的符号约定。彤为玎维欧式空间，足为，z 维非负欧式空间， r “”表示以甩维矩阵空间。l | i l 表示欧式范数。对向量x r ”，i x + = m a x 0 ，x 和 i x 一= m i n o ，x 。对子集jc l 一，h ) ，乃表示x 下标取自j 的子向量。若m r “”， m ，表示m 对应，行和，列的主子阵。 t o i n t 3 5 】给出投影算子的如下性质。 命题1 1 设兀r ( ) 为从r ”到x 上的投影，则 ( i ) 对任意的x 0 ，z r ”有( n j ( z ) 一z ) r ( 兀j ( z ) 一x ) 0 。 ( i i ) 对任意的y ，z r ”，l i h 工( y ) - h 工( z ) l l - - - i l y - z l i 。 ( i i i ) 给定x 贮及d r ”，函数 铂( a ) = 8 兀j ( x + a d ) - x i ，a o 是非减的。而函数 鬼m ) ：i i r i ( x + x d ) - 4 ，九 o 。 旯 是非增的。 定义1 3 设x r ”为非空子集，f ：x 专r ”。如果对任意的x x ，存在常 第一章绪论 7 数三 0 和疋 0 ，使得 j i f ( y ) 一f ( z ) 0 l i l y - z 1 i ，v y ，z b ( x ，瓯) 总成立，则称f 在x 上局部l i p s c h i t z 连续。 假设函数f ：r ”专r ”是局部l i p s c h i t z 连续的，其b - - 导数 3 6 1 为： a 占f c x ，= 【耋l i 葛mf c x 女j 其中磷为f 可导点的集合。记f 的c l a r k e d 7 1 意义上的广义j a c o b i a n 为o f ( x ) ， o f ( x ) = c o n v o b f ( x ) 。 定义1 4 称f 在x r ”处半光滑，若对任意的h r ”， 蹦l i m 、，) v h x + t h ) 矿一、7 ) 。 存在。 从文献 1 2 】和 1 4 】可得到下面关于半光滑和强半光滑的结论。 命题1 2f 在x 处半光滑，则对任意的h 专0 和v o f ( x + h ) ， f ( x + d ) - f ( x ) 一v h = o ( 1 l h l ) 。 定义1 5 称f 在x 处强半光滑，若f 在x 处半光滑且对任意的h 专0 和 v a f ( x + h ) ， f ( x + d ) 一f ( x ) 一砌= d ( 0 向| 2 ) 。 1 5 本文结构 本文主要研究对象是( 1 1 1 ) ，提出了不同于( 1 1 3 ) 的再定式，给出了两种新的 算法，从理论和数值上都解决了问题( 1 1 1 ) 无解时文献【2 7 】中的算法收敛较慢的问 题。具体的，本论文的结构和主要研究内容概括如下： 第二章利用f b 函数把( 1 1 1 ) 转化为新的约束优化问题，提出了一种新的算法， 即可行半光滑牛顿法。给出了算法全局和局部二次收敛性的证明，数值结果表明 新算法可以得到较好的解。 第三章利用f b 函数对( 1 1 3 ) 稍作变形得到与( 1 1 1 ) 等价的约束优化问题，提 出了一种部分投影牛顿法，并给出了该算法的详细的收敛性分析，数值结果表明 算法是有效的。 第四章为结论，分析了算法的优缺点，总结了本文的主要工作。 第二章可行半光滑牛顿算法 9 第二章可行半光滑牛顿算法 本章针对问题( 1 1 1 ) 提出新的模型，并给出一种可行半光滑牛顿算法。对新的 算法进行了收敛性分析，最后给出了数值试验结果。 2 1 极小化模型 本节我们把问题( 1 - 1 1 ) 转化为新的等价的极小化问题。 若( 1 11 ) 有解，则它等价于 日( x ) = 0 ，( 2 1 ) 1 0 随机线性互补问题算法的研究 o v 0 2 ( x ) e o n v m 7d ( s ) m ：s 至z ( x ) ) ， 其中z ( x ) 三 i ：( m x + q ) 。0 ) ，d ( s ) 为对角矩阵，其对角元素为 哟，= 籍& 由以上两个引理可以得到下面的结论。 命题2 2 函数o ( x ) 在r ”上连续可微_ r v o ( x ) = v o i ( x ) + v 0 2 ( x ) ， 光滑。 显然，( 2 - 5 ) 的稳定点满足 x 0 ，v o ( x ) 0 ，x 7v o ( x ) = 0 。 我们给出的算法将得到满足( 2 6 ) 的点，即( 2 - 5 ) 的稳定点。 2 2 解集的有界性 v o ( x ) 强半 ( 2 - 6 ) 本节给出( 2 5 ) 解集有界性的条件。第一章我们给出了随机民矩阵的定义，从 文献 2 2 】可知，若m ( t o ) 的期望矩阵是r o 矩阵，则m ( ) 是随机民矩阵。m ( ) 是随 机r o 矩阵，不能推出存在q 使得m ( c o ) 是r 矩阵。从下面n g n , - i p a 看出， m ( ) 为随机r 矩对( 2 5 ) 解集有界性分析的重要性。 对任意给定的p 慰，定义p ( x ) 的水平集为 厶( ，1 ( x o ) = x r ：9 ( x ) 8 ( ) c o ) ) 。 定理2 1 对任意的g ( ) ，厶( ，) o o ) 是有界的当且仅当m ( ) 为随机r 矩阵。 证明：( 1 ) 充分性。 假设存酬) w x 。) 使叩卜。令以2 翮x k ，不失一般性，设 j ，= 舰坛。显然，i l y l l = l 且y o o ( i ) 我们用反证法证明对任意的j l ，2 ，m ，m ( c o j ) y 0 。假设存在 l ，2 ，聊 和f l ，2 ，船 使得 m ( q ) y 】， 0 ，对七 有 产h 1 【州ij ，、2 u “川。 故对k r o 有 【m ( q ) x + g ( 哆) 】。 o 且【m ( q ) j ，】， 0 。而 州儿也 箐k 产 。 故存在b 0 使得对七 k 有 常h 1 州嗍。 l -0 x 0j 。7 2 。1 1 、“。，1 。 所以，对七 k 有 肘( q ) + g ( q ) 】， 吉【m ( q ) y 】i 肛0 。 即 【m ( 哆) + g ( q ) 】fj 佃，k j 。 由( 2 - 8 ) 知，对任意的 1 ，2 ，m ) 和f 1 ，2 ，刀) ，【m ( q ) + g ( q ) 】，有下界。 ( 胁+ 虿) ，= 所【m ( q ) + 9 ( q ) 】， 1 = 1 = 力【m ( q ) x + g ( q ) 】，+ 岛【m ( q ) + g ( q ) 】， 一厮+ 马【m ( q ) x k + g ( 哆) 】， 1 2 随机线性互补问题算法的研究 故 ( 胁+ 虿) ，啼+ o o ，k 专0 0 ，( 2 - 9 ) ( ) ，2 w ( x k ) t u j 慨七专。 ( 2 邶) 由( 2 - 9 ) 和( 2 - 1 0 ) 可得，1 9 l ( ) 寸+ o o 。这与1 9 l ) p ( p ) 矛盾! 由( i ) 和( i i ) 得，对任意的j l ，2 ，m ) 有 j ，o ，m ( q ) j ，o ，y r m ( ) y = 0 。 而m ( ) 是随j e y l ? , o 矩阵，于是有y = o ，这与ly l = l 矛盾! ( 2 ) 必要性。 令q ( c o ) 三0 ，x o = 0 ，则 o ( x o ) = o ，o 厶( ，) ( 妒) = x 群：d ( x ) 9 ( j c 0 ) ) 。 因为m ( ) 不是随机r 矩阵，故存在x 0 且x 0 使得 x o ，m ( q 如0 ，x r m ( ) x = 0 ，= l ，研。 所以，胁= 0 且见( x ) = 0 。对任意的， o 有， ) 7 a 2 ( t x ) = 00 2 ( i x ) = 0 。故 氏l o ( ，) ( p ) 。这与岛( ，) ( x o ) 的有界性矛盾! 推论2 1 若m ( ) 为随机r 矩阵，则对任意的g ( ) ，( 2 - 5 ) 的解集非空有界。 设& 矿是e v ( 1 - 7 ) 的解集。对任意的虿，若期望矩阵露是r 矩阵，则品矿有界。 由定理2 1 及推论2 1 知，对任意的虿，砖矿有界，则对任意的g ( ) ，( 2 5 ) 的解集 非空有界。反之不一定成立。 2 3 算法 本节我们给出一种求解( 2 5 ) 的可行半光滑牛顿法，算法的具体步骤如下。 算法2 1 步。选择参数叩，p ，g ( 。，1 ) ，仃( 。专) 。选择初始点j c o 。，令6 。= l 及 k ：= 0 ； 步1 计算a ( 矿) 和v o ( x ) ，令以= f ：# o ，v o ( x ) ， o ) ，( i ) 若以非空，求 = a r g m i n x ? ，f 以) ，令 c 办= 般i # i k 。, 第二章可行半光滑牛顿算法 1 3 若o ( x p ) 0 或v o ( x ) ，o ) 。选择矿o v o ( x ) ，解下列线性方程 组得到d v o ( x ) 瓯+ 略，s d = 0 ， ( 2 - 1 1 ) 其中w 吣, k & = 噬。& + 岛e 。若噬，s 的最小特征值大于g ，令& = oi 否则，选择& o ， 使得噬五+ e k e 的最小特征值大于f 。这里占为单位阵。令 c m ；般未 步4 令磋= 一r i v o ( x ) ，其中 一m i l ，_ 篱j o 步5 求满足下式的最小的非负整数m ，记为m k 8 ( + 矛( 6 p ”) ) s 9 ( ) + o v o ( x 。) 7 露( 6 p ”) ， ( 2 1 2 ) 其中对任意的a ( 0 ，1 】 矛f i t ) = ( 九) 露( 九) + ( 1 一( 九) ) 礤( 允) ， 露( a ) ：三 + 旯磋】+ 一，霸( a ) _ 【x + a 以】+ 一，。 这里( 九) 为 ，r a 。【。i ，n 1 】o ( x k ) + v o ( x k ) 7 孑+ 2 ( d ) 7 y 孑( 2 - 1 3 ) 的最优解，其中矛= 磋( a ) + ( 1 一t ) d u 。f i t ) 。令 丸：艿t p 仇，扩：1 1 1 i n f l ，互，x k + l = x k + t ( 丸) 。 步6k ：= k + l ，转步1 。 在步1 中，若以非空，则不满足( 2 - 6 ) 。而( 2 5 ) 的稳定点满足( 2 6 ) ，故某些 # ( f 以) 在解处为0 。所以我们选择最小的# ，并将其置为0 。若新的点x p 使 函数值下降，我们就从新的点出发，继续迭代。稍后我们会证明，算法2 1 产生 的满足，o ，这样步3 中的瓯就是积极集。我们只需要计算的一部分，v 吣, & 的最小特征值就不难计算。步3 得到的牛顿方r h 更加精确，在一定条件下，算法 2 1 是二次收敛的。 1 4 随机线性互补问题算法的研究 2 4 算法的全局收敛性 算法2 1 中的瓦( a ) 和瓦( a ) 分别称为投影梯度方向和投影牛顿方向。( 2 1 3 ) 可以写成 1 m i n 二a t 2 + 3 t + p ， ( 2 - 1 4 ) t e o ，l 】2 。 、 其中 a = ( 如( 九) 一九( 九) ) 7 ( x ) ( 叱( 九) 一“( a ) ) ， ( 2 1 5 ) 卢= ( 如( a ) 一九( a ) ) 7 ( 8 ( x ) d u ( a ) + v 日( x ) ) 。( 2 - 1 6 ) ( 2 1 4 ) 的一个最优解为 fm a x o ，m i n 1 ，- p l a i ，若a 0 ， ，( a ) = 0 ， 若a = o ，3 0 或a _ 1 2 ，( 2 1 7 ) 【l ， 若a = o ，3 0 或口 0 使得i x 一a v p ( x ) 】+ = x 令瓯= f ：# 0 或v o ( x ) ，s o ) 及夏= f ：# = o ，v o ( x k ) ， o 。下面的命题说 明对充分小的a 0 ，步5 中的孑( a ) 是下降方向。 命题2 4 设不是( 2 一1 5 ) 的稳定点，则存在万( o ，1 】使得，对任意的a ( o ，动， d ( 九) 是o ( x ) 在处的下降方向且 o ( x + 孑( a ) ) o ( x ) + o v o ( x ) 7 瓦( a ) 。 证明：首先证明8 瓦( a ) 0 = d ( a ) ，i 恳( a ) 0 = d ( a ) 及i l 孑( a ) 0 = d ( a ) 。 i = 8 ( ，& ) 。1 v 臼( ) si l 。 ，& 的最小特征值满足k ( ，& ) g ，故 扣吣) & i i 扣吣* 又不是( 2 - 5 ) 的稳定点，v o ( x ) s 0 。所以， - v o ( x ) 7 九= v o ( x ) 夏( ) 一v o ( x ) 品 o 。 ( 2 1 8 ) 由步3 知， 第二章可行半光滑牛顿算法 1 5 即 咐一 1 ，- 黹卜 p 从而，i d y l l = i 巾吣啡i 陆令铲扣吣则 慨忙k ：，忱i l k ：。 由命题1 1 知， 瓦( 旯) i j a0 九| l 旯心，0 乏( 允) i | 旯0 吒l i o 。再由命题1 1 得， 对任意的a ( o ，l 】有， 蹦x 丫功伊睁一掣纠胁) l | 2 砒 故对充分小的允 0 ，v o ( x ) 7 1 孑m ) 0 。 膏 证明：由( 2 1 9 ) ，令；i m i n f ，, i = 歹0 。存在 九) 的子列收敛于歹。不失一般性， 设 l i m “= 歹。 ( 2 - 2 0 ) 假设歹= 0 ，不难证明对充分大的k 有 ， r t v o ( x ) 7 d ： 胪一薪。 由命题2 2 得， h l i mi l v 0 o 和b 使得，i i v 。0 f ：，& 兰对七b 成立。从而， a 妇( v 。, k 。) a 衄( 矿) z 2 。 由唧的选择知， & z 2 + ，k ( 噬，) - - - 2 g +