（运筹学与控制论专业论文）求解不等式约束优化问题的一个非线性lagrange函数.pdf

气 毒 l“。多： 务til 譬j 学位论文独创性声明 删吵螋磐烨y 17 9 5 5 8 7 本人承诺：所呈交的学位论文是本人在导师指导下所取得的研究成果。论文中除特别加以标注和 致谢的地方外，不包含他人和其他机构已经撰写或发表过的研究成果，其他同志的研究成果对本人的 启示和所提供的帮助，均已在论文中做了明确的声明并表示谢意。 学位论文作者签名：邀函霞 学位论文版权的使用授权书 本学位论文作者完全了解辽宁师范大学有关保留、使用学位论文的规定，及学校有 权保留并向国家有关部门或机构送交复印件或磁盘，允许论文被查阅和借阅。本文授权 辽宁师范大学，可以将学位论文的全部或部分内容编入有关数据库并进行检索，可以采 用影印、缩印或扫描等复制手段保存、汇编学位论文，并且本人电子文档的内容和纸质 论文的内容相一致。 保密的学位论文在解密后使用本授权书。 学位论文作者签名：邀函霞指导教师签名： 签名日期：如加 年等月习日 4 一 1， 辽宁师范大学硕士学位论文 摘要 将有约束的目标函数用单调且充分光滑的函数转化成等价的经典l a g r a n g e 函数， 这种经典l a g r a n g e 函数在原始空间和对偶空间都有重要的性质，约束优化问题的这种转 化形成了一系列的修正障碍函数和修正障碍函数法修正障碍函数是等价问题的经典 l a g r a n g e 函数，它将经典l a g r a n g e 函数和经典障碍函数非常好的性质结合在了一起 由修正障碍函数好的性质，得到了凸规划问题对偶对新的性质，而且形成了非凸约 束优化问题的对偶理论近现代有许多学者研究讨论过非线性约束优化问题，在研究非 线性约束优化问题时也提出了一些函数，这些函数结合了经典l a g r a n g e 函数和经典障碍 函数好的性质，同时去除了它们的缺陷，也被认为是内点增广l a g r a n g e 函数 本文提出了求解不等式约束优化问题的另一个非线性l a g r a n g e 函数f ( x ，u ，k ) ，该函 数将原问题转化成等价的新问题，证明了该函数具有很好的性质，并构造了基于该函数 的对偶算法，证明了当参数k 大于某一阈值时，由算法生成的原始一对偶点列是局部收 敛的在文中给出了凸规划问题和非凸情形下原始一对偶解的误差估计，说明了该函数具 有局部强凸性，还提出函数的对偶问题，讨论了对偶问题的凸性和光滑性最后用新提出 的l a g r a n g e 函数的对偶算法求解p o l a r 2 问题、p o l a r 3 问题、w o n 9 2 问题和w o n 9 3 问题， 并且给出了算法得到的数值结果 关键词：非线性l a g r a n g e 函数：对偶算法：收敛：强凸：对偶定理 4 u j一 f ， 龟 求解不等式约束优化问题的一个非线性l a g r a n g e 函数 an o n l i n e a rl a g r a n g i a nf o rc o n s t r a i n e do p t i m i z a t i o n a b s t r a c t t h en o n l i n e a rr e s c a l i n gp r i n c i p l ee m p l o y sm o n o t o n ea n ds u f f i c i e n t l ys m o o t hf u n c t i o n s t ot r a n s f o r mt h ec o n s t r a i n t sa n do b j e c t i v ef u n c t i o ni n t oa ne q u i v a l e n tp r o b l e m ，t h ec l a s s i c a l l a g r a n g i a nh a si m p o r t a n tp r o p e r t i e so nt h ep r i m a la n dt h ed u a ls p a c e s t h ea p p l i c a t i o no f t h e n o n l i n e a rr e s c a l i n gp r i n c i p l et oc o n s t r a i n e do p t i m i z a t i o np r o b l e m sl e a d st oac l a s so fm o d i f i e d b a r r i e rf u n c t i o n sa n dm o d i f i e db a r r i e rf u n c t i o nm e t h o d s b e i n gc l a s s i c a ll a g r a n g i a nf o ra n e q u i v a l e n tp r o b l e m ，t h em o d i f i e db a r r i e rf u n c t i o nc o m b i n et h eb e s tp r o p e r t i e so ft h ec l a s s i c a l l a g r a n g i a na n dc l a s s i c a lb a r r i e rf u n c t i o n s d u et ot h ee x c e l l e n tm o d i f i e db a r r i e rf u n c t i o n s p r o p e r t i e s ，n e wc h a r a c t e r i s t i c so ft h ed u a l p a i rf o rc o n v e xp r o g r a m m i n gp r o b l e m sh a v eb e e nf o u n da n dt h ed u a l i t yt h e o r yf o rn o n c o n v e x c o n s t r a i n e do p t i m i z a t i o nh a sb e e nd e v e l o p e d i nt h em o d e mt i m e sal o to fs c h o l a r sh a v e s t u d i e dt h en o n l i n e a rc o n s t r a i n e do p t i m i z a t i o np r o b l e m sa n dal o to ff u n c t i o n sh a v eb e e n c o n s t r u c t e d t h e s ef u n c t i o n sc o m b i n et h eb e s tp r o p e r t i e so ft h ec l a s s i c a ll a g r a n g i a na n d c l a s s i c a lb a r r i e rf u n c t i o n s ，w h i c ha l s oh a v eb e e na st h ei n t e r i o ra u g u m e n t e dl a g r a n g i a n t h i sp a p e re s t a b l i s h e sa n o t h e rn o n l i n e a rl a g r a n g i a nf o rs o l v i n gn o n l i n e a rp r o g r a m m i n g p r o b l e m sw i mi n e q u a l i t yc o n s t r a i n t s t h ef u n c t i o nh a se x c e l l e n tp r o p e r t i e sa n dt h e r ee x i s t sa t h r e s h o l ds u c ht h a tt h es e q u e n c eo fp r i m a l d u a li t e r a t ep o i n t sg e n e r a t e db yd u a la l g o r i t h m b a s i n go nt h en o n l i n e a rl a g r a n g i a nl o c a l l yc o n v e r g e st oam i n i m i z e ri ft h ep e n a l t yp a r a m e t e r i sm o r et h a nt h et h r e s h o l d i ta l s or e p o r tt h a tt h en o n l i n e a rl a g r a n g i a ni ss t r o n g l yc o n v e xi na n e i g h b o r h o o d m o r e o v e r ，t h ep a p e rd e v e l o p sc o r r e s p o n d i n gd u a l i t yt h e o r ya n dt a l k sa b o u t t h ec o n v e x i t ya n ds m o o t h e so ft h ed u a l i t y f i n a l l y ，t h ep a p e ru s e sn e wl a g r a n g i a nt o s o l v es o m ep r o b l e m s ，s u c ha sp o l a r 2 ，p o l a r 3 ，w o n 9 2a n dw o n 9 3 ，a n dr e p o r t ss o m en u m e r i c a l r e s u l t sb yu s i n gt h ep r o p o s e dd u a la l g o r i t h m k e yw o r d s ：n o n l i n e a rl a g r a n g i a n ；d u a la l g o r i t h m ；c o n v e r g e ；s t r o n g l yc o n v e x ； d u a lt h e o r y i i ? l 1一- 辽宁师范大学硕士学位论文 目录 手商要i a b s t r a c t i i 弓i言1 1构建问题和基本假设。3 1 1 考虑不等式约束问题3 1 2 问题( p 1 ) 的假设条件3 2 非线性l a g r a n g e 函数5 2 1 定义非线性l a g r a n g e 函数5 2 2 非线性l a g r a n g e 函数f ( x ，u ，k ) 的性质6 2 3 基于非线性函数f ( x ，u ，k ) 的对偶算法7 2 4 对偶算法的收敛性7 3 问题( p 1 ) 的对偶问题1 5 3 1 对偶问题1 5 3 2 对偶定理16 4 数值结果一：2 2 参考文献2 4 附录2 6 攻读硕士学位期间发表学术论文情况4 3 致谢4 4 f il 气 0 7， 辽宁师范大学硕士学位论文 j o 目 f r i s h 1 2 】和c a r r o l l l 7 分别于1 8 世纪5 0 年代中期和6 0 年代初提出了解决约束优化 问题的经典障碍函数，之后这些函数被f i a c c o 和m c c o r m i c k 广泛研究，并作为不同的解 体技巧，相应的方法成为现代优化理论的重要组成部分( 见 1 0 ，1 7 ，2 2 ，2 3 ) 这些函数和 相应的方法随着线性规划的发展而发展( 见 9 ，1 1 ，1 4 ，1 6 ，1 9 ，2 0 ，2 1 ，2 6 ，2 7 ，3 0 ) 基于这些函数的经典障碍函数和相应的方法有自身的缺陷，最明显的缺陷就是这些 障碍函数在边界点的邻域内无界于是我们研究在可行域任一内点处开始求解，而且不 特别考虑约束时解仍然保持在可行域内部，这就使得可以用光滑优化方法( 8 ，1 3 ，2 3 ) 解决( 非光滑) 约束优化问题，然而当算法接近积极约束边界时经典障碍函数的优势就变 成了缺陷 经典障碍函数及其导数在最优解处不存在当计算过程接近最优解时经典障碍函数 趋于无穷，h e s s i a n 阵的条件数消失，积极约束边界的排斥性变得更强因而即使二阶优 化条件成立，那么随着计算的进行，收敛率也会变得很小更进一步，只有当罚参数趋于 无穷取极限值时，才能使经典障碍函数达到l a g r a n g e 乘子最优值另一方面，基于约束优 化理论分析和计算方法的经典l a g r a n g e 函数还有一些缺陷：( 一) 一般来说，固定一个优 化l a g r a n g e 乘子，在原始空间中即使二阶优化条件成立，经典l a g r a n g e 函数的无约束优 化值也可能不存在：( 二) 在固定的优化对偶变量下，跟线性规划问题相对应的经典 l a g r a n g e 函数的无约束优化值与原线性规划问题的最优值不等：( 三) 基于经典l a g r a n g e 函数的对偶问题的目标函数的光滑性与原函数的光滑性相独立，一般是非光滑的，即使 满足二阶最优性条件的凸规划问题也是这样的 近现代有许多学者研究讨论非线性约束的优化问题，在研究非线性约束优化问题时 也提出了一些函数，如b e r t s e k a s 【1 】提出了指数函数乘子法：p o l y a k n 提出了两种修正障 碍函数一修正f r i s c h 函数和修正c a r r o l l 函数，他证明了在适当条件下，罚参数k 存在阈 值 o ，当k k 0 时，基于这两种函数建立的算法均局部收敛于原始最优解与对偶最优解， 同时也给出了近似解的误差估计：p o l y a k 【3 j 又提出了求解非线性规划问题的 l o g s i g m o i d 乘子法：又如贺素香等 4 1 ，顾剑、任咏红1 5 j 也对用于求解不等式约束优化问 题的非线性l a g r a n g e 函数进行了研究，证明了这一非线性l a g r a n g e 函数的对偶算法具 有q 一线性收敛速度等等这些函数结合了经典l a g r a n g e 函数和经典障碍函数的最好的 性质，同时去除了它们的缺陷，也被认为是内点增广l a g r a n g e 函数 譬l ll 求解不等式约束优化问题的一个非线性啪g e 函数 本文提出了求解不等式约束问题的另一个非线性l a g r a n g e 函数，构造了基于该函数 的对偶算法，证明了该算法的收敛性，又给出了原问题的对偶问题，讨论了该对偶问题的 凸性和光滑性 本文共分五部分，具体组织结构如下： 首先引言介绍了课题研究的背景和前人的工作，以及本论文的主要内容和组织结构 第一章提出了有待解决的问题( p i ) 和解决问题需要的假设条件第二章定义了一个新的 函数来解决问题( p 1 ) ，证明该函数具有非常好的性质并且对问题( p 1 ) 构造了基于这个函 数的对偶算法，证明了这个算法在凸规划和非凸情形下具有局部收敛性和强凸性第三 章给出了问题( p 1 ) 的对偶问题，讨论了对偶问题分别在凸和非凸情形下的对偶定理，最 后在第四章给出了用该算法解决的四个问题的数值结果 弋-一1 辽宁师范大学硕士学位论文 1 构建问题和基本假设 1 1 考虑不等式约束问题 础乏， ( p i ) s t z ( 功0 ，i = l ，2 ，m ， 、 其中z ：孵4 专吼，i = 0 , 1 ，m 设存在工= a r g m i n 饥( 功i z q ) ，其中q = 扛吼”i z ( 力o , i = 1 ，m ) ， l ( x ，“) = f o ( x ) - z ( z ) 是问题( p 1 ) 的经典l a g r a n g e 函数 1 2 问题( p 1 ) 的假设条件 为了叙述的方便引入下列符号： w ( x ) = ( 瓢( 石) ，v f ( 石) ) ， w ，) ( 工) = ( 颗( 工) ，( 功) ， = 恍= m a x 。i x l l ， s ( y ，占) = x 孵”l u g y l l c ， “= ( “：，“：) r 贸”， u ；r 1 = ( “：，u r ) r 吼7 ， u ( m 州= ( u r + l ，“：) r 吼 假设问题( e ) 满足以下条件： ( a ) f i ( x ) ( i = 0 ，l ，2 ，m ) 二次连续可微： ( b ) 存在向量甜+ = ( u i ，“二) r 0 ，使o + ，u + ) 吼”孵”满足k t 条件： v ，( x ，“) = 0 ，z ( x + ) “；= 0 ，i = 1 ，m ； ( c ) 假设i ( x + ) = iiz o ) = o ，i = 1 ，m ) = 1 ，) 是积极约束集合； ( d ) 严格互补松弛条件成立，即“? 0 ，i i ( x ) ； ( e ) v f , ( z ) if i ( x + ) ) 线性无关； ( f ) ( v 。2 一t 一* ，“) y ，y 2 ( y ，y ) ，v y o ，颐，1 0 ) r y = 0 ，其中名 0 是一常数； ( g ) s l a t e r 条件成立，即孵“，使楸o o ) 0 , i = 1 ，聊； ( h ) 有界性条件成立，即j 尼。 0 ，r o ，满足m a x m 黝a ；。x f l ( x ) i 石o k o = o ( k o ) - 0 7 ，且对满足缈= 0 的任何j ，均有 2 ( y ，y ) ，其中兄 0 是一常 数，那么存在 0 ，满足v 0 o ，i = 1 ，m ) ，显然qcq t j 若z ( 曲f - 1 ，m 是凹函数，那么如果q 是紧集则q 。也是紧集：若问题( p 1 ) 是非凸规 划问题，那么q 是紧集不一定能得到q 。也是紧集，这时将会用到条件( h ) ，在( h ) 中如果存 在k o o ，那么对于任意的k k o 条件( h ) 都成立 下面提出一个新的函数来解决问题( p 1 ) ，并且对问题( p 1 ) 构造基于这个函数的对偶算 法，证明这个算法具有局部收敛性 2 1 定义非线性l a g r a n g e 函数 定义 f ( x , u ，k ) =胁一缸篱。， + o o ， 工仨q t 其中q 。= 缸r “i 三妖( 功+ 1 o ，f = l ，z ) ，k 是罚参数，“= ( “。，) 是l a 驰l g e 乘子 3l i l ( 言够( 石) + 1 ) 对v 后 o q = q ，2 缸i 云赫o = 1 ，嘲因而问题p 1 等价于以下问题 m i nf o ( x ) s t 妻篱巩，泓 ( p 2 ) 即x = a r g m i n f o ( x ) 石q ，) ，同时f ( z ，“，尼) 起问题( p 2 ) 的经典l a g r a n g e 函数 求解不等式约束优化问题的一个非线性l a g r a n g e 函数 2 2 非线性l a g r a n g e 函数f ( x ，u ，七) 的性质 显然如果 ( x ) 是凸函数，z ( x ) i = 1 ，一，埘是凹函数，那么对v k o ，“0 ，函数 f ( x ，u ，后) 关于z 是凸的 函数f ( x ，甜，k ) 在k - t 点( 工，”) 处具有以下性质： 定理2 1v k o ，以及k - t 点o ，“) ，下列结论成立： ( 1 ) f ( x + ，“，k ) = 三( 工。，“) = l ( x ) ； ( 2 ) v ，( 石，“，k ) = v ，( x + ，“) = 0 ； ( 3 ) 若问题( p 1 ) 是凸规划问题，则函数f ( x ，甜，k ) 在x 处达到最小值，即 x + = a r g m i n f ( x ，“，k ) lx 吼”) ； ( 4 ) v ：，o ，“+ ，后) = v 二o ，“) + 炳z ，) o ) u v f , ，) o ) r ，其中u = p 弛鲥；r _ l ； ( 5 ) 3 k o 0 ，o 0 ，“o 孵m + ，z o 吼”，令j = 0 步2 ( 近似) 求解r a i n f ( x ，u s , k ) ，得到， 步3 若甜。s ，。、x ) s ，f = 1 ，2 ，m 则终止；否则转步4 步4 更新l a g r a i l g e 乘子”：“川= d i a g g f ( ，) l 甜 步5 令s = s + 1 转步2 2 4 对偶算法的收敛性 设万 o 充分小，o o 和充分小的万 0 ，使得对 v 0 0 ，从而由( 2 2 ) 可得到 ( 2 2 ) ( 2 3 ) 颗，) ( 石+ ) 1 少= 0 ( 2 4 ) 1 主i ( 2 3 ) 和( 2 4 ) 可得( v ：三( 工。，“。) y ，y ) = 0 ，又由( f ) 成立可知y = o ，从而v f ( ，) o + ) w = 0 又( e ) 成立即v f , ，、( x ) 线性无关可得w = o 所以( ) ，w ) r = 0 n + r ，从而v 丸非奇异 由矩阵的b a n a c h 扰动引理知：3 k o o ，p 0 使得对v k k o ，v c k 是非奇异的，且 l l v 靠1 l l 0 , 8 0 以及定义在s ( 足，万) = ( f ，k ) ll t ，i 万，i 圭1 ，m ，k k ，毛噩上的唯一的连续可 微函数x ( f ，忌) ，v ( f ，尼) 满足： x ( t ，k ) = 工，v ( t ，尼) = “0 ) ，v ( t ，j | ) k ， 求解不等式约束优化问题的一个非线性l a g r a n g e 函数 i i ( x o ，尼) ，v ( f ，忌) ) 一( x ，“0 ) ) 0 占，v ( t ，七) s ( k ，艿) ， ( 2 5 ) v f o ( x ( t ，七) ) 一v ，( f ，k ) v z ( x ( t ，后) ) 一h ( x ( t ，七) ，t ，后) = 0 4 ， ( 2 7 ) 1 一l n ( 寺9 i ( x ) + 1 ) v j ( f ，尼) = k ( t i + 七叫“；) _ 上一， i = 1 ，( 2 8 ) ( 妻够( 功+ 1 ) 2 首先估计双扩，) ( f ，七) l i 由( 2 5 ) 及z o ) 口 o ，f = ，+ 1 ，朋，有z o ，七) ) 等，f = ，+ 1 ，聊1 因此 1 一l i l ( 三研( x ) + 1 )1 f f f ( x ( t ，七) ，f ，后) = k t j g f ( 力= k t i 了鱼一k t f _ l ( i 1 奶( 功+ 1 ) 2( i 1 奶( z ) ) 2 飒南弘嚣瓤鑫2 争衙+ 1 m 令c 。2 耵3 6 ，毗( 槲m ) c o k - l u l , 其中c 。与后无关 因此陆_ ，) 一“洲i c 。k 。1 - ，) 一“洲1 v ：l ( x ( t ，尼) ，v ( t ，尼) ) v ，x ( t ，尼) r - v f , ，) o x ( t ，七) v ，v ( ，) ( f ，尼) r = v , h ( x ( t ，后) ，t ，尼) r 七一1 v ，v ( t ，尼) r = ( d ( ，) ( z ( f ，尼) ) ，o r x ( m - r ) ) 一臣，) ( 缸f ，后) ) 二颗，) ( z ) rv ，x ( t ，后) r 其中d ( ，) ( x ( f ，尼) ) = d i a g g ；( x ) k l ，e ( ，) ( x ( f ，k ) ) = d i a g ( k t ，+ “+ ) 鬼( x ) k 1 嗽娴吧副以川川舶 吖k 徽厶o ”r x r ( 舯， 望室堕蔓奎堂堡主兰垡笙茎 一一一 _ _ _ _ - _ _ _ - i - - _ _ _ _ _ _ - _ _ - i _ _ - _ - _ _ _ 一一 考虑上式在t = 0 卅飒”时的情况，得到 盼v t x ( 呲o , k 州) r ) 喝刖似邶从呲加- r ( l v , h ( x 。( ，o 筘别 嘶r v , h ( x ( o 2 搿) 川k 现估计i l v ，j j l ( o ，尼) ，0 ，| | ) 7 1 1 由h ( x ，t ，尼) = e ( x ，t ，豇) ( 功， 可得 v , h ( x ( t ，尼) ，厶尼) r = 玩( 工o ，后) ， 后) v 2 六( 工o ，尼) 。工o ，矿 + 颗) ( x ( f ，七) ) v ，哌脚一，) x ( t ，霓) ，t ，后) 1 ， 而 e ( x ( t ，七) ，t ，k ) = k t f g f ( 石) i = ，+ 1 ，聊， 从而 v ，玩) ( 雄，七) ，t ，七) r = ( 0 ( m - r ) x r , 蛾一) ( x ( f ，训一 七2 d ( f ( 。- ，) ) 。一，) ( x ( f ，j | ) ) v ，正。一，) ( x ( f ，七) ) 7 v ，x ( t ，尼) r ， 其中d ( f ( 。_ ，) ) ： d e 口g f ，挺川，d ( 肼- ，) ( x ( f ，七) ) = d i a g g ，o ) 1 7 _ - 州，曩。- ，) ( x ( f ，七) ) = 陋础，( z ) 挺，+ 1 又当t = 0 ，k k o 时 x ( o ，尼) = z ， 哌，) ( o ，后) = “0 ) = ( “；，”：) 0 ， 玩( x ( o j | ) ，0 ，尼) = o , i = r + l ，聊d ( 。一，) ) = 0 ”1 弘( ”) k 筹赤1 = 志三k o g t ， 土一_ 一2 i 万鬲s 五， ( 奶( z ) + 1 ) 2( i 研( x ) ) 2 h - ，u 所以 v ，h ( x ( o ，克) ，0 ，足) r = 颗。一，) ( x + ) v ，t t ( 一) ( x ( o ，忌) ，0 ，七) = v f , m - r ) ( x ) ( 0 ( m - r ) x r , k d ( 。一，、( x ( 0 ，尼) ) ) ， 因此z 。，1 0 附( 加，桃啡寿阮- r ) ( z ) i | 求解不等式约束优化问题的一个非线性l a g r a i l g e 函数 根据m 及黔( 邢问酬i 壶阢- ，) ( x ) | | 可得到 m a x 积他础i i v , v ( o , k ) 脚( 者心小炉| | = d 者阢“x ) l i + ) ， 从而对于充分小的万 0 和v ( t ，k ) s ( k ，艿) ，不等式 阢舭( 嗍咏广肌( 碱圳| o 满足m 由假设( h ) 及m 知对充分大的及坛均有 厶( z ) 厶( z ) 一三2 彳， ( 2 11 ) 而 f o ( z ) _ - 2m i n o ( x ) l x q i ) ， 由假设条件( c ) 一( 曲及扰动引理知厶( 舅) 厶o + ) 一k t m “；， 因而对于充分大有v 尼厶( 譬) o ) 一三石 ( 2 1 2 ) ( 2 1 2 ) 与( 2 11 ) 相矛盾 所以，i a r g m i n f ( x ，“，k ) lx e q t ) = a r g m i n f ( x ，“，k ) l 工孵一 ，( 1 ) 得证 求解不等式约束优化问题的一个非线性l a g r a n g e 函数 ( 4 ) 由( 3 ) 知f ( x ，u ，k ) 在i = i ( “，k ) = a r g m i n f ( x ，u ，k ) lx 吼”) 的一个邻域内强凸，其 中( “，k ) d ( c ，万) 同时由定理2 1 中( 2 ) 知v ，f ( 孑 ，后) ，“，k ) = 0 ，由定理2 1 中( 5 ) 知 f ( x ，“? ，后) 在i 。，k ) 处强凸，所以i ，k ) = a r g m i n f ( x ，“，k ) iz 孵“) = 工+ 在凸规划中将会有更好的结论 定理2 3 如果函数z ( x ) f = 0 l ，m 二次连续可微，函数l ( x ) 是凸函数，函数 z ( x ) f _ 1 ，m 是凹函数，那么 ( 1 ) 若q = x qif o ( x ) = l ( x ) ) 是紧集，n 对v ( u ，后) 孵? + 1 存在舅= x ( u ，k ) 使得 v 。f ( 舅，“，k ) = 0 ； ( 2 ) 主( ，k ) = x ，五( “，后) = u ； ( 3 ) 若条件( a ) 一( g ) 成立，那么对于v ( u ，k ) d ( s ，万) ，定理2 2 ( 2 ) 中的估计式成立，而 且函数f ( x , u ，k ) 在舅= 曼“，k ) 的一个邻域内强凸 证明：( 1 ) 如果函数兀( z ) 是凸函数，函数z ( 工) i = 1 ，m 是凹函数，且q 是紧集，那 么由 1 0 ，p 9 5 引理1 2 可得对v u o ，k 0 ，在q i 上函数f ( x ，u ，j | ) 在曼处取得最小值，进 而由于当x 专触t 时f ( x ，u ，k ) 专0 0 ，得到v ，( 毛“，k ) = 0 ( 2 ) 由f ( x ，u ，k ) 关于z 是凸函数和定理2 1 中的性质( 3 ) 知对v k 0 ， 叠( “，七) = x ，五( “，露) = u ( 3 ) 如果条件( a ) 一( g ) 成立，这个结论可以依照非凸情况的方法类似证明，但不用条 件( h ) ，因为这时q 。= 缸) 而且对v u o ，k 0 ，f ( x ，u ，k ) 是有界的 辽宁师范大学硕士学位论文 3 问题( p 1 ) 的对偶问题 由2 1 中的知识知对v 后 0 问题( p 1 ) 与问题( p 2 ) 等价，因而问题( p 2 ) 的经典l a g r a n g e 函数f ( x , u ，k ) 具有凸规划问题经典l a g r a n g e 函数的所有性质因而有以下的命题： 命题3 1 如果厶( x ) 和一z ( 功，f = 1 ，m 是凸函数且s l a t e r 条件成立，那么对 v k o ，工+ q 是问题( p ：) 的解的充分必要条件是 ( 1 ) 存在向量u 0 ，使得 “? z ( x ) = 0 , i = 1 , 2 ，m ，f ( 工，“，k ) f ( x ，“，后) ，v z 吼4 ( 3 1 ) ( 2 ) ，u ) 是函数f ( x ，u ，k ) 的鞍点，即 f ( z ，u ，尼) ，( 石，“，k ) f ( x ，u ，后) ，v x 孵4 ，v u 吼：( 3 2 ) 3 1 对偶问题 令 y t ( z ) = s u p f ( x ，“，k ) ， 贝0 幽- 掣_ 巍1 2 耽 原问题( p 1 ) 归结为找出x ，使x + = a r g m i n 缈。( 力i 石吼”) ( 3 3 ) 令 也( h ) 一删i n ff ( x ，“，后) ， 原问题( p 1 ) 的对偶问题为找出u ，使得 u = a r g m a x 也( z ) lu 贸? ) ( 3 4 ) 由( x ) 和k ) 的定义知 厶( x ) = 缈t ( 石) 、壬，七( “) ，v 戈q ，v “吼? ， 因而如果叠和五分别是原问题与对偶问题的可行解且( 曼) = 也( 五) ，那么 量= 石+ ，五= u 对偶函数l ) 的光滑性取决于函数：( 工) ，i = 0 , 1 ，2 ，m 的凸性和光滑性若原问题 ( p 1 ) 是凸规划问题，则对v “0 ，k o ，函数b ) 的光滑性与函数z ( z ) ，i = 0 , 1 ，2 ，m 的 光滑性致若l ( x ) 和z ( z ) ，i = 1 , 2 ，是非凸的，将用以下引理说明 求解不等式约束优化问题的一个非线性l a g r a n g e 函数 引理3 1 如果函数z ( x ) ，i = 0 ，l ，m 光滑，且条件( a ) 到( g ) 成立，那么对任意固定 的k ，凹函数 ) 在以上是二次连续可微的 证明：首先，无论函数厶o ) 和一z ( x ) ，f = 1 , 2 9e 9 m 是否为凸函数，k ) 对于任意 k 0 均为凹函数 由定理2 2 知v ( u ，k ) d ( 占，万) ，函数f ( x , u ，d 在i = i ( u ，k ) 的一个邻域内强凸，因此 i = i ( u ，k ) 是函数f ( x ，u ，k ) 在孑的一个邻域内关于x 的唯一极小点，同时 甲i ) = f 何( “，露) ，u ，k ) 在以上是光滑的，即有 v 。、王0 ( “) = v 。孑( x ，u ) v ，f ( i ( “，后) ，u ，七) + v 。f ( j ( “，尼) ，u ，k ) 由于7 ：f ( y ( u ，七) ，u ，忌) 对于v ( u ，k ) d ( s ，万) 均正定，由系统v ，f ( x , u ，k ) = 0 可以得 到唯一的向量值函数i ( u ，k ) ，使得i ( u ，k ) = 工，且- v 。孑( “，后) = 一v 。2 一、一( 甜，尼) ，u ，七) ( v 二f ( i ( ”，尼) ，“，七) ) 一1 因v ， ( ”，七) ，u ，k ) = o ，所以v 。似) = v 。f ( y ( u ，七) ，u ，尼) ，更进一步有 v ：。q ，七( “) = v 。i ( u ，七) v ：f ( 孑( “，尼) ，u ，七) = 一v 三。f ( i ( “，尼) ，u ，尼) ( v ：，( 双“，尼) ，u ，尼) ) 一1 v ：f ( y ( u ，七) ，u ，七) ， 而 v 。2f ( i ( “，尼) ，u ，七) = 一v 厂( i ( ”，后) ) g ，( g ( u ，后) ) ， 其中 g 。( ) = d i a g g ，( 工) 】至i ， 所以 v 乙，( i ( 甜，后) ，u ，后) = ( v 乙f ( i ( “，七) ，u ，七) ) 7 = 一g _ ( i ( “，尼) ) ( 1 z 厂( i ( “，后) ) ) r 那么 v ：q 0 _ ( “) = - g 。( i ( “，七) ) ( 1 咒厂( i ( “，尼) ) ) r ( v ：f ( i ( “，尼) ，u ，| i ) ) 一1 1 咒厂( i ( “，尼) ) g 。( 孑( “，尼) ) ， 同时有 v ：甲i ( “+ ) = 一6 乙( x ) ( 可丁( z ) ) r ( v 2 x f ( x * , u ，七) ) 。1v f ( z ) g 。( 工) 引理得证 3 2 对偶定理 在凸规划情形下，基于函数f ( x ，u ，k ) 的对偶问题有以下对偶定理 定理3 1 设厶( x ) 和一z ( z ) ，i = 1 , 2 ，m 是凸函数， ( 1 ) 设s l a t e r 条件成立，若问题( p 1 ) 的解存在，则问题( 3 4 ) 的解也存在且 兀( x + ) = t ( x + ) l ( ”+ ) ，v k 0 ； 辽宁师范大学硕士学位论文 ( 2 ) 若l c x ) 强凸，z ( z ) ，i = 1 , 2 ，m 光滑且对偶f n i n ( 3 4 ) 的解存在，n n f 司n ( p 。) 的 解也存在，且目标函数值相同； ( 3 ) 若z ( 力，i = 1 , 2 ，m 光滑，条件( c ) 到( g ) 成立，n , 对v k ，对偶问题( 3 4