（运筹学与控制论专业论文）对称锥优化问题的扰动分析.pdf

大连理工大学博士学位论文 摘要 本论文主要建立对称锥的变分分析并给出对称锥优化问题扰动分析的理论结果， 主要内容可概括如下： 1 第2 章基于欧氏j o r d a n 代数的性质，研究了对称锥的变分性质。首先推导了对称锥 上投影算子b 次微分的计算公式以及对称锥的切锥、二阶切集的表达式。然后定 义了对称锥上的线性二次函数，建立了线性一二次函数与对称锥二阶切集的支撑 函数的关系。 2 第3 章在前一章研究的基础上，阐述了对称锥优化问题的扰动理论结果。首先证 明了对称锥具有# b - - 阶正则性，从而给出对称锥优化问题无间隙的二阶最优性条 件。其次引入对称锥优化问题两种形式的强二阶充分性条件，其中之一通过一线 性二次函数定义，另一个用二阶切集的支撑函数定义。之后，对于上述两种强 二阶充分条件重合的非凸对称锥优化问题，得到了下述条件的等价性：约束非退 化条件下的强二阶充分条件，k k t 条件对应的广义方程的解的强正则性，k k t 条 件对应的非光滑映射( 简称k k t 映射) 的c l a r k e 广义微分的非奇异性，优化问题局部 最优解的强稳定性，以及其他4 条结论相互等价。特别地，对于凸对称锥优化问 题，不需要任何假设，上述9 条性质均等价，且等价于k k t 映射的b 次微分的非 奇异性。最后，对于线性对称锥优化问题，首先刻画了对偶严格约束规范与二阶 充分性条件的等价关系；然后证明了上述1 哚等价性质与原始对偶约束非退化条 件的等价性。 3 第4 章具体推导了二阶锥、半正定实对称矩阵锥、半正定复h e r m i t e 矩阵锥以及半 正定四元数h e r m i t e 矩阵锥二阶切集的表达式，并证明了这四种情况下二阶切集的 支撑函数与对应的线性二次函数是相等的，从而得到了当k 同构于有限多个上述 四种类型的锥的卡氏积时，第3 章提出的两种形式的强二阶充分性条件等价，因 此对于上述形式的k ，第3 章中关于锥优化问题扰动理论的等价性结论是成立的。 对称锥优化问题的扰动分析 关键词：对称锥；锥优化；欧氏j o r d a n 代数；变分分析；扰动分析 一 大连理工大学尊士学位论文 s e n s i t i v i t ya n a l y s i so fo p t i m i z a t i o np r o b l e m so v e rs y m m e t r i cc o n e s a b s t r a c t 3 3 _ l j sd i s s e r t a t i o nf o c u s e so nt h es t u d yo fv a r i a t i o n a la n a l y s i so fs y m m e t r i cc o n e sa n dp e r - t u r b a d o na n a l y s i so fo p t i m i z a t i o no v e rs y m m e t r i cc o n e s t h em a i nr e s u l t s ，o b t a i n e di nt h i s d i s s e r t a t i o n ，m a yb es u m m a r i z e d a sf o l l o w s ： 1 c h a p t e r2 ，b a s e do nt h et h e o r yo fe u c l i d e a nj o r d a na l g e b r a s ，d e v e l o p st h ee l e m e n t si n t h e v a r i a t i o n a la n a l y s i so fs y m m e t r i cc o n e sr e l a t e dt ot h eo p t i m i z a t i o np r o b l e m t h ef o r m u l a s o ft a n g e n tc o n e s ，s e c o n do r d e rt a n g e n ts e t so fs y m m e t r i cc o n e sa n dt h eb s u b d i f f e r e n t i a l o ft h ep r o j e c t i o no p e r a t o ro n t oas y m m e t r i cc o n ea r cd e r i v e d al i n e a r - q u a d r a t i cf u n c d o n i si n t r o d u c e da n dt h er e l a t i o n s h i pw i t ht h es u p p o r t i n gf u n c d o no ft h es e c o n do r d e rt a n g e n t s e ti se s t a b l i s h e d 2 c h a p t e r3 ，b a s e do nt h ev a r i a t i o n a la n a l y s i sd e v e l o p e di nc h a p t e r2 ，s t u d i e st h ep e r t u r - b a t i o na n a l y s i so ft h en o n l i n e a rs y m m e t r i cc o n i co p t i m i z a t i o np r o b l e m f i r s t l y , t h eo u t e r s e c o n do r d e rr e g u l a r i t yo fs y m m e t r i cc o n e si sp r o v e da n dt h en og a po p t i m a l i t yc o n - d i d o n sa r eo b t a i n e d s e c o n d l y , t w ot y p e so fs t r o n gs e c o n do r d e rs u f f i c i e n to p t i m a l i t y c o n d i t i o n sf o rt h eo p t i m i z a t i o no v e rs y m m e t r i cc o n e sa r ep r o p o s e d ，o n eo fw h i c hi sd e s c r i b e dt h r o u g ht h el i n e a r - q u a d r a t i cf o r ma n dt h eo t h e rt h r o u g ht h es u p p o r t i n gf u n c t i o n o ft h es e c o n do r d e rt a n g e n ts e t f o rt h en o n c o n v e xc o n i co p t i m i z a t i o np r o b l e m sw h o s e t w os t r o n gs e c o n do r d e rs u f f i c i e n tc o n d i t i o n sc o i n c i d e ，w es h o wt h a tf o ral o c a l l yo p t i 。 m a ls o l u t i o n ，t h ef o l l o w i n gc o n d i t i o n sa r ee q u i v a l e n t ：t h es t r o n gs e c o n do r d e rs u f f i c i e n t c o n d i t i o na n dp r i m a lc o n s t r a i n tn o n d e g e n e r a c y , t h es t r o n gr e g u l a r i t yo ft h eg e n e r a l i z e d e q u a t i o nc o r r e s p o n d i n g t ot h ek k t s y s t e m ，t h en o n s i n g u l a r i t yo f t h ec l a r k e sg e n e r a l i z e d s u b d i f f e r e n t i a lo ft h en o n s m o o t hm a p p i n g ( k k tm a p p i n gf o rs h o r t ) c o r r e s p o n d i n gt ot h e 对称锥优化问题的扰动分析 k k tc o n d i t i o n sa tt h ek k t p o i n t ，s t r o n gs t a b i l i t yo ft h eo p t i m a ls o l u t i o na n do t h e r4 c o n d i t i o n s m o r e o v e r , f o rac o n v e xc o n i cp r o g r a m m i n gp r o b l e m ，t h ee q u i v a l e n c ea m o n g a l lt h el i s t e dc o n d i t i o n ss t i l lh o l d sw h e nt h ec o n ei ss y m m e t r i c b e s i d e s ，e a c ho ft h e s e c o n d i t i o n si se q u i v a l e n tt ot h en o n s i n g u l a r i t yo fb s u b d i f f e r e n t i a lo ft h ek k tm a p p i n g e s p e c i a l l y , f o ral i n e a rc o n i cp r o g r a m m i n gp r o b l e m , t h er e l a t i o n s h i pb e t w e e nt h es e e - o n do r d e rs u f f i c i e n tc o n 出t i o na n dt h ed u a ls t r i c tc o n s t r a i n tq u a l i f i c a t i o ni sc h a r a c t e r i z e d m o r e o v e r , i nt h i sc a s et h ea b o v e10e q u i v a l e n tc o n d i t i o n sf o rc o n v e xp r o g r a m m i n ga r e p r o v e nt ob ee q u i v a l e n tt ob o t ht h ep r i m a la n dd u a lc o n s t r a i n tn o n d e g e n e r a c i e s 3 i nc h a p t e r4 f o r m u l a sf o rs e c o n do r d e rt a n g e n ts e t so fs e c o n do r d e rc o n e ，t h ec o n eo f p o s i t i v e l ys e m i d e f i n i t es y m m e t r i cr e a lm a t r i c e s ，t h ec o n eo fp o s i t i v e l ys e m i d e f i n i t ec o m p l e xh e r m i t i a nm a t r i c e s ，a n dt h ec o n eo fp o s i t i v e l ys e m i d e f i n i t eq u a t e m i o nh e r m i t i a n m a t r i c e s ，a r ed e v e l o p e da n di ne a c hc a s et h el i n e a r - q u a d r a t i cf o r mi sp r o v e dt oc o i n c i d e w i t ht h es u p p o r t i n gf u n c t i o no ft h es e c o n do r d e rt a n g e n ts e t t h e r e f o r e ，w h e nk i sr e p r e - s e n t e da sac o n ei s o m o r p h i ct oac a r t e s i a np r o d u c to faf i n i t en u m b e ro ft h e s ef o u rt y p e s o fc o n e s ，t h et w os t r o n gs e c o n do r d e rs u f f i c i e n tc o n d i t i o n sa r ee q u i v a l e n ta n da l le q u i v a - l e n tc o n d i t i o n sa b o u tp e r t u r b a t i o na n a l y s i si nc h a p t e r3a r ev a l i dw h e nki so ft h i sk i n d o f f o r m k e y w o r d s ：s y m m e t r i cc o n e ；c o n i co p t i m i z a t i o n ；e u c l i d e a nj o r d a na l g e b r a s ；v a r i a t i o n a l a n a l y s i s ；p e r t u r b a t i o na n a l y s i s 一 大连理工大学学位论文独创性声明 作者郑重声明：所呈交的学位论文，是本人在导师的指导下进行研究 工作所取得的成果。尽我所知，除文中已经注明引用内容和致谢的地方外， 本论文不包含其他个人或集体已经发表的研究成果，也不包含其他已申请 学位或其他用途使用过的成果。与我一同工作的同志对本研究所做的贡献 均已在论文中做了明确的说明并表示了谢意。 若有不实之处，本人愿意承担相关法律责任。 学位论文题目：d j 盈鱼- 丝丛通氐丝堑动盖毯年一 作者签名：垂篓l 一 日期：邋年址月弓互日 大连理工大学博士学位论文 大连理工大学学位论文版权使用授权书 本人完全了解学校有关学位论文知识产权的规定，在校攻读学位期间 论文工作的知识产权属于大连理工大学，允许论文被查阅和借阅。学校有 权保留论文并向国家有关部门或机构送交论文的复印件和电子版，可以将 本学位论文的全部或部分内容编入有关数据库进行检索，可以采用影印、 缩印、或扫描等复制手段保存和汇编本学位论文。 学位论文题目： 盘益缓鱼业固塑锱监逊盈堑 作者签名：至益e t 期：坦墨r 年j l 月上星e l 导师签名：j 磋l 二乏旦一 日期：二型l 年址月翠日 大连理工大学博士学位论文 1 。绪论 本章首先简要地介绍了对称锥优化问题的发展历史及其现状，重点回顾了约束优化 问题稳定性理论的研究历程然后概述本论文研究的内容以及取得的主要结果在这一 章的最后，给出本论文研究所需要的预备知识 1 1 对称锥优化问题 本论文主要考虑如下对称锥优化问题： m i n f ( x ) s t h ( x ) = 0 g ( x ) k ， 其中函数厂：x 一跪，h ：x _ 妒，g ：x _ y 均是二次连续可微的，x 和y 是两个有限维 向量值空间。k 是y 中的对称锥 这里涉及的对称锥的概念，在下述定义中给出 定义1 1n 1 假设v 是一个礼维实欧几里德空间，kcv 是一闭凸锥，用g l ( v ) 表示v 上 所有线性变换构成的集合，a u t ( k ) 表示k 的自同构群，即a u t ( k ) = t g l ( v ) i t k = k ，i n t k 表示k 的内点组成的集合，如果k 满足条件： ( i ) 集合k 是自同构的，即vu ，v i n t k ，存在a u t ( k ) 中的t ，满足t u = 秒； ( i i ) 集合k 是白对偶的，即k 的对偶锥k + 是k 本身：k + = k = z v ：( z ，z ) o ，比 k ) ， 则称k 是对称锥 下面介绍几种常见的对称锥 j 当v = 渺时，k = 啦三 x l x l 0 ，i = 1 ，尼) 表示非负实向量空间，易知k 是一 对称锥 当v = 跄南= 睨跪七一1 时，k = q 缸三 ( z o ，牙) v x o l i 牙1 1 ) ( j j 牙| l = 、z ；+ + z 2 1 ) 表示l o r e n t z 锥或二阶锥，则k 是一对称锥 对称锥优化问题的扰动分析 当v = 妒时，其中妒表示全部尼尼阶实对称矩阵构成的空间，k = t 鞋表示所有半 正定矩阵构成的集合，可以验证k 是一对称锥 对称锥的研究始：j ：k o e c h e r t 酬，他首次利用j o r d a n 代数给出对称锥的计算公式并对对 称锥进行等价分类，而r o t h a u s p l - 与v i n b e r g 扣1 在研究对称锥时引入的概念和方法仍沿用至 今( 见f a r a u t 与k o r s n y i 的专著川中的评述) 1 9 9 4 年，f a r a u t 与k o r l n y i 的专著1 全面概括的 介绍了对称锥和j o r d a n 代数的研究成果，应用欧式j o r d a n 代数理论刻画了对称锥的几何性 质，建立了j o r d a n 代数与对称矩阵空间的关系，考察了凸锥上的管状域的复杂性，分析了 管状对称域上函数空间的特点，并给出对称锥的调和分析，为后来研究对称锥的变分性 质，以及对称锥上的各种问题提供了有效的理论工具 最近十几年。对称锥优化问题已经成为一个相当活跃和热门的研究领域，吸引了一 大批科学研究工作者，其中包括凸规划、线性代数、数值优化、组合优化、控制论、 不确定优化、鲁棒优化、博弈与均衡理论以及统计方向的许多专家究其原因，是因 为人们发现对称锥优化在这些领域有着极其广泛和重要的应用经典的线性及非线性 规划问题。半定规划问题，以及二阶锥( 冰淇淋锥或者l o r e n t z 锥) 优化问题，都可以统一在 对称锥优化问题的框架下甚至某些补问题与变分不等式问题的最优性条件也是通过 求解对称锥优化问题得到的特别是近些年来。对称锥优化问题被广泛应用在经济、 管理、交通、工程设计、通信、控制等实际部门，许多国际优化界的著名专家和学者 也从不同角度致力于对称锥优化问题的研究1 9 9 7 年，f a y b u s o v i c h 盯研基于欧式j o r d a l l 代 数技术，提出了求解线性对称锥优化问题的内点法，并证明了其多项式复杂性此后， s c l a r n i e t a n a l i z a d e h 怫埘用牛顿法求解松弛后的线性对称锥优化问题的k k t 系统证明各 种不同的原始对偶内点法的收敛速度均具有多项式复杂性随着优化理论和算法的不断 完善，许多原来很难解决甚至不能解决的问题都可以转化为求解对称锥优化问题的模型， 然后通过对此模型的求解，进而得到比较满意的结果，尤其是对称锥优化问题中半定规划 的应用和发展，可见v 觚d e n b e 瑁h e 与b 0 y d 【i 。，h e r 注y r o m e s h 军i l i e v e n 3 1 以及圈e r k f 1 等等 刘勇进n 5 1 运用欧氏j o r d a n 代数，研究了对称锥互补问题的光滑函数与一类效益函数以及 它们在线性对称锥优化和对称锥互补问题求解中的应用r o o s 。b a i 与c h a e r a n i u 剀则给出 锥优化模型在r o b u s t 桁架拓扑设计实例中的应用，讨论了几种利用锥优化求解r o b u s t 桁 架拓扑设计问题的方法2 0 0 6 年8 月n e m i r o v s k i 在世界数学家大会上的报告u 7 1 专门对线 性对称锥优化这一类较一般的线性锥优化问题进行了介绍和分析阐述解释基本理论和 概念，从理论上分析，可类似于线性s d p 问题，用内点方法求解对称锥优化问题2 0 0 7 年， 2 一 大连理工大学博士学位论文 修乃华，韩继业的综述性文章8 1 在理论与算法方面总结评述了对称锥互补问题的新成 果，孔令臣9 1 则建立了对称锥互补问题的几个互补函数和效益函数并研究了它们的可 徼性、半光滑性和水平集有界性等，并在此基础上构造了求解对称锥互补问题的算 法，并给出了相应算法的收敛性分析对对称锥互补问题的理论算法有兴趣的读者可参 阅 1 5 ，1 8 _ 2 4 】及其提到的参考文献 众所周知扰动分析是最优化理论中的重要组成部分约束优化问题的一阶，尤 其二阶最优性条件与扰动分析有着密切的联系最近三十年，连续最优化问题的扰动 分析这一研究领域取得了许多重要的研究成果当k 是一凸多面体集合时，相关的稳 定性理论已经非常完备通常研究的非线性规划就是其中的特殊情况，早在7 0 年代， r o c k a f e l l a r f z 5 1 用凸分析的理论工具对其进行了详尽的研究当约束集合k 是非凸多面 体集合时，1 9 9 2 年m a l a n o w s k i 嗍与s h a p 的和b o 姗a i l s 口刀分别研究了一般锥约束优化问题 最优解的稳定性与灵敏度近年来国际优化领域出版了关于变分分析，扰动分析，非 光滑方程和互补与变分不等式的著名专著，见r o c k a f e l l a r - 与w e t s 瞰1 ，b o 皿a n s 和s h a p 曲例， k l a t t e 与k u m m e r t 3 0 1 以及f a c c h i n e i 和p a n g 【3 1 1 在这些专著中，最优化的扰动理论都不同程度 地被给予关注目前当k 是对称锥时。这类优化问题的扰动理论受到越来越多专家和学 者的重视，因为扰动分析和数值算法的收敛分析密切相关 依据b o i u l a i l s 和s h a p i r o 瑚1 ，约束优化问题扰动分析的主要研究方式以及成果可作如 下划分： 1 第一种情况是可将隐函数定理应用到一阶最优性系统的情形这是一种相对简单 的情况，它适合于等式问题，也适合有有限个不等式约束且严格互补性假设成立的 情况这一类型的结果在 3 2 中有较广泛的讨论 2 第二种情况是一阶最优性系统满足由r o b i n s o n h 3 1 提出的强正则性假设的情形粗略 地说这意味着扰动最优性系统具有一个以一种l i p s c h i t z 连续的方式依赖于扰动的 局部唯一解此种情况下最优化问题的灵敏度分析简化为最优性系统的灵敏度分 析这里的强正则性的方法可视为隐函数定理方法的一个推广 3 第三种是强方向二阶充分性条件成立的情况此时可以计算最优值函数的二阶展 开与接近最优解的一阶展开 4 第四种情况就是标准的二阶充分性条件成立的情形，这时可以计算最优值函数的一 阶展式与一个解路径的参数亡开平方阶的一展开 3 对称锥优化问题的扰动分析 5 最后一种情况是在涉及奇异的l a g r a n g e 乘子的二阶充分性条件成立的前提下，处 理l 姗g e 乘子集合为空集的情况可以计算第一项为参数亡的开平方阶的最优值 函数的展开与解路径也是参数t 的开平方阶的一展开式 本论文主要从上述第二种角度对对称锥优化问题进行分析，其他几种情况的理论研 究成果可以参考b o n n a n s 和s h a p i r 0 2 0 0 0 年综述性专著犯明及其参考文献，这里不再叙述 下面仅对与本论文工作有关的优化问题扰动分析的研究情况作简短地综述 1 2 扰动分析的研究现况 我们发现，【2 9 】中建立的扰动理论体系，并没有同优化问题的k k t 系统建立联系，尤 其是对对称锥优化问题，目前没有详细的扰动分析而优化问题最优性条件与k k t 点性 质的关系无论是在优化理论的研究还是在算法的收敛性证明中都有重要的应用因此， 鉴于上述分析，我们试图建立一般的对称锥优化问题的最优性条件与k k t 点强正则性以 及强稳定性的关系首先回顾问题( 1 1 ) 中k 是对称锥中最常见的几种情况时，扰动分析的 研究情况 1 2 1 非线性规划 问题( 1 1 ) 中k 取为正卦限泌就成为经典的非线性规划问题对于非线性问题的研究 已经臻于完善1 9 8 0 年r o b i n s o n p 3 1 针对于一般框架下的广义方程，首次提出强正则解的 概念并给出了保证强正则性成立的一般性结论，具体刻画了非线性规划中保证局部最优 解强正则性的充分条件：即线性无关约束规范与r o b i n s o n 意义下的强二阶充分性条件能 保证优化问题k k t 系统对应的广义方程有强正则解同年，k o j i m a 蚓首次介绍了非线性规 划问题强稳定性的概念，并利用度理论推导不可微方程系统的强稳定性后来，k o j i m a i a ： 明非线性规划强稳定性的方程方法被广泛的应用到变分不等式和互补问题的扰动理论 研究中，并取得了丰硕的理论成果这些相关结论可以参考2 0 0 3 年f a c c h i n e i 署l l p a n g 的专 5 笙1 3 1 1 咽 1 9 8 7 生i z j o n g e n - 等口5 1 1 9 9 5 年b o n n a n s 与s u l e m m ， 1 9 9 6 年d o n m h e v 与r o c k a f e l l a r t ”1 以 及2 0 0 0 年b o i m a i l s 和s h a p 曲分别独立的证明- 了r o b i n s o n 口3 1 提出的强正则解的充分 条件也是必要条件s h a p i r o 曙剐把强稳定性的概念推广到较一般的问题中，1 9 9 9 年， k l a a e 和k l l i i l m e r i 矧对非线性规划的强稳定解进行了更深一步的研究 当k 是多面体集合时，优化问题( 1 1 ) 扰动理论的研究成果可以参考2 0 0 2 年k l a t t e 一4 大连理工大学博士学位论文 与k u m m e r 的专著1 1 2 2 二阶锥规划 当k 是有限多个二阶锥的卡氏积时，b o n n a n s 与r a m f r e z 1 研究了问题( 1 1 ) 的优化理 论。阐明了二阶锥规划问题中强正则解与强二阶充分性条件的关系借助这个重要结 论，w a n g - e ：s z h a n g h 岫1 总结得到了较全面的二阶锥优化问题稳定性和灵敏度的结论：即 强二阶充分性条件与k k t 点的强正则性等价，并且等价于k k t 系统对应函数c l a r k e - - 义微分的非奇异性。光滑化k k t 映射c l a r k e 广义微分的非奇异性，以及k k t 映射的局 部l i p s c h i t z 同胚性质。等等 、 1 - 2 3 半定规划 当k 是半正定实对称矩阵构成的锥时，s u n 建立了半定规划( 1 1 ) k k t 点强正则性 与其他九个条件的等价关系，其中包括约束非退化条件下的强二阶充分性条件，以 及k k t 系统对应函数c l a r k e 广义微分的非奇异性，k k t 点的强稳定性等等对于线性半定 规划问题c h a n 与s u nm 1 证明了原始对偶约束非退化条件等价于k k t 系统对应函数b 一微 分的非奇异性并与s u n 1 中建立的十个条件等价 1 3 本文的主要工作 观察到上述三种问题的研究均是针对是b o i u l a n s 与s h a p 曲瑚1 定义3 1 3 5 意义t c 2 锥简约的情况展开的事实上，c 2 锥简约条件下优化问题( 1 1 ) 扰动分析的理论已 在【2 9 】第5 章第l 节中有过探讨而由于无法确定对称锥的c 2 锥简约性，因此如何刻画一 个具有对称锥约束的一般性优化问题k k t 系统的强正则性就成了一个必然的问题，至 少c 2 锥简约性的理论不再适用本论文就是针对这个问题展开研究的 基于作者与新加坡国立大学孙德锋教授和大连理工大学张立卫教授的合作，形成了 关于对称锥的变分性质以及对称锥优化问题的扰动理论的研究报告m 1 本论文的素材是 研究报告，的深化和扩充主要可以分为两大部分： 第一部分是对称锥的变分分析首先，基于欧氏j o r d a i l 代数的空间分解，得到了对称 锥上投影算子方向导数的计算公式，刻画了投影算子b 一次微分中元素的变分性质其次， 给出j o r d a n 代数中的元素的矩阵表示，得到对称锥的切锥，临界锥与二阶切集的表达式 受s u n 1 的工作的启发，定义了一个j o r d a n 代数中的线性二次函数( 形式) ，建立了这个函 5 对称锥优化问题的扰动分析 数与对称锥的二阶切集的支撑函数的关系最后，详细地推导了如果k 是二阶锥，半正定 对称矩阵锥，半正定复h e r m i t e 矩阵锥，以及半正定四元数h e r m i t e 矩阵锥时二阶切集的表 达式，并证明了当k 同构于有限多个上述锥的卡氏积时，线性二次函数与二阶切集的支 撑函数是相等的 第二部分主要是对称锥优化问题的扰动分析在证明了对称锥具有外二阶正则性之 后，首先建立了对称锥优化问题无间隙的二阶最优性条件，接着定义两种形式的强二阶 充分性条件，阐明了当约束发生某种特殊扰动的最优化问题的二阶增长条件与弱形式的 强二阶充分条件之间的关系由于后续研究涉及某一映射的局部l i p s c h i t z 同胚性质，我们 建立了一般映射局部l i p s c l l i t z 同胚性质与其相对应的广义方程强正则性之间的等价关 系在两种强二阶充分条件重合的前提下，我们得到了非凸对称锥优化问题9 条等价性质： k k t 系统的强正则性，k k t 映射的c l a r k e 广义微分的非奇异性，局部最优解的强稳定性与 约束非退化条件下的强二阶充分条件均相互等价，并等价于其他4 条结论特别地，对于 凸对称锥优化问题，不需要任何假设，上述9 个等价性质均成立，且等价于k k t 映射b 次 微分的非奇异性对于任意的线性对称锥优化问题，首先证明了二阶充分性条件与对偶 严格约束规范的等价性。之后证明上述1 0 条性质中的任何一条均与原始对偶约束非退化 条件等价 1 4 预备知识 本章的最后，主要介绍本论文用到的一些基本的概念，如方向导数，c l a r k e 广义微分， 二阶切集等，然后简要地叙述本论文用到的有关欧氏j o r d a n 代数的一些基本知识 1 4 1 方向导数与c l a r k e 广义微分 定义1 2 令x 与y 是赋范线性空间考虑映射g ：x _ y ( i ) 称g 在z x 处沿方向九x 是方向可微的，若极限 北”= 船血掣 ( 1 2 ) 存在若g 在z 处沿每一方向危x 均是方向可微的。则称g 在z 处是方向可微的 ( i i ) 称g 在z 处是f r h e t 意义下方向可微的，若g 在z 处是方向可微的，且 6 大连理工大学博士学位论文 a ( x + h ) = g ( x ) + 9 7 ( z ，h ) + o ( 1 l h l l ) ，h x ( 1 3 ) 若9 7 ( z ，) 还是线性的，连续的，则称9 在z 处是f r h e t 可微( r 可微) 的 ( i i i ) 称夕在z x 处沿方向 x 二阶方向可微，若9 7 ( z ，九) 和极限 9 ( z + t h + l t 2 w ) 一9 ( z ) 一t g ，( z ，九) ( z ；h ，叫) ：2 觜1 了一 ( 1 - 4 2 。 对所有的伽x 均存在 对f 可微的映射，引入下述记号设x ，z 与m 均是有限维实h i l b e r t 空间 若映射f ：x y z _ m 在点( z ，y ，z ) x y z 处是f - 可微的，则 记p ( z ，y ，名) 为f 在( z ，y ，z ) 处的f r 6 c h e t 导数( f - 导数) ( 相应的，( z ，y ，z ) 为f 在( z ，y ，z ) 处 相对于z 的f - 导数) 令v f ( x ，y ，z ) ：= f 7 ( z ，y ，z ) 表示p ( z ，y ，z ) 的伴随算子( 相应的， v z f ( x ，可，z ) ：= e ( z ，y ，z ) 为罡( z ，y ，z ) 的伴随算子) ，这里线性算子a ：x _ y 的伴 随算子a + ：y 。一x + 由( a + 旷，z ) = ( y + ，触) ，v ( v ，z ) y 幸xx 定义 如果f 在( z ，y ，z ) 处还是二次f - - i 微的，则定义： f ( z ，y ，名) ：= ( f ，) ( z ，y ，z ) ， v 2 f ( x ，y ，z ) ：= ( v f ) 7 ( 2 ，y ，z ) ， 吃( z ，y ，z ) ：= ( e ) ：( z ，y ，z ) ， v l f ( z ，y ，z ) ：= ( v 2 f ) ：( z ，y ，z ) 我们给出l i p s c h i t z 连续函数的b o u l i g a n d 一次微分( b 一次微分) 与c l 砌汜广义微分的概念 设x ，y 和z 是三个任意的有限维实值向量空间，为简便起见内积均记为( ，) ，它引导 的范数记为”i i 令p 是y 中的一个开集，互：p y _ z 是开集p 上局部l i p s c h i t z 连续的 函数用魄记p 中使得函数三是f 可微的点的集合则三在秒处的c l 砌( e 广义微分是有定义 的： o = - ( y ) ：= c o n y 如三( y ) ) ， 其中“c o n v ”表示凸包， o s - - ( y ) ：= y ：y = 1 j m 三7 ( 矿) ，y 七0 - - ，y 七一可) 尤+ 。 7 对称锥优化问题的扰动分析 是三在y 的b 一次微分 复合函数b 次微分的计算公式首先被s u n l 4 。 研究，这里介绍 4 5 q b 的给出的较一般的 结论 引理1 3 嗍假设函数皿：x _ y 在x 的一个开邻域上是连续可微的，函数三：0 y _ z 在包含y + ：= 虫( 。+ ) 的一个开集合p 上是局部l i p s c h i t z 连续的若皿7 ( 矿) ：x _ y 是 映上的，则存在z 的一个开邻域，满足复合函数垂在这个邻域上是f - 可微的当且仅 当三在皿( z ) 是f 可微的，且 如圣( z + ) = c g b e ( y ) 霍7 扛+ ) ， ( 1 5 ) 其中西：_ z ，由圣 ) ：= 三( 皿( z ) ) ，z 定义 这一节的最后简单介绍投影算子几条最基本的性质 设d 是b a n a c h 空间z 中的一个凸集，记d ：z z 为d 上的投影算子，即对任意 的y z ，i i d ( z ) 是下述凸二次规划问题的唯一解： 商n 三( z - - y , z - - y ) s t z d i 扫z a r a n t o n e l l o m 可知n d ( ) 在z 上是几乎处处f - 可微的，且对任意的z ，觚d ( 秒) 都是有 定义的 引理1 4 令d z 是一凸集合，则对任意的秒z ，任意的y a d ( 矽) ，均有： ( a ) y 是自共轭的； ( b ) ( d ，v 回0 ，v d z ； ( c ) ( v d ，d y d ) 0 ，v d z 1 4 2 切锥法锥与二阶切集 这一节，设x ：z 黾= b a n a c h 空间首先，对x 中的子集类a ，其中亡是参数，给出集值映射的 外内极限的定义，即a 在t - - - - - 4t o 时的外极限为： l i ms u p a t ：= 。x ：存在序列亡n _ ，存在z n a 幻满足。竹一z ) ， 一8 大连理工大学搏上学位论文 a 在t 一o 时的内极限为： l i r a t 。幻i n f a t ：= z x ：对任意的序列k _ t 。，存在z n a t ，满足z n _ z ) 然后利用上述的外内极限，引入切锥的概念 定义1 5 溯对b a i l a c h 空间x ，s 是x 的闭子集，。s ，分别定义s 在z 处的切锥与内切锥如 下： 瓦( z ) ：l i r a s u p 竿， t t o o 巧( 小= 孚， ( 1 6 ) ( 1 7 ) 若z 不属于s ，约定这些锥为空集显然有名( z ) c 乃( z ) ，且两者均是闭的若 f f j d i s tx ，s ) 记z x 到媚离，尽1 d i s t ( z ，s ) ：21 琶忙一z i l ，则切锥与内切锥可以表示为下 述形式 乃( z ) = x ：3 t nj ，0 ，d i s t ( z + t n h ，s ) = o ( t n ) ) ， 霉( z ) = 危x ：d i s t ( z + t h ，s ) = o ) ，t o ) 命题1 6 若s 是凸闭集，z s ，则 定义1 7 集合极限 瓦( z ) = 乃( z ) 学”刨鼍亨 = _ 叫x ：d i s t ( z + 亡九+ 主亡2 叫，s ) = 。( 亡2 ) ，亡o ) ， 露( z ，危) ：l i r a s u p 掣 t & o三+ 2 9 一 ( 1 8 ) ( 1 9 ) ( 1 1 0 ) ( 1 1 1 ) 对称锥优化问题的扰动分析 = wex ：刍k l o ，d i s t ( z + 九+ 互1 亡扎2 训，s ) = 。( 磋) ) ， ( 1 1 2 ) 分别被称为s 在点z 沿方向h 的内二阶切集与外二阶切集 由上述的定义显然易知露2 ( z ，h ) c 露( z ，九) ，且两个集合露2 ( z ，h ) 与露( z ，允) 均是闭 的只有h 丁喜( z ) 时内二阶切集露2 ( z ，九) 才可能非空类似地，只有h 乃 ) ，外二阶切 集露( z ，危) 才可能是非空的若s 是凸的，距离函数d i s t ( ，s ) 是凸的由( 1 1 2 ) 得内二阶切 集露2 ( z ，h ) 是凸的，但是外二阶切集露( z ， ) 可能是非凸的为了研究的方便，这就要求 我们给出s 的一些假设来保证外二阶切集的凸性，这将在第3 章中给予讨论 下面仅给出本论文中用到的法锥的概念对于b a n a c h 空间中的z 闭凸集最若z s ， 则s 在z 处的法锥为： 。 人名( z ) = z 。x + ：( z + ，z z ) 0 ，比s ) ( 1 1 3 ) 若z 簪s ，规跳( z ) = d 关于对称锥的切锥，法锥和二阶切集的具体形式与应用，将在后面两章叙述 1 4 3 欧氏j o r d a n 代数 以下的定义，性质及结论均选自陆a u t 与k o r 锄i 的专著n 1 ，有关欧氏j o r d a l l 代数更为 深入的讨论可以参考【1 ，5 0 - 5 2 及其参考文献 定义1 8 1 令f 为实数域或者复数域，v 是f 上一有限维向量空间定义从vxv 到v 的双 线性映射( z ，影) 一2 y ，则称a ：= ( v ，) 是一代数 对于给定的z v ，记c ( z ) ：v _ v 是v 上的线性算子，满足vy v ，c ( z ) ( ) = z y 定义1 9 如果代数a 满足，对vz ，y v ， 1 z 。y = y z 。 2 z ( z 2 y ) = z 2 ( z 可) ，其中z 2 = z z ， 则称a = ( v ，) 是一j o r d 锄代数，记z 可为z 和秒的j o r d a i l 积 一般来说，j o r d a n 代数不一定满足结合律，也就是说，vz ，y ，z v ，z ( y z ) = y ) z 不一定成立但是，j o r d a n 代数满足幂结合律，即护护= z p + q 对- - t ：j o r d a n 代, 1 0 大连理工火学障士学位论文 数a = ( v ，)