（运筹学与控制论专业论文）求解半无限规划问题的对数型lagrange函数.pdf

学位论文独创性声明 本人承诺：所呈交的学位论文是本人在导师指导下所取得的研究成果。论文中除特别加以标注 和致谢的地方外，不包含他人和其他机构已经撰写或发表过的研究成果，其他同志的研究成果对本 人的启示和所提供的帮助，均已在论文中做了明确的声明并表示谢意。 学位论文作者签名：查蕉筌 学位论文版权的使用授权书 本学位论文作者完全了解辽宁师范大学有关保留、使用学位论文的规定，及学校有 权保留并向国家有关部门或机构送交复印件或磁盘，允许论文被查阅和借阅。本文授权 辽宁师范大学，可以将学位论文的全部或部分内容编入有关数据库并进行检索，可以采 用影印、缩印或扫描等复制手段保存、汇编学位论文，并且本人电子文档的内容和纸质 论文的内容相一致。 保密的学位论文在解密后使用本授权书。 学位论文作者签名：疹膨 指导教师签名： 辽宁师范人学硕士学位论文 摘要 半无限规划是数学规划领域的一个具有重要理论意义和应用价值的研究课题，在工 程、经济、管理、信息技术以及计算机网路系统等领域的许多有重要价值的实际问题， 如机器人路径问题、产品生产设计规划、空气污染控制问题等等，均属于半无限规划问 题，该类问题的求解方法成为最优化领域倍受关注的研究热点，将半无限规划问题转化 为有限的非线性优化问题是具有代表性的方法之一而基于非线性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 函数的一阶、二阶最优性 条件；最后，通过实际算例说明了非线性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 函 数的一阶、二阶最优性条件，并给出了证明 第四章分析了广义半无限规划问题与半无限规划问题的关系研究发现，在m f 约 束规范下，从广义半无限规划问题到半无限规划问题的转化是可能实现的，进一步探讨 了这种转化可行的具体条件并给出了证明 关键字：半无限规划；广义半无限规划；对数型l a g r a n g e 函数；非线性l a g r a n g e 乘子； 最优性条件 辽宁师范大学硕士学位论文 a l o g a r i t h m i cl a g r a n g i a nf o rs o l v i n gs e m i i n f i n i t ep r o g r a m m i n g p r o b l e m a b s t r a c t s e m i - i n f i n i t e p r o g r a m m i n g ( s i p ) i s ar e s e a r c ht o p i c 、析t h i m p o r t a n t t h e o r e t i c a l s i g n i f i c a n c ea n dp r a c t i c a lv a l u ei nt h ef i e l do fm a t h e m m i cp r o g r a m m i n g m a n ys i g n i f i c a n t p r o b l e m s i ne n g i n e e r i n g ，e c o n o m i c s ，m a n a g e m e m ，i n f o r m a t i o nt e c h n o l o g y ，c o m p u t e r n e t w o r ks y s t e m sa n ds oo n , s u c ha sr o b o tp a t hp r o b l e m ，p r o d u c t i o nd e s i g np l a n n i n g ，a i r p o l l u t i o nc o n t r o l ，e t c ，a r es 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 s m e t h o d sf o rs o l v i n gs i p p r o b l e m sh a v eb e e np a i dm o r ea t t e n t i o ni na r e a so fo p t i m i z a t i o n t u r n i n gt h es e m i - i n f i n i t e p r o g r a m m i n gp r o b l e mi n t on o n l i n e a ro p t i m i z a t i o np r o b l e mw i t hf i n i t ec o n s t r a i n t si so n eo f t h er e p r e s e n t a t i v em e t h o d s t h ed u a lm e t h o db a s e do nn o n l i n e a rl a g r a n g ef u n c t i o nr e q u i r e s n or e s t r i c t i o n so nt h ef e a s i b i l i t yo fp r i m a lv a r i a b l e s n o n l i n e a rl a g r a n g em e t h o d sp l a ya l l i m p o r t a n tr o l ei ns o l v i n gc 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 s t h i sd i s s e r t a t i o ni sd e v o t e dt o t h es t u d yo fl o g a r i t h m i cl a g r a n g i a n sf o rs o l v i n gs e m i - i n f i n i t ep r o g r a m m i n ga n dg 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 g t h em a i nr e s u l t so b t a i n e di nt h i sd i s s e r t a t i o nm a yb es u m m a r i z e d 嬲f o l l o w s ： c h a p t e r2d i s c u s s e sl o g a r i t h m i cl a g r a n g ef u n c t i o nm e t h o df o rs o l v i n gs e m i - i n f i n i t e p r o g r a m m i n gp r o b l e m f i r s t l y ，n o n l i n e a rl a g r a n g em u l t i p l i e ra n dl o g a r i t h m i cl a g r a n g e f u n c t i o no fs 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 ma r ed e f i n e d ，a n dt h ed u a l i t yt h e o r yb a s e do n p r o p o s e dl a g r a n g i a ni sa n a l y z e d s e c o n d l y ，f i r s ta n ds e c o n do r d e ro p t i m a l i t yc o n d i t i o n s b a s e do nl o g a r i t h m i cl a g r a n g i a na r ep r o v e d f i n a l l y ，t h en e c e s s a r yc o n d i t i o n sf o r t h e e x i s t e n c eo fn o n l i n e a rl a g r a n g em u l t i p l i e r sa r ei l l u s t r a t e db ya ne x a m p l e c h a p t e r3d i s c u s s e sl o g a r i t h m i cl a g r a n g ef u n c t i o nm e t h o df o rs o l v i n gg 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 gp r o b l e m f i r s t l y ，t h el o g a r i t h m i cl a g r a n g ef u n c t i o no 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 gp r o b l e mi sd e f i n e d s e c o n d l y ，f i r s ta n ds e c o n do r d e ro p t i m a l i t y c o n d i t i o n sb a s e do n p r o p o s e dl a g r a n g i a na r ep r o v e d c h a p t e r4a n a l y z e st h er e l a t i o n s h i pb e t w e e 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 ma n d g 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 gp r o b l e m i ti sf e a s i b l et h a tt r a n s f o r m i n gt h e g 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 gi n t ot h es 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 mu n d e r m - fc o n s t r a i n tq u a l i f i c a t i o n f u r t h e r m o r e ，t h ec o n d i t i o n sf o rt r a n s f o r m a t i o na r ee x p l o r e da n d p r o v e d k e yw o r d s ：s e m i - i n f i n i t ep r o g r a m m i n g ；g e n e r a l i z e ds e m i - i n f m i t ep r o g r a m m i n g ；l o g a r i t h m i cl a g r a n g i a n ；n o u l i n e a rl a g r a n g em u l t i p l i e r ；o p t i m a l i t yc o n d i t i o n s 辽宁师范大学硕士学位论文 目录 摘要。i a b s t r a c t i i i 弓i言l 2 半无限规划问题3 2 1 假设条件3 2 2 对数型l a g r a n g e 函数4 2 3 最优性条件1o 2 4 算例l1 3 广义半无限规划问题14 3 1 预备知识1 4 3 2 对数型l a g r a n g e 函数1 6 3 3 最优性条件1 6 4 广义半无限规划问题与半无限规划问题的关系。1 8 5 总结。2 4 参考文献2 5 攻读硕士学位期间发表学术论文情况一2 7 致 射2 8 辽宁师范大学硕士学位论文 1 引言 由于工程、经济、管理、信息技术以及计算机网络系统等领域的许多实际问题的数 学模型均为半无限规划模型，如h e t t i c h 和s t i l l 在【1 】中探讨的机器人路径问题；w a n g 和f a n g 在【2 中研究的产品生产设计规划问题：h e t t i c h 和k o r t a n e k 在 3 】中分析的空气 污染控制问题等都属于半无限规划问题的范畴因此，半无限规划模型的研究具有十分 重要的理论意义和实用价值，半无限规划问题成为求解实际问题的强有力工具，它的理 论分析与求解方法倍受关注 半无限规划问题的早期理论是由c h a m e s 等人建立的，k o r t a n e t 3 1 、l 6 p e z 4 1 1 5 】和 p o l a k t 伽1 1 】等人在这方面做了大量的工作b o n n a s 2 4 1 、g o b e t n a 2 5 】以及s t e i n t 2 6 】给出了关于 半无限规划问题更细节的讨论和研究：p o l a k 在 6 6 中对半无限规划概括出了三类一般模 型，分别建立了他们的最优性条件并且给出了一些有效算法；黄力人和吴恭孚在 8 】中实 质性的改进了由k a w a s a k i l 9 1 10 】对半无限规划问题的模型建立的最优性条件； j j r u c k m a n n 和a s h a p i r o 在【1 1 】中讨论了求解半无限规划问题的增广l a g r a n g e 函数，探讨 了相应增广l a g r a n g e 乘子的存在的充分必要条件 随着高新技术的发展和社会经济的深刻变化，在工程优化设计，电子线路优化设计， 计算机辅助设计及最优控制等许多实际问题中出现了广义半无限规划的数值模型，如 g r a e t t i n g e r 和i c r o g h 在【1 7 】中研究的机器人设计问题；k r a b s 在【18 】中分析的球的加热和 煮沸的最短时间问题；相对c h e b y s h e v 近似【2 4 1 1 2 5 1 等都属于广义半无限规划问题因此， 研究广义半无限规划问题具有重要的现实意义广义半无限规划将半无限规划中指标集 由固定集变为集值映射，这极大的增加了问题的难度并出现了很多与半无限规划和非线 性规划不同的特征解决广义半无限规划问题时，最常见的方法就是在一定的条件下将 它转化为等价的标准半无限规划或有限规划来解决，比如利用增广拉格朗日函数或罚函 数就可实现上述等价转化j o n g e n0 9 】、s h a p i o r t 2 0 1 等人将模型中的y i 推广为极值映象 y ，( x ) ，并给出了最优性条件；j - j r u c k m a n n 在文献 2 1 】中讨论了广义半无限规划问题 的最优性条件和一些应用性算例 本文考虑如下形式的半无限规划问题( s i p ) 卿( x ) s t g ( x ，) o ，c o q ( 1 1 ) 其中，q 是一个( 可能无限) 的非空集合，f ：r ”jr 和g ：r ”q - - - r 是实值函数 对于九：q 一尺，记三( x ，九) - f ( x ) 一九佃) g ( z ，c o ) 作为问题( 1 1 ) 的标准l a g r a n g e 函数 求解半无限规划问题的对数型l a g r a n g e 函数 以及如下形式的广义半无限规划问题( g s i p ) m i n f ( x )s t x m = x r ”fg ( x ，少) o ，y 】，( x ) 】，( x ) = 少r 7iv ，( x ，y ) 0 ，三( 1 2 ) 其中，三为有限指标集我们假设函数厂，g ，m 都是连续函数，并且集值映射】，满足： y ：x r ”一】，( x ) c r 7 ，】，( x ) c c o ，对v x r ”，c oc r 7 为紧集 ( 1 3 ) 注意到，若l ，( x ) 不依赖于x ，即v ，( x ，y ) = v ( y ) ，l ，那么广义半无限规划问题就转 化为半无限规划问题w e b e r 在【2 2 】中研究了在一定的紧的条件下，并且r ( x ) 满足l i c q ， 广义半无限规划问题就可以转化为半无限规划问题g u d d a t 、j o n g e n 以及r t l c k m a n n 在 【2 3 】中也分析了，如果对xoi ，】，( i ) 满足m f c q ，下层问题的可行集r ( x ) 与】，( i ) 同胚， 这种转化也是可行的 近几年来，许多学者在半无限规划问题的理论研究和与算法设计方面取得了许多重 要成果，其中，将半无限规划问题转化为有限的非线性优化问题成为研究的热点之一， 基于非线性l a g r a n g e 函数建立的求解优化问题的对偶方法对原始变量的可行性没有限 制，因此，非线性l a g r a n g e 函数方法在求解约束优化问题中扮演着重要的角色本文主 要研究半无限规划问题的求解方法h e s t e n s 2 7 1 和p o w e l l i 2 8 1 研究了有限多个等式约束的 增广l a g r a n g e 函数法；p o l y a k 在文献【r 2 】中研究了求解具有有限个不等式约束的非线 性优化问题，并提出了两个修正的l a g r a n g e 函数，以及基于该函数的有效的算法另外， 其他学者在半无限规划方面也做了大量的工作i ”h 1 6 】 本文主要探讨求解s i p ，g s i p 的对数型l a g r a n g e 函数方法第二章定义了s i p 问题 的对数型l a g r a n g e 函数以及相关对偶理论，分析了最优性条件，说明了非线性l a g r a n g e 乘子存在的必要条件并通过具体算例得到验证；第三章给出了g s i p 的对数型l a g r a n g e 函数，探讨了最优性条件，并给出证明；第四章，讨论说明了在一定的条件下，g s i p 可以转化为s d 。 一2 一 辽宁师范大学硕士学位论文 2 半无限规划问题 p o l y a k 在文e t 犬 1 2 】中研究了求解具有有限不等式约束的非线性优化问题，并提出了 两个修正的l a g r a n g e 函数，以及基于该函数的有效的算法鉴于非线性l a g r a n g e 函数 在求解非线性优化问题的成功，本章主要探讨在一定的条件下，将半无限规划问题转化 为约束有限的非线性优化问题，从而利用对数型l a g r a n g e 法进行求解 考虑如下形式的s i p 问题： ( 尸) m i n 厂( x ) s t g ( x ，c o ) 0 ， c o q ( 2 1 ) j e 其中，q 是一个( 可能无限) 的非空集合，厂：r ”- - + r 和g ：r “q r 是实值函数 对于九：q - - + r ，记j 巳( x ，九) _ f ( x ) - l ( t o ) g ( x ，) 作为问题( 2 1 ) 的标准l a g r a n g e 函数 e q 本章讨论s i p 问题的对数型l a g r a n g e 函数方法2 1 给出问题( 尸) 满足的假设条件；2 2 给出非线性l a g r a n g e 乘子的定义，并得出对数型l a g r a n g e 函数的相关性质；2 3 讨论s i p 问题基于对数型l a g r a n g e 函数的最优性条件，并给出证明；2 4 通过算例说明非线性 l a g r a n g e 乘子存在的必要条件 2 1 假设条件 假设问题( 尸) 满足如下条件： ( 1 ) f ：r ”一r 和g ：r ”q - - + r 是二阶连续可微的； ( 2 ) g 在而点满足广义m f 约束规范4 1 如果存在一个向量h r “，使得 d , g ( x o ，m ) h 0 ，v i a x ( x o ) 其中( x o ) = 细q ig ( x o ，) = o ) ； ( 3 ) k k t 条件设x 。是问题( 尸) 的( 全局或局部) 最优解，则在一定条件下，存在 f ：q - - + r 满足 v f ( x 。) = f ( ) v , g ( x o ，) ， g ( x 。，) 0 ，f ( ) o ，f ( ) g ( x 。，) = o ，q e n ( 4 ) 假设g ( x ，) 二阶连续可微，记 z l g ( x ，) 向= 办7 v ，g ( x ，) ，d 叠g ( x ，- ) ( 办，办) = h rv 二g ( x ，) 乃 ( 5 ) 二阶最优性条件假设函数( ) 和g ( ，c o ) ，q 是二阶连续可微，并且g ( ，) 在 点满足广义m - f 约束规范，则下n - 阶条件成立如果( ，九) 是问题( 尸) 的一个k t 对，则 求解半无限规划问题的对数型l a g r a n g e 函数 d 2 l ( x o ，九) ( 厅，h ) 0 ，h c ( x o )( 2 1 1 ) 其中c ( x o ) _ j l r ej 6 f 啊ih7 v ，g ( x o ，) 0 ，v o a q ，h v f ( x 0 ) o 2 2 对数型l a g r a n g e 函数 考虑连续函数空间c ( q ) ，假设下述条件成立： ( 4 1 )对任意有限集合轴l 一，肘) cq 和实数只，扛1 ，m ，存在y c ( q ) 使得 y 如i ) = 只，汪1 ，i ，m 记空间r n ：= 九c ( n ) 1 只有限个x ( o ) 0 ) 对九r m ，y c ( n ) 定义内积为 疋，满足0 ( j ，) = 0 当且仅当y = 0 时 定义2 2 1 九r 称为问题( p ) 的非线性l a g r a n g e 乘子如果存在k 0 ，使得 v ( y ) v ( o ) + 七1 0 ，定义 三( x ，九，七) - 瞄i n ( f q ) 厂( x ) 一k 1 ( 九，a ( 砂) ) ig ( x ，) 一y 佃) o ，c o q ( 2 2 3 ) 为问题( p ) 的非线性l a g r a n g e 函数 一4 一 辽宁师范人学硕七学位论文 通过计算司得 心i n ( f n ) v ( y ) 一k 一( 九，0 【( 砂) ) ) 2 心i n ( f n ) 剃i n f f ( x ) 一k 一( 九，a ( k y ) ) i g ( x , o ) 一y 和) 0 ，q ) = ，i n f 脚i n ( f n m x ) 一k _ 1 ( 九，t x ( k y ) ) ig ( x ，) 一y 佃) o ，0 3 q 所以 ，醢) v ( y ) _ k - i ( 九，0 【( 妙) ) 2 磐l ( x , l ，忌) ( 2 2 4 ) 对k 0 ，考虑问题( 尸) 的对偶问题( o k ) ( q ) 黔姊( 九，七) ；剃i n fz ( x ，九，七) ( 2 2 5 ) 定义2 2 3 一个向量对( ，f ) 是非线性l a g r a n g e 函数的局部鞍点，如果存在 x o r ”，佃) 0 ，q ，使得 l ( x ，石，七) l ( x o ，f ，七) l ( x o ，九，七) ，v x s ( x o ；e ) 其中，s ( x o ；s ) ：= x r ”0 x - x o 阵8 , 8 o ) 本文主要讨论0 【( y ) = l i l l y ) + 1 】时的对数型l a g r a n g e 函数，即 地a ) = ，掰i n f m ) 以1 互) l n k y ( o ) + 1 i g ( x , c o ) 一y 晒) 0 徊幽 = f ( x ) - k 卅e ( o d ) l n k g ( x ，) + l 】 ( 2 2 6 ) 对九r m 和v 七 0 ，由( 2 2 4 ) 知，如果g ( x ，国) 0 ，则l n 【堙( x ，) + 1 】0 ，从而 一七1 x ( o ) t n k g ( x ，) + l 】o 所以s u pl ( x ，九，七) = 厂( x ) 否贝i j ，s u pl ( x ，九，七) = 佃，所以 九e r n 九e r l 0 ) v a l ( p ) = i n f s u p 三( x ，九，七) ( 2 2 7 ) x e r “x e r n ) 。、。 定理2 2 1 对适当的七 o ，如果向量对( ，f ) 是三( ，j j ) 的一个局部鞍点，则( ，f ) 是问题( p ) 的k t 对 证明由于( ，天) 是三( ，七) 的局部鞍点，故对v x ( o ) 0 , o q ，有 即 f ( x o ) 一k 一1 x ( c 0 ) l n k g ( x 0 ，) + 1 】厂( ) 一k 一1 九徊) 1 1 1 【堙( 秭，) + 1 】， e i le q 求解半无限规划问题的对数型l a g r a n g e 函数 天如) 1 l l 【姆( ，) + 1 】九佃) l n 【堙( ，) + 1 】 ( 2 2 8 ) 对v 九 ) 0 , o q ，有 九( o ) h k g ( x 0 ，) + l 】o ，q ( 2 2 9 ) 假设存在k ) o ，q ，使得k ( o d ) l n k g ( x o ，c o ) + l 】 0 ，有 z - 石( o ) l n k g ( x o ，) + 1 】硪。( o d ) l n k g ( x o ，) + 1 】， ( 2 2 1 0 ) 但由于k ( c o ) l n k g ( x o ，) + 1 】 0 成立是不可能的，故 ( 2 2 9 ) 式成立 因为九佃) 0 ，c o q ，所以l n 堙( x 0 ，) + 1 】0 ，即g ( x o ，) 0 ，因此是问题( 尸) 的可 行解 由于九的任意性，对( 2 2 8 ) 式取九= 0 ，得f ( c o ) l n k g ( x o ，) + 1 】0 ，q 由( 2 2 9 ) 式得f 佃) l n 【姆( ，) + 1 】0 ，q ，因此 x ( o ) l n k g ( x o ，) + 1 】= 0 , o q 显然，九佃) g ( ，) = 0 , o q 由于而= a r g 恶三( x ，f ，j ) ，所以v ，三( ，后) = o ，即 ：v ，f ( x o ) 一至衲罴k - 。o 湍, = 。 ：e qn 5w ，t 所以，v ，厂( ) = 佃) v 。g ( x o ，) 口 定理2 2 2 对某个k 0 ，( x o ，f ) 是一个局部鞍点当且仅当 ( 1 ) 是问题( p ) 的局部最优解； ( 2 ) f 是问题( q ) 的局部最优解； ( 3 ) 对偶间隙为0 证明由定理2 2 1 知，是问题( p ) 的k - t 点，则f 佃) g ( ，c o ) = 0 , o q 所以， l 一( c o ) l n k g ( x o ，) + 1 】= o ，q 根据局部鞍点的定义，对坛s ( x 0 ；e ) ，我们有 f ( x 0 ) = f ( x o ) - k _ 1 l ( c o ) l n k g ( x o ，c o ) + 1 _ l ( x o ，j j ) t ( x o ，九，七) ，即 k e g ( ，f ) 是( ，后) 的局部鞍点 口 定理2 2 3f 是非线性l a g r a n g e 乘子，：c o 是问题( p ) 的局部最优解当且仅当存在某 个七 0 ，( x 0 ，f ) 是( ，后) 的局部鞍点 证明由( 2 2 5 ) 和( 2 2 7 ) 得，v a l ( p ) v a l ( q ) 如果存在非线性l a g r a n g e 乘子f ，则 1 主1 ( 2 2 4 ) 得， v ( 0 ) = 舛、l ( x ，九，七) ，所以v a l ( o , ) v ( o ) = v a l ( p ) 所以v a l ( p ) = v a l ( d , ) 由于 j e 岱再l 善j 蒜) 三( x , x , k ) o ，( x 0 ，石) 是三( ，七) 的一个局部鞍点，则而是问题( p ) 的局部最 优解，f 是问题( 域) 的一个局部最优解那么我们有 v ( o ) = i n f l ( x ，九，k ) x e s ( x o ；c ) 2 蒜) 蒜抄h 一荟砸) l n k y ( c o ) + 1 l g ( x , c o h m 0 q = y 酊i n ( f n ) ，醮) 厂( x ) 一矿1 互f 佃) 1 1 1 砂) + 1 1 9 ( x , c o ) 一y ) 0 ，q = y i n ( f n ) 1 ，( 少) 一旷1 荟砸) l i l 【砂佃) + q fg ( x , o ) 一y 佃) o 璐 1 ，( y ) 一一佃) l n 【砂晒) + 1 】 求解半无限规划问题的对数型l a g r a n g e 函数 所以，九是非线性l a g r a n g e 乘子 口 对于有限集合o - 1 ，一，。 c 7 f l ，问题( 尸) 的离散化问题记为( p o ) ( 尸o )m i n f ( x ) s t g ( x ，q ) 0 ，f = 1 m 及( 严) 的参数化问题 ( 够) m i n f ( x ) s t g ( x ，q ) 一y 佃f ) o ，f = 1 ，m ( 2 2 l1 ) 类似的，对于( x ，九，k ) r ”r ”疋，我们考虑相关对数型l a g r a n g e 函数 r ( x ，九，后) 一斌i n f 。 f ( x ) 一k 一1 九佃) h 砂如t ) + 1 l g ( x , c o ，) 一y ( c o 。) o ) = f ( x ) - k 。1 九的，) l n k g ( x ，一1 】 问题( 尸o ) 的对偶问题记为( p ；) ( 研) 黔翳口( x ，九，七) 注意到对y ( t o ，) = 只，待1 ，m ，问题( 2 1 1 ) 是问题( 2 1 ) 的一个离散化，所以 v ( y ) 伊( y ) 定理2 2 4 设f r n 是问题( 尸) 的一个非线性l a g r a n g e 乘子，令。净s u p p ( f ) ，则 v a l ( p ) = v a l ( o ) ，并且问题( p ) 和问题( p ) 有相同的最优解 证明对v 七 0 ，九r ( m , a = s u p p ( k ) 由于当o 时，y ( 0 3 ) = y 。如) ，萑o 时， y 细) = 0 ，所以 地，m ) 2 蒜) 饥垆互九 ) l n k y ( o 。) + 1 1 1g ( x , 0 3 ) 叫啦0 , oe 哂 = ，i 酽n f f ( x ) 一k 。1 三九) l n 砂，) + 1 l g ( x , 啦) 一y ( c o 。) o ，扛l ，肌) = r ( x ，九，七) 类似的，l ( x ，九，k ) = r ( x ，九，k ) 因为是问题( 尸) 的非线性l a g r a n g e 乘子，所以对适当的k 0 ，是问题( q ) 的 一个局部鞍点，则 ，。恐) 三( x ，九，七) ，。恐) 三( x ，九，七) ， 于是她、口( x ，九，k ) i 。n ，f 、f ( x ，九，k ) 工5 t o 善j工e j 【知善j 所以，f 是问题( q ) 的一个局部最优解，并且 v a l ( d t ) = ，憝) r ( x ，九，七) - ，撼) l ( x ，九，七) 2 v a l ( d 女) j 6 t j 知二c )j e j 善) 一8 一 辽宁师范大学硕士学位论文 从而可得v a l ( p ) v a l ( 尸o ) v a l ( 研) = v a l ( d t ) 由存在非线性l a g r a n g e 乘子f 知v a l ( p ) = v a l ( d , ) ，所以v a l ( p ) = v a l ( p ) 如果x o 是问题( p ) 的局部最优解，由于是问题( 尸) 的非线性l a g r a n g e 乘子，则 ( ，九) 是三( ，k ) 的一个局部鞍点，即 l ( x o ，九，k ) l ( x o ，九，k ) t ( x ，九，k ) 由于( x ，九，七) = f ( x ，九，k ) ，所以l 。( x o ，九，k ) l 。( x o ，f ，七) r ( x ，f ，k ) 所以，( ，九) 是f ( ，k ) 的一个局部鞍点，而是问题( p ) 的一个局部最优解 反之，如果j c o 是问题( 尸o ) 的一个局部最优解，f 是问题( 尸) 的非线性l a g r a n g e 乘子， 则v ( 少) ，( o ) + 一元- ( c o ) h a i l ( c o ) + 1 ，即 e q v a l ( p y ) v a l ( p ) + _ 天- ( c o ) l n k y ( o a ) + 1 e ：q 由v a l ( p ) - - v a l ( ) 得v a l ( p j ，) = 词( 碍) ，则 砌( 哆) v a l ( p o ) + 后一f 佃) l n 【砂细) + 1 】 t o o 所以，f 是问题( 尸o ) 的一个非线性l a g r a n g e 乘子，( ，c ) 是f ( ，七) 的一个局部鞍 点，显然的，( 而，f ) 也是三( ，七) 的一个局部鞍点所以，而是问题( p ) 的一个局部最优解， 即问题( p ) 与问题( p o ) 有相同的最优解 口 考虑下述条件： ( 彳2 ) 存在一个有限集合o = 细l ，。) c q 使得v a l ( p ) - - v a l ( p ) ( 彳3 ) 问题( 尸o ) 存在非线性l a g r a n g e 乘子 由定理2 2 4 知，条件( a 2 ) 是问题存在非线性l a g r a n g e 乘子的必要条件 对y c ( q ) ，令只= y ( o ，) ，c o ，o ，r r 鳓，使得 s u p p ( k ) = o ，r 细j ) = 石，f = 1 ，m ， 则尼- 1 佃) l n 【砂 ) + 1 】= 后一r ) 1 1 1 砂细) + l 】 t a ) q ， e q 由条件( a 3 ) 得， v t y ) = v a l ( p a v a l ( 罗y ) 砌( 尸) + z ( t o ) l n k y ( t o ) + 1 日了 = v ( o ) + 一r 如) l i l 【砂佃) + 1 】 求解半无限规划问题的对数型l a g r a n g e 函数 所以，r 是问题( p ) 的非线性l a g r a n g e 乘子因此，为证明s i p 问题( 尸) 具有非线性 l a g r a n g e 乘子，只需证明条件( a 2 ) ，( a 3 ) 成立即可 2 3 最优性条件 在本节，我们给出问题( 尸) 基于对数型l a g r a n g e 函数三( ，七) 存在最优解的最优性条 件 定理2 3 1 ( 一阶最优性条件) 假设条件( 1 ) 一( 4 ) 成立，若j c 0 是s i p 问题( 尸) 的一个 局部最优解，则存在2 - r ( m ，并且对v 七 0 ，使得 d x l ( x o ，f ，k ) h = 0( 2 3 1 ) 证明因为l ( x ，九，七) = ) 一k - 1 l ( o d ) l n k g ( x ，) + 1 】， 贝l jd x l 九啪纠眠m o ) - 乏确蒜赫) 因为和满足k k t 条件，所以q 厂( x 。) = r f ) v ，g ( ，) ) ，那么 d x l ( x o , x - , k ) h = h r 丕虱叻v x g ”神t 1 - 志】) e s 2z 5 “0 ”，o 又因为九( 0 3 ) g ( x o ，) = 0 ，九细) 0 ，所以d , l ( x o ，九，k ) h = 0 口 定理2 3 2 ( 二阶最优性条件) ( 1 ) 若x o 是问题( p ) 的一个局部最优解，f 是问题( p ) 的非线l a g r a n g e 乘子，则 v 后 0 ，v h c ( x o ) = r ”ih 2 v ，g ( x o ，) o ，v q ，h w ( x o ) o ) d 三r ( x o ，九，j j ) ( 厅，厅) o ，v h c ( x o )( 2 3 2 ) ( 2 ) 若对v k 0 ，v h c ( ) ，存在问题( 严) 的非线性l a g r a n g e 乘子f ，满足 p 三f ( x o ，九，七) ( 办， ) o ，v h c ( x o ) ，则而是问题( p ) 的局部最优解 证明( 1 ) 因为r ( x ，九，后) = f ( x ) - k - 1 z , ( o o ) l n k g ( x ，) + 1 】，则 三i 暑f ( x o ，九，后) ( 办，办) = 办7 v l f ( x o ) 一薹( ) 黜+ 委f ( ) 竺二基鼍毫美要兰铲) 1 z 由于 x o 是问题( 尸o ) 的一个局部最优解，f 是问题( 严) 的非线性l a g r a n g e 乘子，则( ，f ) 是 辽宁师范大学硕士学位论文 f ( ，露) 的一个局部鞍点那么( x 。，) 是问题( p ) 的一个k - t 对，满足条件( 2 1 1 ) 所以