（运筹学与控制论专业论文）一类广义半无限规划问题的转化与算法.pdf

摘要 半无限规划在工程设计、最优控制、信息技术以及经济均衡等方面具有广泛 的应用，因此目前它已经成为最优化领域中非常活跃的一个研究分支。 近几年随着高新技术的发展和对社会经济行为的深入研究，广义半无限规划 问题出现在上述各种领域中，因此研究广义半无限规划问题具有重要的实际意义 由于对标准半无限规划问题，许多学者在理论研究与算法设计方面已经取得了很 多重要成果，因此在解决广义半无限规划问题时，最常见的方法就是在一定的条 件下将它转化为等价的标准半无限规划或有限规划来解决，比如利用增广拉格朗 日函数或罚函数就可实现上述等价转化。 本文主要针对一类广义半无限规划模型进行研究。主要思路是将广义半无限 规划模型转化为一族光滑函数方程，利用求方程解的牛顿型方法( l m 算法) 来 求解光滑函数方程。 第一章是本文的绪论部分，简要介绍了半无限规划的起源与发展和本文的主 要工作。 在第二章中我们将文献 3 0 3 2 】中的转化方法推广到广义半无限规划。首先在 广义半无限规划问题的最优解集x 处满足某些条件的前提下将广义半无限规划 模型转化为一个k k t 系统，引入一类n c p 函数，将此k k t 系统转化为一族半 光滑函数方程。我们对f b 函数做以修改使之修改后的函数是一个连续可微的 n c p 函数，从而得出了一个光滑函数方程。我们应用文献【2 9 1 对非线性方程组给 出的l m 算法来解决这个光滑函数方程，该算法具有全局收敛性，并且在局部 误差界的条件下，算法具有二次收敛速率。我们通过数值实验验证数值效果良好。 若能保证在水平集q 上光滑函数的j a c o b i a n 矩阵可逆条件成立，那么就能保证所 得到光滑函数方程的解为g s i p 问题的稳定点。 第三章针对广义半无限规划转化来的k k t 系统，我们又通过扰动的f b 函数 将此半光滑函数方程转化为一族光滑函数方程。设计了一个类似于l m 算法的 算法光滑型l m 算法，证明了算法的全局收敛性并且在光滑函数方程解集处满 足局部误差界的条件下证明了算法具有超线性收敛速率。最后通过数值实验验证 了算法的可行性。与文献 3 0 ，3 1 相比，我们给出的k k t 系统是固定维数的k k t 系统，而文献 3 0 ，31 】给出的刀+ ( m + q + 1 ) p 维的k k t 系统是一个p 随石变化而变化 的k k t 系统，并且我们将水平集上的j a c o b i a n 矩阵可逆的条件弱化为局部误差 界的条件。由于k k t 系统的维数的固定性，在算法中它不需要对p = l ，2 ，行进 行尝试，这相对减少了算法的计算量。而相比于第二章的l m 算法，虽然它的 收敛速度只具有是超线性收敛，但通过数值实验验证第三章的数值结果更精确一 些，且所用时间明显更少。 ， 关键词：广义半无限规划，光滑l m 算法，n c p 函数，全局收敛，超线性 收敛二次收敛 a b s t r a c t s e m i - i n f i n i t ep r o g r a m m i n gh a sw i d ea p p l i c a t i o n si n m a n yf i e l d ss u c ha s e n g i n e e r i n gd e s i g n ，o p t i m a lc o n t r o l ，i n f o r m a t i o nt e c h n o l o g ya n de c o n o m i c e q u i l i b r i u m i th a sb e c o m ea na c t i v ef i e l do fr e s e a r c hi no p t i m i z a t i o n r e c e n t l y ，w i t ht h ed e v e l o p m e n to fh i g ht e c h n o l o g ya n dt h ep r o f o u n dr e s e a r c ho n t h es o c i a l e c o n o m y , al a r g e n u m b e ro fm a t h e m a t i c a lm o d e l so fg e n e r a l i z e d s e m i - i n f i n i t ep r o g r a m m i n ge m e r g ei na b o v ef i e l d s t h e r e f o r e ，i ti sv e r ys i g n i f i c a n tt o s t u d yg e n e r a l i z e ds e m i - i n f i n i t ep r o g r a m m i n g b e c a u s em a n yi m p o r t a n tr e s u l t si n t h e o r e t i c a la n dn u m e r i c a la s p e c t so fc o m m o ns e m i i n f i n i t ep r o g r a m m i n gp r o b l e m sa r e o b t a i n e d ，w ec a nt r a n s f o r mt h eg e n e r a l i z e ds e m i - i n f i n i t ep r o b l e m si n t oc o m m o n s e m i i n f i n i t ep r o b l e m so rf i n i t ep r o b l e m s i np a r t i c u l a r , u s i n ga u g m e n t e dl a g r a n g e f u n c t i o n so r p e n a l t yf u n c t i o n si st h em a i nm e t h o dt oc o m p l e t et h ee q u i v a l e n t t r a n s f o r m a t i o n i n t h i sp a p e r ，w es t u d yaf o r m o fg e n e r a ls e m i i n f i n i t e p r o g r a m m i n ga n d r e f o r m u l a t et h ek k t s y s t e mo ft h eg s i pp r o b l e m si n t oas y s t e mo fs m o o t he q u a t i o n s g i v e nt h em a i nm e t h o do ft h es o l v i n ge q u a t i o n s - - l mm e t h o dw h i c hi so n e t y p eo f n e w t o nm e t h o d ，w es o l v et h ee q u a t i o n sb yi t t h i s c h a p t e r s c h a p t e r1 i st h ei n t r o d u c t i o no ft h i sp a p e r ,w h i c hi n t r o d u c e st h ed e v e l o p m e n to f s e m i i n f i n i t ep r o g r a m m i n ga n dt h em a i nr e s u l t si nt h i sp a p e r i nc h a p t e r2 ，w ee x t e n dt h et y p eo fr e f o r m u l a t i o no fs i p p r o b l e m st ot h eg s i p p r o b l e m s 【3 0 3 2 f i r s tw er e f o r m u l a t eg s i pp r o b l e mi n t oas y s t e mu n d e rs o m e c o n d i t i o n sa tt h es e tx t h a ti st h es e to fm i n i m i z e so fg s i pp r o b l e m s t h e nb y i n t r o d u c i n go n ef o r mo fn c pf u n c t i o n sw er e f o r m u l a t et h ek k t s y s t e mi n t oas y s t e m o fs e m i - s m o o t he q u a t i o n sa n dw ec h a n g et h ef o r mo f f b f u n c t i o nt om a k es u r e c o n t i n u o u s l yd i f f e r e n t i a b l eo ft h ek k ts y s t e ma n dt h es e q u e n c eg e n e r a t eb yl - m m e t h o di nr e f e r e n c e 2 9 】w h i c hi st h em e t h o dt os o l v et h en o n l i n e a re q u a t i o n s c o n v e r g et ot h es o l u t i o ns e tw h i c hi st h em e r i tf u n c t i o n ss t a i o n a r yp o i n to ft h e s m o o t hf u n c t i o nq u a d r a t i c a l l yu n d e ral o c a le r r o rb o u n do ft h es y s t e mo f s m o o t h i n g e q u a t i o n s a tl a s tw ei l l u s t r a t et h eg o o dp e r f o r m a n c eo ft h em e t h o db yn u m e r i c a l r e s u l t s b u tb e c a u s et h ej a c o b i a nm a t r i xn o n s i n g u l a r i t yc o n d i t i o ni sw e a k e nt ob et h e l o c a le r r o rb o u n dc o n d i t i o n i fw ec a ng u a r a n t e et h en o n s i n g u l a r i t yc o n d i t i o ni nt h e l e v e ls e tqt h es o l u t i o nw eg e ti st h es t a t i o n a r yp o i n to ft h eg s i pp r o b l e m s i nc h a p t e r3 ，w es o l v et h ek k t s y s t e mo ft h eg s i pp r o b l e m sb ya n o t h e rm e t h o d b yu s i n gap e r t u r b e df i s h e r b u r m e i s t e r f u n c t i o nw er e f o r m u l a t et h es y s t e mo f s e m i s m o o t he q u a t i o n si n t oas y s t e mo fs m o o t he q u a t i o n sa n dw ed e s i g nas m o o t h i n g l mm e t h o df o rs o l v i n gt h i ss y s t e m t h e nw ep r o v et h em e t h o di sg l o b a l l ya n du n d e r al o c a le r r o rb o u n dc o n d i t i o nf o rt h es y s t e mo fs m o o t he q u a t i o n st h em e t h o di s s u p e r l i n e a r l yc o n v e r g e n t c o m p a r ew i t ht h er e f e r e n c e 【3 0 ，31 】o u rs y s t e mi sa i n v a r i a b l e d i m e n s i o n a l s y s t e m b u t t h e s y s t e m o ft h e p a p e r 3 0 ，31 i s a v a r i a b l e d i m e n s i o n a ls y s t e mb e c a u s e pv a r i e sw i t h 工a n dw eu s et h ea s s u m p t i o n o fl o c a le r r o rb o u n di n s t e a do ft h en o n s i n g u l a r i t yc o n d i t i o nt h el e v e ls e tqt h a ti s w e a k e rt h a nt h en o n s i n g u l a r i t yc o n d i t i o n a tl a s tw ei l l u s t r a t et h ep e r f o r m a n c eo ft h e m e t h o db yn u m e r i c a lr e s u l t s b e c a u s eo ft h ei n v a r i a b l e d i m e n s i o n a ls y s t e m ，t h e a d v a n t a g ei st h a tw en e e d n tt r yp = 1 ，t h e np = 2 ，a n ds oo n c o m p a r ew i t ht h em e t h o d i nc h a p t e r2i tp r o v e sab e t t e rp e r f o r m a n c eb yn u m e r i c a lm e t h o d a n dt h et i m e si tn e e d i sl e s sa l t h o u g ht h es m o o t h i n gi sj u s ts u p e r l i n e a r k e yw o r d ：g e n e r a l i z e d s e m i i n f i n i t e o p t i m i z a t i o n ，s m o o t h i n gl m m e t h o dn c pf u n c t i o ng l o b a l c o n v e r g e n t ，s u p e r l i n e a r q u a d r a t i c a l c o n v e r g e n t 符号表 本文所用符号，除特别说明外，均按如下规定： 1 尺”表示n 维欧式空间 2 r 表示实数集，表示自然数集 3 w ( x ) 表示f ( x ) 在x 点处的梯度向量 4 s u p 表示取上确界，m a x 表示取最大值，m i n 表示取最小值 5 表示属于，芒表示不属于，j 表示存在，v 表示任意 6 表示因为，表示所以 7 = 表示等于，表示不等于 8 专表示趋向于 9 x 7 表示向量工的转置 曲阜师范大学博士硕士学位论文原创性说明 ( 在口划“”) 本人郑重声明：此处所提交的博士口硕士叫论文一类广义半无限规 划问题的转化与算法，是本人在导师指导下，在曲阜师范大学攻读博士口 硕士酵羊位期间独立进行研究工作所取得的成果。论文中除注明部分外不包 含他人已经发表或撰写的研究成果。对本文的研究工作做出重要贡献的个人 和集体，均已在文中已明确的方式注明。本声明的法律结果将完全由本人承 担。 作者签名： 咄1 卫受 日期：沙7 ， 曲阜师范大学博士硕士学位论文使用授权书 ( 在口划“) 一类广义半无限规划问题的转化与算法系本人在曲阜师范大学攻读博士 口硕士醋生位期间，在导师指导下完成的博士口硕士呼羊位论文。本论 文的研究成果归曲阜师范大学所有，本论文的研究内容不得以其他单位的名 义发表。本人完全了解曲阜师范大学关于保存、使用学位论文的规定，同意 学校保留并向有关部门送交论文的复印件和电子版本，允许论文被查阅和借 阅。本人授权曲阜师范大学，可以采用影印或其他复制手段保存论文，可以 公开发表论文的全部或部分内容。 作者签名：客1 旦复 - , g m i 签g , ：匀乡乏耖 ：h o 尸彳 ：伽口罗石 ， 舭缝杰煮 曲拿择范大学- - - 0 0 l 硬士学位论文 第一章绪论 1 1 半无限规划的起源与发展 半无限规划问题最早出现于2 0 世纪6 0 年代，其早期理论主要由c h a r n e s 等 人创立，k o r t a n e k 1 i 、l o p e z 2 3 1 和p o l a k 4 别等人在这方面做了大量的工作。作为数 学规划的一个分支，其研究引起了国内外学者的广泛关注，现已成为数学规划 的一个重要研究方向。19 9 7 年p o l a k 5 1 对半无限规划概括出三类标准模型，分别 建立了他们的最优性条件并给出了一些有效的算法。这三类标准模型分别是： 1 ) 半无限极大极小规划( s m m p ) ： m i n f ( x ) ：z r ”) 厂( 工) = m a x f 7 ( z ) ：歹j ) 2 ) 带不等式约束的半无限规划( s i c p ) ： m i n f o ( 工) ：f 。( x ) s0 ，_ ，j ) 3 ) 带等式和不等式混合约束的半无限规划( s i e c p ) ： r n i n f o ( x ) ：。( x ) o ，j ；g ( x ) = 0 其中： f ( x ) = m a x 矽。( 工，少) ：y l ) j = ( 1 ，2 ，g 7 ：r ”r 唧哼r ，一r m , ，j u o ) ，g ：r ”一r 7 ( ，甩) 对于这些标准半无限规划问题，许多学者在理论研究与算法设计方面已经 取得了很多重要成果。在理论方面，k a w a s a k i 在【6 ，7 】中对模型( s m m p ) 建立 了二阶最优性条件，黄力人和吴恭孚在【8 】中实质性地改进了上述二阶最优性条 件。对于第二个模型( s i c p ) ，b o n n a n s 和s h a p i r o t 9 1 对它进行了摄动分析，建立 了稳定性定理。在算法的研究方面，文献【10 】建立了路径最优逼近法；文献 【5 ，1 1 ，12 】和 13 1 建立了离散化逼近法；文献【1 4 】给出了极大熵方法；以及文献【15 】 一类产叉半毛眼规划问题的转化与霉法第1 页 骢缝杰煮 曲阜洚范大学- - 0 0 2 z 硕士擘位论走 建立了s q p 方法等，都是有效的具有收敛性的方法。关于标准的半无限规划问 题的已有成果还可参考其它文献，例如文献【1 6 2 1 】等。 近年来，随着高新技术的发展，广义半无限规划受到越来越多的关注文献 2 2 2 6 】 研究的广义半无限规划问题是将模型( s i c p ) 中的l 推广为集值映射f ( x ) ，并在f ( 力一 致紧致的条件下，给出了一阶及二阶最优性条件。而关于广义半无限规划问题的算法研 究方面，最常见的方法是将广义半无限规划问题转化为一个半无限规划问题，然后利 用解决半无限规划问题的方法来求解广义半无限规划问题，比如利用罚函数或增广拉格 朗同函数将广义半无限规划问题转化为半无限规划问题 2 7 ，2 8 】。 1 2 本文主要内容 在本文中，作者主要研究模型为： r a i n ( x ) ：g ( x ，y ) 0 ，v y 】，( x ) 的广义半无限规划问题。其中 y ( 砖= y e r ”：c j ( x ，y ) 0 ，歹= l ，留 我们首先在一定的条件下将模型转化为一族固定维数的k k t 系统，然后 引入非线性互补函数( n c p 函数) ，得到了一族半光滑函数方程，但由于此n c p 函数在( o ，0 ) 点处不可微，我们在第二章中对此n c p 函数做了一下修改，得到 了一族固定维数的光滑函数方程。直接利用【2 9 给出的l m 算法，得到了二次 收敛的数值效果，并且通过数值实验验证数值效果良好。在第三章针对转化而 来的广义半无限规划问题的半光滑函数方程，我们给此n c p 函数加了一项参 数占，此参数不为零，那么保证了n c p 函数的可微性，从而将半光滑函数方程 组转化为一族光滑函数方程，然后给出了一个光滑的l m 算法，证明了算法 的全局收敛性，并且在一定的条件下给出了算法的超线性收敛证明，通过数值 实验验证了算法的可行性并且数值效果比第二章中的算法的效果要好，且所需 时间更少。 一类广叉半无限规翘问题的转化与箕法第2 页 助q t a it , 辅h o r m a 。孽杰燕 曲阜 j 币范走学，二o o 九t 硕士学位论文 第二章一类广义半无限规划问题的转化及l m 算法的应用 本章作者主要讨论在广义半无限规划问题的最优解集x 处满足某些条件的前提下将广义半无 限规划问题转化成一个固定维数的k k t 系统，引入n c p 函数，通过修改的f b 函数，将此k k t 系统转化为一组光滑函数方程。应用l m 算法，该算法具有全局收敛性，在一定的条件下有二阶 收敛速度，通过数值实验验证了数值效果。 2 1 引言 对于广义半无限规划问题： g s i p ：m i nf ( x ) s tx s 其中，可行域s = 工r ”：g ( x ，少) 0 ，v y l ，( x ) ，而 y ( z ) = y r ”：c j ( x ，y ) o ，= l ，g ) ，函数厂：r ”jr ，g ：r ”xr “一r ， c ，：r ”r ”一r ，j = l ，q ，是二次连续可微函数。 当r ( x ) 暑y 时，问题( 1 ) 即是经典的半无限规划问题( s i p ) 。 设x 为问题( 1 ) 最优解集，又假设： v ( x ) = m a x g ( x ，y ) ：v y 】，( x ) ) ，r o ( x ) = y y ( x ) ：g ( x ，y ) = ，( x ) ) 。 那么对于给定的x ，r o ( x ) 为非线性规划问题： n l a x g ( x ，y ) s t 巳( x ，y ) o ，= l ，g 的全局最优解集，我们将问题( 2 ) 称为 三( x ，y ，w ) ：g ( x ，y ) 一圭叶勺( x ，y ) 为其l a g r a n g i a n j = l l a g r a n g i a n 乘子。 ( 1 ) ( 2 ) g s i p ( 1 ) 的内部问题。定义 函数，其中h ( - - l i 9 9 ) 为其 在参考3 揪 3 0 ，3 1 ，3 2 】中，l i q u n 。q i 等人在s i p 最优解集处满足广义m f 约束规范并且y 为非空紧致集的条件下将s i p 转化为一个维数为刀+ ( 柳+ p + 1 ) p 维的k k t 系统，其中 + ( 所+ p + 1 ) p 随着变量x 的变化而变化，然后通过f b 函 数将这个k k t 系统转化为一族半光滑函数方程，在本章中作者对f b 函数稍做 修改得到了一个连续可微的n c p 函数，应用于k k t 系统，得到了一族光滑函 一类广叉半无限规划问题的转化与算法 第3 页 骢骢杰曼 曲阜狰范大学- - - 0 0 2 z 颀士学位论吏 数方程。应用文献 2 9 】中的l m 算法来求光滑函数方程的解。通过数值实验证 明了数值结果良好。通过l m 算法所求得的解是光滑函数的价值函数的稳定点， 如果能在此解处保证j a c o b i a n 矩阵可逆，那么就能保证其为广义半无限规划问 题的稳定点。 2 2 广义半无限规划问题k k t 系统的转化 我们首先将广义半无限规划问题转化为一个固定维数的k k t 系统，然后引入n c p 函数及半光滑函数定义，将这个k k t 系统转化为一组半光滑函数方程。 2 2 1 广义半无限规划问题的k k t 系统 首先作出如f 假设： 假设2 1 ：对比r ”，】，( 功a ，并且r ( x ) 在解集z 上一致有界，即存在的x 的 一个邻域n ( x 。) = x r ”：d i s t ( x , x ) s 艿 和有界集z ，对v xen ( x ) 有y ( x ) t 。 假设2 2 ：广义m f 约束规范在x 上成立，即对v xes c j9 v y t o ( x ) ，w 为内部问 题( 2 ) 的l a g r a n g i a n 乘子，存在一个向量厅0 ，满足v ，l ( x ，y ，w ) 7 h 0 。 设假设2 1 与假设2 2 成立，当工r ，由文献 3 3 ，3 4 1 9 【i ，当v ( x ) = 0 存在 元0 ，( f = 1 ，2 ，刀) ，使得： 夥( x ) + 五v ，l ( x ，y ，w j ) = o ( 3 ) i = l 成立。 其中y 。t o ( x ) ，为内部问题( 2 ) 的关于y 的l a g r a n g i a n 乘子( i = 1 ，2 ，功。 又由于g ( x ，y ) = l ( x ，y ，w ) = v ( x ) = 0 ，所以有： 以0 ，g ( x ，y ) 0 ，2 , g ( x ，y ) = 0 f = 1 ，r ( 4 ) 而当v ( x ) 0 即v ( x ) 0 时，由文献 3 3 1 在假设2 1 的条件下有v ( x ) 在x 处是 上半连续的。可知x 为定义域s 的内点，那么有v f ( x ) = o 。可取五= 0 ，i = l ，刀， 一类广叉半无限规餮l 问题的转化与算法 锥4 页 遁多堂点璺点杰煮 曲阜狰范大学二o o 九磺士学往论吏 则( 3 ) 、( 4 ) 式同样成立。 下面考虑y k ( x ) ( 待1 ，? ) ，若内部问题( 2 ) 在y i 处满足一个约束规范， 如s l a t e r 约束规范，m f 约束规范等，那么y 。为内部问题( 2 ) 的k k t 点，因此 k k t 条件成立。即： v j ，三( 而y ，) = o ，( f = l ，厅)( 5 ) 杉o ，e j ( x ，y ) o ，杉c j ( x ，y ) = o ，( ，= 1 9 d9 q ，f = 1 ，玎)( 6 ) 于是由( 3 ) 一( 6 ) 组成了广义半无限规划问题的k k t 系统。 在k k t 系统中，工称为g s i p 的稳定点，a ，y 。( 江l ，2 ，刀) 分别称为k k t 系统的l a g r a n g i a n 乘子和到达点，w ：( 歹= 1 ，g ，i = 1 ，2 ，甩) 为k k t 系统的副 l a g r a n g i a n 乘予。 由于凸规划问题的k k t 点为全局最优点，我们作出如下假设： 假设2 3 ：g ( x ，) 为凹函数，c j ( x ，) ( j = l ，q ) 为凸函数。 相较于文献 3 0 ，3 1 】给出的p 随x 变化而变化的力+ ( m + 口+ 1 ) p 维的k k t 系统，此 k k t 系统的维数是固定，并在随后的算法中不需要对p = 0 ，l ，丹进行尝试，这相对减 少了算法的计算量。 2 2 2 半光滑函数方程 定义2 1 ( 1 3 0 ，3 l ，3 5 ，3 6 j ) ：函数矽：r 2 寸r 称为非线性互补函数( n c p 函数) ， 矽( 口，b ) = o 成立当且仅当满足条件口，b 0 且a b = 0 最常见的n c p 函数有两种类型： 矽( 口，6 ) = m i n a ，b 和 ( 口，b ) = 口2 + 6 2 一口一b 第2 种函数我们通常称为f b 函数。 定义2 2 ( 1 3 0 ，3 1 ，3 6 1 ) ：称函数f ：只”专足p 在x 处半光滑，若f 在刊怂方向可微， 一类广叉半无限规勘问题的转化与算法 第s 页 兽曼璧。孽杰煮 曲阜烽范太学二o o 九硕士学住论文 并且对v 矿卵( x + d ) ，d 一0 ，有； f ( x + d ) 一f ( x ) 一i d = o ( i idl i ) 和 f ( x ；d ) = v d + d ( 1 ld1 1 ) 其中a f 是f 的广义j a c o b i a n 矩阵，f ( x ；d ) 是，在x 点上沿方向d 的导数。 称局部l i p s c h i t z 函数，在在x 处强半光滑，如果满足： f 。( x ；d ) - v d = o ( i id | | 2 ) 由于f b 函数在( 0 , 0 ) 处不可微，所以f b 函数不是光滑函数，但它是强半 光滑函数( 见参考文献 3 7 】) 。 我们将f b 函数应用于k k t 系统，作出如下定义： n 缈( z ) = w ( x ) + a , v ，三( x ，y tw ) i = l i f ，( z ) = ( ( z ) ，虬( z ) ) r ( z ) = 如( 丑，- g ( x ，y ) ) f - l ，, ，( 2 ) = ( ( z ) ，厶( z ) ) r ( z ) = v j ，l ( x ，y 。，) i = 1 ，厅 ( z ) = ( 办( z ) 7 1 ，九7 ( z ) ) 7 谚( z ) = ( 谚。( z ) ，九( z ) ) ， c o ( z ) = ( 杉，一c ，( x ，y ) ) f - 1 ，”，j = l gj 9 9 胃0 ) = 9 ( z ) 沙( z ) ，( z ) ( z ) 其中z = ( x ，y ，y ”， ，矗，w ：，吖，睇) ，令t = 刀( 历+ q + 2 ) ，对z r ， h ( z ) 为半光滑函数，k k t 系统的求解就转变为求半光滑函数方程日( 2 ) ：o 的 一类广义半无限规笺l j 问题的转化与算法第6 页 量曼黧点杰篓 解。 2 2 3 光滑函数方程 曲阜烽范天学二0 0 九磺士学位论文 由于f ，g ，c j ，= 1 ，g 是二次连续可微的函数，我们对f b 函数作出修改， 提出如下形式： o f b ( a ，6 ) ：( 孺一口一6 ) ： 知，它在r 2 上是连续可微的。 令： 缈( z ) = ( 订( z ) ，以( z ) ) r ( z ) = q 朋( 丑，一g ( x ，少) i = l ，刀 ( z ) = ( ：( z ) 7 ，：( z ) 7 ) 7 ：( z ) = ( 1 ( z ) ，乙( z ) ) 7 ；( 2 ) = 邶( 嘭，- - c j ( x ，y ) ) f = 1 ，疗，= l ，q h ( z ) = 眇( z ) 杪( z ) ，( z ) ( 2 ) 有日( z ) 连续可微。那么，日0 ) 满足如下性质： 性质2 1 ：设z 为h ( z ) = 0 的解集，z z ，存在b ( 0 ，1 ) 和c l ( 0 ，) 满足 v h ( z 2 ) ( z l z 2 ) 一( 日。( z 1 ) - - h ( 乞) i 喀c l 毛一z 21 1 2 其中忱i ，z 2 ( z ，6 ) = z ：l lz - - z 。i i 0 ，使得： c l l z z i i 0 ，有： 1 1 日5 ( z ) 一h ( z ) i l 满足乙_ z ，( 七专o o ) ，取 等= i x 亏乏石瓦，以= f ：劈o , i = 1 ，m 劈= 小面万i 匹瓦，刀= ( f ，) ：菇o ，j = l ，g ，i = l ，甩) ， = 蚵n ( 等，；z ) ，( 菇，( i ，) 彳) ， 当争专。，( 七专) 时有 l i md i s t ( v h ( 缸) ，c 3 h ( z ) ) = 0 置+ 成立。 为方便起见我们分别记h ，v h 代表吼，v 日矗。 性质3 6 ： q ) 和 唧) 为正数序列，若对固定的口( 0 ，1 ) 满足： 吼口i + 吼一l ，k = 1 ，2 ， 并且& 0 ，使得： 一类广叉半无限规划问题的转化与算法 第n 页 墓胞镍熏 成立。 西阜烽范天学- 二0 0 y l 硕士学位论丈 c z z i i l lh ( z ) l iv z ( z ，6 ) 3 3 1 光滑l m 算法 s t e po ：选择初始点z o r ，e o ：= h ( z o ) i | 2 ，觞：= h 岛( 气) 1 1 2 ，口，y ，p ( o ，1 ) ，k - 0 s t e p1 ：若i jv h ( z a 7 h ( z di l - g ，停止。 s t e p2 ：巩满足如下关系式： ( p k l + v h 。( 气) 7 v ( 气) ) d = 一v ( 乙) 7 h ( 乙) 若i | h ( + d , ) l l ：若 气) 收敛到z 贝, 1 。l i m 。d i s t ( v h ( 乙) ，c 3 h ( 气) ) = 0 由算法知，引理1 显然成立。 利用引理1 我们有全局收敛性证明如下： 定理i - 设 气 由算法产生的序列，若 乙 存在一个聚点z ，那么z 为价值函数 一美广叉半无限规勘问题的转化与算法 第、4 页 鹭胞篓杰熏 曲车师范大学r 二0 0 , z 硕士学位论文 o ( z ) = 芝1i i ( z ) 1 1 2 的稳定点，o p oea 。( z ) 。进一步假设：v v o h ( z ) 都是可逆的， 则h ( z 1 = 0 ，z 的分量x 即是g s i p 的稳定点。 证明：( 反证法) 假若。仨a o ( z ) ，设序列 气) 为 乙) 的子序列，满足气- - - z ，f 一， 由引理l ，有： l i m d i s t ( v h ( 气) ，阳( 气) ) = 0 i - - a t o o 那么，有： l i m d i s t ( v o 一( 乙。) ，0 0 ( z k ) ) = , 0 j 。 则存在乇，当f f o 时，v o 屯( 气) o ，有h 电( 气) 0 ，吒o ， 有： v o t ( 气) 7 民= 一( ( 心，+ v 日一( 气) 7 v h 屯( 气) ) 吒) 7 矾 一n k , i i 以1 1 2 ( 7 ) 则算法产生的下一个迭代点气+ 。= 气+ 吒或气+ 。= 气+ p 仇吒 若气+ 。= 气+ 噍时， l ih t ( 气+ 1 ) i i - 2 i ih ( z 屯) 1 1 若z = z b + 矿d k j 时， 0 t ( 气+ 矿噍) t ( 气) + 印v e t ( 气) 7 吮 o o ，f 寸，p 批- 1 , o ，上式不成立。则是有上界的，那么，p i i 噍1 1 2 是 有下界的。即存在 乇时，有： 1 1 日屯( 气+ 1 ) i i r i i h t ( 气) i j 。 对v 七，由于喀为0 ( z ) 的下降方向，那么： h ( 气+ 。) 1 1 - q 证明：首先由于函数日( z ) l i p s c h i t z 连续，那么存在工r ，对任意的k 满足： l | 劈( 缸) l ll l 乙一7 | f ( 1 0 ) 又因为气一z ，( 七专) ，则当k 充分大时，气( z ，6 ) ，满足局部误差界条件。 根据性质3 4 、局部误差界条件及( 1 0 ) 有： c1 1 名一z i i - t lh ( z 女) 1 1 - 1 1h 。( 气) i i + 訇ih 。( 缸) 一h ( z ) + 跗( 气) ( z - z k ) + v ( 气) ( 缸一z 。) i i