（应用数学专业论文）互补约束优化问题若干算法研究.pdf

s t u d yo ns e v e r a la l g o r i t h m s f o rm 姐h e m j 姐i c a lp r og r a m s w i t hc o m p l e m e n t a r i t yc o n s t r a i n t s l i us h u i x i a s u p e r v i s e db yp r o f e s s o rc h e ng u o q i n g s c h o o lo fm a t h e m a t i c a ls c i e n c e s 。 i n n e rm o n g o l i au n i v e r s i t y ，h o h h o t ，0 1 0 0 2 1 o c t o b e r ，2 0 0 9 原创性声明 本人声明：所呈交的学位论文是本人在导师的指导下进行的研究工作及取得的研 究成果。除本文已经注明引用的内容外，论文c f r 不包含其他人已经发表或撰写的研究 成果，也不包含为获得内蒙古大学及其他教育机构的学位或证书而使用过的材料 与我一同工作的同志对本研究所做的任何贡献均已在论文中作了明确的说明并表示谢 意 学位论文作者签名； 日 期： 指导教师签名： 拯丝e t期：写逊 在学期间研究成果使用承诺书 本学位论文作者完全了解学校关于保留、使用学位论文的规定，即：内蒙古大学 有权将学位论文的全部内容或部分保留并向国家有关机构、部门送交学位论文的复印 件和磁盘，允许编入有关数据库进行检索，也可以采用影印、缩印或其他复制手段保 存、汇编学位论文为保护学院和导师的知识产权，作者在学期间取得的研究成果属 于内蒙古大学作者今后使用涉及在学期间主要内容或研究成果，须征得内蒙古大学 就读期问导师的同意；若用于发表论文，版权单位必须署名为内蒙古大学方可投稿或 公开发表。 么、 学位论文作者签名：玉塑兰塞指导教师签名：盘竺 日 期：辎掣日期：? 芦监 互补约束优化问题若干算法研究 摘要 互补约束优化问题( m p c c ) 在经济平衡、工程设计和多层对策等方面都 有着重要应用本文主要对互补约束优化问题的算法进行研究，所取得的 主要结果有： 1 利用互补问题的l a g r a n g e 函数，将互补约束优化问题( m p c c ) 转化为 等价的含参数非线性规划结合参数的修正公式，提出了求解互补约束优化 问题的乘子序列罚函数法讨论了算法产生的迭代序列聚点的可行性在互 补约束优化问题线性独立约束规范( m p c c l i c q ) 和上水平严格互补( u l s c ) 条件下，迭代序列收敛于m p c c 的b 一稳定点而且，若罚问题满足二阶必 要条件，m p c c 也满足二阶必要条件 2 提出了求解互补约束优化问题的乘子序列部分罚函数法无需二阶必 要条件，只要算法产生的迭代序列的聚点满足m p c c l i c q ，且聚点是m p c c 的可行点，则算法收敛于m p c c 的m 一稳定点另外，在u l s c 条件下，算 法收敛于m p c c 的b 一稳定点数值实验表明算法有效 3 利用互补问题的l a g r a n g e 函数，提出一种新的积极集识别函数将积 极集识别技术与乘子序列部分罚函数法相结合，提出求解互补约束优化问 题的混合法在u l s c 条件下，该方法具有有限步终止性质 4 提出了求解互补约束优化问题的乘子松弛法在较弱的条件下，互补 约束优化问题的松弛问题满足线性独立约束规范在m p c c l i c q 条件下， 松弛问题稳定点的任何聚点都是m p c c 的m 一稳定点无需二阶必要条件， 只在u l s c 条件下，就可保证聚点是m p c c 的b 一稳定点另外，给出了算 法收敛于b 一稳定点的新条件 5 结合互补问题的l a g r a n g e 乘子修正公式，提出了求解互补约束优化 问题的一种新的p s q p 法在较弱的条件下，算法收敛于m p c c 的分片稳定 点进而，若部分m p c c l i c q 成立，则算法收敛于m p c c 的b 一稳定点 6 利用极小化函数的熵函数，提出了求解互补约束优化问题的一种新 的光滑近似法当光滑因子趋向于零时，无需u l s c 或渐进非退化条件，只 在m p c c l i c q 条件下，证明了光滑近似问题满足二阶必要条件的k k t 点 序列收敛于m p c c 的b 一稳定点 关键词：互补约束优化问题，l a g - r a n g e 函数，罚函数，熵函数，二阶必要 条件，b 一稳定点 s t u d yo ns e v e r a la l g o r i t h m s f o rm a t h e m a t i c a lp r o g r a m s w i t hc o m p l e m e n t a r i t yc o n s t r a i n t s a b s t r a c t t h em a t h e m a t i c a lp r o g r a m sw i t hc o m p l e m e n t a r i t yc o n s t r a i n t s ( m p c cf o rs h o r t ) h a s m a n ys i g n i f i c a n ta p p l i c a t i o n si ne c o n o m i ce q u i l i b r i u m ，e n g i n e e r i n gd e s i g na n dm u l t i l e v e l g a m e s t h i st h e s i si sd e v o t e dt os t u d yt h ea l g o r i t h m sf o rs o l v i n gm p c c t h e m a i nr e s u l t s a r es u m m a r i z e da sf o l l o w s ： 1 u s i n gt h el a g r a n g i a nf u n c t i o no ft h ec o m p l e m e n t a r i t yp r o b l e m ，am a t h e m a t i c a l p r o g r a mo fc o m p l e m e n t a r i t yc o n s t r a i n t si sr e f o r m u l a t e da sag e n e r a ln o n l i n e a rp r o g r a m - m i n gp r o b l e mw i t ht h ep a r a m e t e r an e ws m o o t hm u l t i p l i e rs e q u e n t i a lp e n a l t ym e t h o d f o rs o l v i n gm p c ci sp r o p o s e db yt h es i m p l em o d i f i e ds t r a t e g yo ft h ep a r a m e t e r t h el e a - s i b l i t yo ft h el i m i t e dp o i n to ft h es e q u e n c eg e n e r a t e df r o mt h ea l g o r i t h mi sd i s c u s s e d w e s h o wt h el i m i t e dp o i n ti sb s t a t i o n a r yp o i n ti ft h em p c cl i n e a ri n d e p e n d e n c ec o n s t r a i n t q u a l i f i c a t i o n ( l i c q ) a n dt h eu p p e rl e v e rs t r i c tc o m p l e m e n t a r i t y ( u l s c ) h o l d m o r e o v e r ， m p c cs a t i s f i e st h es e c o n d o r d e rn e c e s s a r yc o n d i t i o ni ft h ep e n a l t yp r o b l e m ss a t i s f yt h e s e c o n d o r d e rn e c e s s a r yc o n d i t i o n 2 am u l t i p l i e rs e q u e n t i a lp a r t i a lp e n a l t ym e t h o df o rs o l u t i o no fm p c ci sp r e s e n t e d w i t h o u tr e q u i r i n gt h es e c o n d o r d e rn e c e s s a r yc o n d i t i o n ，w es h o wt h el i m i t e dp o i n to f t h es e q u e n c eg e n e r a t e df r o mt h ea l g o r i t h mi sm s t a t i o n a r yp o i n ti fi t i st h ef e a s i b l et o m p c ca n dt h em p c c l i c qh o l d s m o r e o v e r ，i ti sb s t a t i o n a r yp o i n ti ft h eu p p e rl e v e r s t r i c tc o m p l e m e n t a r i t y ( u l s c ) h o l d s n u m e r i c a le x a m p l e sa r eg i v e nt od e m o n s t r a t et h e e f f e c t i v e n e s so ft h em e t h o d 3 u s i n gt h el a g r a n g i a nf u n c t i o no fc o m p l e m e n t a r i t yp r o b l e m ，w ep r e s e n tan e w a c t i v es e ti d e n t i f i c a t i o nt e c h n i q u ea n da p p l yt ot h em u l t i p l i e rs e q u e n t i a lp a r t i a lp e n a l t y i n m e t h o d w ep r o p o s eah y b r i da l g o r i t h mf o rs o l v i n gm p c cw h i c hi st e r m i n a t i o ni nf i n i t e i t e r a t i o n su n d e ru l s ca s s u m p t i o n s 4 an e wr e l a x e dp r o b l e mo fm p c ci sg i v e n w es h o wt h a tt h el i n e a ri n d e p e n d e n c e c o n s t r a i n tq u a l i f i c a t i o nh o l d sf o rt h en e wr e l a x e dp r o b l e mu n d e rs o m em i l dc o n d i t i o n s a m u l t i p l i e rr e l a x e dm e t h o df o rs o l v i n gm p c c i sp r e s e n t e d t h el i m i t e dp o i n to fs t a t i o n a r y p o i n t so ft h er e l a x e dp r o b l e m si sm s t a t i o n a r yp o i n tu n d e rt h em p c c l i c q ，a n di ft h e u l s ch o l d sa tt h el i m i t e dp o i n t ，i ti sb s t a t i o n a r yp o i n t a tl a s t ，w ep r o p o s ean e w c o n d i t i o nf o rc o n v e r g e n c et ob s t a t i o n a r yp o i n t 5 an e wp i e c e w i s es q pa l g o r i t h mf o rs o l v i n gm p c ci sd i s c u s s e db yt h er e a s o n a b l e m o d i f i e ds t r a t e g yo ft h em u l t i p l i e ro ft h el a g r a n g i a nf u n c t i o no ft h ec o m p l e m e n t a r i t y p r o b l e m u n d e rm i l dc o n d i t i o n s ，t h en e wa l g o r i t h mi sg l o b a l l yc o n v e r g e n c et ot h ep i e c e - w i s es t a t i o n a r yp o i n t m o r e o v e r ，i ft h ep a r t i a lm p c c l i c qh o l d s ，t h e ni t i sg l o b a l l y c o n v e r g e n c et ob s t a t i o n a r yp o i n t 6 an e ws m o o t ha p p r o x i m a t i o nm e t h o di sp r e s e n t e df o rs o l v i n gm p c cb yt h e e n t r o p yf u n c t i o no ft h em i n i m i z a t i o nf u n c t i o n a st h es m o o t hp a r a m e t e rt e n d st oz e r o ， w i t h o u tr e q u i r i n gs t r o n ga s s u m p t i o n ss u c ha st h eu p p e rl e v e rs t r i c tc o m p l e m e n t a r i t y c o n d i t i o no rt h ea s y m p t o t i c a l l yw e a k l yn o n d e g e n e r a t ec o n d i t i o n ，t h el i m i t e dp o i n to f t h ek k t p o i n ts e q u e n c eo ft h es m o o t hp r o b l e m st h a ts a t i s f i e ss e c o n d o r d e rn e c e s s a r y c o n d i t i o ni sb s t a t i o n a r yp o i n ti ft h em p c c l i c qh o l d s k e y w o r d sm a t h e m a t i c a lp r o g r a m sw i t hc o m p l e m e n t a r i t yc o n s t r a i n t s ，l a - g r a n g i a nf u n c t i o n ，p e n a l t yf u n c t i o n ，e n t r o p yf u n c t i o n ，s e c o n d o r d e rn e c e s s a r yc o n d i t i o n ， b s t a t i o n a r yp o i n t l v ：= s t 兮 = 争 v 仍 皿n 皿礼m n 手 z + z f 7 ( z ) f 7 ( z ；h ) v f ( x ) o f ( x ) 如f ( x ) m t n c p m p c c m p e c m p c c l i c q m p c c m f c q m p c c s m f c q l l s c u l s c s o n c 符号说明付丐况明 在文中代表“定义为”或“记为” 受限于 等价 蕴涵 任意 实数域 实n 维空间 实n m 矩阵空间 在文中代表集合 1 ，2 ，m ) 互补约束优化问题的可行域 z 为n 维向量，矿足以对为第i 个分量的n 维向量 x 为n 维向量，x 一足以z _ 为第i 个分量的n 维向量 f ( x ) 的j a c o b 阵，也称作f ( x ) 的导数，即f 7 ( z ) ：= ( o r ( x ) o z j ) f ( x ) 在z 点处沿方向h 的( 广义) 方向导数 v f ( x ) ：= 【f 7 ( z ) 】t 是f ( x ) 的梯度 f ( x ) 的广义j a c o b 阵 f ( z ) 的b 一微分 矩阵m 的转置 非线性互补问题 互补约束优化问题 平衡约束优化问题 互补约束优化问题线性无关约束规范 互补约束优化问题m a n g a s a r i a n f r o m o v i t z 约束规范 互补约束优化问题强m a n g a s a r i a n f r o m o v i t z 约束规范 下水平严格互补 上水平严格互补 二阶必要条件 v 弱二阶必要条件 二阶充分条件 强二阶充分条件 i 1 ，2 ，m ) ig i ( z ) h i ( z ) ) 指标集 ii i ( x ) = o ) 指标集 zl 五( z ) o ) 指标集 ii 六( z ) o ) 指标集 ii 五( z ) o ) ， p ：= p ( 牙) ：= ig i ( 牙) = 0 ，皿( 牙) = o ，( 1 1 ) ，y ：= ，y ( 牙) ：= tg t ( 牙) 0 ，皿( 牙) = o 】， 其中p 称为退化指标集若p = p ，则称牙是非退化的 下面给出依赖于孟厂且与互补约束优化问题( 1 6 ) 紧密相关的两个非线性规划 1 7 ，6 1 】： 1 紧规划t n l p ( 2 ) m i n f ( x ) s t g ( x ) 0 ，h ( x ) = 0 ， g ( z ) = 0 ，凰( z ) 0 ，i q ， ( 1 2 ) g i ( x ) = 0 ，凰( z ) = 0 ，i p ， g i ( x ) 0 ，凰( z ) = 0 ，i 7 3 内蒙古大学博士学位论文 易知，t n l p ( 5 ：) ( 1 2 ) 的可行集足m p c c ( 1 6 ) 的可行集的子集这表明，若牙是 m p c c ( 1 6 ) 的局部极小，则牙是相应的紧规划t n l p ( 牙) 的局部极小 2 松规划r n l p ( 牙) m i n i ( x ) s t g ( x ) 0 ，h ( x ) = 0 ， g t ( z ) = 0 ，凰( z ) 0 ，i q ， ( 1 3 ) g i ( x ) 0 ，凰x ) 0 ，i p ， 皿( z ) = 0 ，g d x ) 0 ，i ，y 易知，若牙是松规划r n l p ( 牙) 的局部极小，且满足互补约束条件 g ( 孟) t 日( 雪) = 0 ， 则牙是m p c c ( 1 6 ) 的局部极小 1 2 1互补约束优化问题约束规范 众所周知，互补约束优化问题的任何可行点都不满足非线性规划约束规范，例如 线性独立约束规范( l i c q ) ，m a n g a s a r i a n f r o m o v i t z 约束规范( m f c q ) ，这使得典型的 k k t 条件( 对于非线性规划，在l i c q 或m f c q 成立的条件下，局部极小一定满足一 阶最优性条件) 不适用于互补约束优化问题，故需要建立适用于互补约束优化问题的约 束规范和稳定点概念互补约束优化问题的约束规范的建立与紧规划t n l p ( 牙) ( 1 2 ) 密 切相关【6 1 】，我们将以紧规划t n l p ( 孟) ( 1 2 ) 的约束规范来定义互补约束优化问题的约 束规范设z 歹，若t n l p ( x ) ( 1 2 ) 在z 处满足l i c q ( m f c q ，s m f c q ) ，则称互补约束 优化问题在z 处满足l i c q ( m f c q ，s m f c q ) ，分别记为m p c c l i c q ( m p c c m f c q ， m p c c s m f c q ) 具体定义如下： 1 互补约束优化问题线性独立约束规范( m p c c l i c q ) c 定义1 1 设x 厂，若向量组 v g t ( z ) ，i a ( x ) up ( z ) ，v 鼠( z ) ，i p ( z ) u7 ( z ) ， v g j ( x ) ，j 毛( z ) ：= 歹i 缈( z ) = 0 ， ( 1 4 ) v h l ( x ) ，2 = 1 ，2 ，g 4 第一章绪论 线性无关，则称在z 处满足m p c c l i c q 2 互补约束优化问题m a n g a s a r i a n f r o m o v i t z 约束规范( m p c c m f c q ) 定义1 2 设z ，若向量组 v g l ( z ) ，i o e ( x ) up ( z ) ，v 皿( z ) ，i 卢( z ) u7 ( z ) ， v h l ( x ) ，f = 1 ，2 ，g 线性无关，且存在向量v 卿，使得 v g t ( z ) t = 0 ，i a ( x ) up ( z ) ， v 鼠( z ) ? = 0 ，i p ( z ) u ，y ( z ) ， v h f ( z ) r v = 0 ，f - 1 ，2 ，g ， v g j ( x ) t 口 0 ， v h d z ) ，z = 1 ，2 ，g ( 1 5 ) ( 1 6 ) 线性无关，其中为紧规划t n l p ( x ) ( 1 2 ) 中对应于约束条件易( z ) 0 的乘子，且存 在向量v r n 与上面的向量组( 1 6 ) 正交， v g j ( x ) t 秒 0 ，v i 0 ，或u i v i = 0 ，v i p ( z ) ，则称z 是互补约束优化问题的m 一稳定 点； ( i i i ) u i 0 ，v i 0 ，v i p ( z ) ，则称z 足互补约束优化问题的s 一稳定点 若z 厂足m p c c 的s 一稳定点，则z 足松规划( 1 3 ) 的稳定点 设z 厂是m p c c ( 1 6 ) 的局部最优解，则对于p ( z ) 的任意分块尸，q ，z 一定是 下列数学规划的局部最优解， m i n ，( z ) s 亡9 ( z ) 0 ， ( z ) = 0 ， f 1 1 4 ) c i ( z ) = 0 ，凰( z ) 0 ，i a ( z ) u 尸， g i ( x ) 0 ，玩( z ) = 0 ，i ，y ( z ) uq 7 内蒙古大学博士学位论文 定义1 1 1 设xe 厂若对于p ( z ) 的任意分块p ，q ，存在乘子向量入i r v ，p 皿q ，u 皿m ，v i r m ，使得 0 = v f ( x ) + v 夕( z ) 入+ v 允( z ) p v g ( z ) 乱一v h ( x ) v ， 入0 ，) t t g ( x ) = 0 ， u i = 0 ，i 一y ( z ) ，u i 0 ，i q ， v i = 0 ，i 乜( z ) ，v i 0 ，i 只 则称x 是互补约束优化问题的分片稳定点 由定义1 1 0 和定义1 1 1 可得如下蕴含关系： s 一稳定点号分片稳定点 u m 一稳定点 u c 一稳定点 u w 一稳定点 下面给出具体例子来说明各种稳定点之间的区别 m i n - y s t x y = 0 ， ( 1 1 5 ) x 0 ，y 0 ，x t y = 0 由于问题( 1 1 5 ) 只有一个可行解( 0 ，o ) ，故( o ，o ) 足问题( 1 1 5 ) 的唯一最优解 首先，( 0 ，0 ) 不足非线性规划意义下的稳定点若( o ，o ) 足稳定点，则k k t 乘子 应满足下列方程组： 10 = ( 0 ，一1 ) t + p ( 1 ，一1 ) t 一仳( 1 ，o ) t 一御( o ，1 ) t + 叩( o ，o ) t ， i i 乱0 ， 0 而上述方程组无解，这就是说，在非线性规划意义下的k k t 乘子不存在 为了说明( 0 ，0 ) 是问题( 1 1 5 ) 的c 一稳定点，我们考虑下列方程组： ，0 = ( 0 , - - 1 ) t + p ( 1 ，一1 ) t - - u ( 1 ，0 ) t - v ( 0 ，1 ) t ， 1 伽0 第一章绪论 对于任意一1 u 0 ，( 弘，u ，u ) = ( u ，u ，一1 一钆) 都是上述方程组的解因此，( 0 ，0 ) 是 问题( 1 1 5 ) 的c 一稳定点 方程组 10 = ( 0 ，一1 ) t + 肛( 1 ，一1 ) t u ( 1 ，o ) 丁一v ( o ，1 ) t ， 【“ o ，口 o 或u = 0 有解，解为( p ，u ，v ) = ( 0 ，0 ，一1 ) ，( p ，札，v ) = ( 一1 ，- 1 ，o ) 因此，( 0 ，0 ) 是问题( 1 1 5 ) 的 m 一稳定点 ( 0 ，0 ) 是下列子问题的最优解， m i n 一 s t x y = 0 ， ( 1 1 6 ) x 0 ，y = 0 ( 0 ，0 ) 也足下列子问题的最优解， m i n 一可 s t x y = 0 ， ( 1 1 7 ) x = 0 ，y 0 问题( 1 1 6 ) 的k k t 乘子( p ，u ，v ) 应满足下列方程组： 三三譬一1 ) t + p ( 1 ，一1 ) t 一让( 1 ，。) t 一钉( 。，1 ) t ， 问题( 1 1 7 ) 的k k t 乘子( p ，u ，v ) 应满足下列方程组： 兰三譬一1 ) t + p ( 1 ，一1 ) t 一乱( 1 ，。) t 一秽( 。，1 ) t ， 因此，( 0 ，0 ) 是问题( 1 1 5 ) 的分片稳定点，对应的k k t 乘子( p ，让，v ) 满足 ( 钍，u ，- 1 一u ) ：乱o ) u ( 一1 一v ，- 1 一v ，v ) ：v o ) 但是，( 0 ，0 ) 不足问题( 1 1 5 ) 的s 一稳定点若( 0 ，0 ) 是s 一稳定点，对应的k k t 乘子( p ，u ，v ) 应满足 10 = ( 0 ，一1 ) t + p ( 1 ，一1 ) t u ( 1 ，o ) t 一口( o ，1 ) t ， i 乱0 ，u 0 内蒙古大学博士学位论文 而上述方程组无解 下面给出s 一稳定点、b 一稳定点、局部极小之间的关系 1 7 ，1 8 ： 定理1 1 2 设x 厂是m p c c 的s 一稳定点，则x 是m p c c 的b 一稳定点；反过 来，若z 是m p c c 的b 稳定点，且在x 处满足m p c c s m f c q ，则z 是m p c c 的s 一 稳定点 定理1 1 3 设x 厂是m p c c 的局部极小，且在z 处满足m p c c l i c q ，则x 足 m p c c 的s 稳定点，且存在唯一的乘子向量使得( 1 1 0 ) 一( 1 1 3 ) 成立 定义1 1 4 1 7 ，3 1 设x 厂是m p c c 的、v - 稳定点，即存在乘子向量入，p ，u ，v ， 使得( 1 1 0 ) 一( 1 1 3 ) 成立，若 u i v i 0 ，v i p ( z ) ，( 1 1 8 ) 则称在x 处满足上水平严格互补( u l s c ) 设x 厂，若z ( z ) = 声，则称在x 处满足下水平严格互补( l l s c ) 显然，若在。处l l s c ，则在x 处u l s c 若在z 处u l s c ，则m 一稳定点一定是b 一 稳定点 1 2 3m p c c 的二阶最优性条件 先简单回忆一下非线性规划n l p 的二阶最优性条件 ( n l p ) m i nm ) ( 1 1 9 ) s t g ( x ) 0 ，h ( x ) = 0 ， 其中，：1 r n _ 1 r ，g ：砑一砰，h ：研_ 础二阶连续可微 若z 是n l p ( 1 1 9 ) 的局部最优解，且在x 处线性独立约束规范( l i c q ) 成立，即 v 吼( z ) ，i 毛( z ) ，v ，0 ( z ) ，j = 1 ，2 ，q 线性无关，则存在k k t 乘子向量a 卿，pe 皿9 ，使得 v z l ( z ，入，弘) = 0 ， g ( z ) 0 ，入0 ，入r g ( x ) = 0 ， ( z ) = 0 ， 1 0 ( 1 2 0 ) 第一章绪论 其中l ( x ，入，肛) = s ( x ) + ) c g ( x ) + p t h ( x ) 称为n l p ( 1 1 9 ) 的l a g r a n g e 函数，且满足 ( 1 2 0 ) 式的乘子向量a ，p 存在且唯一 设n l p ( 1 1 9 ) k k t 乘子向量入，p 存在且唯一，称在x 处满足二阶必要条件( s o n c ) 是指矩阵 m = v ：l ( x ，a ，弘) 在临界锥c ( 。，入) 上半正定，即 矿m d 0 ，v d c ( z ，a ) ， 其中 c ( x ，入) = d 1 r nv 吼( z ) t d = 0 ，i 毛( z ) 且a t 0 ， v 吼( z ) 丁d 0 ，i ( z ) 且a t = 0 ， v h y ( x ) t d = o ，j = l ，2 ，g ) 一 若m 在临界锥c ( z ，a ) 的子空间 c 7 ( z ，a ) = c ( x ，a ) n d r 礼iv 俄( z ) t d = 0 ，i 毛( z ) = d 皿? lv 吼( z ) t d = 0 ，i 毛( z ) ，v h j ( x ) 丁d = o ，j = 1 ，2 ，g ) 上半正定，则称在x 处满足弱二阶必要条件( w s o n c ) 若x 是n l p ( 1 1 9 ) 的局部最优解，且在x 处l i c q 成立，则z 一定是n l p ( 1 1 9 ) 的稳定点且满足弱二阶必要条件 同样，我们可以定义互补约束优化问题二阶必要条件( m p c c s o n c ) 3 ，17 】和互补 约束优化问题弱二阶必要条件( m p c c w s o n c ) 4 ，2 4 i 设v z l ( z ，a ，p ，u ，v ) = 0 ，定义在 z 处的临界锥， c ( z ) ：- - d 丑妒iv ( z ) t d = 0 v 仍( z ) t d 0 ， j 毛( z ) 且a 歹= 0 ， v h l ( z ) t d = 0 1 =1 ，2 ，q ， v g t ( z ) t d = 0 ，i a ( z ) ， v 鼠( z ) t d = 0 ，i 7 ( z ) ， v g t ( z ) t d = 0 ，i p ( z ) 且乱i 0 ， v g i ( z ) t d 0 v 凰( z ) t d = 0 v 玩( z ) t d 0 1 1 卢( z ) 且钆t = 0 ， p ( z ) 且 0 ， p ( z ) 且饥= o ) ， 内蒙古大学博士学位论文 若v ：l ( x ，入，p ，也，v ) 在e ( z ) 上半正定，即 c l t v ：l ( x ，入，p ，u ，v ) d 0 ，v d c ( z ) ， 则称在x 处满足m p c c s o n c 若v ：l ( x ，入，肛，钍，v ) 在临界锥的子空间c 7 ( z ) 上半正定，即 矿v ：l ( z ，a ，p ，u ，v ) d 0 ，v d c 7 ( z ) ， c 7 ( z ) ：- - - d 1 r 礼iv g j ( x ) t d = o ，j 毛( z ) ， v h l ( x ) t d = 0 ，f = 1 ，2 ，g ， v g i ( z ) t d = 0 ，i a ( x ) u p ( z ) ， v 玩( z ) t d = 0 ，i p ( z ) u 7 ( z ) ) ， 则称在z 处满足m p c c w s o n c 定义1 1 5 【1 8 ，2 0 ，3 1 】设x 是m p c c 的s 一稳定点，若 d r v ：l ( x ，入，p ，让，v ) d 0 ，v d c ( z ) ， 其中入，p ，钆，v 是使得( 1 1 0 ) 一( 1 1 3 ) 式成立的乘子向量，则称在x 处互补约束优化问题 二阶充分条件( m p c c s o s c ) 成立若 d t v ：l ( x ，入，p ，钆，v ) d 0 ，v d c 7 ( z ) ， 则称在x 处互补约束优化问题强二阶充分条件( m p c c s s o s c ) 成立 定理1 1 6 【17 】( 互补约束优化问题的二阶最优性条件) ( i ) 若x 是m p c c 的局部极小，且在z 处满足m p c c s m f c q ，则z 是m p c c 的 s 一稳定点，且存在唯一的乘子向量入，p ，“，v 使得( 1 1 0 ) 一( 1 1 3 ) 式成立而且，在z 处 满足m p c c s o n c ，即 v ：l ( z ，a ，p ，乱，v ) d 0 ，v d c ( z ) ( i i ) 设z 是m p c c 的s 一稳定点，a ，p ，u ，v 是满足( 1 1 0 ) 一( 1 1 3 ) 的乘子向量若 在z 处满足m p c c s o s c ，即 v ：l ( z ，入，p ，u ，v ) d 0 ，v d c ( z ) 且d 0 ， 则z 是m p c c 的严格局部极小 12 第一章绪论 1 3 互补约束优化问题的算法概述 本节概述求解互补约束优化问题的已有算法其基本思想就足将互补约束优化问 题转化为相对简单等价( 或近似) 的优化问题，并在此基础上，利用已有较成熟的非线 性规划算法( 有时需要适当加以改进) 来求解互补约束优化问题，得到互补约束优化问 题的最优解或某种类型的稳定点 求解互补约束优化问题困难主要在于互补约束条件的存在，m p c c 没有严格可 行点，从而不满足m f c q ，这使得标准非线性规划方法不能直接应用于求解( 1 6 ) 处 理该问题的一类方法是引入光滑参数或引入松弛因子，使问题存在严格可行点，下面 先介绍这两类货：法特点及收敛性 ， 1 3 1光滑化方法 光滑化方法被广泛地应用于求解非线性互补问题和变分不等式问题，很自然地， 它被推广用于求解带特殊互补约束优化问题 4 ，2 5 ，2 8 ，3 3 ，8 0 】然而，这些方法大多数 需要非退化( 即下水平严格互补) 假设，才能保证算法收敛到m p c c 的b 一稳定点， 而有些问题只能收敛到m p c c 的c 一稳定点f u k u s h i m a ，p a n g 刚研究了磨光连续方 法( s m o o t h i n gc o n t i n u a t i o nm e t h o d ) ，该方法一方面去掉了迭代序列的聚点满足下水平 严格互补条件，另一方面又证明了迭代序列收敛于互补约束优化问题( 1 6 ) 的b 一稳定 点y i nh o n g x i a 6 7 】研究了光滑近似法( s m o o t ha p p r o x i m a t i o nm e t h o d ) ，该方法在上 水平严格互补条件下收敛于m p c c ( 1 6 ) 的b 一稳定点 ； 下面介绍两种比较典型的光滑化方法 1 利用扰动的f i s c h e r - b u r m e i s t e r 函数【3 6 】 ( 1 1 ) 欢处处可微且满足 。a ，b ) = 0 兮a 0 ，b 0 ，a b = e 2 f a c c h i n e i 4 和f u k u s h i m a i s o 】给出了m p c c ( 1 6 ) 的光滑近似： m i n y ( x ) s t g ( x ) 0 ，h ( x ) = 0 ， ( 1 2 ) 农。( g t ( z ) ，h i ( x ) ) = 0 ，i = 1 ，2 ，仇， 】3 内蒙古大学博士学位论文 其中e 七为光滑参数 定理1 1 7 设g k 一0 ，x 七是问题( 1 2 ) 满足弱二阶必要条件( w s o n c ) 的稳定点， 且序列 ) 收敛于孟若在牙处m p c c l i c q 成立， 矿) 满足渐近弱非退化条件， 则 矿) 收敛于m p c c ( 1 6 ) 的b 一稳定点 粗略地说，若 z 七) 满足渐近弱非退化假设，是指对于v i p ( 牙) ，g ( z 七) 和皿( 扩) 以相同的数量级趋向于0 很显然，这个性质弱于l l s c 2 利用最大值函数的归并函数 设w ：衍一r ，w ( x ) = m a x w l ( x ) ，叫2 ( z ) ，w m ( z ) ，其中妣( z ) ，i = 1 ，2 ，仇 是连续可微函数显然，叫( z ) 在皿n 上连续，但不是处处连续可微对于v t 0 ，叫( z ) 的归并函数w ( x ，t ) ：皿叶1 _ 毋定义为 m 伽( 亡，z ) = t l n e 似( z ) 肛，( 1 3 ) i = 1 ( 1 3 ) 也可看作是指数罚函数，曾用于求解非线性规划的乘子法中 9 4 ，9 5 ，后被推广应 用于求解广义线性互补问题和一些非线性互补问题 3 9 ，8 6 ，9 3 】 注意到，a 0 ，b 0 ，a b = 0 当且仅当m i n a ，6 ) = 0 对于v t 0 ，利用上述归并 函数定义m i n a ，6 ) 的光滑近似函数： 似n ，6 ) = 一知( e - 纽+ e - t b ) 对于任意t 0 ，也( n ，6 ) 连续可微，且 i - m u t ( n ，6 ) = m i n a ，6 ) y i nh o n g x i a 给出了m p c c ( 1 6 ) 的另一种光滑近似： ( 1 4 ) m i n ，( z ) s t 夕( z ) 0 ，h ( x ) = 0 ，( 1 5 ) 咖t 。( g t ( z ) ，鼠( z ) ) = 0 ，i = 1 ，2 ，m ， 其中t 七为光滑参数 定理1 1 8 设t k _ 0 ，砂是问题( 1 5 ) 满足s o n c 的稳定点，且序列 矿) 收敛于 孟若在牙处m p c c l i c q 和u l s c 成立，则圣足m p c c ( 1 6 ) 的b 一稳定点 对于v i p ( 孟) ，v 砖v e t , ( g t ( 扩) ，鼠( 扩) ) ， 谚= 7 7 乞v g ( 矿) + 施v h , ( x 岛) ， 其中叩恐，叩袅( 0 ，1 ) ，且叩乞+ 叩象= 1 1 4 第一章绪论 推论1 1 9 设如一0 ，矿是问题( 1 5 ) 满足s o n c 的稳定点，且序列 扩) 收敛于 牙若在面处m p c c l i c q 成立，