（计算数学专业论文）半无限非线性问题的杂交化方法的研究.pdf

摘要 这篇论文致力予研究求勰半无限a # 线性规划的杂交化方法。求 勰半无限规划的方法黪基本恩想是将原闯题转化为个( - - 列) 等 价的或近似的有限约束规划，通过求解这个( 些) 有限约束规划而得 嗣原问题的( 近似) 解我们给滋瀚杂交化方法是一个两阶段方法 磁：第一阶段中，我们用离散网格代替约束变鏊集y 得到原闽题的 、个离散近似有限约柬问题，并通过求解列这样的离散近似闯糕 丽得到躲阎蕊解的个比较好近似我们采用s q p 方法求解这 些离散近似有限约束畿划，并且在子瓣越中只考虑对应予一小郝 分适当的网格点的约束，从而在保证s q p 方法收敛性的前提下大 大藏小了子闯题的溉摸当第阶段求褥的近似解“足够好”时， 我们以它作为初始点转铡第二除段送行计箨第二阶段羯是基予 局部约他的思想( 在定条终下，溅问题在鼓优矮懿局部等馀予 个隐式确定的有限约束规划) ，第一阶段的计算保证了第二阶段的 初始点胬锻优解不会太远，觚丽在第二除羧不会进行太多的约柬 交换这阶段我们利蠲有隈缝寨规划枣黪s q p 方法来求原闻慰 瓣一个迓似解， 在这篇论文中，我们详细讨论了杂交化方法的理论性质，并证 绢了杂交仡方法豹全灞收敛性繇怒部裁线性收敛速瘦筏们游数 鬣结梁说l ! ! l 杂交纯方法舆有较好豹诗算效率 关键谪；半无限j # 线* 障优化，离散方法，麟部约纯，杂交亿方法。 a 懿s t r a c t 1 1 h i st h e s i s w ed e v o t eo u ri n t e r e s t st o hh 3 h i d i n ( 、 ；h e lf o r1 t ( ) l d i n e a r s ( ，n l i + i n f i n i t e p r o g r a i r i m i n g 。t h eb a s i c i d e a sf o rs o l i n gs e m i i n f i n i t ep r o t ) t e m s i s “) ：( ) l n e r rt i l e o r i g i n a lp r o b l e mt oa ( s e r i e so f ) a p p r o x i m a t eo r ( ! c l t f i v a l m l l ， f i n i t e c o n s t r a i n e dp r o b l e m ( s ) ，a n db ys o l v i n gt h ef i n i t ep r o b l e i 拄：w eg e tt h e ( a t ) p r o x i m a t e ) s o h i t i o no ft h eo i i g i n mp r o b l e m 。 t i l eh 3 ，b r i dm e t h o di sat w o s t a g em e t h o d h lt i l ef i r s ts t a ，g e 。w es u l ) s t i l l i t e t h ec o l l s t r a i n tv a r i a b l es e tyw i t hg r i d st og e ta l la p p r o x i m a t ed i s c r e t ef i l l i t e c o n s t r a i n e dp r o b l e m ；a n d 酶s o l v i n gas e r i e so fs u c hp r o b l e m sw i t ht h em o d i f i e d s q 尹n m t h o d ，w eg e ta “s u f f i c i e n t l yg o o d ”a p p r o x i m a t es o l u t i o n ，t h e n w i t hth e a p t ) r o x i m a t cs o l u t i o n 氇sas t a r t i n gp o i n t ，v c es w i t c ht ot i l es e c m l ds t a g e ，w h i c hi s ) l s e do i lt h ei d e ao fl o e a lr e d u c t i o n h lt h i st h e s i s ，w ea n a t y s et h et h e o r yp r o p e r t i e so ft h eh y b r i dm e t h o d ，a n d 1 ) l o v e i t s g l o b a lc o n v e r g e n c ea n dl o c a ls u p l i n e a rc o n v e r g e n c y 。t h en u m e r i c a l r e s u i t sp r o v et h ee f f i c i e n c yo f 濂eh y b r i dm e t h o d 。 k e y w o r d s ：n o n l i n e a rs e m i i n f i n i t ep r o g r a m m i n g ，d i s c r e t i z a t i o nm e t h o d s ，l o c a i r e d u c t i o n ，h y b r i dm e t h o d 致谢 三年来，我的导师袁亚湘研究员耐心地指引我进入最优化理论 及其计算方法这一富有活力的研究方向，并且指导我完成了这篇 博士论文，在此，我对袁老师表示衷心的感谢。 感谢参加最优化理论与计算方法讨论班的所有老师和同学，大 家在一起富有建设性的讨论使我受益匪浅。 感谢科学与工程计算国家重点实验室对我的培养。感谢科学与 工程计算国家重点实验室所提供的良好上机条件和实验室的老师 们在上机中给予我的帮助。感谢李桂珍老师在日常生活中对我的 关怀和照顾。 最后，我还要深深地感谢我的父母，感谢父母多年来对我的关心 和鼓励 箔一蠢孳l 京 我们考察默下一般彩式戆钱貔潮熬 ，窖 g p ( z ；y ) 0 ；y y p ，ep h # 囊) 一o ，q 鼯， 葜中n ；紧集p g 霞脚；如n ，静p = l ，妨；n ，缀数，轳f 魏n ，霹) g q * ，巍g 强* n u 味；，孙c 3 ( r 8 j “，竭、p p 翔聚繁舍p 嚣任一p p 器怒煮隈黎，掰s 翳翻阮热秘怒蠢艇约浆傻佬瓣题，鳃聚存在 p p 傻稼 p p 。，则勰溅蠢笼穷多个缝窳，我钠拣逮榉黪瓣怒为拳秃戳撬 化闷越+ 半滩袋撬纯滴题称为线襁鹩或题戆，翔黎强拣溺数，和约絮滋激 # ，“辨，y 妒楚镑羹； 线拣翁或凸鹃，髓h 。，q 楚髂辩线悭秘，罾剽稔蠹誓秃 限非线瞧缆纯润题。 鲡爨镣= ； p l = l ，】“* e l y 。，剃( s i 磊g 磷”麓纯为 ：芝知，j ，j ： 。嚣。 9 。，y ) 0 ，y 。y + ( 1 1 j x 知，j 7 j = 嚣8 9 ，) ， + 筏们在遮篇论文审讨谂遨释形式黪攀秃陵嚣缆谶钱纯阍湛。实豁上，邋瀵逡 溺瓣媳疆，( s i p , “f ，9 ，h d 慧冒戳转偬愆这瓣彩戴。褒不攀 越混淆麓祷援下我 们懑( s z p ) 讽( s x p 鳓) 。我枢只驽惑半无簸嚣线链傀讫黼题鹩数值麟法，蕊 线潍或鼹拳无疆麓戆瓣鼗缓方法鬻鬣f 2 窝，l 羽。 在文献中求藤漤线拣( s i p ) 黪数镶方法烹螯蠢默下几类； 黎予紧粲y 鹣蓠数鹣方法 这类方法秘瘸y 戆菇窍有黻稽禄鹣离散予纂k ，将s i p ) 转缳为避议瓣鬻 数憋越： 暇蜀，般铂潆谳螂雕k ， 鞲篇 拜爝有黻约索饕线梭往讫赡数毯方法求解，京邋瀑鳓祭髂下，弼聚越j 7 豹足够精缁拘离散，潮s ，马) 蠡| j 解邈是( s i p ) 鹩瓣韵一个充分好酌避议， 闵扰辫羧灏越瓣勰可俸瓷原麓麓黪一个邋骰瓣。封这静方漆鹃讨论掰蔼l 蚓 辏予鼹潞约饿憋方浚 h e t t i c h 溯j o n g e n 凌f 矧中掇濑，程定祭传下，半无戳撬纯润题瀚珂褥臻 联 7 露棼乏双穗鸯黢令终寨灏稳霆，邀襻( s i p ) 在鼹郝裁爵以麓徐予个只蘅 育戳多个约柬的稚线设伉纯润越。如爨给定酌襁始点在解的附谶，剜田以碟 这令豁徐懿露袋鳓寒阍越来求激趣熬虢鼹稍粥金裁化策潞，貔们掰辍袋遮 耱方浚楚全属收敛鼹 臻躐 ，l，liii、 起 窖，r f 泠 弓 富薅：上论文 杂交化方法 我们还可以将离散化方法与局部约化方法结合起来首先我们求解一系 列越来越精细的离散问题( s i b ) ，其翳的是找到一个足够好的初始近似点， 然磊我们褥瑙矮基于蕊亵约诧戆翳辩狡鼓方法求求怒 我们在这篇论文中主要讨论求解半无限菲线性优化问题的杂交化方法 在第二章服，我们简要介绍了有限约束优化问磁和半无限优化问题的基础 理论，包括最优性条件和稳定性理论第三章讨论了求解半无限规划的两类 数值方法，鄹局部收敛的方法秘金髑收敛的方法在第四章，我们详细讨论 了求辩( s i p ) 豹杂交纯方法麓理论，褥第五章巍绘盘了杂交纯方法鹃算蘧实 现附录中列出了检测杂交化算法的效率时所使用的测试问题 第二鬻有限约束非线；睦优化和半无限套车线性优仡瑗论 本鬻簿癸分缫一慧有辍约窳j # 线筏镶纯秘拳无段j # 线性优化豹撩臻蠡疆 论，有兴趣的读者可参考隰陬 l l j ，( 3 q ，f 嘲，l 删有戳终柬非线悭优乞) 翻1 2 强 f 2 孔泌3 ， 7 l j 半无双蒋线性绕纯) 。 x 舻，我们对一般形式酌优化润越 定义其( 严格) 垒髑授小氆点和( 严格，孤立) 髑部缀小值点。 定义2 1 点扩x 黪为 1 。瀚慧f o p t ) 瓣垒爨缀夺蘧点，鲻祭，扩) ，( # ) ，魄芒x 2 阚惩o p t ) 瓣爝帮缀小渣点，如粱存在。+ 既开邻城u ( x 8 ) 娌“，使褥 f ( x 。) ，( $ ) ，v x 轳 。) n x ( 2j ) 3 闽瑟o p t ) 鹣严臻垒爨凝小壤点，鳐聚，( 矿) ，$ k 溉gx ，# 8 i 或闻惩( o p t ) 的严格蜀酃掇小值点，如聚存在矿的开邻城u ( x 8 ) 重r “，使 褥，( 。：4 ) ，( 。) ，v # 琶u ( 4 ) n x ，嚣甚+ 。 4 澜题 o p t ) 的孤立髑部极小德点，熟粱静谯矿的开邻城驴( 。4 ) 嚣“，使褥 ，( 矿) 0 ，v r 妫( 劬f 2 1 7 ) 贝i 挖。( ) 一磁( 彩，从蕊? ( 鳓= 雪口) = 掌+ ( 莉 定义2 1 1 缀设a 冀”一楚瓣称瓣阵，? r ”怒维数p 魄的线畿空闷，翔 槊f 崔 0 ，v 烈 噱我们称 键? 上正定，记为 扫 o 类似她有爿在r 上半正定、伴，负焱穗非奇异酌概念。 我们定义游题( f p ) 瓣l a g r a n g e 蠲鼗蔻 l ( y ，刚) = 弛) + ，c r ( g ) + d 。 ( 2 1 s ) r e 冀* 6 s 以下关予( f 川盼局郝极小点的二除必要性条件懿定理可见f 3 8 l 。 定璎2 1 2 口楚( f p j 的鼹帮极小点，( f l i c q ) 条律在口成立，剿 第二警 i 存在唯一乘子向量( i ，i ) l m ( y ) ，即陋，b ( 口) | = 1 2 l a g ， a n g e 函数( 21 8 ) 的h e s s e 阵在( 口，i 2 ，i ) 处于于( 口) 上半正定，即 ( s o n g ) 毒，v 目# ( 雾，露，西) 专0 ， v f 爹( 雾) ( 21 9 ) 将二阶必要性条件( s o n c ) 稍微加强一些，可得到( f p ) 的严格( 孤立) 局部 极小点婀二阶充分性条传( 【3 ) 定瑾2 1 3 假设口】7 ，l m ( f 1 ) o 如果l a g r a n g e 函数在点( 口，i ，o ) r ”r i 删r is 1 处的 h c s s e 阵于于( 口) o 上正定，即 ( s o s c )f v # l ( t j ，f t , o ) 0 ，增亍( ) o ，( 2 ，2 0 ) 则口是( f p ) 的严格局部极小值点 2 假设( f m f c q ) 在f 】满足，l ，n ( 彩0 ，若在( 玩i ，o ) 蠢以下条件成立： ( g s o s c )f ，v f f 五( 雪，霜，哥) f 0 ，v ( e ，话) ，n 括) ，v 毒亍( 雪) o ) ，( 22 1 ) 则口是( f p ) 的孤立局部极小点 下霹考虑“岛，r r ，去，s s 侪射线性”娥“，e ，r 露凸，d 。，s s 傍髓线 程”辩的最傥往条佟( 翻) 引理2 1 4 t 如果f l y 是( 胛) 的局郝极小点，c r ，蟊仿射线性，则l m ( y ) 0 0 ，疗挺格，凸，辞螽，d ，仿射线注，如采m ( 蓟# ，劐是( f 尹) 豹俨搐， 全局极小点 2 1 。2有限约束i 线牲臻 乏麓惩稳焉部稳定瞧 本节讨论( f p s ，q d 】) 的局部稳定性结果( ( 3 q 5 s ，) 定义2 1 5 1 我铜穆超题( f p f ，c ，透懿可行集y b 胡艇燹，翔巢( f l i c q ) 条嵇在任意 ”y c ，d 满足 2 我们称问题( f p i ，c ，d 】) 规则，如果y c ，d 】舰则，且( f p f ，c ，d d 的任意关键 点都是非退化鲍 ! 蔓鳖望素 线性饶纯穗半无疆j # 线性傥纯理论湾论文 一 ：二：一二二 ( j 1 p ) 的关键点口】7 称为非退化的，如果互补性条件 满学乙曼v ”l 池n ，。) 在丁，( 卿上非奇异即甏求以下条 牛满足： ，关系式( 26 ) ( 2 9 ) ， ( f p ) 的局部极小点口称为非遇化的，如粜以下条件满足： f1 ) ( f 三，g 。) 条件( 24 ) ， e 凇固篙s c c 嚣黑1 7 ) _ 2 _ 4 b 忿：。； | 3 ) () 条件( 2 ， ”7 l4 ) ( s o s c ) 条件( 22 0 ) 陋卜蚤趣，扩舻焘妒 拿三6 ， ? ) 。楚擘g 舻1 为中心的半径为6 o 的闭球，在伊( r m ，r ) 1 + i r i 郴l 上定义半范数： 。 删i 丽2 ，器焉州加。m 姒a x 删三删口) | 塞兰耋j 1 6 令7 是坚鬻! 舅f ，c ，d 1 ) 的k k t 点， ”b 田规则我们称口是强 稳宴尊k k t 点，抑。墨煮亳5 o ，辩 壬蠢戆5s ( j ，西蕃表。；j 爱毒蓊莩 v 。( l a , d ) ( r “，蠢) ”僻睁| s | ，若矿= y 离鼋规剜，条秫i i ( 1 一l c - ，d 一面i 百嘉 满足，则问题( f 尸 ，d ，胡) 在否了丽内存在傩一的，k k t 点 “ 塞塞三芝似鲫令y f c ，碑规则如果( 即，e ，翻) 黝k k t 点f 非退化，贝g 也是 强稳定静 一 罩孥三除充分谴条彳譬在黩i ，i ；藏立，辩l a g r a n g e 爵数戆觇s * 阵在芦( 扔 o ) ( s s o s c ) 7 v “”己( 口，口，i ) 0 ，v 于+ ( 口) f 0 ) ，f 22 4 ) 那么# 是( f p ) 的强稳定k k t 点， 博士论文第二章 2 如果 j 口是( f p ) 的强稳定的k k t 点， 圳( f 1 l c q ) 条件在口满足， ，纠二阶必要性条件( 2 1 9 ) 在d 成立， 那么( s s o s c ) 条件( 22 4 ) 在( 口，日，o ) 满足 我们将有限约束非线性优化问题中的一些概念推广到以下的有限约束非 线性参数优化问题： m 。i 。n ：； 。，。，：。，。r 。i 。，。，。，。r ，。，：。，。s ， f 22 5 1 其中9 ec 3 ( r “y c ，t i ，r ) ，参数( 向量) z 舻，nen 用( f p ( z ) ) 记( f p g ，d ( z ) ) 】7 记y c ，卅 l ( x ，y ，u ，u ) = 9 ( 蝴) + t t r c r ( ”) + d 。( ) ( 22 6 ) r 月s e s 2 点( z ，口) r “r ”称为参数优化问题( f p ( 。) ) 的f r i t z j o h n 点，如果口是 ( f p ( i ) ) 的f r i t z - j o h n 点 3 ( f p ( z ) ) 的f r i t z - j o h n 点( i ，口) 称为k k t 点，如果y 是( f p ( i ) ) 的i ( k t 点 即存在( 日，o ) 满足以下( k k t ) 条件： v ”g 忙，口) + 日t r v 岛( 口) + 。( 口) = 0 r e rs e s 类似于( 21 5 ) ，定义l a g r a n g e 乘子集 口，c ，( 口) = 0 c ，( 口) 0 d 。( 口) = 0 日，0 r r ， r r 8 s ， r r f 2 2 7 1 2 8 2 9 3 0 3 1 l m ( x ，口) = “i ，i ) r 1 8 fxr 1 8 jj ( 2 ，口，6 ，。) 满足( 22 7 ) ( 23 1 ) ( 23 2 ) 4 ( j ，口) r “r ”。称为参数优化问题( f p ( z ) ) 的非退化局部极小点，如果口 是( f p ( z ) ) 的非退化局部极小点即在( 2 ，口) 处， ( f l i c q ) 条件在口对于( f p ( j ) ) 满足， 圳( t ) 条件( 2 2 7 ) ( 23 1 ) 成立， 为数函妒 m 9 h 的 s r r r r n ruu 可 z 在 9 扣 m 即 义 ， 定 1 ( 有限约束非线性优化和半无限非线性优化理论博士论文 ，l ( z ，口，i ，i ) f 0 ，v 于( 口) f o ) 6 ( j ，口) r ”r 称为( f p ( z ) ) 的强规则或强稳定局部极小点，如果9 是 ( f p ( i ) ) 的强规则或强稳定局部极小点它满足： ，( f p ( 2 ) ) 在9 处的( f l i c q ) 条件， 到( k k t ) 条件( 2 2 7 ) 一( 2 3 1 ) ， 圳( f p ( ) ) 在( 9 ，i ，i ) 处的( s s o s c ) 条件( 2 2 4 ) ，即： f 7 l ( x ，口，日，o ) 0 ，v f t + ( 口) ( o ) 或：纠( f p ( i ) ) 在9 处的( f k g f c q ) 条件， 纠( k k t ) 条件( 2 2 7 ) ( 2 3 1 ) ，l m ( i ，9 ) o ， 圳对任意l a g r a n g e 乘子( i ，i ) l m ( i ，口) ，( s s o s c ) 条件在( 9 ，i ，i ) 满足 注2 2 0 由定义21 9 易知：( 2 ，口) 是非退化局部极小点= ( i ，口) 是强规则局部极 小点辛( i ，口) 是强稳定局部极小点 我们给出以下记号： 。= ( ，“， ) r “xr i r o ( ”) ixr i “，z ( z ) = ( ( z ) ，u ( z ) ，u ( 。) ) ， e r o ( y ) ( ) = ( c ，( ) ) ，r 。( 扪r 1 8 。妇) | ，d s ( y ) = ( d 。( 9 ) ) 。e s r 1 5 l ， v c r o ( ”) ( ) = ( v c ，( ) ) 乏r 。( ，) r 刚”l “，v d s ( v ) = ( v d s ( ) ) 乏s r m “ ( f p ( z ) ) 的l a g r a n g e 函数l 在( i ，口，日，o ) = ( i ，j ) 的梯度和h e s s e 阵分别为： v 。9 ( 孟，雪) v ，g ( 孟，雷) + ，r 。( 口) 西v c r ( 雪) + 。sv s v d s ( 雪) c r 。( 口) ( 雪) d s ( 9 ) _ ： v 。9 ( i ，9 ) v ”l ( 孟，雪，面，百) v 。r 。( 口) ( 9 ) v d s ( 口) 0 e t r o ( 9 ) ( 口) 0 o 0 v d ；( 9 ) 0 o v 。：l ( 亍，j ) 7 ) v ：l ( f ，j ) b立 屯成成功 p忙f p 0对于回 对m 口悔在在 加 2 2 件件条条陛陛补分互充格阶 严二 圳纠 是果电 定稳强或则规强 的 点黔为定称稳淼酽贝规动强的 、 一z z o z l l z z v v ， 一z 一0 z z l l z ： 口 z v v ， 一一 溥论文第二章 弓l 琏2 。t 令qt 托”“ i ，_ er ”m h ，rcm ， f 2 ( ：f ) ，剐 ，。哦( 且) = ，。；q k 。，： ) 0 m 非奇髯 ( 2 ，3 3 ) 证峨：驭商量y 形椒“搿，使得 国+ a 飞= 0 ， a y 20 第一式蹰端圊时象秉执褥f 7 国十a v ) “= 吼利爝第= 式有p 国= 0 ，f v ”锄m ( a ) 可知y o ；因此a 7 “一0 ，又由r a n k ( a ) = r 知一0 结沦成立，髓 是蘧2 。2 2 | ，鳓 骰谖t r “ ，如巢口魁( f p ) 的非邋化局部檄，j 、点，则存在的邻域u ( ) 董舻，# 的 邻域彬( 劝量妒，诉的邻域疗( ，) s r ，re 岛渤，蟊鲍邻域矿。慨) 捉，8 s ， 和蕊数，c 1 ( 耵 ) ，妙7 ( n ，) ) ，c 1 ( 玎擘) ，矿s ( ) ) ，yec 1 ( ( 叠) ，礴，( g ) n ) ，漩 足# ( g ) = ，n ，( ) = 弼，r 戴o ( g ) ，v s ( 净，s s 并置对任意# 驴( 茔) ，有； 嚣。( f o ) ) = 瑜( f ) 印f ( z ) 是( f p ( 。) ) 昀非退化局部极小点，因此也是孤立的。 卵函数 二阶连续可微，虽 v 。( z ) = v 。9 p ，# ) ) ， v 。雾( 尊) = v 。警囊，祭( 嚣) ) 牛夥￥。譬涵分( 。) ) v 秽( 堂) 一翠。g ( z ，# ( 。) ) 一v y ( z ) v # 五括，# 缸) ) v # ( # ) v ；。窖( ，彭( 2 ) ) 一v 。五( 茹，o ( o ) ) 。v ：l ( z ，# ( o ) ) 哪v # l ( x ，o ( 2 ) ) f 2 + 3 ) ( 2 3 6 ) g 。魏梁口楚f 尹( g ) 懿强甄粼菊郄辍小煮，剿存谯邻城驴2 ) r “，辩( f ) 露m ， 扩( 西) r ，r 弱( 口) ，伊( 魄) g 矗；8 s ，和，( 习上豹l i p s c h i t z 逸续溺数 “r ：驴鞲) 扩嫡，) ，r 蕊口) ，：耵( 蕾) v 8 ) ，s s ，# ：，( # ) h 秽( ) n 一满足 如( ) = ，r r o ，= 蟊，s s ，p 一i ，并羟对任意$ 秽( 耋) ，有： 矗毒季) 曼j 孙妇( # ) ) 霞。殛) 印y ( z ) 怒( f 尹) 瓣嚣裁鬟| l 两郝缀小点，困鼗氇楚孤立粒。 铆由( 2 3 4 ) 怒义的c 1 渺( 瓤固，且v ；口( 。) 在u ( ) 上建l i p s c h i t z 连续黼 数，鄹( 2 3 5 ) 成立，髓分片t | 蓠于伊澎碧) ，冀n ) 3 如粱# 楚( f p ) ) 蛉强稳定两部缀小点，则存在邻城r ”，彬托“， 扩( 弼) r ，r 蕊( 鳓，矿5 ( 吼) 矗，s s ，蕊熬# c 。( 秒( k 露( 彩n q 与袋蕊浚 有黻约束菲线褴德纯和半无敝菲线潍优化理论博士论文 射，：矽 ) m ( ，( # ) ，影搠n j ) ，满足 ，( i ) = a ( 女，口) ，( * ) = # 并且对任意 。u ) ，有： z ，妇) m _ - 岛( 珐 印n ( g ) 燕( f p ( 。) ) 的濒稳定的孤立髑部梭小点，并且= l m d z ；。g 缸) 魁 紧多黼体 。夥国江3 4 ) 定义游口1 ( ( i l 矗) ，。驻育( 23 习式成立 诞鳃：我们只筒要诞嘲定理的第一部分 因为( f l i c q ) 条停在满足，阚鲍对于翘阵a 渤= ( v 。f 驰( 巍v d s ( 口) ) 剁“o ( 9 ) 1 + i 剖) x t 8 ，有m n 汹( ) = i r o ( _ | 7 ) + 研因为g 怒舔退纯璃帮授小点，所 以v 。，己隔# ，玩自) 在? ( f ) o ) 上正定，从黼在? ( 口) 一k e r n ( a ( 口) ) 上非奇异，由 弓| 理2 j 霹戋霾v ：五( 2 ，习 驽异濑v ：( i ，动= 0 ，懿耀憋舔数定瑗霹知，存 在i ，f ，n ，戆邻蠛驴( ) 捉”，辩( ) ! 兰r “，g ( a ) 剧鳓测，驴( 刘5 f 琴嚣溺数 。( # ) c 1 ( 玎( 蕾) ，霄( 鳓f t ( 嘞矿珐嫒褥对予z 扩( 妨，蠢：v ：g ，# ) = 0 ，鼠 v ；。五( ，z ( z ) ) v z ( ) = 一v 。9 ( $ ，g ( # ) ) ( 2 3 7 ) 这榉，邋过选驭( 却黪个逶送瓣予铝壤，我稍爵娃霞簿慰z 驴( 2 ，有 ，# ，0 ) 0 ，r 蕊，蕊( # 妇”= 凰，# 缸，2 铷；) 毫# 0 ，羼f 蹩 ( f p ( z ) ) 麴 # 潺彼是郝缀小点。 ( 23 5 ) 和( 2 , 3 6 ) 可利用( 2 3 7 ) 进行简单的推导而褥 口 2 2拳无限 譬线性优化润题的熬本瑷论 2 。2 + 1一除必要最俄牲条髂 我们考虑形式如- v 的半无限非缆性优化问题： ( s s p l l s ) 愕n l r i 飘 淄 其中， 】7 兰 擎震m lc r 国) 0 ，尹r ，或 鼙) 等0 ，$ s ( 2 3 8 ) 辖0 9 ) 怒冠m 中的非空紧集，非线性函数，g 3 ( 矗_ n ，r ) ，g c 3 ( 舻】7 ，r ) ，非线性黼 数岛，d 。8 3 ( k 最) ，r 簏一 l ，一， ；n ，s s = l ，t t ，i ，炳， 0 ，z r “，定义集合k ( z ) ，( z ) y 如下： 】：( z ) = f y y ig ( x ，y ) ( z ) 一e ) ，( 24 5 ) y ，( z ) = y y 9 ( z ，y ) + ( 。) 一e )( 24 6 ) 若e = 0 ，则得到( z ) 和盼( z ) ： ( 。) = ( y y i9 ( 5 ，y ) = ( z ) ) ，( 24 7 ) 盼( x ) = y y ig ( x ，y ) = 矿( z ) )( 2 4 8 ) 注2 2 3 由( z ) 的定义可知，对任意的z r “， y 。碥( z ) 号y 9 是( p ( z ) ) 的全局极大点( 2 4 9 ) 因为9 ( z ，y ) 在紧集y 上有最值，所以k ( z ) 0 ，记( z ) 的指标集为山( 。) j 碥( z ) = y j y ij 山( 。) )( 25 0 ) 2 如果。x ( y ) ，则( z ) 0 ，+ ( z ) = o i 如果zgx ( y ) o z ( y ) ( o x ( y ) 为x ( 】7 ) 的边界) ，贝4 ( z ) = + ( z ) 另夕 ： ( 。) 0 甘( z ) = y o + ( z ) 甘k ( z ) = l ( z ) 甘盼( z ) d ，( 2 5 1 ) ( 。) 0 ，有y o ( x ) k ( z ) y ，且( z ) 和k ( z ) 紧 类似于( f l i c o ) 和( f m f c o ) ，我们给出( s i p ) 的常见的约束规范条件 ! !塑坠竺窭非线性优化和半无限非线性优化理论博士论文 一 ：二：二 定义2 2 4 似? j 我们说问题( s i p ) 在点z x ( 】，) 7 满足( l i c q ) 约束规范条件，如果v 。g ( z ，) ，盼( i ) 线性无关 2 v 满曼算篇e 印) 约束规范条件，如果存在向量f r ”，使得f r v 。9 ( i ，口) 吼 y 】付( z ) 一”“， 注2 2 5 。( l i c q ) 在j 盖( 1 7 ) 对( s ，尸) 满足号( m f c q ) 在i 满足 2 ( l i c q ) 在i x ( y ) 对( s i p ) 满足j 盼( z ) 的指标有限 3 翟果兰! 一( y ) ，( i ! 二o ，( m f c q ) 在j 满足，则由( i ) ：，寸f i ) 和( 24 2 ) 可 知，存在d e r ”，使得d d c ( x ) 0 ，即d 指向可行域x ( 1 ，) 内u 部x - 。 字娄2 j 6 假设2 、jx ( y ) ，o 刊f ( 。? j 9 ( z ，w ) ，v ”( 叼( 露) n y ) 挣 我们称假设2 2 8 中的函数嵋，j 山( 2 ) 为9 m 一函数，并定义 ( j ) = n 曙( ) o j e j 。( i ) 引理2 2 9 令假设22 8 成立，则碥( i ) 是有限集，即存在r 9 ( i ) n ，使得山( j ) = 1 ， ，。( i ) ) ，】自( ) _ 刃，j 山( 2 ) ) 证明：( 反证) 若碥( i ) 是无限集，则存在点列f 霹) j 。- ，满足爵( j ) ，n ， 且弼霸j i 由( i ) 的紧性可知，存在收敛子列 9 - 。j - ) k ，n ，j k l = o 。， 其极限点口( i ) ，且女聍，v k k 这样，口的任意小的邻域内都存在聍， 因此口不可能是孤立的全局极大点，导出矛盾 口 引理2 3 0 ( 约化引理) 令假设2 船成立，则存在i 的邻域u ( j ) 吃( i ) ，使得对 任意的z u ( i ) ，有： y o ( z ) ；( 。) lj 山( ) ) ，且i 山( i ) o 。即对于这些z ，( p ( z ) ) 的全局极大 点一定在；，j 山( ) 中 2 z x ( 】7 ) 乍争9 ( z ，；( z ) ) o ，j 如( i ) 即问题( s i p ) 的可行集x ( y ) 在j 的局 部可由隐式定义的约束g j ( z ) = 9 ( z ，；( z ) ) ，j 矗( i ) 所确定 证明：我们先构f l i 弓l 理中i 的邻域【，( i ) 吃( i ) 任取霹】0 ( j ) ，j 山( i ) ，则 对任意u j j 。( t ) 哪( 蟛) = p ，有9 ( i ，) 一( j ) 0 由和9 ( ，) ，】7 的连续 | 生以及r 紧，可知存在u ( z ) 吃( i ) ，使得： 令$ ( z ) = i i i a x 。p9 ( z ，) ，贝4 $ ( z ) 一( z ) 0 ，v z u ( i ) 簿士沦文第二蠢 由, - j l 理2 2 9 可知i l ( 引l p ) o 导出矛艨，所以女x ( y ) 口 注2 3 l 如果假设2 2 8 猩igr n 满足，则问题( s i p ) 程局部侧引理23 0 中的扩( i ) 嘲等徐予露融终絮侥纯溜题： f 酬如p 摩”) ) = 冀2 矗铲泓嘲嗽吣吲引 f 26 4 1 这个瓣题以矮拣梵2 处黪麓郝溉终游题。翔爨。4 秽溷，慰 矿是( s 糟) 熬拶溅格，鞭烹，髑部极小点 芍( 26 5 ) 。* 跫( s j p r 。d ) 昀疗亚捂，孤立，局郝极小点+ o 。懑骰浚g 。8 勰孳 理2 ，艘巍g 薹) 时，母滤足： 2 羚妣”) ，器熟如蝎( 。) ) 2 j 器甄。哪m 嘲a x 鑫) 如幻t ( 2 6 6 ) 以”f 萼 理给出了一个使得骰设2 2 8 成立的充分条件 引瓒2 3 2 令舻，碥( g ) = 露1j 而 ，如果谯意彰砺( 乱j 而( 口) 都是 ( p ) 蛉 退化蛇全局檄大点，那么瑕设2 嚣窿点2 成立。 诞鹞：参考定理2 + 2 2 的话明。 口 注2 3 3 在孳i 理2 础的骰设下，啦定理2 貔玉9 m 一溺数g ；莎( ( 2 ) ，彬嘲) nl 飞 且矿伊( ，r ) ，巧而( 动困此对予z 矿( i ) ，利用( 2 3 5 ) 可得： v y ( x ) 十脚v 。g ( x ，；) = v 绺) 十n ，v ；9 3 ( 。) f 2 嘲 有限约隶嚣线性优化和半无限菲线性优化理论博士论文 即如果( t ) 条件在( 引z ) u ( i ) r 。对i 处的局部既约问题( s i p , 。f ( j 成立，鼷东溆n ) 对瓣题s i p ) 奄成立 我们定义以下集合 蹦i ) = 口。f 乳是( p ( i ) ) 的关键点) = f 彰fj 五( i ) ，( 2 6 8 ) ，k ? 量) = 雾k 符r ly i ( k t 是( p ( 量) ) 戆k k t 点 然 露定r | 歹j k 群? 扛) t 26 9 ) l ( ) = 蟊 蕊楚( p ( 2 ) ) 的局部极小点) = 贸| j ( i ) ，( 2 7 0 ) ；，c ( i ) = f # | 蟊，e ， ( i ) ，羹g ( # ，f ，；) 簪( 一 最，；5 卤f ( 2 ) ( 27 1 ) h 面讨论的求解( s z p ) 的基于局部约化的方法要求所有的