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

r 学位论文作者签名： 幽rl li iilli ii i i l i j i lr l l l , | l i i i i i i i i i i i i i i i l a l y 18 9 0 0 6 7 果。论文中除特别加以标注 ，其他同志的研究成果对本 学位论文版权的使用授权书 本学位论文作者完全了解辽宁师范大学有关保留、使用学位论文的规定，及学校有 权保留并向国家有关部门或机构送交复印件或磁盘，允许论文被查阅和借阅。本文授权 辽宁师范大学，可以将学位论文的全部或部分内容编入有关数据库并进行检索，可以采 用影印、缩印或扫描等复制手段保存、汇编学位论文，并且本人电子文档的内容和纸质 论文的内容相一致。 保密的学位论文在解密后使用本授权书。 学位论文作者签名：指导教师签名： 五皇盘i 垄 签名日期： 幽f 年午月r 日 辽宁师范大学硕士学位论文 摘要 工程设计，最优控制，信息技术以及经济均衡等领域的许多实际问题的数学模型均 为半无限规划模型，半无限规划已成为求解实际问题的强有力的工具，关于半无限规划 问题的求解方法倍受关注，将半无限规划问题转化为约束有限的非线性优化问题是具有 代表性的方法之一非线性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 函数，并基于该函数讨论了广义半无 限规划问题的一阶与二阶最优性条件 第四部分讨论了半无限规划问题与广义半无限规划问题相互转化的条件证明了在 一定的紧的假设条件下，并且集合】，( x ) 满足线性无关约束规格( l i c q ) ，这种转化是可行 的；或若对x i ，函数】，( i ) 满足m f 约束规格( m f c q ) ，下层问题的可行集r ( x ) 与 】，( i ) 同胚，这种转化也可行 关键词：半无限规划；广义半无限规划；指数型l a g r a n g e 函数；非线性l a g r a n g e 乘 子；最优性条件 a n e x p o n e n tl a g r a n g i a n f o rs o l v i n gs e m i i n f i n i t ep r o g r a mm - i n g p r o b l e m a b s t r a c t m a n yp r a c t i c a lp r o b l e m si nt h ef i e l d so fe 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 n t e c h n o l o g ya n de c o n o m i ce q u i l i b r i u me t c ，c a nb em o d e l e da sas e m i - i n f i n i t ep r o g r a m m i n g ( s i p ) p r o b l e m ，w h i c hh a sb e c o m eap o w e r f u lt o o lt os o l v ep r a c t i c a lp r o b l e m si nr e s e n ty e a r s m e t h o d sf o rs o l v i n gs i pp 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 n t u r n i n gs e m i - i n f m 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 n lf 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 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 li m p o r t a n tr o l ei ns o l v i n g c 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 na i m sa tt r a n s f o r m i n gs i pp r o b l e mi n t o n o n l i n e a rp r o g r a m m i n gw i mf i n i t ec o n s t r a i n t s ，d i s c u s s i n ga ne x p o n e n tl a g r a n g ef u n c t i o nf o r s o l v i n gt h es i pp r o b l e ma n dc o r r e s p o n d i n gf 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 t h o s eo fg 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 ( g s l p ) p r o b l e ma r ed i s c u s s e da sw e l l m o r e o v e r ，t h er e l a t i o n s h i p sb e t w e e ns i pp r o b l e ma n dg s i pp r o b l e ma r ea n a l y z e d t h em a i n r 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 da sf o l l o w s ： c h a p t e r2d i s c u s s e se x p o n e n tl 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 ，t h ec o n d i t i o n sf o rt r a n s f o r m i n gs i pp r o b l e mi n t on o n l i n e a r p r o g r a m m i n gw i t h f i n i t ec o n s t r a i n t sa r ea n a l y z e d 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 d e x p o n e n tl a g r a n g ef 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 e d u a l i t yt h e o r yb a s e do np 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 r o p t i m a l i t yc o n d i t i o n sb a s eo ne x p o n e n tl a g r a n g i a na r ed i s c u s s e d f i n a l l y ，a l le x a m p l ei s p r e s e n t e d t oi l l u s t r a t en e c e s s a r yc o n d i t i o nf o r t h ee 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 c h a p t e r3d i s c u s s e sa l le x p o n e n tl a g r a n g i a nf o rs o l v i n gg s i pp r o b l e m i tp r e s e n t st h e s t a n d a r dl a g r a n g i a no ft h el o w e rl e v e lp r o b l e ma n dd e f i n e sa ne x p o n e n tl a g r a n g ef u n c t i o n o ft h eu p p e rl e v e lp r o b l e m f i r s t - o r d e ra n ds e c o n d - o r d e ro p t i m a l i t yc o n d i t i o n sf o rg s i p p r o b l e ma r ei n v e s t i g a t e db a s e do np r o p o s e dl a g r a n g i a n s e c t i o n4d i s c u s s e st h ec o n d i t i o n so ft r a n s f o r m i n gt h eg s i pp r o b l e mi n t o t h es i p p r o b l e m i tp r o v e s t h a tt h et r a n s f o r m a t i o nc a l lb ed o n e ( a tl e a s tt h e o r e t i c a l l y ) u n d e r a p p r o p r i a t ea s s u m p t i o n s ，s u c h 嬲c o m p a c t n e s s a n dl i n e a r i n d e p e n d e n t c 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 ) i ss a t i s f i e db ys e t 】，( x ) o nt h eo t h e rh a n d ，i th a sb e e ns h o w n t h a tt h e t r a n s f o r m a t i o ni sf e a s i b l ei ff u n c t i o n 】，( i ) s a t i s f i e st h em fc o n s t r a i n tq u a l i f i c a t i o na n dt h e f e a s i b l es e t l ，( x ) o fl o w e rp r o b l e mi sh o m e o m o r p h i ct of u n c t i o n 】，( i ) w h e nxc o n v e r g e st o i 求解半无限规划问题的指数型l a g r a n g e 函数 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 i n i t ep r o g r a m m i n g ；e x p o n e n t l a g r a n g i a n ；n o l l l i i l 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 i v 1 弓i言1 2 半无限规划问题4 2 1 假设条件4 2 2 指数型l a g r a n g e 函数4 2 3 一阶与二阶最优性条件1 0 2 4 算例12 3 广义半无限规划问题1 4 3 1 预备知识1 4 3 2 指数型l a g r a n g e 函数1 6 3 3 一阶与二阶最优性条件l6 4 半无限规划问题与广义半无限规划问题的关系1 9 5 总结2 5 参考文献2 6 攻读硕士学位期间发表学术论文情况2 8 致谢2 9 一v 一 1 引言 众所周知，工程设计，最优控制，信息技术以及经济均衡等方面的许多实际问题的 数学模型均为半无限规划问题如机器人路径问题i ，产品生产计划问题 2 1 ，空气污染 控制问题1 3 】，c h e b y s h e v 逼近问题等等因此半无限规划成为我们解决实际问题的重要 工具 考虑如下形式的半无限规划问题( s i p ) ： ( p ) 劣s j g ( 嚣xc o ) o q ( 1 1 ) ，0 ，q 、7 其中q 是一个( 可能无限的) 非空集合，f ：r ”一r 与g ：r ”q 专r 是实值函数记 l ( x ，九) ：= 厂( x ) 一芝：九( ) g ( x ，) 面 为问题( p ) 的标准l a g r a n g e 函数，其中九：q jr 是实值函数 关于半无限规划问题的求解方法倍受关注m ，如l 6 p e z 和v e r c h e r t 7 1 研究了不可微 非凸半无限规划的最优性条件；p o l a k t 8 】研究了在工程设计中不可微优化的“数学效果 “( a p 用半无限规划解决大型工程问题) ；张庆祥【9 。1 1 】研究了非光滑非凸半无限规划的最 优性、对偶性和非光滑多目标半无限规划的弱非控解的充分条件张成科和陈世国1 1 2 1 对 在b a n a c h 空间上的局部l i p s c h i t z 函数提出了一些广义不可微函数，给出了此类半无 限规划的最优性条件：李师正和高荣兴【1 3 1 等研究了一个不可微半无限规划，给出了弱对 偶及强对偶的一个充要条件；杨洪礼与贺国平1 1 4 1 在f i s c h e r - b u r m e i s t e r 非线性互补函数 的基础上，得到了半无限规划问题的一个新的一阶必要条件，并将半无限规划问题转化 成一个光滑的无约束优化问题，给出了适合该问题的一个d a m p - n e w t o n 算法；贾世会， 吕绪华和万仲平f l5 】为了得到优化模型中半无限规划问题的局部最优解，结合z o u t e n d i j k 可行方向算法以及基于有限覆盖理论基础上的对约束集合离散的算法。给出了一种新的 求解半无限规划问题的离散与可行方向结合的算法，并根据择一定理以及一阶最优性充 分条件，证明了由此新算法得到的迭代点序列能够收敛到半无限规划问题的局部最优解 最后利用此新算法求解了一个半无限规划问题的实例，得到的迭代最优点序列收敛到了 最优解，验证了此算法的可行性：r u c k m a n n 等1 1 6 1 讨论了求解半无限规划问题的增广 l a g r a n g e 函数法，在一定条件下，将半无限规划问题转化为离散化问题进行研究，探讨 了相应增广l a g r a n g e 乘子的存在的充分必要条件 在问题( p ) 中r ，若将其扩展到函数域即1 0 】，( x ) ，x r ”，其中 求解半无限规划问题的指数型l a g r a n g e 函数 y ( x ) = j ，r l1 ( x ，y ) 0 ，z 三 ， 那么半无限规划问题就有可能转化成了广义半无限规划问题 广义半无限规划问题在工程优化设计，电子线路优化设计，计算机辅助设计及最优 控制中有着广泛的应用例如设计问题：球的加热或煮沸的最短时间问题：相对c h e b y s h e v 近似但到目前为止，大多数算法仅考虑广义有限规划问题，而且将广义半无限规 划问题转化为其它问题的算法并没有充分利用广义半无限规划问题的结构，因此难以获 得较高的效率如刘芳和王长钰0 7 1 利用指数型增广拉格朗日函数将一类广义半无限极 大极小问题在一定条件下转化为标准的半无限极大极小问题，使它们具有相同的局部与 全局最优解并提出了两个转化条件：一个是充分与必要条件，另一个是在实际中易于 验证的充分条件通过这种转化，又给出了广义半无限极大极小问题的一个新的一阶最 优性条件：刘茜 1 8 1 是通过一类由1 范数定义的精确罚函数，将广义的半无限极大极小规 划中的约束条件消除，使该问题转化为半无限极小极大极小规划在不需要假设集合 的条件下证明，当罚参数充分大时，半无限极大极小规划与广义半无限极大极小问题具 有相同的最优值，相同的局部最优解以及相同的全局最优解利用这种等价性，进一步 给出了广义半无限极大极小问题的一个最优性条件最后，对文中建立的最优性条件与 其它文献中的最优性条件之间的关系进行了讨论 周金川1 1 9 等人讨论了一类指标集依赖于决策变量的广义半无限规划首先通过刻 画目标函数的c l a r k e 导数和c l a r k e 次微分，建立其一阶最优性条件其次。通过对下层 问题o ( x ) 进行扰动分析，我们得到q ( x ) 的一个精确罚表示由此，利用一组精确罚函数 将广义半无限规划转化为经典的半无限极大极小规划，从而可利用已有的经典半无限规 划的算法来对广义半无限规划进行求解j j r t l c k m a n n 和a s h a p i r o 2 0 】考虑了广义半无限 规划问题，其中指标集的不等式约束依赖于决策变量，以及所涉及的函数都假设是连续 可微的通过对相应最优值函数的上下方向导数求边界而导出一阶最优性条件在最优 值函数是方向可微的条件下，基于给定的线性性质提出了一阶条件最后通过利用拟微 分研究了一阶充分条件o s t e i n 和g s t i l l t 2 1 】把半无限规划的一阶最优性条件推广到了广 义半无限规划问题中在没有局部限制的假设条件下，给出了局部极小问题的一阶充要 条件引用了r t l c k m a n n 和s h a p i r o 的思想，在对下层问题的限定在m f c q 条件下，给出 了充分必要条件的简短证明 考虑如下形式的广义半无限规划问题( g s i p ) ： 硕士学位论文 恶磐 ( x ) ( g s i p ) s t g ( x ，y ) 0 ，y 】，( x ) h x ) = j ，r l1 ，( x ，y ) 0 ，) 其中，三为有限指标集我们假设函数厂，g ，m 都是二阶连续函数和集值映射j ，满足： y ：r ”- - 92 彤，r ( x ) cc o ， ( 1 2 ) 其中对v x r ”，c oc r 7 为紧集 若r ( x ) 不依赖于x ，即v ，( x ，y ) = ，( y ) ，l ，那么广义半无限规划问题就转化为半 无限规划问题w e b e r t 2 2 1 已经指出，在一定的紧的假设条件下，并且r ( x ) 满足l i c q ，那 么广义半无限规划问题就可转化为半无限规划问题g u d d a t 2 3 】也指出，如果对x - - - ) i ， 】，( i ) 满足m f c q ，下层问题的可行集r ( x ) 与r ( i ) 同胚，这种转化也可行 本文主要探讨求解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 方法首先定义了求解半无限规划问题( 1 1 ) 的指数型l a g r a n g e 函数及非 线性l a g r a n g e 乘子，并给出了相关对偶性质的一般性讨论；其次讨论了问题( 1 1 ) 基于指 数型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 函数，并证明了广 义半无限规划问题基于指数型l a g r a n g e 函数的一阶，二阶最优性条件；第四部分我们讨 论g s i p 问题可以转化成s i p 问题的条件 求解半无限规划问题的指数型l a g r a n g e 函数 2 半无限规划问题 b e r t s e k a s 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 函 数的对偶性质及一阶，二阶最优性条件 2 1 假设条件 考虑如下形式的半无限规划问题( s i p ) ： m i n 厂f 扪 ( p ) 甍 g ( 。x 二o ，q ( 2 1 )、7 s j ，) o ，q 、7 上面问题中的函数满足下列假设条件： ( 1 ) f ，g 是二阶连续可微的； ( 2 ) g ( x ，) 在x o 点满足广义m a n g a n s a r i a n - f r o m o v i t z 约束规范，即存在向量h r ” 使得 r v ，g ( x o ，) o ，v a ( x o ) ， 其中a ( x o ) = c o qig ( x o ，) = 0 ) 【4 】 ( 3 ) 设x 。是约束优化问题( p ) 的( 全局或局部) 最优解，则当g ( x ，) 在点满足一定 条件时，存在九：qjr 满足 v f ( x 。) = 天( ) v ，g ( x 。，) ，g ( x 。，) o ，天( ) g ( x 。，) = o ，天( ) o ，q ( 4 ) 若g 阮) 在处是二阶连续可微的，则在点处它的一阶，二阶微分形式分别 为： d ，g ( x o ，) 办= h r v ，g ( x o ，) ，珑g ( x o ，) ( 办，办) = h t v 三g ( x o ，) 办 ( 5 ) 如果x 。是问题( p ) 的局部最优解和( 而，九) 是问题( p ) 的k t 对，那么 g l ( x o ，九) ( 办，h ) 0 ，v h c ( x o ) ， 其中c ( x o ) = h r 肘ih v ，g ( x o ，) o ，o 口a ( x o ) ，h v f ( x o ) 0 ) 2 2 指数型l a g r a n g e 函数 考虑连续函数空间c ( q ) ，假设下述条件成立： ( a 1 ) 对任意有限集细l ，一，脚 cq 和任意实数只，i = l ，m ，存在y c ( n ) 使得 辽宁师范大学硕士学位论文 y ( o j ) = y f ，i = l ，m 记r 娜轨c ( q ) 1 只有有限个q ，使得九佃) o ) ，对九r ( 和y c ( q ) ，定 义内积轨，y ) _ 九佃) y 佃) 对于有限集合6 = 舢i ，一，肼 cq 和少c ( q ) ，用y 。来表 示函数少( ) 在。上的限制，且厂 ) = y 苫：兰主三记s u p p ( m - - q f 九细) o ) 显 然有( 九，y ) = ( 九，y 。) ，其中o ：= s u p p ( z , ) 假设问题( p ) 的最优值v 对( p ) 是有限的，以及对每个x r ”，函数g ( x ，) c ( q ) 考 虑问题( p ) 的参数化问题( 0 ) ： ( 。) m 3 盖l n g 爱三一y ) 。，q ( 2 2 1 ) 其中y c ( q ) ，相应的最优值为v ( y ) ：= v a l ( g ) ，则有当y = 0 时，v ( o ) - - v a l ( p ) 考虑非负 值凸函数0 【：c ( n ) - - + r + ，使得a ( y ) = 0 当且仅当y = 0 定义2 2 1 如果存在k 0 与九r ( n 使得 ，( y ) v ( o ) + ( 九，后a ( y ) ) ，v y e c ( n ) ， 则称九是问题( p ) 的非线性l a g r a n g e 乘子，其中j i 奉0 【( 力= 七一1 0 【( 幼 命题2 2 1 设是问题( p ) 的局部最优解，则非线性l a g r a n g e 乘子集合是非空的且 下述条件是等价的： ( i ) m a n g a s a r i a n f r o m o v i t z 约束规范在x o 处成立； ( i i ) 奇异l a g r a n g e 乘子集合是空集； ( i i i ) l a g r a n g e 乘子集合是非空有界凸集 对v 九r q 与k 0 ，定义问题( p ) 的指数型l a g r a n g e 函数为 三( x ，硐= y 甄) m ) 一萋九( ) 1 巧帕】l g ( 删) 一少佃) o ，( d q = f ( x ) - k 。1 x ( o 。) 1 - e 蜊】( 2 2 2 ) 则相应的非线性l a g r a n g e 乘子九满足 以少) v ( o ) + 九幻) 1 一e 制】 x f f ( 2 2 2 ) 式如果g ( x ，) 0 ，那么- k - 1 九佃) 1 一p 一船j 柚) 】0 ，因此 s u pl ( x ，九，k ) = f ( x ) ； k e r m ) 求解半无限规划问题的指数型l a g r a n g e 函数 否则s u pl ( x ，九，k ) = + o o ，所以 a e r m ) v a l ( p ) 2 ，i n ；霄( 。九s 。u p 足。n ，l ( x , x , k ) ( 2 2 3 ) 又因为 y 搿i n f v ”扩1 互【1 _ p 由佃) 】) 2 删i n f 瑚i n f 。 f ( 炉扩1 乏 1 - p 由佃) 】i 贴灿) 一y ) 加脚印 2 臻y 搿i n fm m 一至九l 可圳刚( 圳) 一y ( t o ) o 删， 所以 y 掰i n f 1 ，( y h 。1 丕【1 _ p 由佃) 】) = 瑚i n ( 地a 囊) ( 2 2 4 ) 考虑问题( p ) 的对偶问题，记为( d k ) ： ( q ) 黔 臻l ( x ，九，吼 ( 2 2 5 ) 定义2 2 2 如果存在和九，其中九佃) o ，q ，满足 l ( x ，九，七) l ( x o ，九，七) l ( x o ，九，七) ，v x s ( x o ；) ，九( ) o ，q ， 其中s ( x o ；) = x r ”0x - - x oi 0 ，设( x 。，九) 是三( ， 后) 的局部鞍点，当且仅当x 。和九分别是问题( p ) 和( d 。) 的局部最优解，且对偶间隙为零 证明由于( x 。，九) 是三( ，k ) 的局部鞍点，故对v 九( c o ) o ，q ，有 f ( x 。) 一k 一1 天 ) 【1 一p 一堙知舯) 】厂( ) 一k 一1 九) 【1 一e 一堙知瑚】， c o d ic o f f l 即 e l ( o ) 1 一p 一培知神】九( ) 1 一p 一船而柚】 ( 2 2 6 ) e qt o r e f l 现在用反证法证明：对v 九 ) o ，q ，有 x ( o ) 【1 一e 一培知脚】0 , c o q ( 2 2 7 ) 假设存在k ) o ，q ，使得k ) 【1 一e 一坛两舯】 0 ，有 天( ) 【1 一p 蜊柚】诚。的) 【l p 蜊知扣】， ( 2 2 8 ) t 0 e a l 劬 辽宁师范大学硕士学位论文 但由于k 如) 【l p 啦川】 。，q ，( 2 2 8 ) 式不成立，故( 2 2 7 ) 式成立 又因为x ( o ) 0 ，q ，所以1 一e 一培而柚0 ，即g ( x o ，) 0 ，因此x o 是问题( p ) 的 可行解 由于九的任意性，对( 2 2 6 ) 式取九= 0 ，得 f ( c 0 ) 1 - e 蜊训】0 , o q 再由( 2 2 7 ) 式又有 九( ) 1 一p 一 苫知釉】0 ，q ， 因此 天( ) 1 一e 一七暑( 知舯】= 0 , o q 又由局部鞍点定义知，对任意x s ( x 。；) 有 f ( x 。) = ( ) 一k 一天佃) 1 一p 一堙如和) 】厂( x ) 一k 一1 天如) 1 一口一舭归) 】厂( x ) ， 因此是问题( p ) 的局部最优解显然九是问题( 取) 的局部最优解因为 l ( x ，九，七) l ( x o ，九，七) ， 所以 蝉地天，七) = 地，天，七) = 似。) 一k 一1 酗) 1 一p 蜊圳】= m 。) ， x “( x o ；cj：二 因此对偶间隙为零 反之，由于x 。是问题( p ) 的局部最优解，则g ( x o ，t o ) 0 因为九是问题( 仇) 的局部 最优解，所以 则i n 删f 地，- k ) ：- - ，媳) y 骢抄h 。1 乏f ( 酬l v 圳1 咖y 细) 20 , 睢f l 厂( ) - k 。1 元- ( o ) 1 - e 吲】( x 。) ， 由于对偶间隙为零，则描i n ( f 善) ( x ，九，七) = l ( x 0 , 九，七) = f ( x o ) ，又因为 f ( x o ) = s u pl ( x o ，九，后) ， 所以l ( x ，九，七) l ( x o ，九，k ) l ( x o ，九，七) ，故( x 。，九) 是l ( ，k ) 的局部鞍点 口 定理2 2 2 若x 。和九分别是问题( p ) 的局部最优解和非线性l a g r a n g e 乘子当且仅当 对于k 0 ，( ，九) 是l ( x ，九，七) 的一个局部鞍点 证明由( 2 2 3 ) 式推知 v a l ( p ) _ v a l ( d t ) 而且，如果存在非线性l a g r a n g e 乘子九，那由( 2 2 4 ) 式又可推知 v ( o ) = 她、l ( x ，九，忌) j e j ( 南；c ) 因此v a j ( 仇) v ( 0 ) ：= v a l ( p ) ，即 v a l ( p ) 2v a l ( d k ) ， 由于 删i n 圳fl ( x , ) l , k 垮瑚i n ( 郇fk s u 俨p ，l ( 工，九，后) = v a l ( p ) ：2v ( o ) = 瑚i n ( 圳f l ( x ，五七) ， 因此九是问题( q ) 的局部最优解又因为x 0 是问题( p ) 的局部最优解，所以( ，元) 是 l ( x , x ，k ) 的一个局部鞍点 反之，如果( x 0 ，九) 是l ( x , x ，后) 的一个局部鞍点，那么天是问题( b ) 的局部最优 解；是问题( p ) 的局部最优解；v a l ( p ) = v a l l ( q ) ，则有 ，( o ) _ i 。n ，f 、l ( x ，九，j j ) 工e j t x o ：c ， = ，悬懈i n ( f q ) 扒矿一丕f l 可坝1 j g ( 删一州0 ，喇 2 y 删i n f 1 ，一圣砸) 【1 - e - 妙( 0 ) ig ( 硼) 一y 的) o 舭q 0 ，i 1 ，m 卿) 。 s j ，) 一y ( f ) 0 ，1 ， 、7 记移。( 力：2 河( 嚣) 对于 ，九，七) r ”r ”b ，考虑问题( 巧) 的指数型l a g r a n g e 函数 r ( x ，九，七) ：2 璐n f f ( x ) 一九( 。) 1 卜 ，) o ，f = ，m ) 一8 一 = f ( x ) - k 。1 九 ，) 1 - e 啦似】 及其对偶问题( 噬) ： ( d 7 ) 黪 骤口( x ，九，吼 易知，问题( 2 2 9 ) 是问题( 2 2 1 ) 的离散化问题，因此v ( y ) 移口( y ) 定理2 2 3 若问题( p ) 有一个非线性l a g r a n g e 乘子九r n 且令o ：= s u p p ( 九) ，则 v a l ( p ) = v a l ( p 。) 且问题( p ) 与问题( p 。) 有相同的最优解集 证明对任意的七 o ，九尺( 哟与0 1 r o ms u p p ( 九) ，因为y o , 佃) ： y ? ) ，罗，所以 l0 ，萑a 砸九耻y 醢) 抓垆扩1 丕九1 _ p 由佃 1 g ( x , o ) 一y ( t o ) 0 衅q ) = 璐 ( x ) 一九佃t ) 【l p 制蚶】ig ( 工，) 一j ，佃，) o ，f - 1 ，2 ，肌) i ( x ，九，七) ， =l=iy 同理可证，l ( x ，九，七) = 口( 工，九，七) ，所以r ( x ，九，七) = y ( x ，九，七) 由于九是问题( p ) 的一个非 线性l a g r a n g e 乘子，故对适当的k 0 ，九是问题( q ) 的局部最优解，则 i n f 、r ( x ，九，七) = 瞰、l ( x ，九，七) i n f 、l ( x ，九，七) = i n f 、r ( x ，九，七) ， x e s ( x o # ) x e s ( x o 善) x c - s ( x o ；c ) x r = s ( r , o ；c ) 因此九也是问题( 研) 的局部最优解且 v a l ( d ： ) = 毋f 、f ( x ，九，k ) = i 。n ，f 、l ( x ，九，k ) = v a l ( d t ) ， 工e 6 ( x o 二cj工3 【j c d 善j 所以v a l ( p ) _ v a l ( p 。) v a l ( d ；) = v a l ( d t ) 又由于l a g r a n g e 乘子的存在性推知v a l ( p ) = v a l ( d k ) ，所以v a l ( p ) = v a l ( 尸a ) 如果是问题( p ) 的局部最优解，因为九是问题( p ) 的非线性l a g r a n g e 乘予，所以 ( x 0 九) 是三( ，k ) 的一个局部鞍点，又因为l ( x ，九，七) = r ( x ，九，七) ，所以 f ( x o ，九，七) r ( x o ，天，七) f ( x ，天，七) ， 因此( ，九) 是r ( ，k ) 的一个局部鞍点，那么x 。也是问题( p a ) 的局部最优解反之，如 果x 。是问题( p a ) 的局部最优解，因为九是问题( 尸) 的非线性l a g r a n g e 乘子，所以 1 ，( y ) v ( o ) + 七1 天- ( c o ) 1 - e 吲】， 即 v a l ( p r ) v a l ( p ) + k 。1 汹) 【l p 咧。】 求解半无限规划问题的指数型l a g r a n g e 函数 又因为v a l ( p ) = v a l ( p 。) ，所以v a l ( 尸v ) = v a l ( e ；) ，则 v a l ( 彤) v a l ( p 。) + 七一f ( c o ) 1 - e 咧】， 因此九是问题( p 。) 的非线性l a g r a n g e 乘子，所以( x 。，九) 是r ( ，k ) 的一个局部鞍点，同 样可以推知( ，九) 是三( ，k ) 的一个局部鞍点，因此x 。又是问题( p ) 的局部最优解因此， 问题( p ) 与问题( 尸a ) 有相同的最优解集 口 考虑下述条件： ( a 2 ) 存在一个有限集合1 3 = l 一，。) cq 使得v a l ( p ) = v a l ( 尸o ) ( a 3 ) i h - 题( p ) 存在非线性l a g r a n g e 乘子九 由定理2 2 3 知，条件池) 是问题( p ) 存在非线性l a g r a n g e 乘子的必要条件 对y e c ( n ) ，令只- y ( 0 3 ，) ，q o ，再令r r n 使得 s u p p ( x ) = o ，r 1 ) = ，扛1 ，m ， 则 k 。1 r ) 【l p 咧】= i 。1 f 佃) 1 一p 吲】， 由条件( a 3 ) 得 ，( y ) = v a l ( b ) v a l ( 哆) v a l ( p a ) + l - ( ) 1 - e 咧】= 1 ，( o ) + 七一1 r 佃) 【1 一p 嘲】 所以，r 是问题( p ) 的非线性l a g r a n g e 乘子因此为证明半无限规划问题( p ) 二i i e 线性 l a g r a n g e 乘子的存在性，只需验证条件( a 2 ) 和( a 3 ) f 1 1 n - i 2 3 一阶与二阶最优性条件 在这节我们讨论关于问题( p ) 的非线性l a g r a n g e 函数的一阶与二阶必要性条件 定理2 3 1 假设条件( 1 ) - ( 4 ) 成立，若是问题( p ) 的局部最优解，则存在九r n 使得 d x l ( x o ，九，七) = 0 ( 2 3 1 ) 证明因为 l ( x ，九，后) ：= 厂( x ) 一七。1 l ( o ) 1 - e 嘲圳】， e q 所以 d , l ( x 。，天，七) = o f ( x 。) 一硒) d x g ( x 。，弘蜊训 n 又因为和九满足k k t 条件，所以 师范大学硕士学位论文 d f ( x 。) = 天佃) q g ( ，c o ) ， e q 则有