（运筹学与控制论专业论文）锥优化的最优性条件的刻画.pdf

k_；。，y扣 学位论文独创性声明 4 i il li ii l li i i ii i iiill y 18 9 0 0 7 2 本人承诺：所呈交的学位论文是本人在导师指导下所取得的研究成果。论文中除特另l j j j d 以标注和 致谢的地方外，不包含他人和其他机构已经撰写或发表过的研究成果，其他同志的研究成果对本人的 启示和所提供的帮助，均已在论文中做了明确的声明并表示谢意。 学位论文作者签名：7 么至笙 学位论文版权的使用授权书 本学位论文作者完全了解辽宁师范大学有关保留、使用学位论文的规定，及学校有 权保留并向国家有关部门或机构送交复印件或磁盘，允许论文被查阅和借阅。本文授权 辽宁师范大学，可以将学位论文的全部或部分内容编入有关数据库并进行检索，可以采 用影印、缩印或扫描等复制手段保存、汇编学位论文，并且本人电子文档的内容和纸质 论文的内容相一致。 保密的学位论文在解密后使用本授权书。 学位论文作者签名 指导教师签名：兰盗 签名日期： 2 纠, rp 年岁月夕日 辽宁师范大学硕士学位论文 摘要 在非线性规划研究中，最优解所满足的必要条件和充分条件十分重要，它们为各 种算法的推导和分析提供了必不可少的理论基础锥约束优化又是近年来非常热门的优 化问题研究领域本文着重梳理研究对锥约束优化问题的最优性条件的刻画 本文的第二章给出了锥与二阶锥的定义，并研究了二阶锥的切锥、二阶切集以及其 代数性质对经典的优化问题的最优性条件的刻画做了总结介绍研究了在刻画最优性 条件中非常重要的几种约束规范以及它们之间的关系 本文的第三章先对一般锥约束优化问题的一阶和二阶最优性条件进行了介绍二 阶锥规划问题的提出很早，但对其深入研究开始得比较晚随着二阶锥在计算机等领域 的广泛应用，越来越多的学者开始对此问题深入探讨，本文在介绍了一般锥约束优化问 题的基础上对二阶锥规划问题的一阶、二阶最优性条件进行了研究 关键词：锥；二阶锥；对偶问题；最优性条件 - 锥优化的最优性条件的刻画 d e s c r i p t i o nf o rt h eo p t i m a l i t yc o n d i t i o n so f c o n i co p t i m i z a t i o n a b s t r a c t i nn o n l i n e a rp r o g r a m e ，t h ec o n d i t i o n st h a t t h eo p t i m a ls o l u t i o ns a t i s f i e da r ev e r y i m p o r t a n t t h e yp r o v i d en e e d f u lt h e o r e t i c a lf o u n d a t i o nf o rd e r i v a t i o na n dc a l c u l a t i o no fa l l k i n d so fa l g o r i t h m s i nr e n c e n ty e a r ，c o m eo p t i m i z a t i o ni sv e r yp o p u l a rf i e l do fo p t i m i z a t i o n t l l i sa r t i c l ef o c u s e so ns u m m i n gu pa n di n v e s t i g a t i o no fc o n i co p t i m i z a t i o n c h a p t e ri io ft h i sa r t i c l es e t st h e d e f i n i t i o n so fc o n ea n ds e c o n do r d e rc o n e ，t h e n i n v e s t i g a t e st h et a n g e n tc o n e 、s e c o n do r d e rt a n g e n ts e ta n da l g e b r a i cp r o p e r t i e so fas e c o n d o r d e rc o n e 砸sa r t i c l es u m su pd e s c r i p t i o nf o rt h ec l a s s i c a lo p t i m i z a t i o n ，a n di n v e s t i g a t e s s e v e r a li m p o r t a n tc o n s t r a i n tq u a l i f i c a t i o i l sa n dt h er e l a t i o n s h i pa m o n gt h e m c h a p t e rh io ft h i sa r t i c l ef i r s t l yi n t r o d u c e st h ef i r s ta n ds e c o n do r d e ro p t i m a lc o n d i t i o n o fg e n e r a lc o n i co p t i m i z a t i o n s o c pw a sp r o p o s e de a r l y ，h o w e v e r ，t h ei n t e n s i v es t u d y o c c u rl a t e w i t ht h ee x t e n s i v eu s eo fs o c pi na p p l i c a t i o na r e as u c ha sc o m p u t e r , m o r ea n d m o r er e s e a r c h e r sb e g i nt oi n v e s t i g a t es o c p t h i sa r t i c l ei n v e s t i g a t e st h ef i r s to r d e ra n d s e c o n do r d e ro p t i m a lc o n d i t i o n so fs o c pa f t e ri n t r o d u c i n gt h a to fg e n e r a lc o n i co p t i m i z a t i o n k e yw o r d s ：c o n e ；s e c o n do r d e rc o n e ；d u a lp r o b l e m ；o p t i m a l i t yc o n d i t i o n s i i 辽宁师范大学硕士学位论文 目录 摘要i a b s t r a c t i i 1弓i 言l 1 1 历史概述及研究背景1 1 2 本文的研究工作3 2 预备知识3 2 1 锥的相关知识3 2 1 1 锥与二阶锥3 2 1 2 二阶锥的切锥、二阶切集及j o r d a n 代数3 2 2 一般优化问题的最优性条件8 2 2 1 无约束优化问题的最优性条件8 2 2 2 一般约束优化问题的最优性条件1 0 2 3 约束规范1 8 2 3 1 一般约束优化问题中的约束规范1 8 2 3 2 一般锥约束优化问题中的约束规范2 0 3 锥优化问题的最优性条件2 5 3 1 一般锥约束优化的最优性条件2 5 3 1 1问题的提出2 5 3 1 2 一般锥约束优化问题的一阶最优性条件2 7 3 1 3 一般锥约束优化问题的二阶最优性条件2 8 3 2 二阶锥规划问题的最优性条件的刻画3 0 3 2 1问题的提出3 0 3 2 2 二阶锥规划问题的一阶最优性条件3 l 3 2 3 二阶锥规划问题的二阶最优性条件3 4 3 2 4 二阶锥规划问题的强正则条件3 9 4 总结与展望4 4 参考文献4 6 致谢4 8 辽宁师范大学硕士学位论文 1引言 简单的s o c pi h - j 题 1 二阶锥规划问题在运输，物流，工程，以及组合优化等领域都有 m i n + 乞+ 岛 ( 2 乙，( ： 乙，( ：， 乙 1 0 c a t i o np r o b l e m ) 幂g ls t e i n e r 最短树问题( s t e i n e rm i n i m a lt r e ep r o b l e m ) 【l 】；天线阵权重模 型( a n t e n n aa r r a yw e i g h td e s i g n ) 【2 ，3 】；f i r 滤波器设计( f i rf i l t e rd e s i g n ) p l 题【4 】；带分片 线性s p r i n g s 的平懈( e q u i l i b r i u mo fs y s t e mw i t hp i e c e w i s e - - l i n e a rs p r i n g s ) 4 】；桁架设 计( t r u s sd e s i g n ) 【5 ，6 ，7 】；带风险损失约束的投资组合优化问题( p o r t f o l i oo p t i m i z a t i o n w i t hl o s s r i s kc o n s t r a i n t s ) 4 ；鲁棒投资组合优化问题( r o b u s tp o r t f o l i oo p t i m i z a t i o n s o c p 问题研究的流行还因为它是凸的二次约束二次规划( q c q p ) 的推广形式，例 如：考虑如下q c q p 问题： 烹stx x t 戮q 。，i ：。，m ， c l l ， q x + 2 6 j l x + q 0 ，= 1 ，m ， 。 啪出圳凡m h 旧睁账m 一成： 锥优化的最优性条件的刻画 i n l n x 0 乙+ 2乙+ 2 ，i = 1 ，m 非线性最优化发展至今，其研究对象除了非线性规划，还有其他形式的约束优化问 题，s o c p 问题和目前人们非常关注的半定规划( s d p ) 就是两类重要的锥约束优化问题， 1 9 9 8 年r o c k a f e l l a rrt 与w e t srj b 合作的变分分析和2 0 0 0 年b o n n a n sjf 与s h a p i r o a 合作的最优化问题的扰动分析【9 】一书中对非线性二阶锥问题进行了细致的分析和 研究 目前对二阶锥规划的研究分为线性二阶锥规划和非线性二阶锥规划两类线性规 划、凸二次规划以及具有二次约束的凸二次规划等均可转化成线性s o c p 问题【4 】上个 世纪9 0 年代，凸二次约束规划引起了学者们的广泛兴趣，而它是s o c p 的一种特殊 况g o l d f a r b ，l i u 和w a n g 1 0 ，j a r r e 11 】以及m e h r o t r a c - 和s u n 1 2 各自独立地将k a m a r k a r 的 内点法【1 3 】推广到凸二次约束规划问题上随后，n e t e r o v 和n e m i r o v s k i 1 4 证明了将自协 调障碍中的一般结果应用到线性s o c p 问题上时，可得到线性s o c p 的内点算法，并且得 到对有，个二阶锥不等式约束问题算法的迭代复杂性为厂 基于欧氏若当代数，可以把线性规划，半定规划以及二阶锥规划统一到一种理论上 去f a r a u t 和k o r f i n g 在文献 1 5 中给出了这一理论的基础 f a y b u s o v i c h 1 6 1 8 从若当代数的角度，讨论了非退化条件并给出了n t ，x z 和z x 方 法s c h m i e t a 1 9 】以及s c h m i e t 卿a l i z a d e h 2 0 ，2 1 运用若当代数的工具将s d p 上的 m o n t e i r o z h a n g 类内点法分析推广到所有的对称锥上t s u c h i y a 2 2 ，2 3 借助若当代数对 线性s o c p 上的内点法进行了分析 近年来，由于对线性二阶锥规划问题的研究已较为完善，因此，学者们又把目光转 到非线性二阶锥问题的研究上来b o n n a n s 和r a m i r e z 2 4 研究了非线性二阶锥规划问题 的一阶及二阶最优性条件，并从二阶最优性条件的角度描述了强正则性，从而为发展非 线性二阶锥规划问题的算法提供了理论基础随后，诸多学者也先后提出许多求解非线 性s o c p 问题的方法，近年来发展的方法主要包括以下几类：原始对偶内点算法 ( p r i m a l d u a li n t e r i o rm e t h o d s ) ，半光滑牛顿方法( s e m i s m o o t hn e w t o nm e t h o d s ) ，光滑化牛 ，上一，i一 + 一 二 q q 一 ： 兰2 兰2 1 翰 酽一笙 ；篓三盼 + 一 一一 一 而一 o +一2+一2 1 印 x x q篓主跏 辽宁师范人学硕士学位论文 顿方法( s m o o t h i n gn e w t o nm e t h o d s ) 。序列二次规划( s q p ) 方法( s e q u e n t i a lq u a d r a t i c p r o g r a m m i n gm e t h o d s ) ，增广l a g r a n g e 方法( a u g m e n t e dl a g r a n g em e t h o d s ) 1 2 本文的研究工作 本文先介绍了锥、二阶锥、切锥和二阶切集的概念，并介绍了与二阶锥密切相关的 一种称为j o r d a n 代数的欧氏代数 本文对在最优性条件研究中作用突出的几种不同约束规范的一般形式、等价条件和 在一般锥约束优化和二阶锥规划问题中的具体形式进行了研究 作为铺垫，本文对一般锥约束优化问题的一阶和二阶最优性条件进行了总结、介绍 在此基础上，本文对二阶锥规划的约束非退化条件和一阶与二阶最优性条件及强正则条 件进行了研究 2 预备知识 2 1 锥的相关知识 2 1 1 锥与二阶锥 设x 是有限维h i l b e r t 空间，x 中的非空子集c 被称为锥( c o n e ) ，若对任何x c ，对 任意的f 0 ，有t x c 对锥c c x ，它的极锥( p o l a r c o n e ，或称负对偶锥) c 一定义为： c 一：= p x ：( x ，x ) o ，对所辄c ( 2 1 1 ) 还可以定义双极( b i p o l a r ) 锥 ( c 一) 一净p x ：( x ，x ) o ，对所辄c 一 ( 2 1 2 ) 由上述定义知，c 一可表示为闭凸半空间的交，因此，它在x 的相容拓扑下是闭凸的 类似的，( c 一) 在x 的相容拓扑下是闭凸的 定义2 1 吼”1 中的二阶锥定义如下： z 0 + 1 2 s 2 ( ；f ) 吼孵册：i i 可i i - 0 ，v te 0 ，n + t h 咽五o ，：= l i m m s u p 孚 5 ) 命题2 3 设g ：x 专员是一下半连续凸函数，考虑相联系的水平集： s = x x ：g ( x ) 0 设g ( x o ) = 0 ，且存在i 满足g ( 习 0 ( s l a t e r 条件) ，则 t s ( x o ) = h x ：g 。( x o ，办) o ( 2 1 6 ) 证明：由于g 是凸函数，集合s 是凸的，又因为g 是下半连续的，集合s 是闭集注 意下述两个包含关系成立： h x ：g 。( x o ，办) 0 ct s ( x o ) ， ( 2 1 7 ) r s ( x o ) c h x ：g 上( x o ，办) o j ( 2 1 8 ) 事实上，若g 。( x o ，办) 0 ，有g ( x o + f 尾吃) f 屏。毛得到 g + ( x o ，吃) ( 1 一a d s + g ( 习 因8 n c t 专0 ，这意味着g 。( 而，瓦) 0 ，因此吃属于( 2 1 7 ) 左端，因为吃- - + h ，得到结论- 命题2 4 令s 乙+ l ，则 一4 一 辽宁师范大学硕士学位论文 r e + 。( j ) 2 孵”， s i n t z 搠+ l z m + l ， s = 0 ， ( 2 1 9 ) d 孵斛1 ；孑t i - - a o o ) ，s b d z m + 。 o ) 证明：当s i n t z 埘+ l 及j = 0 时，由切锥的定义司直接得到所要的结论 下面假设s b a z + 。 o ，! 1 0s o = l li - i i * o 注意到在这种情况下( i lsi | o ) ，吵( j ) 是连续可微 函数由于函数( s ) 是l i p s c h i t z 连续的，y 7 = ，根据命题2 3 ，可得到 砭+ 。( s ) = d 孵”1 ：少7 ( s ；d ) o ( 2 1 1 0 ) 因为此时( s ) ( s ；d ) = v y ( s ) 1d = 矿了| if - d o ，所以当j b d z m + 。 o ) 时，结论成立命 题得证- 命题2 5 设集合s 定义为形式s ：= z x ：g ( x ) 0 ，其中g ( ) 是正常的凸的下半连 续函数令g ( 而) = o 且g 。( x o ，办) = o ，设存在i 满足g ( 习 0 ( s l a t e r 条件) 则s 在处沿 h 方向的内、外二阶切集为( 见定义3 5 ) ： r 孑( x o ，办) = 缈x ：( x o ；h ，国) o ， ( 2 1 1 1 ) i ，2 ( 而，办) = 缈x ：g ，( x o ；h ，缈) o ( 2 1 1 2 ) 证明：先证明( 2 1 1 1 ) 成立考虑国( 嘞，矗) ，选取序列乙山o ，吼j0 3 满足 而+ 乙乃+ 圭e s ，因而有g ( 而+ 乙厅+ 丢q 。则 ( x o ；h 川止竿趔删纠u，国) j 广u + d ( 1 ) d ( 1 ) 吉 2 ” 从而有( x o ；h ，c o ) o 相反的，先设g ( x o ；h ，c o ) g ( 而+ 砌鼍12 卜一尹1 2 ，m 川+ 圭a t 2 9 ( x - ) ， 0 ， ( 2 1 1 3 ) 其中 y c ，缈，= g ( 而+ r c 一j 1 口r 2 ，。1 办+ 三，2 c 一三口，2 ，。缈) 定义与酰满足关系：( 1 一圭口) = 乙，即= 乙( 1 + j 1 口乙) 一1 与( 1 一丢口) 酰= 则 碱，酰) = g ( 蚴+ 三) _ o ( n 由于山o ，酰+ 口何一j c o ) j 及g ( 习 0 有 芷( x o ；h ，吼) c e g ( i ) 0 f f j | 导x = c r ( y o ；- y ) 证明：由于x ，j ，乙+ l ，所以有 - i iii i ，y o - i iy 1 1 根据j o r d a l l 乘法定义，由x o y = o - i 得虿t y + ：r o y 。= 0 ，因此，一方面，由上面的结论可得一矿y - l l i i i iyi i ；另- - y y 面，由 锥优化的最优性条件的刻画 c a u c h y - s c h w a r z 不等式得到一i t 歹- 0 使得i = 一仃歹，此时可得= ii i ，= i i 歹i | ， 于是有x o = a y o ，从而得到x = 仃( y o ；- y ) _ 2 2 一般优化问题的最优性条件 2 2 1 无约束优化问题的最优性条件 考虑非线性规划问题： m i n f ( x ) ，x 卯 ( 2 2 1 ) 其中厂( x ) 是定义在孵”上的实函数这个问题是求厂( x ) 在刀维欧氏空间中的极小点，称 为无约束极值问题这是一个古典的极值问题，在微积分学中已经有所研究，那里给出 了定义在几何空间上的实函数极值存在条件，这一节只是把已有理论在欧式空间中加以 推广 为研究函数( x ) 的极值条件，先介绍一个定理，它在后面的证明中将要多次用到 定理2 8 设函数f ( x ) 在点i 可微，如果存在方向d ，使夥( i ) 1d 0 ，使得对每个五( o ，万) ，有厂( i + 名d ) ( i ) 定理2 9 设函数厂( x ) 在点i 可微，若i 是局部极小点，则梯度可( i ) = 0 证明：用反证法设v 厂( i ) 0 ，令方向d = 一夥( i ) ，则有 町( i ) 1d = 一夥( i ) 1 耵( i ) = 一夥( i ) 1 1 2 0 ，使得当旯( o ，万) 时，成立 ( i + 五d ) f ( x ) 这与i 是局部极小点矛盾一 下面，利用函数厂( x ) 的h e s s i a n 矩阵，给出局部极小点的二阶必要条件 定理2 1 0 设函数厂( x ) 在点i 处二次可微，若i 是局部极小点，则梯度夥( i ) = 0 ， 并且h e s s i a n 矩阵v 2 厂( i ) 是半正定的 证明：定理2 9 已经证明耵( i ) = 0 ，现在只需证明h e s s i a n 矩阵v 2 f ( x ) 半正定设 d 是任意一个行维向量，由于厂( x ) 在i 处二次可微，且夥( i ) = 0 ，因此有 一8 一 辽宁师范大学硕士学位论文 ( i + 五d ) = 厂( i ) + 去力2 d t v 2 ( 芽) d + 允2l la1 1 2 口( 穿，见d ) ( 2 2 2 ) 其中当五。0 时，口( i ，名d ) 斗0 把式( 2 2 2 ) q b ( i ) 移致等号左端，并两端除以兄2 ，得到 2 三掣：丢d t v z ( i ) d + i l dl l ：口( i ，五d ) 旯22 。、7、。7 由于i 是局部极小点，当h 充分小时，必有 厂( i + 名d ) ( i ) 以及五j0 时，口( i ，力d ) - - - ) , 0 ，因此由式( 2 2 2 ) 推得 d t v 2 厂( i ) d 0 即v 2 厂( i ) 是半正定的一 下面给出局部极小点的二阶充分条件 定理2 11 设函数厂( x ) 在点i 处二次可微，若梯度w ( i ) = 0 ，且h e s s i a n 矩阵 v 2 厂( i ) 正定，则i 是局部极小点 证明：根据函数二次可微的定义，有 厂( x ) = 厂( i ) + v 厂( i ) t ( x i ) + 妻( x i ) t v 2 ( i ) ( x i ) + i i x i i l 2 口( i ，x i ) ( 2 2 3 ) 其中当x 专i 时，口( i ，x - 2 ) 专0 下面用反证法设i 不是局部极小点，则存在收敛于i 的点列 z ( ，使得对每个七 有 厂( x ( 。) 0 ，使得对每个五( o ，万) ，都有 ( i + 旯d ) 厂( i ) 则称d 为函数( x ) 在i 的下降方向 7 如果f ( x ) 是可微函数，且w ( i ) d o ，使得v 五( o ，万) ，葡+ 名d s ) ， ( 2 2 1 1 ) 称为在i 处的可行方向锥 锥优化的最优性条件的刻画 由可行方向和下降方向的定义可知，如果i 是厂( x ) 在s 上的局部极小点，则在i 处 的可行方向一定不是下降方向 定理2 1 6 考虑问题 m l n f ( x ) s t x d 设s 是孵中的非空集合，i s ，f ( x ) 在i 处可微如果i 是局部最优解，则 矗n d = o 其中矗和d 分别由式( 2 2 1 0 ) 和( 2 2 1 1 ) 定义 证明：用反证法设存在非零向量d f ono ，则d f o 且d d 根据f o 的定义，有 夥( i ) 1d 0 ，当名( o ，4 ) 时，有 厂( i + 五d ) 0 ，当力( o ，嘎) 时，有 x i + t d s ( 2 2 1 3 ) 令艿= l l l i n 磊，嘎 ，则当五( 0 ，万) 式，( 2 2 1 2 ) 和( 2 2 1 3 ) i n i n 成立这与i 是局部最优解 相矛盾一 下面研究问题( 2 2 8 ) 先以几何方式研究最优解的一阶必要条件，再给出代数表达 为此定义集合： h o = 冲哆( i ) t d = 0 ，川，口 可以证明，当v ( i ) ，v 红( i ) ，v 均( i ) 线性无关时，风等于等式约束 ( x ) = 0 缟( x ) = 0 岛( x ) = 0 所定义的超曲面在i 处的切平面关于这一结论的证明，可参看文献 2 7 1 下面给出一般约束优化问题( 2 2 8 ) 的一阶必要性条件 定理2 1 7 ( 一阶必要性条件) 设在问题( 2 2 8 ) 中，i 为可行点，i - i l g , ( g ) = o ，f 和吕( f ，) 在点i 可微，g ，( f 萑，) 在点i 连续，吃( ，= 1 ，) 在点z 连续可微，且 v 啊( i ) ，v 吃( i ) ，v h , ( i ) 线性无关如果i 是局部最优解，则在i 处，有 辽宁师范大学硕士学位论文 eng on 4 0 = a 其中昂和g 0 的定义为 y o 引w ( i ) t d 0 ， 定理2 1 8 ( k - t 必要条件) 设在问题( 2 2 8 ) 中，i 为可行点，= f l ( i ) = o ) ，厂和 ( f ，) 在点i 可微，g t ( f 诺，) 在点i 连续，吃( = 1 ，) 在点i 连续可微，向量集 v g i ( i ) ，勺( 万) l f ，j = l ，口 线性无关如果i 是局部最优解，则存在数嵋( f i ) s o v s ( ，= 1 ，t ) 4 吏 ! q w ( i ) 一w , v g , ( i ) 一_ v 勺( i ) = o ，w o ，f i ，e ， j = l 当& ( f 仨，) 在点i 也可微时，令其相应的乘子m 等于零，于是可将上述k - t 条件写 成下列等价形式： 夥( i ) 一w , v g , ( i ) 一_ v 嘭( i ) = o ， i = 1 j = 1 w j ( i ) = o ，扛1 ，m 0 ，f _ l ，n 定义2 1 9 广义的l a g r a n g e 函数： l ( x ，w ，v ) = 厂( x ) 一w , g ；( x ) 一_ 乃( x ) ( 2 2 1 4 ) i = l j = l 则在定理2 1 8 的条件下，若可为问题( 2 2 8 ) 的局部最优解，则存在乘子向量诼0 和 矿，使得v ，( i ，诼，矿) = o 这样，k - t 乘子访和矿也称为l a g r a n g e 乘子这时，一般情形 的一阶必要条件可以表达为： v 。l ( x ，w ，1 ，) = 0 g ，( x ) o ，f _ 1 ，m ( x ) = o ，j f = l ， ( 2 2 1 5 ) w ( x ) = o ，f = 1 ，m i v , 0 ，f = 1 ，m 前面给出的一阶最优性条件，都不涉及目标函数及约束函数的二阶导数实际上， 二阶函数反映函数的曲率特性，它们对稳定算法的设计具有重要意义，因此要研究约束 问题的二阶最优性条件 锥优化的最优性条件的刻画 为研究二阶必要条件，需要像研究一阶必要条件那样，对约束条件加以适当的限制 为此我们需要利用预备知识中给出的切锥的概念 现在我们考虑问题( 2 2 8 ) 设在可行点i ，对应不等式约束中的起作用约束和等式 约束的l a g r a n g e 乘子分别为羁0 ，f ，瓦，= 1 ，定义一个集合 ii g f ( x ) = o ，f ，且嘎 0 l s = h 岛( x ) o ，f 堪羁= 0 il 勺( x ) = 0 ，= l ，i 记集合歹在点i 的切锥为于再定义一个集合 g = i v g f ( i ) td = o ，i ，且厩 o d v g , ( i ) 1d o ，i ，且羁= 0 v 嘭( i ) t d = o ，j = l ， 答易证明g3 t 设d 于，则存在可行序列 x ) c 曩和正数列 五 ，使得l 鳃五( x 一i ) = d ，把 ( x ) 和吃( x ) 在i 展开，得到： & ( x 佧) = ( i ) + v g ，( i ) t ( x 一i ) + i i x 似一i i a ( i , x ( k ) - i ) 吃( x 耻) = 勺( i ) + v 嘭( i ) t ( x 忙一i ) + i ix 忙一x ia ( x , x ( k ) - - i ) 由于当f ，时，岛( i ) = o ，当f ，且羁 o 时，g ( x ( ) = o ，当f ，且嘎= o 时，有 & ( x 仕) o 以及_ ( x ) = 勺( i ) = 0 ，因此： 1 ) 当，且嘎 o 时，有( 孑) t ( z 一孑) + i ix 一i | | 口( i ，z 砷一i ) = 0 2 ) 当f ，且羁2 0 时，有v g i ( i ) t ( x ( k ) - y ) + l ix 一i i | 口( i ，x 。一i ) o 3 ) 当，= l ，时，有v 勺( i ) t ( x 一i ) + i i x 一ii i 口( i ，x 一万) = 0 把以上格式两端乘以五，令k - o o ，得到( i ) td = o ，f ，且羁 o v g f ( i ) t d o ，f 1 r = o v 勺( i ) t d = o ，y = l ， 即d a 所以召3 于由以上分析可见，切锥于必定含于召，但是反之不成立，即集 合召不一定含于切锥于 辽宁师范大学硕士学位论文 下面，在gct 也成立的假设下，给出关于问题( 2 2 8 ) 的局部最优解的二阶必要条 件 定理2 2 0 ( 二阶必要条件) 设i 是问题( 2 2 8 ) 的局部最优解，厂，( 扛1 ，聊) 和 嘭( ，= l ，) 二次连续可微，并存在满足( 2 2 1 5 ) 的乘子诼= ( 厩，呒) 和1 ，= ( 巧，巧) ， 再假设在点i 约束规范召= 于成立，则对每一个向量d 召都有d t v ：( i ，访，v ) d 0 ，其 中v ：( i ，诼，矿) = v 2 ( i ) 一暖v 2 & ( i ) 一v , v 2 勺( i ) 是l a g r a n g e 函数三( 毛w ，v ) 在点i ，5 i j = l 关于x 的h e s s i a n 矩阵 证明：设向量d o ，d a 由于约束规范g 一= t 一成立，因此d 于从而存在可行序 列 x ) c 可和正数列 五 ，使得憋五( x 一i ) = d 将( x ，订，矿) 在x ( 展开，则 三( 以访，矿) = 三( _ ，访，矿) + v ，( i ，诼，矿) t ( x 一i ) + 专( x 似一万) 1v ：三( i ，厩矿) ( x 似一i ) ( 2 2 1 6 ) + i ix ( 一2 1 1 2 口f i ，x ( 七1 一i 1 其中当x 一万时，口( i ，x 一i ) 专o 由于x 。季，因此必有勺( x ) = 0 羁蜀( x ( 七) = o 根据l a g r a n g e 函数的定义，得到 ( x o ，诼，歹) = 厂( x 似) ( 2 2 1 7 ) 工( i ，诼，矿) = ( i ) ( 2 2 1 8 ) 把( 2 2 1 7 ) 和( 2 2 1 8 ) 代入( 2 2 1 6 ) ，并注意到i 是局部最优解，v ，三( i ，死矿) = o ，则有 厂( x 似) = 厂( i ) + 吉( x 似一i ) 1v ：( 孑，诼，矿) ( x 似一i ) + i ix ( 。) - 2 1 1 2 口( i ，x o 一i ) ( 2 2 1 9 ) 由于i 是局部最优解，当七充分大时，必有厂( x 。) 厂( 舅) ，1 7 7 1 此，对充分大的七，由 ( 2 2 1 9 ) 得出号( x ( 0 - 2 ) 1v ：三( 瓦厩矿) ( z 似一孑) + i lz o 一万| | 2 口( 五石 一i ) o ，两端乘以刀， 并取极限得：d t v 2 l ( 2 ，诼，v ) d oi 为给出局部最优解的二阶充分条件我们定义集合 锥优化的最优性条件的刻画 g = = d o ( i ) t d = 0 ，f ，且羁 o v ( i ) td o ，f ，且羁= o v 吃( i ) td = o ，j = l ， 定理2 2 1 ( 二阶充分条件) 设在i h - j n ( 2 2 8 ) 中，f ，g ，【f - 1 ，m ) 和吃【歹2 1 ，z j 二次 连续可微，i 为可行点，存在乘子诼= ( 厩，或) 和矿= ( 巧，巧) 使条件( 2 2 1 5 ) 成立，且 对每个向量d g ，都有 d t v ：三( i ，诼，矿) d 0 则i 是严格的局部最优解 证明：用反证法假设i 不是严格的局部最优解，则存在收敛于i 的可行序列 x ， 使 厂( x ) 厂( i ) ( 2 2 2 0 ) 令 ) - 高 叫1 ) 由于 d ( ) 为有界序列，则存在收敛子序列 d _ ) ，设其极限为d ( o ) 将& ( x ) 在点 i 展开，再令x ：x ( ，得到 ( 叫= ( i ) + 。( i ) t 一i ) + i i x 吲i 口( 耻心一万) ( 2 2 2 2 ) 其中当乃一时，口( i ，x 一i ) j o 当f ，时，& ( i ) = o 又知x 是可行点，蜀( x 似) o 因此由( 2 2 2 2 ) 得出 ( i ) t 一i ) + i ix 似吲i 口h 钏一i ) o 上式两端除以l ix ( 一il i ，令屯专。o 则推得 取，( i ) td o o ，f ， ( 2 2 2 3 ) 用类似的方法可以得到 以及 v 乃( i ) t d 。= o ，j = l ， w ( i ) t d 。o ( 2 2 2 4 ) ( 2 2 2 5 ) 辽宁师范大学硕士学位论文 _ - _ _ 一 卜向分两种情彤讨论： ( 1 ) d ( o ) 诺g 此时，由式( 2 2 2 3 ) 和集合g 的定义可知，必存在下标f j 使得嘎 o j l v g ；( i ) t d 。 o 这样，利用k