（运筹学与控制论专业论文）变分不等式的例外簇和epvi的误差界.pdf

变分不等式的例外簇和e p v i 的误差界 摘要 在这篇文章中，一方面，我们利用例外簇来考察变分不等式解的存在性 文中给出了。一例外簇的概念，并据之给出了变分不等式解的存在性定理和 无例外簇的条件；而且利用另一例外簇讨论了非线性互补问题的可行性另一 方面，我们以g a p 函数为工具，考察了e p v i 问题的误差界 关键词：例外簇，变分不等式，非线性互补问题，e p v i 问题，误差界 a b s t r a c t i nt h i sp a p e r ，w ei n t r o d u c ean e w c o n c e p to fo e x c e p t i o n a lf a m i l yf o r v a r i a t i o n a li n e q u a l i t yw i t hg e n e r a ln o n e m p t yc l o s e dc o n v e xs e t s w ea p p l y t h i sc o n c e p tt od e a lw i t ht h ee x i s t e n c e p r o b l e m so ft h es o l u t i o n m o r e o v e r ， w ed i s c u s s e dt h ef e a s i b i l i t yo fn o n l i n e a rc o m p l e m e n t a r i t y p r o b l e mb ya n o t h e r e x c e p t i o n a lf a m i l y o nt h eo t h e rh a n d ，w em a k eu s eo fg a p - f u n c t i o nt o s t u d y t h ee r r o rb o u n df o re p v i k e yw o r d s ：e x c e p t i o n a lf a m i l yo fe l e m e n t s ，v a r i a t i o n a li n e q u a l i t y , n o n l i n e a rc o m p l e m e n t a r i t y p r o b l e m ，e p v i ，e r r o rb o u n d 第一节引言 定义1 1 设函数f ：r - - r ，叩：r r _ r 和，：兄_ r 均 为连续可微函数，且叩( 。，。) = o ，v x r 所谓的广义的预变分不等式问题 ( e p v i ) ：即求。o r 使得 ( f ( x o ) ，叩( z o ，可) ) f ( x o ) 一，( g ) ，v y r “ ( 1 1 ) 易见，当叩( 吐9 ) = y z ，为常值函数时，e p v i 即为v i ( r ，f ) 而本文我 们主要讨论定义在一般闭凸集上的变分不等式问题 定义1 2设k 是空间r 中的非空闭凸集，f ：k _ r 为一连续 函数变分不等式问题v i ( k , f ) 是：求一点z + k ，满足 ( f ( x + ) ，。一。4 ) 20 ，v x k ( 1 2 ) 自1 9 6 4 年g s t a m p a c c h i a 在文9 中提出这一问题以来，变分不等式问 题( v i ( k ，f ) ) 已经得到长足的发展关于它的发展近况，p a n g 在文献 3 0 作 了详细介绍变分不等式问题是应用数学中的一个十分重要的研究领域，这不 仅仅是因在非线性最优化中具有相当广泛的应用，而且在微分方程、力学、控 制论、经济平衡理论、对策论、交通，社会和经济模型等方面都有着重要的应 用 当定义1 2 中的是锥时，v i ( k f ) 转化为非线性互补问题( n c p ( k ，f ) ) 定义1 3 设k 是冗中的任一非空集合，f ：k _ r 非线性互补 问题( n c p ( k ，f ) ) 即求一向量矿使得 。+ e f ( x + ) k + ，( f ( x ) ，卫+ ) = 0( 1 3 ) 其中耳+ 是k 的对偶锥，k + ：= x 兄：( 茹，y ) 0 ，v y k ) 这一问题是s k a x a m a r d i a m 在文 3 2 】中提出的，而且在力学、工程学、 经济学等方面已经被人们广泛的研究 1 0 一1 2 ，1 5 ，2 0 一2 2 】 v i ( k ，f ) 和一n c p ( k ，f ) 的基本问题之一是解的存在性问题：即在何种条 件下， v i ( k ，f ) 和n c p ( k ，f ) 有解p a n g 在文献【3 0 中已经列出了很多 个v i ( k ，f ) 解的存在性定理另外，1 9 8 4 年s m i t h 在文献 5 】中提出概念” 例外序列”，并据之来研究n c p ( k ，f ) 解的存在性问题之后，i s a c g 1 l 】和 n h a d j i s a 【纠等人相继利用例外簇来研究v i ( k ，f ) 和n c p ( k ，f ) 解的存在性 1 在这篇文章的第二，三部分，我们采用例外簇来研究v i ( k ，f ) 的解的存在性 和n c p ( k ，f ) 的可行性为了研究问题的方便，许多作者提出了不同的例外 簇【3 , 4 ，1 0 - 1 4 ，1 8 2 1 ，2 5 2 6 最近，张立平和陶仕冰在文献【1 】和 2 中分别提出 了v i ( k ，f ) 的两种不同的例外簇因此，在本文中我们试着用一种例外簇将 其统一起来在第二节，我们提出了。一例外簇的概念( 详见定义2 1 ) ，它统一 了文 1 和文 2 中的例外簇，并据之提出了解的存在性定理( 详见定理2 ，1 ) 在第三节，我们提出了另外一种a 一例外簇的概念( 详见定义3 1 ) ，并据之给 出了n c p ( k ，f ) 的可行性定理( 详见定理3 1 ) v i ( k ，f ) 的另一个基本问题是算法对于求解v i ( k ，f ) 问题，一个重 要的手段是利用g a p - 函数( 见定义4 1 ) 把v i ( k ，f ) 问题转化为一个等价的最 优化问题，从而利用最优化算法，求解v i ( k ，f ) 问题在第四节，我们利用 g a p 一函数( 如口) ，将广义预变分不等式( e p v i ) 转化为最优化问题 。m i n ，g n f 3 ( z ) 讨论了加万的误差界及e p v i 的算法( 下降法) ( 详见定理4 5 ，4 6 ) 在下文中，我们用”) 分别表示欧几里德范数和内积，p k ( ) 表示闭 集k 上的投影算子令d 是r 中的有界开子集，面和o d 分别表示d 的闭包和边界， b ，：= 忙r ：恻l 0 ，当i i x l l _ + o 。时，i i g ( x ，圳一+ o 。这样，当o z = 0 时，( 2 1 ) 式变为 一 亡r ( 。，一岔) + f ( x ，+ 0 一茹，) ) 】k ( 茹，) ， 即 研) ，+ o ocr 是文献 1 1 中的例外簇如果令g ( 石，t ) = $ ，则g 满足定 义2 1 中的条件这样，当0 t = 1 时，( 2 1 ) 式变为 一【亡r 0 ，一圣) + ( 1 0 ) f ( 。，) 1 n k ( ( 1 + 0 ) z ，) 即 一f f ( 斟) + 土1 - t r r 一童) 1 坛( ( 1 + 。) z r ) 从而， 研) ，_ + + o 。cr 是文献【2 中的例外簇 为了建立关于v i ( k ，f ) 的解的存在性定理，我们需要下面几个引理 3 引理2 1i t 】设x 是r n 空间，k 是x 的非空闭凸子集，f ：k _ x 连续，则x + 是y j ( ，f ) 的解充要条件是 x + = p k ( z + 一f ( x + ) ) 引理2 2 x 7 设d 是r 空间的有界开集，设日：西x 【0 ，1 _ + r 是连 续函数，如果y r 且y 隹 日( z ，t ) ：x o d ，t 0 ，1 】 ，则d e g ( h ( ，t ) ，d ，y ) 保持常数( 对于0 t 1 ) 引理2 3 1 7 1设d 是r 空间的有界开集，设f ：万一r ”是连续函 数，如果y r ，y 譬f ( o d ) 以及d e 9 ( f ，d ，y ) 0 ，则f ( x ) = y 在d 中有 解 定理2 1设圣r ，k 是兄。空间中的非空闭凸子集设f ：r 斗 r ，g ：r x 0 ，1 】_ k 是连续函数，且当l i x l l _ + o 。时，i i g ( x ，1 ) l l 。十o 。 假设v i ( k ，f ) 无解则 ( i ) 设d e 9 ( 9 ( 石，1 ) 一9 ( 圣，1 ) ，耳，0 ) 0 则对任意a 0 ，1 ) ，v i ( k ，f ) 有关于 圣的o l 一侧外簇 ( i i ) 设9 ( z ，1 ) 是1 1 的，且2 9 ( 空，1 ) k 则v i ( k ，f ) 有关于畲的1 一例 外簇 注2 2 ：易见，当o = 0 ，g ( x ，t ) = ( 1 一t ) z + 如时，( i ) 是文献 1 中 的定理1 1 而当o = 1 ，9 ( z ，t ) = z 时，( i i ) 是文献 2 】中定理2 1 证明：记 b r ：= z r ：i l 。| | 忙l l ， 珥s ，t ， o ，1 ，使得 0 = 日( 研，0 ) 否则，存在铂 忙i i 使得 0 隹 日( 茹，t ) ：写只，t 0 ，1 j ) 这样，由引理2 2 ， d e g ( h ( x ，o ) ，氏，0 ) = d e g ( h ( x ，1 ) ，o ) 4 ( 2 2 ) 存在 ( 2 3 ) ( 2 4 ) 注意到，由( 2 2 ) 式和( i ) 中的假设， d e g ( 9 ( 茁，1 ) 一g ( 岔，1 ) ，b r o ，0 ) = d e g ( h ( x ，1 ) ，b r 。，0 ) 0 ， 所以由( 2 4 ) 式，d e g ( h ( x ，o ) ，b 。0 ) 0 由引理2 3 ， h ( z ，0 ) = 9 ( z ，0 ) 一p k ( g ( z ，0 ) 一f ( g ( z ，o ) ) ) = 0 在耳。内至少有一解根据引理2 1 ，v i ( k ，f ) 有解，这与假设矛盾因此， 对任意r 恻i ，存在研s ，t ，【0 ，1 ，使得( 2 3 ) 式成立，即 e ( z ，t ，) = ( 1 0 ) 尸：k b ( 。，t ，) + 0 0 雪( 奎，t ，) 一( 1 一耐，) f 0 ( 。，t r ) ) 】( 2 5 ) 下面我们证明t ，( 0 ，1 ) 事实上，若t r = 0 ，由( 2 5 ) 式得，g ( x ，0 ) 一 p k ( g ( 研，0 ) 一f ( g ( x ，o ) ) ) = 0 ，与v i ( k ，f ) 无解矛盾若t ，= 1 ，e h ( 2 5 ) 式得，g ( z ，1 ) 一口( 岔，1 ) = 0 这与条件恻i _ + o 。时，i i g ( x ，1 ) | | 斗+ 。矛 盾这样，由( 2 5 ) 式我们得 掣= 攻 ) 捌她一( 1 - a t r ) ( 础) ) 】，( 2 6 ) 即止1 - - 盘t rj 是下面方程的唯一解： 瓣 l l v 一( 口( t r ) + 。t r 9 ( 圣，o ) 一( 1 一n 4 ) f ( g ( t r ) ) ) 协 于是 一。可e ( x r , t _ r ) 叫卅咖( 训+ ( 1 一乜舻( 旭堋】坛( 掣) 即 一 击( 抵刊训) + f ( 堋】坛( 剖) 根据定义2 1 ， 研) ，。+ 。cr 是v i ( k ，f ) 在岔点处的a 一例外簇 ( i i ) 设g ( z ，1 ) 是1 1 的，且2 9 ( 奎，1 ) k 作函数h ：r 【0 ，1 - r 如下： h ( z ，t ) = ( 1 + t ) g ( z ，t ) 一斥b ，t ) + 幻 ，t ) 一( 1 一t ) f ( g ( x ，t ) ) 下证对任意r 蚓i ，存在研s ，t ， 0 ，1 】使0 = h ( x ，0 ) 否则，存在 r o 恻l 使得 0 隹t 日。( g ，t ) ：z s r 。，t 【0 ，1 】) 5 这样，由引理2 2 ， d e g ( h ( x ，o ) ，b 。0 ) = d e g ( h ( x ，1 ) ，b r o ，o ) ( 2 7 ) 下证岔是方程 h ( x ，1 ) = 2 9 ( x ，1 ) 一p k ( g ( z ，1 ) + 9 ( 童，1 ) ) = 0 的唯一解不妨设x + 是h ( x ，1 ) = 0 的另一个解则 2 9 ( x + ，1 ) = p ；c ( g ( x + ，1 ) + 9 ( 圣，1 ) ) 即2 9 ( x + ，1 ) 是 驶m 一( 9 ( z + ，1 ) + 9 ( 圣，1 ) ) 0 ) 的唯一解于是 一 2 9 ( z ，1 ) 一( g ( x + ，1 ) + g ( 圣，1 ) ) 】n ；c ( 2 9 ( x + ，1 ) ) 从而 ( 9 ( 岔，1 ) 一9 ( z + ，1 ) ，y 一2 9 ( x + ，1 ) ) 0 ，vy k ( 2 8 ) 将y = 2 9 ( 圣，1 ) k 代入( 2 8 ) 式有 怕( 岔，1 ) 一9 ( x 4 ，1 ) l i = 0 注意到，9 ( z ，1 ) 是1 1 的，所以矿= 圣，从而h ( x ，1 ) = 0 的解唯一由拓扑 度的定义知i d e g ( h ( x ，1 ) ，b r 。，0 ) l = 1 从而由( 2 7 ) 知，d e g ( h ( x ，o ) ，b r 。，0 ) = 咖( g ( 石，t ) 一p k ( g ( z ，t ) - f ( g ( x ，t ) ) ) ，b r 。，0 ) 0 类似( i ) 中的证明，v i ( k ，f ) 在b ，。内有解与已知y f ( k ，f ) 无解矛盾因此有 0 = h ( x ，t ，) = ( 1 + 0 ) g ( z ，t ，) 一致b ( 研，t ，) + t r g ( 岔，t r ) 一( 1 0 ) f ( 9 ( 研，0 ) ) ( 2 9 ) 若t ，= 0 ，由( 2 9 ) 式得，g ( 研，o ) - p k ( g ( = ，o ) 一f ( g ( z ，o ) ) ) = 0 与v i ( k ，f ) 无解矛盾若t ，= 1 ，由( 2 9 ) 式得 2 9 ( x ，1 ) 一p k ( g ( x ，1 ) + 9 ( 童，1 ) ) = 0 ( 2 1 0 ) 由于当r 充分大时，j i g ( z ，1 ) 1 i - + o o ，故i i g ( z ，1 ) 1j 怕( 癣，1 ) m 从而， i i p k ( g ( z ，1 ) - fg ( 岔，1 ) ) 0 一i i g ( 金，1 ) 1 l i i r k ( g ( = ，1 ) + g ，1 ) ) 一p , c ( g ( e ，1 ) ) i i g ( z ，1 ) 1 1 6 于是 l i p k ( g ( x ，1 ) + g ( 岔，1 ) ) | | 恻i ，t r ( 0 ，1 ) ， ( 1 + 0 ) 9 ( z ，t r ) = p k b ( z ，亡r ) + 0 9 ，t ，) 一( 1 一亡r ) f c g ( g ，0 ) ) 】k ( 2 1 1 ) 从而( 1 + 0 ) g ( 研，0 ) 是 瓣m 一( g ( 亡r ) + t r g ( 圣，亡r ) 一( 1 一o ) f ( g ( t 圳m 的唯一解故 一( g ，0 ) 一9 ( 圣，t ，) ) + ( 1 0 ) f ( g ，0 ) ) 1 k ( ( 1 + 靠) g ( z ，0 ) ) ( 2 1 2 ) 即 ， 、 一 击小舭冉) ) 啪) ) 】胀( 掣) 其中e ( z ，t ) = ( 1 一a t 2 ) g ( z ，t ) 一( 1 一血) 幻( 岔，t ) ，o l = 1 由定义2 1 知， 研) ，+ 旧c 兄是v i ( k ，f ) 在圣点处的1 一例外簇 口 推论2 1 在定理2 1 的条件下，如果存在圣r ”使v s ( k ，f 】在童点 无q 一例外簇，则v i ( k ，f ) 有解 2 2 r 空间中变分不等式无。一例外簇的条件 定理2 2 设kc r 是一非空闭凸集，f ：r _ + r ，g ：r 【0 ，1 】- - + k 是连续的，且满足g ( x ，1 ) 是1 1 的若存在点岔r n ，满足2 9 ( 圣，t ) k 使每个序列 研) ck 且i i 研j | _ + 。o ( r _ + 。) 均存在珥，任意t ( 0 ，1 ) 有 i i 研| | 怕p ，t ) i i 使 ( z ，一g ( 岔，t ) ，f ( x ，) ) 0 ( 2 1 3 ) 则v i ( k ，f ) 在圣处无口一例外簇陋( 0 ，1 ) ) 证明；假若v i ( k , f ) 在圣点有。一例外簇，则由定义2 1 知t ( ) ，旦忱i i = + 。o ，且，旦l i g ( z r ，t ) l l = + 。； ( i i ) 对于任意的。，r 存在t r ( 0 ，1 ) 使得 ( 击。，“) 一f ，。) ) + f 。，。) ) ，一 ( 1 一a t ；) g ( x ，t ，) 一( 1 业鲤1 2 ) o 1 一t ， 其中y 是k 中的任一向量 注意到， 9 ( 岔，t ，) k ，2 9 ( 岔，t r ) k ，令y = ( 1 + a t ，) 9 ( 圣，t ，) k 把! ，代 7 入上式并整理得 ( 击( f ( o ) 一g ( 圣，o ) ) + f ( 9 ( m 9 ( 童，o ) 一9 ( o ) ) o 于是 ( f ( g ( o ) ) ，9 ( 4 ) 一9 ( 圣，。) ) 茎一击似o ) 一9 ( 岔，圳2 因当r _ 十0 0 时，怕( 研，t ，) | | _ o o ，从而存在x ，使( 研，t r ) i | l i g ( i ，t r ) i i ，所 以 ( f ( g ( x ，0 ) ) ，9 ( 研，t ，) 一g ( 岔，0 ) ) 0 ( 2 1 4 ) 因9 ( 研，t ，) k ，g ( 圣，t r ) k 且怕( 研，t ，) i | - o o ( 1 1 z ，| | - o o ) ，于是( 2 1 4 ) 式 与( 2 1 3 ) 式矛盾，从而假设不成立故v i ( k ，f ) 在圣点无一例外簇口 定义2 2 称函数f ：r “- or “在k r 中伪单调若v x ，y k ，x y ，有( f ( 。) ，y x ) 0 = ( f ( ”) ，y z ) 兰0 注2 3 ：当f 是伪单调时，v i ( k ，f ) 有解的条件也是必要的 推论2 2 设k 是r ”中的非空闭凸子集，f ：兄”叶r ”，g ：r ”- k 是连续函数，若存在圣r 满足任意t ( 0 ，1 ) 有2 9 ( 圣，t ) k 使 r ( 岔) = 。k ：( 茁一g ( 圣，t ) ，f ( z ) ) 0 ，设函数 f ：r 斗r 是连续的，h ：【o ，1 】耳_ r n 连续，且h ( t ，茁) = ( 1 一a t ) x c l t x o t p k 【( 1 一o t ) 一f ( z ) ) 一t y t x o 当。碧 日( t ，霉) ，z a 日，t 【0 ，1 1 时，h ( 1 ，x ) = o 在目内有解 证明： 因f ( ) ，p k ( ) 是r 上的连续函数，于是日( ，) 是其定义域上 9 的连续函数由假设知 0 隹 日0 ，x ) ：z o b r ，t 0 ，1 1 根据引理2 2 得 d e g ( h ( o ，卫) ，研，0 ) = d e g ( h ( 1 ，z ) ，日，0 ) 又因h ( o ，x ) = x = 0 在缉内有唯一解故l d e g ( h ( o ，z ) ，b r ，o ) l = 1 ，从而 i d e g ( h ( 1 ，茁) ，耳，o ) i = 1 由引理2 3 知h ( 1 ，x ) = 0 在b r 内有解 口 引理3 2 设k 是r 中非空闭凸锥，。o k ，q ( 0 ，1 ) 设函数日： 0 ，1 】耳_ r 连续，且h ( t ，x ) = ( 1 一a t ) x a t x o t p k ( 1 一口t ) 扛一 f ( z ) ) 一a t x o 若存在z + 耳使得 h ( 1 ，x + ) = o 则n c p ( k ，f ) 是可行的 证明：由假设知 0 = h ( 1 ，x + ) = ( 1 一n ) z + 一口z o p , d 0 一o ) ( 。+ 一f ( 峦+ ) ) 一a x o 即 ( 1 一n ) $ + 一o 。o = p k ( 1 - - a ) ( x + 一f ( x + ) ) 一q z o ( 3 1 ) 这样，由性质c 1 ，( 3 1 ) 式得 ( ( 1 一) f ( 石+ ) ，y ) 0 ，v y 因为q ( 0 ，1 ) ，所以f ( x + ) k + 又由( 3 1 ) 式得 ( 1 一) 。+ = o 俘o + 尸k ( 1 一o ) ( 茹一f ( 茁+ ) ) 一口石o ) 】 因x 0 k ，p , d 0 一o ) ( z + 一f ( 矿) ) 一a z o ) 】k ，且k 为锥，则有矿k 于 是矿为n c p ( k ，f ) 的可行点从而g c p ( g , f ) 是可行的 口 在文献l ：i _ 0 】中，g i s a c 在k 是满足k c k 或k = k 的闭凸锥的条件 下，给出了例外簇的概念在此我们摒弃了k 的限定条件，定义了n c p ( k ，f ) 的一种新的例外簇 定义3 1 设z o 为中任一点，0 0 ，存在t ，( 0 ，1 ) 使 1 ，= ( 1 一n o ) ( f ( 茹，) 一。，) + ( 一a ) z ，+ a ( o 一1 ) x o b t 满足札，k + 及( “，( 1 一q 0 x ，一a t ，石o ) = 0 定理3 1设kcr 是非空闭凸锥，x o 为k 中任一点令f ： r 斗r 是连续函数，则n c p ( k ，f ) 是可行的或者在x o 点有。一例外 簇陋( 0 ，1 ) ) 证明；对任意q ( 0 ，1 ) ，下面分两种情况讨论 ( i ) 存在r 0 ，使a ( t ，x ) o ，v x a 研，t 0 ，1 】 根据引理3 1 知 h ( 1 ，z ) = ( 1 一q ) z o z x 0 一j ( 1 一q ) ( z f ( z ) ) 一o t x 0 】= 0 在b ，内有解，不妨令解为z + 则由引理3 2 知n c p ( k ，f ) 是可行的 ( i i ) 任意r 0 ，存在耳o b r ，t ， 0 ，1 使h ( t ，x ，) = 0 即 ( 1 一a t ，x ，一a t r x o 一辞尸k ( 1 一a t ，) ( z ，一f ( x ，) ) 一a t ，x o 】= 0 ( 3 2 ) 下面我们证明t r ( 0 ，1 ) 事实上，若0 = 0 ，由( 3 2 ) 式知x ，= 0 与研a 研 矛盾若t ，= 1 ，由( 3 2 ) 式知x ，是 h ( 1 ，z ) = 0 的解这样，由引理3 2 知n c p ( k ，f ) 是可行的因此，n c p ( k ，f ) 或者 可行或者任意r 0 ，存在斟o b r ，t ，( 0 ，1 ) 使( 3 2 ) 式成立，即 坠型学= 刚1 - c z t r ) ( x r - f - - a t r x o 】( 3 3 ) 由性质c 1 ，( 3 3 ) 式得 1 ( ( 一1 一a + o l t r ) x ，+ ( a t r o ) 岱o + ( 1 一口如) f ，) ，y ) 0 ，v y k 令 u ，= ( 1 - a t r ) ( f ( 研) 一研) + ( 丢一d ) x r + a ( t r 一1 ) 茹。 我们有 ( i t ，鲈) 0 ，v y 皿 故u ，k + 由c 2 ，( 3 ，3 ) 式得 1 ( u ，( 一d ) 岱，一。o ) = 0 b r 因i b i | - + o o ( r - - + o 。) ，根据定义3 1 ，( 研) ， 0 是n c p ( k ，f ) 在x o 点的o t 一 例外簇 口 推论3 1设k cr ”是非空闭凸锥，令f ：r _ + r 是连续函数 如果n c p ( k ，f ) 在k 中某一点不存在定义3 1 中的例外簇，则n c p ( k ，f ) 是可行的 1 2 第四节下降法解广义预变分的误差界问题 在本节，我们考察广义的预变分不等式问题( e p v i ) 设函数f ：r _ r “，卵：r ”r ”_ r 1 和，：r ”_ r 均为连续可微函数，且卵( z ，。) = 0 ，y x r 所谓的广义的预变分不等式问题( e p v i ) ( 见 7 d ：即求x 0 r 使得 ( f ( x o ) ，7 7 ( z o ，) ) f ( x o ) 一，( g ) ，v y 冗“ 该问题已被一些作者所研究( 见【7 | ，i s ，【9 1 ) 为了求e p v i 的解，其中一个方 法是把e p v i 转化为求最小值的优化问题为此，我们定义g a p 函数 定义4 1 令k 为r 。中任一非空集合，函数0 ：k - r 被称为e p v i 的g a p 函数如果 ( i ) o ( x ) 0 ，比k ， ( i i ) o ( x o ) = 0 铮z o 是e p v i 的解 设函数咖：r 。r _ r 满足下匿的条件 g 1 ：曲在r 1 r 上连续可微 c 2 ：咖( o ，y ) 0 ，v x ，y r “ 凸：( z ，) 在。点一致强凸，即存在a 0 ，使任意。r 曲( 石，y 1 ) 一咖( 。，y 2 ) ( v 9 ( z ，2 ) ，y 1 一) + a l l 1 一y 2 | | 2 c 4 ：( z ，y ) = o 甘z = y c 5 ：v 。母( ，y ) = 一v 9 咖( ，掣) ，v z ，y r n c b ：i l v ，( z ，y 1 ) 一v ，咖( z ，y 2 ) l i l i l l y l 一b 0 ，v y l ，y 2 r 设卢 口 0 ，定义函数 五( z ) 2 ，m 。i n 。，妒i ( z ，可) ，i = n ，卢 其中诹 ，y ) = ( f ( 茹) ，叩0 ，y ) ) 一f ( x ) + i ( y ) + 钾1 0 ，y ) 我们定义函数乳口：r - r 如下 如口( 石) = 厶( z ) 一厶( 茹) i = o ，卢 易知，蚰口是我们把e p v i 问题转化为最优化问题的g a p 函数 在本节，我们首先证明阳是e p v i 问题的g a p 函数，然后考虑它的误 差界，进而给出一个e p v i 的算法首先我们假设e p v i 问题有解，且对任意 z r ，九( $ ，) 和咖( z ，) 有唯一的最小值点，分别记为拈( 。) 和耶( z ) 1 3 4 1e p v i 的g a p 函数 下面我们研究如口的一些性质 定理4 1令咖满足c l a ，则乳p 可微，且 v g 。口( 茹) = v f ( z ) ( z ，y 口( 石) ) 一口( 嚣，y 。扛) ) ) + f 0 ) ( v z 叩( 。，耶 ) ) 一v z 叩 ，啦( 。) ) ) + 芦v 。审( $ ，掣p ( z ) ) 一a v 。咖( 。，y 。( z ) ) ( 4 1 ) 证明，由f ( ) ，q ( ，) 及咖( - ，) 的可微性知，如口可微 因为 厶( z ) 一厶( z ) s( f ( z ) 一f ( z ) ，目( z ，蜘( z ) ) ) + ( f ( 2 ) ，叩( 2 ，乳( z ) ) 一q ( 茹，她( 。) ) ) 一f ( z ) + ， ) + q 咖( 。，( 茁) ) 一0 ，) ) f o ( z ) 一厶( z ) 2f ( z ) 一f ( 茹) ，叼( z ，掣。( 名) ) ) + ( f ( 。) ，叩( 名，可n 0 ) ) 一? 7 ( 。，如( 石) ) ) 一f ( z ) + f ( z ) + 血( z ，纨。( z ) ) 一“西0 ，蜘( z ) ) 所以 v 丘( z ) = v f ( z ) 卵( z ，g n ( z ) ) + f ( 。) v 。q ( z ，y o ( x ) ) 一v f ( x ) + n v 。曲( z ，y a ( z ) ) 故 v g 。口x ) = v f ( 。) ( 卵( z ，耶( z ) ) 一町( 。，掣。( z ) ) ) + f ( z ) ( v 。叩( z ，耶( 。) ) 一v z 叩( 。，! 如( z ) ) ) + z v 。( z ，3 忸( z ) ) 一口v 。咖( 茁，! n ( 。) ) 口 令假设条件a 为： a 1 ：v 。叩( z ，y ) = 一v ，叩( z ，) 推论4 1 令西满足q 一侥在假设a 的条件下，有v g 。z ( x ) = v f ( z ) ( ，7 ( 。，3 佃( z ) ) 一卵( z ，3 k ( 。) ) ) + v ，( 即( 。) ) 一v ，( ! 8 ( z ) ) 证明：因为( 石) ，y z ( x ) 分别是札( z ，f ) ，咖( 石，y ) 的最小值点，故 f ( x ) v ，叼( 篮，驰( 。) ) + 卢v ，( z ，g 忙( z ) ) = 一v ，( 卯( 。) ) ， f ( x ) v ，目( 口，g 如( z ) ) + q v y 咖( 。，s a ( 。) ) = 一v f ( u n ( 。) ) ， 于是，由条件侠，假设a l 和( 4 1 ) 式得 v g 口卢( z ) = v f ( z ) 扛，耶0 ) ) 一q 0 ，y 。( 口) ) ) + v ，( 淞0 ) ) 一v ，( ”。( 。) ) 口 1 4 命题4 1 函数g a 3 具有如下性质 ( 卢一q ) ( 茁，口( z ) ) g 卵( 。) ( 卢一口) ( 石，y a ( 茹) ) 这样，若咖满足g ，则有g a z ( x ) o ，v x r ” 证明：因 9 i 叩( z )( f ( z ) ，叩( z ，! n ( $ ) ) 一卵( z ，! b ( z ) ) ) + ，( ! k ( 。) ) 一，( 3 k ( 茁) ) + ( 卢一o ) ( z ，3 k ( z ) ) = ( 卢一) 咖( z ，! b ( z ) ) 同理 9 h 口( z ) ( 卢一o ) ( z ，o 忙( z ) ) 从而，由条件q 知，如口( z ) 0 ，v x r 。 口 引理4 1 n 如果| i 满足a a ，则v 9 咖( z ，y ) = 0 的充要条件是。= y 定义4 2 令f ：r - r ，q ：r xr ”一r 满足叩( z ，z ) = 0 如果， 和町满足下面的两个条件： ( 1 ) 任意z ，y d o m ( f ) ，有x + t u ( x ，y ) d 。m ( ，) ， ( 2 ) f ( x + q ( 。，口) ) 茎( 1 一t ) ，扛) + t f ( y ) ，v x ，y d o r a ( f ) 则称，关于叶是预凸的 如果，关于”预凸可微函数，则 f ( y ) f ( x ) + ( v f ( x ) ，町( 。，可) ) ，v x ，y d o m ( f ) ( 4 2 ) 事实上， ( v ，( z ) ，叩( z ，) ) = l 。i m ，。! 兰_ = ! 兰里! ! 掣 由定义4 2 中的( 2 ) 知； ( v ，( z ) ，卵( z ，) ) 茎 i m + 。卫! 。丛! l ；2 2 1 ：二盟 = ，( 掣) 一，( 。) 令假设a 2 为， a 2 ：v 卵( 石，z ) = ，且，关于叩是预凸的 引理4 2 令满足a a ，在假设a 2 下，如果任意茹r ，v ，啦( z ，x ) = 0 ，i = o ，卢则f ( z ) + v f ( x ) = 0 证明，因 啦0 ，x ) = ( f ( z ) ，v i 卵扛，。) ) + v f ( x ) + i v ，( z ，。) ，i = q ，卢 1 5 由引理4 1 ，假设a 2 知 v ，咖( z ，z ) = ( f ( z ) ，i ) + v f ( x ) = f - i ( x ) + w ( x ) = f ( x 1 + v ( x ) 由假设知 f ( x ) + v f ( x ) = 0 口 定理4 2令西满足岛，q ，在假设a 2 的条件下，对任意。r ( i ) x = y a ( 石) = y z ( x ) 的充要条件蛳( 。) = 0 ， ( i i ) x = ( z ) = 卯( z ) 的充要条件是z 是e p v i 的解 这样，g a z 是e p v i 的g a p 函数 证明：由命题4 1 知，如口( z ) 0 ，y x r ”我们首先证明( i ) 必 要性显然成立只需证充分性若9 。口( z ) = 0 ，则由命题4 1 及条件晚知 ( 。，淞( 。) ) = o 从而x = 驰( z ) ，这样，如( 茁) = 厶( z ) = 0 由假设可。( z ) 是 吡( 。，y ) 的唯一最小值点，故x = y a ( x ) = 耶( z ) 下证( 虮如果z 为e p v i 的解，则( f ( 。) ，町( 口，) ) 一，( z ) + i ( y ) 0 ，v y r “ 这样， 厶( z ) = ( f ( 。) ，叩( 茁，! k ( 茁) ) ) 一，( 。) + ，( 3 k ( 。) ) + o 咖( 茁，3 k ( z ) ) “西( z ，s h ( z ) ) 从而由条件伤，厶( z ) 0 另一方面 f o ( z ) 。，r a 。i n ，( f ( 。) ，叩( z ，可) ) 一，( z ) + ，( g ) + 。曲( z ，g ) 兰( f ( z ) ，7 0 ，z ) ) 一，( 。) + i ( x ) + n 咖0 ，茹) = 0 故厶( z ) = 0 同理可证如( 。) = 0 这样，我们有9 。口( z ) = 0 由( i ) 知 x = f 。 ) = 口口 ) 反过来，由口= ( z ) 且y c , ( x ) 是札( z ，y ) 的最小值点得 v 口九( 。，( z ) ) = 0 根据引理4 2 ，0 = f ( x ) + v ，( z ) 从而由( 4 2 ) 式得 0 = ( f ( x ) + v ，( z ) ，叩( z ，可) ) ，y y r n ( f ( z ) ，叮( 为s ，) ) + f ( y ) 一，( z ) 即z 是e p v i 的解因此由( i ) ，( i i ) 知：乳口( 盘) = 0 的充要条件是e p v i 有 解所以如口是e p v i 的g a p 函数 口 】6 定义4 3 设f ：r _ r 1 ，町：r ”r - r 我们称v f 关于町是 正定的，如果对任意的z ，y ，z r ，y 五满足 ( y z ，v f ( z ) ( 町( z ，y ) 一叩( z ，g ) ) ) 0 定义4 4 设f ：r v 斗r ，叩：r r _ + r ，设p 0 我们称f 关 于叩是p 一强单调的，如果对任意z ，y ，z r ，y z ，有 ( f ( v ) 一f ( z ) ，q ，y ) 一q ，z ) ) p o g z l l 2 例如： f ：r 1 - r 1 ，满足f ( y ) = f ；叩 意y ，g r ，我们有 v ( x ，y ) 一叩 ，z ) = y 一。2 + 1 f ( y ) 一f ( z ) = y 一。 所以 r 1 r 1 斗r 1 满足彳( 。，y ) = 暂一2 + 1 对任 ( f ( g f 弘) ，”0 ，y ) 一q 扛，。) ) ) = ( y z ) 2 ；哂一z ) 2 故f 关于可是；一强单调 注4 1 ：当叩( 石，y ) = y 一。时，v f 关于叩正定即通常意义下的正定； f 关于叩是p 一强单调即通常意义下的p 一强单调， 定理4 。3 令满足g g 在假设4 。的条件下，若函数v ，是单调 函数，而且v f 关于叩是正定的，则当v g 叩( x ) = 0 时，x 是e p v i 的解 证明t 设v g 。z ( x ) = 0 则由推论4 1 知 v g a z 0 ) = v f ( z ) ( 町( z ，s c 8 ( z ) ) 一v ( x ， ) ) ) + v ，( 驰( z ) ) 一可，( 钝( 。) ) = 0 于是 ( v f 0 ) ( 町( z ，卯0 ) ) 一叩( 。，0 ) ) ) + v ，( 邬p ) ) - - v f ( y 。( x ) ) ，的0 ) 弛( z ) ) = 0 由v f 关于叩是正定及v ，单调知 ( v f ( z ) ( 印( z ，耶( 石) ) 一町( z ，y a ( 。) ) ) ，驰( z ) 一3 k ( 。) ) 0 ， ( v ，( 卯( z ) ) 一v ，( 拈( z ) ) ，珈( 。) 一如( 。) ) 0 于是 卵( z ) = ( 口) ( 4 3 ) 将( 4 3 ) 代入定理4 1 中的v 啦口( 茹) ，结合v 如口( $ ) = 0 得到v ，( 。，( 石) ) = 0 由引理4 1 得石= 弧( z ) = 鲫0 ) 由定理4 , 2 ( i i ) 知z 是e p v i 的僻 口 1 7 4 2 函数! 五万的局部误差界 设h ：r ”- r 的实值函数，设s 是问题 舢m i n ， ( 。) 的解集- 设r = 。m 。r i n ， ( z ) 若存在5 0 使得 d s ( x ) 5 ( h ( x ) 一下) 则称6 为h 对s 的误差界 令假设条件a 3 ，a 4 为t a a ：i l 卵( z ，y ) 一q ( z ，z ) l i 茎l i z 一l i ，比，y ，z r a 4 ：( f ( y ) 一f ( z ) ，叩( z ，y ) 一即( z ，z ) ) p i i 一z i m v x ，y ，z r 即f 关 于”是肛一强单调的 在这一部分，我们要求z 兰x 声，f 是l i p s c h i t z 连续的( l i p s c h i t z 常数 为l ) ，下面具体考虑函数菇万的