（应用数学专业论文）隐互补问题的迭代算法.pdf

南京航空航天大学硕士学位论文 摘要 首先通过背景介绍引出文章要解决的主要对象：隐互补问题，讨论了互补 问题的各种形式以及互补问题如何应用于最优化问题中。 在得出隐互补问题的一般形式后，文章讨论t n 用各种方法来解决隐互补问 题。第一种方法利用互补函数将隐互补问题转化为无约束最优化问题，讨论了在 何种条件下无约束最优化问题的局部极小点是隐互补问题的解。在一定条件下， 隐互 问题与广义的变分不等式是等价的，第二种方法利用辅助问题准则建立了 两种求解隐互补问题的迭代算法，并证明了算法的全局收敛性，这是本文的主要 创新点。第三种方法将隐互补问题转化成非线性互补问题，利用不动点理论来解 决隐互补问题。本文的结果推广了经典互补问题的相应的结论。 关键词：隐互补问题，约束最优化问题，广义变分不等式，辅助问题准则，收 敛性 隐互补问题的迭代算法 a b s t r a c t f i r s t l y ，i m p l i c i tc o m p l e m e n t a r i t yp r o b l e m ( a b b r i c p ) i si n t r o d u c e db yt h e b a c k g r o u n d o f c o m p l e m e n t a r i t yp r o b l e m s ( a b b r c p ) a l l f o r m so fc pa n di t s a p p l i c a t i o n t os o m e o p t i m i z a t i o np r o b l e m sa r ed i s c u s s e d i c pi ss o l v e db ys e v e r a lm e a n si nt h i sp a p e r ，s u c ha su n c o n s t r a i n e do p t i m i z a t i o n ， a u x i l i a r yp r o b l e mp r i n c i p l ea n df i x p o i n tt h e o r y t h ec o n d i t i o nt t l a te n s u r e st h el o c a l o p t i m a lp o i n t st ob et h es o l u t i o no fi c pi s d i s c u s s e di nu n c o n s t r a i n e do p t i m i z a t i o n u n d e rs o m ea s s u m p t i o n s ，i c pi s e q u i v a l e n t t o g e n e r a l i z e dv a r i a t i o n a li n e q u a l i t y ( a b b r g v i ) w es u g g e s tt w oc l a s s e s o fi t e r a t i v em e t h o d sb u i l to nt h e a u x i l i a r y p r o b l e mp r i n c i p l ef o rs o l v i n gi c p , a n ds t u d yt h ec o n v e r g e n c eo ft h e s em e t h o d s l a t e r , t h ef i x - p o i n tt h e o r yi su s e dt os o l v ei c r k e y w o r d s ： i m p l i c i tc o m p l e m e n t a r i t yp r o b l e m ，u n c o n s t r a i n e do p t i m i z a t i o n p r o b l e m ，g e n e r a l i z e d v a r i a t i o n a l i n e q u a l i t y ，a u x i l i a r y p r o b l e m p r i n c i p l e ， c o n v e r g e n c e 承诺书 本人郑重声明：所呈交的学位论文，是本人在导师指导下，独立进行研究 工作所取得的成果。尽我所知，除文中已经注明引用的内容外，本学位论文的 研究成果不包含任何他人享有著作权的内容。对本论文所涉及的研究工作做出 贡献的其他个人和集体，均已在文中以明确方式标明。 本人授权南京航空航天大学可以有权保留送交论文的复印件，允许论文被 查阅和借阅，可以将学位论文的全部或部分内容编入有关数据库进行检索，可 以采用影印、缩印或其他复制手段保存论文。 作者签名：i ：l 童函 日 期：述：i f 南京肮空航火人学硕士学位论文 1 1 背景介绍 第一章绪论 互补理论起源于经济学中的均衡问题，d e n t z i g 和c o tl l e 于1 9 6 3 年阿先 提出互补问题。互补问题的出现，引起了当时人们的浓厚兴趣，许多人纷纷参 与这项研究。l e m k e 、c o t t ie 与d e n t z i g ”1 等人也对其进行了研究。到8 n 年代 中后期，经过2 ( 】余1 j 的努力，在算法研究方面取得了丰硕成果：( j ) 对线性7 j 补问题，有直接方法( 如l e m k e 法、c ( 儿t l e d e n t z i g 法) 和迭代法( 如m a n g 1 1 法) ；( ii ) 对非线性7 f 补问题，有不动点法，同伦法、投影法，n e w l o n 法等， 相关内容可见” 和p a n g 的综述文献豫j 及文献 4 簿，也见优秀争菥 5 ，6 ，7 。 现在互补理沦作为数学学科的一个重要分支，在工程物理、经济与交通i 【 衡等领域都具有广泛应用，并且与刁i 动点理论、变分不等式、线性和非线性分 析及其他应用数学如优化、对策论、经济、随机优化控制等密切联系”z 这 个领域在理论和应用上f e 经历着深入的发展。隐互补问题是互补问题的更一舣 形式，但对于隐互补问题的研究主要集中在解的存在性方面，对于算法的研究 很少见到。 1 2 互补问题 定义1 2 1 设反，足两个实向肇空间，如果在f x ，i 上存在双线性函数( ，) 使 ( 1 ) ，t ，j 、v t 0 如果厅是个点凸锥，偏序“”还满足： ( 3 ) 工y 爿1 ，工j = 1 ， 此时称( e ，) 足序向量审削。 设( e ，) 是序向量空削，如果v x ，e ，在f 中存在卜确界x y 和上确界 x v y ，满足条件： ( 1 ) x a y + z 。( t 十：) ( y 十2 ) ； 互补问题可以分为很多类，常见的有： ( 1 ) 广义互补问题( ( ；e n e r aj jz e d c o r n p l e m e n t a r i t yp r o h l e m ) 殴( e f ) 是周部1 1 _ 空间的对偶系统，f ：k 呻f ，k 足f 中的闭凸锥，广义 互补问题( 6 l 7 ，) 是指： 求x k ，使得，( x 。) 符且( x 。，厂( x ) ) = o 如果，x ) = ( ) + 6 ，其中? 1 。，是线性映射，6 f ，则称( “p ) 为线 1 ， w 眠 r i 巴，勺g 0 ，v x ，y d ，x y ， 则称f 在d 上是严格单调的。 ( 3 ) 如果j 0 ，使得 ( 厂( x ) 一厂( y ) ，x y ) - 1 l x y l l 2 ，v x ，y e d ， 则称f 在d 上是强单调的。 下面给出强凸函数的定义及其一些重要性质“： 定义1 4 2 i 发m ( x 1 是定义在凸集s 匕h 上的有限函数，如果存在m 0 ， 搬，x 2 s ，有 m ( a x i + ( 1 - a ) x 2 ) - 2 r o l l x i - - x 2 1 1 2 1 5 本文的主要工作 隐互补问题是互补问题的更一般形式，对于隐互补问题的研究，一般分为 理论与算法，前者主要研究解的存在性、唯一性；后者则主要建立有效的算法 及相应的算法分析。鉴于现在对隐互补问题的研究主要集中在解的存在性方面， 对于算法的研究很少见到。本文主要研究隐互补问题的迭代算法。根据已经掌 握的知识，在讨论隐互补问题时最直接的想法是转化为无约束最优化问题，由 于无约束优化法较为成熟，因此，对这类方法的研究重心在于如何转化上。本 文利用m a n g a s a r i a n 和s o l o d o v 提出的互补函数将隐互补问题进行转化，解决 了无约束最优化问题的局部最优点成为隐互补问题解的条件。辅助问题准则是 解决经典变分不等式的一类方法，基于隐互补问题与广义变分不等式的等价性， 考虑用辅助问题准则解决隐互补问题，这在作者所见的文献中都未曾提及，本 文对有限维和无限维的情况分别进行了讨论。最后利用不动点理论来解决隐互 补问题，建立了隐互补问题与不动点问题的等价性，利用不动点理论建立求解 隐互补问题的算法，并给出算法的收敛性证明。本文的结果推广了经典互补问 题的相应的结论。 一堕至堕至堕盔奎堂堡主堂堡笙塞 第二章隐互补问题转化为无约束最优化问题 设g ，f ：r ”斗r ”是任意函数 彤= x = ( x“f t o l 本章考虑如下隐互补问题的解法 求x r ”，使得g ( x + ) o ，厂( x ) o ，( g ( 工) ，厂( x ) ) = 0 记，( x ) = ( 石( x ) ，z ( x ) ) 7 ，g ( z ) = ( g ( z ) ，g n ( x ) ) 7 ，则( 2 1 ) 等价于 求x r ”， 使得吕( x ) o ，( x ) o ，g ，( x ) ，( x + ) = 0 ， 显然，如果g ( x ) = x ，则( 2 1 ) 即为经典互补问题。 2 1 互补函数的性质 i = l ，2 ，胛 本文利用m a n g a s a r i a n 和s o l o d o v “”提出的互补函数： 妒( 啪) 谢+ 剖( ( 埘+ 口) ：彳+ ( - g a + b ) 一) ，训 这里( ：) + 是一个向量，( ( ：) + ) ，= m a x o ， ，i = 1 ，2 朋 k a n z o w ”已经证明了互补函数妒( 盯，6 ) 具有如下的性质： 引理2 1 1 ( a ) 妒在尺2 上连续可微，v 妒( o ，0 ) = ( o ，o ) ( b ) 妒( d ，b ) o ，v ( a ，6 ) 7 r 2 ( c ) 妒( d ，b ) = 0 ，口o ，b o ，a b = 0 警( 啪) 雾( 啪) o ，v ( 咖) 7 “ 9 ( 2 1 ) 隐互补问题的迭代算法 等( 咖) 警( 啪) = o 妒( 啪) _ o 引理2 1 2 p ( 口，b ) = 0 铮v 妒( 口，b ) = 0 证明 ( j ) 假设妒( n ，b ) = 0 ，由引理2 1 1 知，( d ，6 ) 。是妒的整体极小点 因为妒是连续可微的，故v ( o ( a ，b ) = 0 ( 乍) 设( “，妒e r 2 ，且v 妒( “，b ) = 0 ，即 知铲a 一( 吉 口+ ( 口 口6 ) + 一( 6 一口n ) + = 0 瓢垆口一( 加( 珈刮+ 七碱- o 眨，z ， 考虑f 面的四种情况： ( 1 ) a a b 蔓o ，b o t a 0 ，则( 2 1 1 ) 和( 2 1 2 ) 可以改写为： a = l 吉) o o = o 1 1 ) 。= ( 一形z ) n ， 因为凹 1 ，所以a = 0 ，从而6 = 0 ，由引理2 1 1 的( c ) 可以知道妒( 臼，b ) = 0 ( 2 ) 口一a b 0 ，b 一口玎 0 ，由( 2 1 1 ) 可得 o = ( a 一) a ， 因为口 1 ，所以口= 0 ，从而6 0 ，由引理2 1 1 的( c ) 可以知道妒( 口，b ) = 0 ( 3 ) a a b o ，b 一口口0 ，由( 2 1 2 ) 可得 o = o j 一形) 。， 因为口 1 ，所以b ：0 ，j a v a 0 - 由引理2 1 1 的( c ) 可以知道p ( 口，b ) = 0 ( 4 ) 盯一a b 0 、6 一o j a 0 ，由( 2 1 2 ) 可以得出 0 = - b + 盘盘 0 矛盾，从而这种情况是不存在的。 南京航空航天大学硕士学位论文 2 2 隐互补问题转化为最优化问题 把上节中的价值函数应用于，g 的各个分量，则有 仍( x ) = 妒( 吕( z ) ，( x ) ) ，i = 1 ，2 ，” 从而互补问题转化为如下的无约束最优化问题： m i n p ( x ) = ( x ) = 妒( g ，( x ) ，z ( x ) ) ( 2 2 1 ) i = 1i = l 由f z l 的定义，给出如下的引理： 引理2 2 1 下列条件是等价的 ( 1 ) g ( x ) o ，f ( x ) o ，( g ( x ) ，厂( z ) ) = 0 ， ( 2 ) g ( x ) = ( 一口厂( x ) + g ( x ) ) + ( 3 ) f ( x ) = ( 一a g ( x ) + ( x ) ) + 上述引理只要对一d z ( z ) + 岛( x ) o 与- a f ( x ) + g ，( z ) i ，故j o ，从而g ，：0 1 3 ) 一a f l + g l 0 可以得到： 2 c e c p ( g ，) = ( 口2 1 ) g , 2 0 因为口2 1 ，v ( g ，) = o ，故舅= o ， 0 ，从而昌，：0 ( 4 ) 一口z + g ， o ，- a g j + ， o ，璺 0 ， 2 口妒( gr ，) = 2 口g ，一g ? 一，22 l 酽# 1 - o 上述不等式是由： 2 a g ，一g ? 一，2 2 酽一g ；一，2 = g ? 一，2 2 t z g ，一g ? 一，2 2 ，2 一酽一，2 = ，2 一g ? 南京航空航天大学硕士学位论文 又因为妒( 蛋，) = 0 ，从而g ? = z 2 ，可得岳= z = 0 这与一a f , + g ， 0 ，f 占在x + 是 二次可微的，且 可( x ) 刖，v g ( x ) 。 是线性无关的，这里 ，：= jj i x ) = o ) ，世：= 恤，( x ) = o 则( x ) = o ，k x 是y 卜) 的局部唯一的整体极小点。 证明由定理2 2 - 1 知x 是( z ) 的整体极小点，且妒( x ) = o 一f q 通过e v 2 y ( x + ) 是正定的，来证明工是妒( x ) 的严格局部极小点，因为 口v ( z ) = a v g ( x ) 7 仆+ ) + 可( x ) 7 9 ( x ) + f - 口可p ) 7 。十( x ) 7 ) ( 一口厂( 工) + g ( z ) ) + 一强( x ) 7g ( 工+ ) + ( 一口豫7 + w ( x ) 7 ) ( 一口g + 厂( x + ) ) + 一夥( x ) 7 厂( x ) = ( 一川( x 7 4 - v g ( x ) 7 ) ( ( - 。巾) + g ( x + ) ) + 一g ( z ) ) + f 一口v g ( z ) 7 + w ( 。) 7 j ( ( 一口g ( 。) + 厂( x ) ) + 一( 。) ) 2 2 5 v ( 一口厂( x + ) + g ( x ) ) + = 一a 可咒上：p v g j x c ：z s a ， v - a g ( x ) + m ) ) + = 一魄小孓f ) 眨：肺， 利用( 2 ，6 a ) ，( 2 2 6 b ) 及g ( x + ) = ( 一d ，( x ) + g ( x ) ) + ，厂( 工) = ( 一口g ( x ) + ，( x + ) ) 钾2 桫( z + ) = ( 一吼( x + ) r + v g ，( x ) 7 ) ( _ o v f , ( x ) + v g 。( ) ) + 州( x ) 7 ( x + ) _ v g ( x ) 7 ( x ) + 卜a v g 。( 玎+ 阢( x + ) 7 ) ( 一口豫。( 工) + 阢( z + ) ) + a v g ( x ) 可( 上) 一v ，( x ) 7 w ( x ) = 酣2 ( z ) ( z ) + 口2 v g 。( 工) 7 1 v g 。( x ) 一v g x ( x ) 。( x ) - ( x ) 7 ( x ) = ( 口2 一t ) ( 啊( x ) 7 ( x ) + 。( x ) 7 v g 。( x ) ) 跏小跏f h f f ) 陋甜 隐互补问题的迭代算法 严的 卜 y 是石而从定正 卜 v以所的舜奇非黾 叫f ， kv 厂il 。 且 占 “ 极 d 部 为 局 因 格 南京航空航天大学硕士学位论文 第三章辅助方法求解隐! i 2 丰1 、问题 近几年来，辅助技术得到了发展，它的起源可追溯到l i o n s 与 s t a m p a c c h f a “，g l o w in s k i 、l i o n s 与t r e m o l i e r e s l ”曾用来研究混合变分不等 式解的存在性；n o o r “利用辅助技术研究求解各种变分不等式的预校正方法： z h a o ”利用辅助技术建立了一种求解单调变分不等式的推广的投影方法； f a r o u q “2 ”1 研究了用辅助问题准则求解伪单调变分不等式的算法的收敛性：有关 经典变分不等式的许多算法都可以统一在所谓的辅助问题准则框架里 甑2 5 - 2 6 1 。 设是- 2 b e r t 空间，占是其中的非空闭凸子集，妒：日j 日，经典的变分 不等式可以描述为： 求x e s ，使得( 妒( x , x - x - 0 ，觇e s 该问题有许多种解法，其中很多方法都可以用辅助问题准则来描述： 选取强凸可微函数们：- - - r ，和正数序列 ) ，构造如下算法： 算法3 1 第一步：任意选取妒日 第二步：设x 。已知，则z “是下列优化问题的解 喈( m ( z ) + ( f 妒( x ) 一m 协) ，x ) ) 第三步：如果舻“一0 满足某个终止条件，停止；否则，令：x “转第二 步。 关于算法3 1 的详细描述和收敛性证明可以参见相关的文献m ，“。 本节我们利用辅助问题准则建立求解隐互补问题的迭代算法，并给出算法 的收敛性证明。先引入本章需要用到的一些相关概念。 隐互补问题的迭代算法 3 1 相关概念 设是一个历6 e ，f 空间，定；- i i x i i = 狄i 巧，x e h ，厅是打中的一个凸 锥，设函数厂，g ：h 寸h ，口是中的一个闭子集。 定义3 1 1 ( 1 ) 如果v u l ，“2 ，z h ，| p 0 ，使得 ( 厂( ) 一厂( “：) ，g ( z ) 一g ( “：) ) 一p l l g ( “，) 一g ( z ) j 2 则称f 关于g 满足部分松弛强单调条件。 ( 2 ) 如果v u l ， 2 抒，j 卢 0 ，使得 ( 厂( u i ) 一( “：) 、g ( u 1 ) 一g ( u 2 t ) - ，；l l f ( u 1 ) - s o ：) n 则称f 关于g 是一致强制的。 定义3 1 2 ( ：) 如果坛l ，x 2 k ，有 ( s ( x ：) 一f ( x 。) ，g ( x ：- g ( x ) ) o 则称f 在k 上关于g 单调。 ( 2 ) 如果3 a 0 ，使得坛，x 2 k ，有 ( 厂( t ) 一，( _ ) ，g ( x ：) 一g ( ) ) 0 1 1 9 ( 恐) 一g ( 一) 则称f 在k 上关于g 强单调。 ( 3 ) 如果v x l ，x 2 k ，有 ( 厂( x 。) ，g ( x 2 ) 一g ( x 。) ) o j ( 厂( x ：) ，g ( x ：) 一g ( x ) ) o 则称f 在k 上关于g 伪单调。 ( 4 ) 如果j e 0 ，使得v x i ，x 2 k ，有 ( f ( x 1 ) ，g ( x 2 ) 一g ( _ ) ) o j ( 厂( z ：) ，g ( 恐) 一g ( x 1 ) ) e i i g ( x ：) 一g ( ) ij 2 则称f 在k 上关于g 强伪单调。 南京航空航天大学硕士学位论文 ( 5 ) 如果j e 0 ，使得v x ，x ，k ，有 ( ，( ) ，g ( x ：) 一g ( x - ) ) o j ( ，( 叠) ，g ( x ：) 一g ( _ ) ) 吉1 1 j l x ：) 一厂( 圳2 则称f 在k 上关于g 伪一致强制。 定义3 i 2 中的各广义单调性之间有如下的关系： g 强单调等g 单调乍 g 一致强制性 上上上上l 上 g 强伪单调jg 伪单调乍g 伪一致强制 注上述各关系的逆是不成立的。 例如： ( 1 ) 令，( x ) = 1 一x ，g ( x ) = x ，k = ( 一m ，o 】，关于占是伪单调的，但不是 占单调的，也不是g 伪一致强制的，不是g 强伪单调的。 ( 2 ) 令，( x ) = 必，g ( x ) = x ，k = 1 ，+ 。) ，关于g 伪一致强制，但不是g 一致强制，从而不是占单调的，也不是占强伪单调的。 引理3 1 1 1 v “，v h ，有 ( “，v ) = 吉q “+ v 1 2 一i l “1 1 2 一j l vj 1 2 ( 3 1 1 ) 2 + ( ) 一扣i 1 2 ( 3 1 2 ) 引理3 i 2 若，关于占是常数为口 0 的一致强制的，则，关于g 是常数为 的部分松弛强单调的。 证明v u ，v ，z h ，有 ( ( 甜) 一厂( “：) ，g ( z ) 一g ( “：) ) = ( ，( “，) 一，( “z ) ，g ( z ) 一g ( ) ) + ( 厂( ) 一厂( “：) ，g ( q ) 一g ( “：) ) 隐互补问题的选代算法 ( ，( “。) 一厂( “：) ，g ( z ) 一g ( “) ) + 口i i ，( “) 一厂( “：) lj 2 2 a l _ ，( “) 一厂( “：) j 1 2 + i i ( 厂( “，) 一厂( “：) ，g ( z ) 一g ( “。) ) 一击蜘- ) 一g ( 哪 l h ( 31 2 1 ，令 m ) 一巾：) ，v 2 i 1 ( g ( z ) 一g ( 讲 这就可以得到，关于g 是常数为1 的部分松弛强单调的。 q a 定义3 1 3 如果3 l 0 ，使得帆l ，x 2 k ，有 ) 一厂( ) 忙z l l g ( x , ) - g ( x ：) 则称，关于g 是l i p s c h i t z 连续的，l 是l i p s c h i t z 常数。 引理3 1 3 若，是常数为p 的强伪单调的，常数为的g - - l i p s c h i t z 连续的 则厂是常数为钐的g 伪一致强制的。 注上述引理由定义j 容易证得。 3 2 隐g l b f * 7 题与变分不等式的等价性 以下建立隐互补问题与变分不等式之间的联系，考虑下面的广义变分不等 式( 6 v _ r ) ： 瓤e d ，使g ( x ) k ，( 厂( x ) ，y g ( x ) ) o ，k ( 3 2 1 可以看出，如果g = ，是单位映射，则( o v z ) 就退化为经典的变分不等 式问题( v z ) ： 求z k ，使( ( z ) ，y x ) o ，v y e k 广义变分不等式( o v i ) 与如下的隐互补问题( i c p ) 密切联系，即 堕夏堕至堕盔盔堂堡主堂垡笙塞 求x e d ，使g ( x ) e k ，( x + ) e f ，( ，( x + ) ，g ( z ) ) = 0 命题3 2 1 x 是( g v i ) 的解当且仅当x 是( i c p ) 的解 i t n 设x + 是( 占”) 的解，从而x d ，且 g ( x ) e k ，( 厂( x + ) ，y g ( x ) ) o ，e 足 特别，令j ，= g ( x + ) + x ，v x k ，则 ( 厂( x + ) 扩g ( x + ) ) = ( “( x ) ) o ，地k 在3 2 3 ) 中分别令2 0 ，y = 2 9 ( x + ) ，从而( ，( x ) ，g ( 工) ) = 0 因此x 是( i c p ) 的解。 反之，设z 是( i c p ) 的解，从而z d ，且 g ( x ) k ，( x ) e k + ，( 厂( 工+ ) ，g ( x + ) ) = 0 ( 3 2 2 ) ( 3 2 3 ) 所以( 厂，_ y g ( x ) ) = ( 少，( z ) ) 0 ，砂e 量 因此x 是( 8 v i ) 的解。 引理3 2 1 ( 1 ) 若，关于f 伪单调，i 和x ：是( 6 v i ) 的解，则 ( ，( 引，g ( 蔓) 一g ( x ：) ) = 0 ( 3 2 4 ) ( 2 ) 若，关于g 伪致强制，则集合 s = 厂( x ) l ( 厂( 石) ，g ( x ) 一g ( x ) ) o ，v g ( x ) 足 是单点集。 ( 3 ) 若，关于g 强伪单调，且占是单射，问题( 6 v d 有解，则解唯一。 证明设i 和x ：是( 6 v i ) 的解，则 ( 厂( x ) g ( x ：) 一g ( i ) ) o ( 3 2 5 ) 2 i 隐互补问题的迭代算法 ( ( x ；，g ( x ? ) 一g ( x ：) ) o ( 1 ) 若，关于g 伪单调，由( 3 2 5 ) 可以得到 ( ，( x ；) ，g ( x ；) 一g ( 工i ) ) o 再由( 3 2 6 ) ，就可以得到( 3 2 4 ) 。 ( 2 ) 若，关于占伪一致强制，则 。= ( 厂( 蔓) ，g ( 蔓) 一g ( x ：) ) 去l l s ( x ：) 一厂( x ? ) | | 2 因此，厂( x i ) = ，( z ；) ( 3 ) 若，关于g 强伪单调，则 。= ( ( 葛) ，g ( x ：) 一g ( x j ) ) j g ( x ；) 一g ( x i ) 1 1 2 因为g 是单射，故有x ：= 蔓 3 3 有限维空间中的辅助问题准则 ( 3 2 6 ) 前面已经证明了求解隐互补问题( i c p ) 等价于求解下面的广义变分不等式 ( 占) ： 耙e d ，使g ( x + ) k ，( 厂( x ) ，y g ( x + ) ) 0 ，v y e k 以下假设是r ”空间，d h 是闭子集，世h 是闭凸锥，尸是任意的1 7 阶实对称正定矩阵，d o 是给定实数，且g ( d ) k ，我们构造算法如下： 算法3 3 1 第一步：取妒d ，使g ( p ) 足，k = o 第二步：在第k 步，知道x ，y k 是下列优化问题的解 m 雕i n 一2 1 口y 7 砂一吉g ( ) 7 砂+ m ) 7 y ( 33 1 ) 南京航空航天大学硕士学位论文 第三步：如果妙一g ( ) i | 满足某个终止条件，停止，取x + = ；否则，令 g f x “1 1 = y ，k ：= k + 1 ，转第二步。 注因为p 是正定矩阵，所以唧去y 7 彩一击g ( ) 7p y + f ( x ) 1y 是强凸规y 5 2 d口 、7 划问题，对于这类问题的求解有很多种算法。 下面给出算法3 3 1 的收敛性证明。 定理3 3 1 设函数，g 满足如下条件： ( 1 ) ，g 在上连续， ( 2 ) ，关于g 是常数为p 的部分松弛强单调的，p 0 ， ( ”。l i mi i g ( x ) i | _ 。，常数口满足o 口 o ，e k ， ( 3 3 ，2 ) 设x 是( 占玎) 的一个解，令y = g ( x + ) 代入( 3 3 2 ) ，y = g ( x “1 ) 代入 ( 3 2 1 ) ，可得到 ( 口厂( x 2 ) + p ( g ( x t m ) 一g ( x ) ) ，g ( 石) 一g ( z “。1 ) ) o ( 3 3 3 ) ( 口，( x + ) ，g ( x “) 一g ( 工) ) o ( 3 3 4 ) 由( 3 3 3 ) 和( 3 3 4 ) 可得 ( p ( g ( x “1 ) 一g ( x ) ) ，g ( x ) 一g ( x ) ) ( 口厂( x 。) 一口厂( x ) ，g ( x 2 “) 一g ( 工) ) 又由f 关于g 满足部分松弛强单调条件，可得 隐互补问题的迭代算法 ( 尸( g ( x “) 一g ( x ) ) ，g ( x ) 一g ( x “) ) ( 口厂( x 。) 一口( x ) ，g ( x “1 ) 一g ( x ) ) 由引理3 1 1 ，令 从而 一c r p 1 9 ( x k + 1 ) 一g ( x k ) 1 1 2 “= p “( g ( x “1 ) 一g ( x k ) ) ，v = p 。( g ( x + ) 一g ( x k + 1 ) ) o g ( x k + 1 ) 一g ( x ) ) 7 p ( g ( x + ) 一g ( 1 ) ) + 印m z “) 一g ( x k ) 1 1 2 = 圭8 尸( g ( x ) 一g ( x ) ) 1 1 2 一| l p “( g ( x 女+ 1 ) 一g ( x ) ) 1 1 2 0 尸巧( g ( x i + 1 ) 一g ( x ) ) 8 2 + 印x k + 1 ) 一g ( ) ) 1 1 2 圭0 9 ( x ) 一g ( 工) ：一i g ( x + 1 ) 一g ( x ) 0 ：一i f g ( x + ) 一g ( 工“1 ) j | ； + 印垆i l i l l g ( x “ ) 一g ( ) 旺 其中1 | z 1 | ；= z t p z ，于是 l l g l x k , ) 一g ( 石嘶慨x 2 ) 一g 沪i 一叫眇l g ( x k + t ) 一g ( x 饰( 3 。s ， 因为。 口 盘2 p ，故序列0 9 ( ) 一g ( x ) 旺 单调下降，从而存在非负数胁满足 蚓g ( x ) 一苫( x 诜= m 由( 3 3 5 ) 和( 3 3 6 ) ，可得 i r ai g ( x 。+ ) 一g ( p ) | | p = 0 ( 3 3 6 ) ( 3 3 7 ) 由条件l i m g ( 、x ) | j = 。，可知 ) 有界，设i 是 ， 的一个聚点， x 是收敛到 南京航空航天大学硕士学位论文 i 的子序列，则 g ( i ) k ，i d 在( 3 3 2 ) 中，令：= x “，k s 哼。o ，可得 ( 口，( i ) ，y g ( 覃) ) o ，r y e k 从而i 是( 6 v ) 的一个解，由命题3