（计算数学专业论文）半定规划问题的两种数值解法.pdf

a b s t r a c t o p t i m a l i t v c o n d i t i o n sa n dn u m e r i c a l m e t h o d so fn o n l i n e a r s e m i d e f i n i t e p r o g r a m m i n gw e r es t u d i e di nt h i sp a p e r w h i c hi n c l u d e dt h ef o l l o w i n gt h r e ep a n s t h ef i r s tc h a p t e rd e s c r i b e dt h eb a s i ck n o w l e d g eo fs e m i d e f i n i t ep r o g r a m m i n g ， o u t l i n e do p t i m a l i t yc o n d i t i o n s ，w h i c hw e r ep r e p a r e df o rt h el a g r a n g em e t h o di nt h en e x t c h a p t e r ，a n do nt h i sb a s i s ，w ed e r i v e do p t i m a l i t yc o n d i t i o n sf o ra c l a s so fn o n - s m o o t h s e m i d e f i n i t ep r o g r a m m i n gp r o b l e mw i t he q u a lc o n s t r m n t s i nt h es e c o n dc h a p t e r ，an o n l i n e a rl a g r a n g ef u n c t i o nf o rg e n e r a ln o n c o n v e x s e m i d e f i n i t ep r o g r a m m i n gw a sg i v e n w ea n a l y z e dt h ec h a r a c t e r i s t i co ft h i sl a g r a n g e f u n c t i o no nt h ek k tp o i n t u n d e rs o m ec o n d i t i o n s ，t h el o c a lc o n v e r g e n c eo ft h em e t h o d b a s e do nt h i sf u n c t i o nw a sp r o v e dt h a tt h e r ee x i s t sat h r e s h o l do ft h ep e n a l t yp a r a m e t e r s u c ht h a tt h es e q u e n c ep r o d u c t so ft h ea l g o r i t h ml o c a l l yc o n v e r g e t ot h ek k t p o i n tw h e n t h ep e n a l t yp a r a m e t e ri sm o r et h a nt h et h r e s h o l d b e s i d e s ，t h ee r r o rb o u n d o ft h es o l u t i o n s w i t ht h ep e n a l t yp a r a m e t e rw a se s t i m a t e d n u m e r i c a le x a m p l e sa l s od e m o n s t r a t e dt h e e x e c u t i o na n de f f e c t i v e n e s s i nt h et h i r dc h a p t e r , a na n a l y t i cc e n t e rc u t t i n gp l a n em e t h o dw a sg i v e nf o rs o l v i n g t h e1 扣髫e s c a l es e m i d e f i n i t ep r o g r a m m i n g t h ec o n v e r g e n c eo ft h i sm e t h o dw a sp r o v e d ， a n de v e n t u a l l yt h ep r a c t i c a le x a m p l ew a sr e p o r t e d k e yw o r d s ：s e m i d e f i n i t ep r o g r a m m i n g ；o p t i m a l i t yc o n d i t i o n s ；l a g r a n g em e t h o d ； a n a l y t i cc e n t e r ；c u t t i n gp l a n e 目录 弓i 言l 第一章最优性条件”4 1 1 基础知识4 1 2 一类非光滑半定规划问题的最优性条件6 第二章一个非线性l a g r a n g e 乘子法。1 4 2 1 非凸半定规划问题1 4 2 2 非线性l a g r a n g e 函数及其性质。l 5 2 3 基于非线性l a g r a n g e 函数的乘子法及其收敛性1 7 2 4 数值计算实例2 3 第三章半定规划问题的解析中心割平面法2 5 3 1 半定规划问题的转化“2 5 3 2 解析中心割平面算法及收敛性2 7 3 3 数值结果2 9 结论3 1 参考文献3 2 攻读学位期间的研究成果3 5 致 射”3 6 学位论文独创性声明、学位论文知识产权权属声明一3 7 引言 引言 半定规划是半j 下定矩阵上的线性规划。近二十年来半定规划的理论和算法取得 了很大的进展，广泛应用于组合优化，系统工程和电子工程等领域，它已逐渐成为 数学规划领域中一个非常活跃的研究方向。 2 0 世纪6 0 年代，由r b e l l m a n 和k f a n ”1 构造了一个半定规划问题，他们考虑将 线性规划中的向量变量用矩阵变量代替，并且给出了对偶理论以及强对偶理论成立 的一个j 下则条件。2 0 世纪7 0 年代初，d o n a t h 和h o f f m a n ，c u l l u m * h w o l f e 把一些难的 图分割问题转化为一个特征值优化问题求解，而这个问题的求解又可以转化为半定 规划问题。二十多年里半定规划问题一直没有受到关注，主要是由于半定规划的可 行集不再是多面体，并且没有适用的单纯形法。内点法问世以后，对半定规划领域 的研究才逐渐火爆起来，使得半定规划获得了飞速的发展。1 9 9 2 年，n e s t e r o v ， n e m i r o v s k y ，a 1 i z a d e h 与k a m a t h ，k a r m a r k a r 独立的把l p 的内点法推广到半定规划， 使内点法成为求解半定规划问题的主要算法。 半定规划问题的标准形式是 r a i nc x s t 肚= b x 0 其中表示玎刀对称矩阵集合。熨表示以，z 半正定矩阵集合。x 0 表示x 掣。 c x 表示t r ( c r x ) 。月是s ”专尺的线性映射，可以认为月是由后个线性函数构成 的，约束魁= b 等价于后个线性约束乃- x = 6 f ，f = 1 ，j j 近些年来国内外对于半定规划的研究主要集中在线性半定规划的研究上，上个 世纪末本世纪初，半定规划问题的研究又被推广到非线性半定规划问题上，即线性 或非线性目标函数受到( 非线性) 矩阵不等式和( 或) 向量不等式约束的优化问题 r a i n f ( 曲 s t h ( x ) 0 且办( x ) = 0 ( 1 ) 其中f ：r ”j r ，日：r ”专畔( 掣是由l r l m 的半定矩阵组成的空间) 和h ：r ”一r p 青岛人学硕十学位论文 这种半定规划问题主要来自最优结构设计、最优鲁棒控制、鲁棒反馈控制设计等领 域，由于线性半定规划不能给出满意模型的优化问题而且非线性半定规划才刚刚起 步，它的发展还很不成熟，因此研究求解非线性半定规划的算法无疑是有重要意义 的。s h a p i r o1 4 通过锥的性质给出了非线性半定规划一阶和二阶最优性条件， f o r s g r e n i 1 采用非线性规划的最优性条件分析的技巧也讨论了非线性半定规划的最 优性条件。无论在线性规划中还是在非线性规划中，罚函数法和对数函数法对算法 的研究起着重要的作用。m o s h e y e v ，z i b u l e v s k y 提出了一类惩罚障碍乘子方法用于 求解约束为线性矩阵不等式的非线性半定规划问题。b u r e r ，m o n t e i r o ，z h a n g 考虑 将一类特殊的半定规划转化为非线性规划进行求解。j a r r e ，r i n g e r t z 采用障碍方法 求解非线性半定规划。然而，障碍方法要求迭代初始点是严格可行的内点，这一要 求在实际中往往很难满足。为克服上述方法的不足，h e s t e n s 与p o w e u 各自独立提出 了近似增广l a g r a n g e 函数，来求解具有等式约束的非线性优化问题，最初的乘子法 是基于二次增广l a g r a n g e 函数建立的，这一方法的优点在于克服了早期罚函数的病 态问题以及收敛速度慢等弱点。后来g l a d 研究了对增广l a g r a n g e 函数中的l a g r a n g e 乘子的不同的更新方法的收敛性质。b o g g s & t o n e ( 1 9 8 0 ) 引入了一类新的乘子法，发 展了对偶理论，构造了一类新的惩罚函数并建立了精确罚函数和乘子法的联系。随 着将增广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 算法主要研究由标准半定规划问题转化而来的半定规划问题( 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 函数是 三( x ，u ，矿) = f ( x ) - 4 - 此l a g r a n g e 函数提供了一种从约束优化问题到无约束问题求稳定点的转换，它是 刻画最优化特征以及构造最优化算法的基本工具。 半定规划的一个增广l a g r a n g e 函数为 l t ( x , u , v , t m 刮f i , ( u - 半，0 2 - - m 2 k 哪 + 譬 实际生活中遇到的半定规划问题大多数是非线性的，包括非光滑半定规划，非 引肓 凸半定规划等，本文研究非线性半定规划的一些数值方法。在第一章，我们探讨了 一类非光滑半定规划的最优性条件。第二章，在满足非凸半定规划最优性条件的基 础上，我们给出了一般形式的非线性l a g r a n g e 函数，讨论了函数在k k t 点的性质， 给出了非线性l a g r a n g e 算法，在适当的条件下，证明了当罚参数大于某一阈值时， 算法具有局部收敛性，并给出了与罚参数相关的解的误差估计。数值算例验证了算 法的可行性和有效性。第三章将标准形式的半定规划问题进行转化，给出了可以用 于求解较大规模半定规划问题的解析中心割平面算法，证明了算法的收敛性，实际 算例表明了算法的有效性。 本文中常用到的符号如下： 矩阵a 0 表示a 是一个半正定矩阵。令r 帆”表示m x 以的矩阵构成的空间。对于向 量口，b r ”，我们定义内积 = a r b ，对于矩阵么，b r ，内积为 = a b = v e c ( b ) 7 v e c ( a ) = 驴( a ) ，( 其中v e c ( a ) 表示由a 的列向量组成的 行2 l 的向量，护( 彳) 代表矩阵彳的迹) ，本文中相应的向量范数取2 范数，矩阵范数 取f 范数。符号。表示矩阵的克罗内克积a o b = q l ba 1 2 b a l b 嘭1 b 吃2 b a 2 。b l b 2 b 。b ，它是一 个刀2 疗2 矩阵。符号v ，厂( x ) 表示( x ) 在x 处的梯度，而v 2 j ( x ) = v ，( v ，厂( x ) ) v ，乃( x ) 表示h ( x ) 在x 处的梯度，v 。曩( x ) 表示其第i 行。其中只( x ) = 胡( x ) o x , 是m m 的偏 微分矩阵。我们由此定义m 2 f 的矩阵讲( x ) 锄：= v e c ( h l ( x ) ) ，v e c ( 乜( x ) ) 】 3 第一章最优性条件 1 1 基础知识 第一章最优性条件弟一早取1 兀。l f 土余仟 目前许多专家和学者正致力于非线性半定规划( n l s d p ) 的研究，尤其是对于 大规模( n l s d p ) 的研究，讨论了其最优性条件。相关学者对非凸半定规划【1 1 和非 光滑半定规划1 3 1 的最优性条件作出了突出贡献，本章对已有理论进行推广，证明了 带有等式约束和不等式约束的一类非光滑半定规划问题的最优性条件。 我们考虑下面的半定规划问题 m i n f ( x ) s t 日( x ) 0 且办( x ) = 0 ( 2 ) 其中h ：r ”一贮( s 7 是由m m 的半定矩阵组成的空间) 和h ：r ”一只尸，且它们是 二次可微的。f ：r ”专r ，是连续可微的，并且v ，f ( x ) 是局部l i p s c h i t z 的。 定义1 1 3 1 设f ( x ) 是连续可微函数，如果存在三使得 l i m 。2f ( x + t d ) - f ( x ) ，- t ：l ， 则称三为f ( x ) 在x 关于方向d 的二阶p e a n o 导数，记为( x ；d ) 上下p e a n o 导数分别定义为 驰炉l i 毋渺2 坐堕逊半盥业， 刀( 圳f ) - l i m s u p 2f ( x + t d ) - f ( x ) ：- t t 4 0z 设问题( 2 ) 的可行点为x ，即h ( x + ) o 且办 ) = 0 ，定义m xm 阶正交矩阵q ， q = ( g ，q ) 其中g 的列向量形成h ( x + ) 列生成空间的一组基，q 的列向量构成 h ( x + ) 零空间的一组基。矩阵q 依赖于点x ，q 不一定唯一。 设，分别是矩阵q 与0 2 的列向量的维数，s ”为m xm 阶对称矩阵空间。 定义集合i l l s ( a ，x ) = m ：m s ”，= 0 如果j 占 0 ，对于使( x ) = 0 的任意x ，有 4 青岛人学硕十学位论文 i x - - x + 0 。对称矩阵疗( x ) 定义为 疗( x ) = 日( x ) 一h ( x ) q l ( q r h ( x ) q i ) 一q f h h ( x ) ， 则疗( x ) 为局部可行矩阵。下面给出疗( x ) 的相关性质。 引理1 1 如果a 和曰是半正定对称矩阵，则a b 有实的非负特征值。特别地， 有t r ( a b ) 0 引理1 2 【1 1 设h ( x ) 0 成立，则b ( x ) = 0 ，对于充分接近x 且满足 骈h ( x ) q 0 的点x ，有舛疗( x ) = 0 ；i t ( x ) 0 当且仅当日( x ) 0 引理1 3 i q 设h ( x ) 0 成立，则下面关系式成立 疗( x + ) q 1 ：0 ；醒掣盟q 2 ：醇翌盟鲮，扛1 ，2 ，刀 o x ,o x , 引理1 4 设日( x ) o 成立，则矩阵鹾掣q ，f ：l ，2 ，刀生成空间 9 t m q z ：m s ( 疗，x ) ，当且仅当矩阵掣，待1 ，2 ，刀生成 q 醇坞醇：m s ( b ，x ) ) 由上面疗( x ) 的性质可知，在x + 的某个邻域内，问题( 2 ) 等价于下面问题 m i n 厂( x ) s j 疗( x ) 0 办( x ) = 0 设x 是问题( 2 ) 的可行点，对于充分接近x + 且满足讲日( x ) q 0 的点工定义 局部半定l a g r a n g e 函数： 三( x ，u ，y ) ：厂( x ) 一 + 5 第一章最优性条件 1 2 一类非光滑半定规划问题的最优性条件 为引出最优性条件，先给出以下定义和定理： 定义1 2 1 3 1 满足h ( x ) 0 的点x + 被称为一个正则点，如果 ( a ) 矩阵醇型鍪尘q 2 ，f - 1 ，2 ，挖，生成空问 醇吆：m s ( 疗，x ) ) 吸j ( b ) 科惚：m s ( 膏，x ) ) 中存在一个正定矩阵。 定义1 3 t 3 1 问题( 2 ) 的一个可行点x r ”称为稳定点或k k t 点，如果存在 u + s 7 ，v + r ，使得在点( x ，u + ，矿+ ) 处满足下面条件： ( a ) 掣圳掣巾崩x ) ) v ，川，儿 l fl ， ( b ) u h ( x ) = 0 ，u 0 定理1 1i l l 设x 是问题( 2 ) 的一个正则点和局部极小点，则存在矩阵 u q 饼鳞：u b ( 疗，x ) ) ，v r 尸使得 掣= t r ( o h ( x ) u + ) 一( v ，囊( x ) ) v ，汪1 ，儿 l ，w ， u h ( x 1 = 0 ，u + 0 下面给出此类非光滑半定规划的一阶最优性条件： 定理1 2 假设x r ”是问题( 2 ) 的一个可行点，存在矩阵u + q 鲤踢醒： u b ( b ，x ) ) ，v r p 满足 掣= t r ( 掣一( v x h ( x 矿v ，刀； l 珥fc 珥， u h ( x 、) = 0 ，u 0 而且曩，( x ) 是凹函数，i = 1 ，聆，j - - - 1 ，z ( 毫，j ( x ) 代表矩阵膏( x ) 的元素) ， 办( x ) 是凸函数，那么，是问题( 2 ) 的一个局部极小点。 证明由条件知局部半定l a g r a n g e 函数 l ( x ，u ，v ) = ( x ) 一 + 是凸函数，由次微分的定义知 o 比( x ，u ，v ) ，零向量是函数l ( x ，u ，y ) 在点( x ，u + ，v ) 处的次梯度，因此任给 可行点y ，有 6 青岛人学硕十学位论文 l ( y ，u + ，v ) 2 ( x + ，u ，v + ) + ，即 f ( y ) - + f ( x + ) 一 + + 因为x + 满足h ( x ) 0 ，h ( x ) = 0 ，由引理1 2 知f l ( x ) = 0 由y 的可行性知 f f l ( y ) 0 ，办( j ，) = 0 ，由引理1 1 知 0 因此对于任意可行点y ，下面 不等式成立 厂( y ) f ( x ) 从而可知x 是问题( 2 ) 的一个局部极小点。 为引出二阶最优性条件先给出一个引理： 引理1 5 1 设d r ”，g 是从r ”到s ”的二次连续函数。q 是研m 阶j 下交矩阵， 分块形式为q = ( q ，q ) 。如果点x + 的某邻域中的点满足，g ( x ) q o = 0 ，并且如果 m x m 阶矩阵诒( x ) o x , ，i = l ，胛生成空间 q g t 场场1 ：m s ( g ，x + ) ) ，则存在 占 0 以及一个二次可微连续函数x ( ，) ，v t ( 一占，s ) 满足 石( o ) = z ，石( o ) = d 且g ( x ( ，) ) = g ( 石) + d 。( o g ( x ) l o x , ) t 引理1 6 n 1 设g 是从尺”到s ”的二次连续函数，假设x ，d 和f 满足g ( x ) = 0 ， g ( x + f d ) o ，f o ，ld k | i = 1 ，! 觋f = o ，! i m d 。= d + ，则有 主掣匆狐 乞瓠；j 定理1 3 设x 是问题( 2 ) 的一个正则点和局部极小点，则存在矩阵 u 0 2 讲v 0 2 醇：u 曰( 疗，x ) ) ，v r 尸，满足下列关系式： 掣= t r ( 掣巾胤x + ) ) 7 v ，丹； u h ( x ) = 0 ，u 0 且v 川圳”：喜埘警q 2 _ o ，( v 姒x ) ) o ) 都有 互：( z + ，u + ，v ；d ) 0 证明 定理1 1 知存在矩阵u + 0 2 9 崛讲：u b ( 疗，x ) ) ，v r p ，满 7 第一章最优性条什 掣嘲( 掣叩朋x ) ) y ，川 苏、叙。 7 、一、“ 7。 u h ( x ) = 0 ，u 0 现假设d r ”满足： 喜醇警q 2 删巾以x ) ) = o 根据引理1 3 有，疗( x + ) q l ：o ；磋1 掣q ：饼堂堕鲮，江l ，2 ，z o x ,o x ； 矿掣州删百o f t ( x ) ( q l ，0 2 ) 趔攀o x , 喇警q 2 卿i出i 一 撕 因此上式等价于髟t = l 掣鳓- 0 ，又由于q 为正贿嗉警删 因为x 是个j 下则点，由引理1 5 知，存在s 0 以及一个二次可微连续函数x ( f ) ， 其中x ( 。) = x ， 一( 。) = d ，且对于f ( 一s ，) 有疗( x ( 嘞= 疗( x ) + 窆i = | 盟o x i d j 忙。， 厅( z ( 嘞= 办( x ) + 喜v ，曩( x ) 谚f = ( v x h ( x ) ) 7 功= 。设g ( ，) = 厂( x ( 呦，因为x + 是局部极 小点，所以有 g ( 0 ) = v f ( x ) 7 d = 0 ， 鲜( o ；d ) - l i m m i n f2 g ( o + t d ) - g ( o 厂) - t 由p e a n o 导数 = 易( x ；d ) + 夥( x ) 7 ，( 0 ) 鲜( o ；1 ) - l i 毋矿2 塑坐号兰坚峻 ：l i mi n f 2 f ( x ( t ) ) - f ( x * ) = - t v f ( x ) r x 一( o ) ，o t ：l i m i n f 2f ( x + + x ( t ) - x ) - f ( x ，) - t ，0 ，2 8 青岛人学硕十学位论文 ；一 “嘧f ( 2 巡业塑丝孚型避+ ， 盟竺! 型! 二兰业2 二丛兰! q ! 丛q 婆 鬈( x ( o ) ；x ( 0 ) ) + l i r a 川i n f ( 2f ( x ( o ) + 础o ) + 罢以劲一m ( 。型 = g ( x ( o ) ；x ( o ) ) + l i m m i n f 2 上t - - v f ( 7 一 x ( 7 7 ) ) 7 x ”( 善) = 易( x ( o ) ；x ( o ) ) + w ( x ( o ) ) r ，( o ) ， 其中 x ( 刁) ( x ( 。) + 反，( o ) ，x ( 。) + ( 。) + i t 2 ，( 跏孝( f 、l0 时，孝山0 ，x ( 7 7 ) 争x ( 0 ) 同理，鲜( o ；一1 ) 墨( x ( o ) ；一( o ) ) + 夥( x ( o ) ) r ，( o ) ，因此有 鲜( o ；d ) = 职x ；d ) + 夥( x ) 7 x ( o ) o 又由于，对于r ( 一占，s ) 有日( x ( f ) ) = 0 ，凼此 塑盟q ! ! ：o ，一d 2 q ( x ( o ) ) ：o d t d t 即一d 2 f f l ( x ( o ) ) = 势掣+ 芸警= 。 带入u 得，护( 翌掣u + ) = 杰1 = 1 蜘j = l ( 鬻哆+ 嘉护( 警邶) - 0 由乃( x ( 嘞= o ，得望铲= o ，d 2 矿h ( x ( o ) ) = o 带入y 得，讲口l d 7 ( j 。 y 7 ) v ，( v e e v ，厅( x ) ) d + y 7 1 v 。h ( x ) x ”( o ) = 0 9 ( 1 2 ) ( 1 3 ) 第一章最优性条什 由( 1 1 ) ，( 1 2 ) 和( 1 3 ) 式得： 舭m 耵f n 仰) 一喜扣( 鬻吒一骞护( 掣羽) 一d 7 ( lo v * r ) v ，( v e c v ，厅( x ) ) d v ”v ，h ( x ) x ”( o ) 0 由p e a n o 导数定义可得 跏删娜啊 即) 一喜驴( 警羽) + v * r v h ( x 矿( 0 ) ) = l 。p ( x , u , v * ；d ) + 窆j = l ( 等却( 警+ v r v x 删们) 0 因为钞( x ) 叙，：护( 型挚垒u ) 一( v ，厅，( x ) ) r y ，歹：l ，刀，故 。 o x 。 髟( x ，u ，v ；d ) o 定理1 4 设x + 是问题( 2 ) 的一个正则点和k k t 点，即存在矩阵 u 。 q q ；吆鳞：u b ( f i ，x + ) ，v r p ，使得 u + h ( x + ) ：o ，u + o 和可( x ) o x , ：u + 皇宅姜! ! 一( v 。矗( x + ) ) r 矿，f ：1 ，刀 且对于任意的 d 彤，d 0 喜z q r 望墓竽q 2 = 。且( v 。办( x ) ) 7 d = 。) ，有 2 ( x + ，u + ，v ；d ) 0 ，贝, l j x 是问题( 2 ) 的严格局部极小点。 证明假设定理条件成立，n x 并不是局部极小点，则存在一点列 ) ，对于 v k 有矿x ，! i m ，。x 。= x ，且满足日( ) o ，h ( x ) = o 但厂( ) 厂( x ) ，令 扩2 网x k - - x * ，记矿= z 删，则对于每个七都蚓矿l i = 1 ，。一l i m ，= 。 由于每个d 都包含于一个紧集，不失一般性，可以假设对于d 。r ”，有l i m d 。= d + 正 由h ( x ) 0 ，根据引理1 2 ，当k 充分大时，有疗( ) 0 。由u 存在性，表明 t r ( r i ( x ) u ) 0 1 0 青岛人学硕十学位论文 对于仕蒽k ，足义幽数纯( ，) = t r ( h ( x 。+ 耐“) u 。) ，有纸( 0 ) = 0 ，识( ，。) 0 微分得： 群( ，) = 喜护( 学【，) 矿 啪) = 喜喜咖( 掣 当，= o 时，因为u h ( x ) = o 所以u 为h ( x ) 的零空问中的矩阵。又因为q 为 h ( x + ) 的列生成空间中的基，因此群u = 0 ，则 椰) = 喜护百o f i ( x ) 矽= 兰j = l 护( 警彬- o ， 当t = ，时， 吼( f ) ：f k 魄t ( o ) + 掣k2 群( ，。) o ，矿( o ，1 ) f ( x + t k d t ) 一厂( x ) = t k v ，( x ) v + 华墨( z + + 孝k t k d t ) o ，尹( o ，1 ) 因为h ( x 。) = 0 ，有h ( x + ，d ) = h ( x + ，d 。) 一h ( x ) ：f 。v ，厅( x ) d 。+ 垒妥蔓( d ) z v ，2 办( x + + f * t k d 。) d t ：o ，f 。( o ，1 ) 结合以上式子得，当k 充分大时： r 奢警叫警吧驰y n 露 + 华g ( x + f t t k d k ；d k ) + 华( 妁r v x 2 h ( 石煳t 一喜扣c 学徊 由u ，v + 的性质，上式右边第一个式子为0 ，则可得 华g ( x 心卜华( n r v ，：蛳+ 乳锗) 一窆t = l 兰j = l 狲警删 令k - - 0 0 ，则 l 。a x , u 。，v ；d ) 0 ( 1 4 ) 第一章最优性条件 当f 。一o ，纯( ，) 0 ，贝, l j l i m 。i n f 僦( o ) o 因为一y + 所以有， l i m ( p ；( o ) = 新警蛐 ( 1 5 ) 因为h ( x + ，d ) = 0 ，y 专y 得 慨耐) 7 d + ( t z k ) 2 d r v2 h ( x 灯) d = 。，所以v x h ( x ) 7 d + = 。 此外，已知x + 是k k t 点，贝i j 棚) = 和挚m 叱m + ) r d k _ v x h ( x * ) 7 以 所以，我们有j i m 科( 0 ) 0 ， 片，v o 结合( 1 5 ) 式有 由引理1 3 ， l i mc , o , ：= 势挚一o 州窆j = lc 驰v j m c 喜挚o h ( x ) = 窆j = l 驴c 挚一o 由引理1 6 得 因为u 0 ，则 再由引理1 3 得， 喜警狐 ；l”， 喜挚夸。 j = 1w ， 姜挚夸。， 从而有，矿1 2 喜型墓1 胆巧0 因为此矩阵是对称半正定矩阵，且 桫胆喜掣叫( 喜( 掣阶。， 因此有 矿nv 2 挚即巧一o ，：lc ， q 的列构成h ( x ) 零空间的一组基，且u 和u 讹l 的生成空间相同，因此a 的 1 2 青岛人学硕十学位论文 列的生成空问与u 1 2 的列的生成空间相同。因此兰g 型癸；运彳：o ，由( 1 4 ) ，= ll “ 式可知与题设矛盾，则x 是问题( 2 ) 的严格局部极小点。 本章讨论了类含有有等式约束和不等式约束的非光滑半定规化问题把现存 的结果扩展到约束是结构稀疏矩阵的情况，证明了一类含等式约束的非光滑半划问 题的一阶必要性条件和二阶的充分性和必要性条件。 1 3 第二二章一个1 卜线性l a g r a n g e 乘子法 第二章一个非线性l a g r a n g e 乘子法 2 1 非凸半定规划问题 本章讨论一般非凸半定规划问题 ( n c s d p ) m i n 厂( x ) s t 日( x ) 0 且办( x ) = 0 ( 3 ) 其中f ：r ”hr ，h ：r ”i - - - ) 贮( s 7 是由m xm 的半定矩阵组成的空间) ，h ：r ”hr ， 且它们是二次可微的，这罩不要求f ( x ) 是凸函数。 本章将求解非线性规划问题的非线性l a g r a n g e 方法推广到解决非凸半定规划 中去，给出一个非线性l a g r a n g e 函数来求解非凸半定规划。 设非凸半定规划问题( 3 ) 的l a g r a n g e 函数为 l ( x ，u ，矿) = f ( x ) - + ， ( x ，矿，y ) 为问题( 3 ) 的k k t 点，即满足 掣圳( 掣) 巾烈x ) ) v ，咒 l fc ， u + h ( x ) = 0 ，u 0 在下面的讨论中要用到下列假设条件1 2 0 l ( a ) 严格互补条件成立：即r a n k ( h ( x + ) ) = ，r a n k ( u + ) = m r ( b ) 二阶充分条件成立： 对删础附) _ 悱驯喜z e r 警e = 咀( v 崩x ) ) 饥0 ) ， 有下面不等式成立 d r v 2 l ( x , u ，v ) d + d7 j ( x ，u ) d 0 其中e r ”，其m 一，个列向量构成h ( x ) 零空l 日j 的一组标准正交基， j ( x ，u ) = ( j o ) = 2 ( 解( x ) a x ) 7 ( u o 【日( x ) 】一) ( 讲( x ) 融) ， 以：2 u a l l ( x ) h ( x ) 】- l _ a n ( x ) ，f ，j ：1 ，刀 。 o x , o x ； ( c ) a ( x ) 在x + 处是l i p s c h i t z 的，即存在占 0 及盯 0 ，对于任意 青岛人学硕十学位论文 x b ( x ，占) = x 川x - - x * 0 e , x e r ”) ，都有l i h ( x ) 一h ( x ) i l o 下面讨论f ( x ，u ，v ，) 的一些性质。 引理2 11 3 0 l 设( x ，u + ，v ) 为问题( 3 ) 的k k t 点，则存在m xm 标准讵交阵 q = c e ，f ，满足日c x ，= q ( 三三) q 7 且u = q ( 言：) 9 7 ， 其中a = d i a g ( a , ) r r , r ，q 0 ，i = l ，厂；b = d i a g ( o j ) r t n - r t l f l - 7 ，a j 0 ，= 1 ，竹一， 由q 一= q 7 1 得e e 7 + 阿7 = 厶，且h ( x + ) = f a f 7 ，u = e b e 7 引埋2 21 7 1 令d r ，是对称矩阵，w r 切，t = d i a g ( t ，) r “，其中 t 0 ，i = 1 ，z ，若由w y = 0 可得y 7 d y 0 ，则存在风 0 ，使得对于即 ， d + p w 7 研是j 下定矩阵。 定理2 1 设m ( x ，u ，v ，f ) = u e 一嘲7 圩。( ，+ ，2 日( x ) 2 ) ，n ( x ，u ，v ，f ) = v + t h ( x ) ， 若( x ，u ，v + ) 为问题( 3 ) 的k k t 点，则有 m ( x + ，u ，y + ，t ) = u ( x 。，u ，矿，) = v v t 0 证明由引理2 1 可得 m ( x ，u ，y ，f ) = u e 删“坍。( ，+ f 2 h ( x ) 2 ) 一1 b 钮i o b = p l 。l o q 丁q ( 名7 罟 q 7 c q ( 名7 兰) q 7 1 ，。1 旧瓢7 跏r 珂 这罩召= d i a g ( e 一棚嘲，) s 7 ，0 = d i a g ( 1 + t 2 e ( x + ) 2 ) s 7 ，f h fh ( x ) = 0 ，从而有 ( x + ，u ，矿，) = v + + t h ( x ) = v 1 5 第二章一个1 r 线性l a g r a n g e 乘子法 定理2 2 若( x + ，u ，v ) 为问题( 3 ) 的k k t 点，则 f ( x ，u + ，y ，) = ( x + ，u ，v + ) = f ( x ) 证明瞰，旷吒，) _ m ) + 删。巧w ) ) ) + + 扣x ) j 1 2 冈为u h ( x ) = 0 ，所以u ( ，一e 一删卸州。) = 0 ，再由h ( x 。) = 0 可知 ，( x ，u + ，y ，) = ( x + ，u ，v ) = f ( x ) 定理2 3 若( z ，u ，v ) 为问题( 3 ) 的k k t 点，则 v ，f ( x + ，u + ，矿，f ) = 0 ，v t 0 证明 v 。f ( x ，u ，v ，t ) = v x f ( z ) 一肛( v ，( u e 一咖脚“) ) + f ( v ，办( x ) ) 7 办( x ) + ( v ，办( x ) ) 7 v = v ，f ( x ) - ( o h ( x ) o x ) 7 v e c ( m ( x ，u ，v ，) ) + ( v ，办( x ) ) 7 1n ( x ，u ，v ，f ) 由l ( x ，u ，y ) 的定义得，v ，l ( x ，u ，y ) = v 。厂( x ) 一( o h ( x ) o x ) 7 v e c ( u ) + ( v ，乃( x ) ) r v 因此，v ，f ( x + ，u ，v i i9 f ) = v ，f ( x + ) - ( o h ( x + ) o x ) r v e c ( m ( x * , 【，矿。，) ) + ( v 。h ( x ) ) 7 ，u 。，y + ，) = v ，f ( x ) - ( o h ( x ) o x ) r v e c ( u ) + ( v ，h ( x ) ) 7 v = v ，三( ) r + ，u + ，v ) = 0 定理2 4 如果条件( a ) 一( c ) 成立，则存在，o 0 ，当f t o 时，v 2 f ( x , u ，v i i9 f ) 是 严格正定的。 证明0 2 f ( x ，u ，v ，t ) 苏, o x j ：职x ) 一m ( 五u ，y ，) 弋0 2 h ( x ) ，) + ，f r ( 掣m ( 墨u ，y ，) 掣) 钡i o x i0 o x j + ( v ，( v ，忽( x ) ) ) r n ( x ，u ，v ，f ) + f ( v ，红( x ) ) ，v 。办，( x ) ，f ，j = l ，胛 贝0v ：f ( x ，u ，v ，f ) = v 2 x f ( x ) 一( 厶o ( v e c m ( x ，u ，v ，f ) ) r ) v ，v e c ( o h ( x ) o x ) + ( 厶 n ( x ，u ，v ，f ) 7 ) v ，v e c ( v ，办( x ) ) + f ( v ，办( x ) ) 7 v ，办( x ) + t ( o h ( x ) o x ) 7 1 ( ( m ( x ，u ，v ，f ) ( ，+ ，2 何( x ) 2 ) 一( ，+ 2 日( 石) ) 7 o l ) ( a 日( x ) a 力 由l ( x ，u ，y ) 的定义得 1 6 青岛人学硕一卜学位论文 v ：t ( x ，u ，y ) = v ：( x ) 一( 厶圆( v e cu ) 7 ) v ，v e c ( o h ( x ) o x )