（应用数学专业论文）线性二次半定规划问题若干研究.pdf

福建师范大学康志林硕士学位论文 记号与约定 尼n ，尺似n ，r + + ：分别表示m 维欧氏空间，n 阶实矩阵构成的集合，全体正实数 s ”：礼x 钆阶实对称矩阵空间 s ( n l ，) ：分块对角矩阵空间且各分块的维数为n l i 一， 咒：半正定矩阵锥 k o ：锥k 的极锥 z , j ：矩阵x 上的( i ，j ) 元素 x t ：矩阵x 的转置 x ，x t ：分别表示矩阵x 的逆矩阵，m o o r e p e n r o s e 广义逆 x 三o ( x - 0 ) ：矩阵x 是半正定( 正定) 的 x 考， x ：半正定矩阵x 的对称方根 v e c ( x ) ：死阶矩阵x 的列叠成的n 2 维列向量 m a t ：v e c 的逆算子，表示舻维列向量排成n 阶矩阵 i | x 怯：矩阵x 肝舰的f r o b e n i u s 范数 e ：舒中的n 维向量，且e = ( 1 ，1 ) t ：铲中的标准内积 圆：标准k r o n e c k e r 积 t r ( x ) ，r a n k ( x ) ：矩阵x s “的迹，矩阵x 的秩 4 ：s ”到胛上的线性算子，且4 x = 【a i x ，a 。x ra i 为给定对称阵 a + ：线性算子4 的伴随算子，且有y = y i a i 厶，：n 阶单位矩阵 d i a g ( x 1 ，z n ) ：对角元为x 1 ，的n 阶对角矩阵 d i a g ( x ) ：矩阵x 对角元构成的n 维向量 a 。嚣( x ) ：矩阵义的最大特征值。 a ( x ) ：矩阵x 实特征值组成的向量即a ( x ) = ( a 1 ，a n ) r c = m a x a ，6 ) ：c 中第i 个分量c i = m a x a i ，执】- ，其中a ，b 是肝中礼维向量 a r gm i n f ( z ) ：o x ) ：y ( z ) 在x 上的最小值解集 v ，( z ) ：1 ( 2 7 ) 在点z 的梯度 + 。：正无穷大 i n t s ，r i s ，o s ：分别是集合s 的内部，相对内部和边界 ：定理或命题证毕，例子求解完毕 v i 福建师范大学学位论文使用授权声明 本人( 姓名)康志林 学号 至q q 墨鱼曼q 专业应用数学所呈交的论文( 论文题 目：线性二次半定规划问题若干研究) 是我个人在导师指导下 进行的研究工作及取得的研究成果尽我所知，除了文中特别加以标注 和致谢的地方外，论文中不包含其他人已经发表或撰写过的研究成果 本人了解福建师范大学有关保留、使用学位论文的规定，即：学校有权 保留送交的学位论文并允许论文被查阅和借阅；学校可以公布论文的全 部或部分内容；学校可以采用影印、缩印或其他复制手段保存论文 ( 保密的论文在解密后应遵守此规定) 学位论文作者签名婢指导教师签名一 签名日期 福建师范大学康志林硕士学位论文 摘要 本文主要探讨线性二次半定规划问题( l - q s d p ) 的结构特征及其求解算法，主 要由三部分组成第一部分，先讨论线性二次半定规划问题的对偶性理论及其最优 性条件，进而讨论该规划问题的原始对偶内点算法。给出了基于? 搜索方向唯一 性的证明数值试验上，对礼= 3 的情况，给出具体算例，并在m a t l a b7 。0 1 上进 行数值模拟，验证了算法的可行性同时，进一步探讨了该二次半定规划与半定最小 二乘问题的联系，给出了在一定条件下它们之间的转换关系第二部分，拓广了半定 最小二乘问题模型( s d l s ) 的定义，提出了变量有界半定最小二乘问题( b v - s d l s ) ， 同时给出了任意实对称矩阵在由有界约束矩阵变量构成的闭凸集上的精确投影表示 式，并在此投影基础上，探讨了该( b v s d l s ) 的求解算法，即投影拟牛顿算法，给 出了其算法框架最后在m a t l a b7 0 1 上进行数值试验，并与原始对偶内点算法 比较，进一步说明算法的可行性及有效性第三部分，进一步考虑( b v - s d l s ) 模 型的拓广形式，探讨了一些特殊情形以及施加某种限制下的投影显式，并考虑它相 应的求解算法 关键词：二次半定规划半定最小二乘内点算法 变量有界投影拟牛顿 算法 福建师范大学康志林硕士学位论文 a b s t r a c t i nt h i sp a p e r ，w ed i s c u s st h ef e a t u r ea n ds o l v i n ga l g o r i t h m sf o rt h el i n e a r q u a d r a t i cs e m i - d e f i n i t ep r o g r a m m i n g ( l - q s d p ) t h i sp a p e rm a i n l yc o n s i s t so ft h r e e s e c t i o n s i nt h ef i r s ts e c t i o n ，w ee s t a b l i s ht h ed u a l i t yt h e o r ya n dt h eo p t i m a l i t yc o n d i t i o n s i nt h ep r o b l e mo fl - q s dp a n ds t u d yt h ep r i m a ld u a li n t e r i o rp o i n tm e t h o df o rt h i s p r o b l e m m e a n w h i l e ，w eg i v et h ep r o o fo ft h eu n i q u es o l u t i o nb a s e do nt h en t s e a r d ld i r e c t i o n f u r t h e r m o r e w em a k et h em a t l a bc o d ef o re x p e r i m e n tw h e n t h en u m b e ro fd i m e n s i o nn = 3 ，a n dg i v et h en u m e r i c a ls i m u l a t i o ni nm a t l a b7 0 1 ， w h i c hv e r i f yi t sf e a s i b i l i t y f i n a l l y , w ed i s c u s st h er e l a t i o nb e t w e e nt h eq u a d r a t i c s e m p d e f i n i t ep r o g r a m m i n ga n dt h es e m i - d e f i n i t el e a s ts q u a r e sp r o b l e m ，a n dt h e n p r o v i d et h ec o n v e r s i o nr e l a t i o n s h i pb e t w e e nt h e mu n d e rs o m ec o n d i t i o n s i nt h es e c o n ds e c t i o n ，w ce x t e n dt h ed e f i n i t i o no ft h es e m i d e f i n i t el e a s ts q u a r e s p r o b l e m ( s d l s ) ，a n dp r o p o s et h es e m i d e f i n i t el e a s ts q u a r e sp r o b l e mw i t hb o u n d e d v a r i a b l e s ( b v - s d l s ) a tt h es a j n et i m e ，w eg i v et h ep r o j e c t i o no fs y m m e t r i cm a t r i x o n t ot h ec l o s e dc o n v e xs e t w h i c hi sc o m p o s e do ft h eb o u n d a r yc o n s t r a i n s w e a l s os t u d yt h es o l v i n ga l g o r i t h mf o r ( b v s d l s ) b a s e do nt h i sp r o j e c t i o n ，i e t h e p r o j e c t e dq u a s i n e w t o na l g o r i t h m ，a n dg i v et h ea l g o r i t h mf r a m ef o rt h i sp r o b l e m i n t h ee n d ，w em a k ea ne x p e r i m e n ti nm a t l a b7 0 1 。a n dc o m p a r en u m e r i c a lr e s u l t s w i t ht h a to ft h ep r i m a ld u a li n t e r i o rp o i n tm e t h o d n u m e r i c a lr e s u l t ss h o wt h a tt h e e x t e n d e da p p r o a c hi sf e a s i b l ea n dv a l i d i t y i nt h et h i r ds e c t i o n ，w ef u r t h e rd i s c u s st h ee x t e n s i o no f ( b v - s d l s ) ，a n dp r o p o s e t h ee x p l i c i tp r o j e c t i v ef o r m u l ai nc e r t a i np a r t i c u l a rc i r c u m s t a n c e s 。m o r e o v e r ，w ea l s o s t u d yi t ss o l v i n ga l g o r i t h m k e y w o r d s ：q u a d r a t i cs c m i d e f i n i t ep r o g r a m m i n g ，s e m i - d e f i n i t el e a s ts q u a r e s ， i n t e r i o rp o i n tm e t h o d ，b o u n d e dv a r i a b l e s ，p r o j e c t e dq u a s i - n e w t o na l g o r i t h m 。 i i 福建师范大学康志林硕+ 学位论文 中文文摘 本文主要探讨二次半定规划问题的特征和求解算法，研究的理论依据主要是对 称矩阵论及非线性规划的对偶理论文章的结构安排如下 第一章概括了目前国内外关于( 二次) 半定规划问题的研究情况和主要成果， 指出( 二次) 半定规划数学模型广泛的实际应用背景及其重要的理论意义 第二章研究一类特殊的二次半定规划问题的结构，其目标函数中的半正定自伴 随线性算子q ( x ) = 只x 只，r 三0 ，即 z x r a i s n 。i l x i = 1 只x r + c x s ta x = b x 一o 其中c s n , x s n , 4 x = ( a a x ，a m x ) ，a s ”，且集合 a d i = 1 ，2 ，m ) 中各矩阵元素线性无关同时，讨论该线性二次半定规划问题的对偶 性理论及其最优性条件，在此基础上。进而考虑该规划问题的原始对偶内点算法。 给出了当x 。z 正定时，系统 ( 一杰c 兰 只，h 三ti 。) ( i a 塞a 1 ni 、) 2 ( 囊) ill i 、7 ij p l l 一( 只 只)i - l 砌i i =i ijii m0 八、叱c 口厶，r c 福建师范大学康志林硬士学位论文 与半定最小二乘问题的联系及其转换关系，主要结论是命题2 4 1 ，命题2 4 2 ，命题 2 4 3 第三章中，我们从第二章中二次半定规划问题出发继续深入探讨特殊的二次 半定规划问题( z = 1 ，p = 厶) ，即半定最小二乘问题( s d l s ) ，并在此基础上，提出 了比( s d l s ) 更一般化的变量有上限约束半定最小二乘问题( b v - s d l s ) x m 秒i n 划i x c 幅 s ta x ：b( b v s d l s ) 0 墨x 墨8 j n 本章主要工作是，先对半正定矩阵锥趿进一步拓广，定义一闭凸矩阵集合 q p = f x s n05x5p 厶) ，其中p 0 ，并给出了任意实对称矩阵c 酽在该 闭凸集护上的精确投影表示式 r 口( g ) = 僻= p c d i a g m a x o ，r a i n f i e ，a ( c ) ) ) ) 露 以及c 到闭凸集q 口的半平方距离( h a l f - s q u a r e dd i s t a n c e ) d n p ( c ) 2 x r a n i n 口1 i x c l l ；- = i 1 ( 执一缪) 2 + 碍) t 口a t o 其中凡是实对称矩阵c 的特征值主要结论有定理3 2 1 0 及其推论3 2 1 l ，推论 3 2 1 2 在上述投影的基础上，进而探讨了变量有界半定最4 - - 乘问题( b v - s d l s ) 的求解算法，即投影拟牛顿算法，并给出了其算法框架。邵算法0 0 1 ( 文中算法3 3 1 ) 算法0 0 1 投影拟牛顿算法 给定初始点y o 艘，初始h e s s i a n 逆近似矩阵风s m ，0 - o 基于该问题的广泛性，人们就希望能够通过分析半定规划的内部结构，寻求一 种求解s d p 问题的有效算法 1 9 8 4 年，k a r m a r k a r 9 l 提出了求解线性规划的多 项式时间内点算法，至此以后的几年里，内点算法发展迅速并日趋成熟，同时也为 s d p 的发展奠定了必要的基础，1 9 8 8 年，n e s t e r o v 和n e m i r o v s k i i l l o ，l l j 通过引 入自调和函数( s e l f - c o n c o r d a n tf u n c t i o n ) 提出了用内点算法解决凸规划问题的方法 框架。同时说明凸集上线性函数的最小化。可借助子该集上的自调和障碍函数在” 多项式时间”内完成特别指出，线性规划，含凸二次约束的凸二次规划，半定规 划都有明确且易于计算的自调和障碍函数，因此它们都可以在”多项式时间”内完 成由于半定规划是线性规划的拓展许多学者就考虑将线性规划的内点算法推广 至半定规划，1 9 9 2 年，a l i z a d e h 1 2 】直接将求解线性规划的多项式时间的内点算法 推广至半定规划，自此以后的十几年里，诸多学者就一直热衷于研究半定规划问题 的内点算法，包括j a r r e i l 3 】，a l i z a d e h ，h a e b e r l y , a n do v e r t o n i l 4 j ，k o j i m a ，s h i n d o h ，a n d h a r e 1 5 】，n e s t e r o va n dt o d d 1 6 l 等等值得注意的是，半定规划的内点算法不同于线 性规划，依k k t 系统给出的搜索方向并不能满足对称性，故有必要先对k k t 系统 中的互补松弛条件对称化经过几年的发展和完善，现今的对称化方法主要有a h o 方向1 1 4 ，k s h 方向【1 5 】，丁方向1 1 6 1 ，经验表明使用j v 丁方向相比于a h o ，k s h 方 向会更加稳健( r o b u s t ) 1 6 j 可以发现，自上世纪9 0 年代以来的十几年里，半定规划的求解更多的是考虑用 内点算法，但在一定条件下对矩阵变量的维数死足够大，约束超过7 0 0 0 个的问题 2 n 妨i i 仉一 一u以( 14 仉 n 、， 11 口 一 ，o r t ， 1 4 第1 章引言 时，内点算法就显得无能为力了，而在实际工程运用中，经常遇到大规模的问题， 故有效解决大规模半定规划问题已经成为迫切需要解决的问题基于此，c h r i s t o p h h e l m b e r g 等1 1 7 1 【7 l 于1 9 9 7 年将削甲面算法用于线性半定规划的松弛问题，并得到 了很好的效果至此，割平面算法也成为了求解线性半定规划的热门研究话题，直 至今日，割平面算法主要有三种不同类型的方法：谱丛方法【1 8 1 ，线性规划割平面方 法【1 9 1 ，解析中心割平面算法( a c c p m ) 2 0 1 2 0 0 1 年，k a n z o w 和n a g e l 【2 l 】1 2 2 】将扰 动的互补松弛条件等价改写为非线性映射西：p 酽r + _ s n ：( x ，s ，7 - ) = 0 ， 在此主要讨论了两种西形式，光滑最小化函数( s m o o t h e dm i n i m u mf u n c t i i o n ) 和 光滑f b 函数( s m o o t h e df i s c h e r - b u r m e i s t e rf u n c t i o n ) ，并将牛顿型方法应用于非 线性系统，数值结果显示这种方法优于内点法2 0 0 6 年，j p o v h 等提出了线 性半定规划的边界点算法( b o u n d a r yp o i n tm e t h o d ) ，实际上是将增广l a g r a n g i a n 罚函数方法应用于半定规划问题，从半定规划的最优性条件( k k t 系统) 出发，但 其不同子原始对偶内点算法，在每次的循环过程中，始终保证每次迭代的原始变量 儿及对偶变量五处于半正定矩阵锥的边界上，且恒满足k k t 系统互补松弛条 件当关于原始与对偶线性方程在误差允许范围内满足可行性，该算法最终保证原 始变量虬和对偶变量磊趋于原问题和对偶问题的最优解x ，z 半定规划的日渐成熟与发展，为分析和解决工程及其他规划问题提供了强有力 工具，比如非凸二次约束的二次规划问题、整数规划问题对于非凸二次约束的二 次规划问题： i n f z 丁q o z 营 s t x t a z = bv i i n f q o x x t z s t q t z z t = qv i 通过适当的替换( 令z z 7 = y ) ，可以很容易得到如下s d p 松弛问题 西y s t q i y = qv i y 三0 从而可获得原问题的一个界值估计 我们知道，大部分整数规划都是n p 一完全或者n p 难问题，很难找到多项式 时间算法求解，目前解决整数规划( i p ) 的通用方法主要有：分支定界法，割平面方 法，动态规划方法当然，在利用这些通用算法求解时，并不是仅仅孤立地使用， 为了得到更好的效果，经常是将这些方法或者与其他方法结合起来在求解整数规 划过程中经常涉及到最优解的定界问题，可以通过求解s d p 松弛问题【2 4 】来获得 3 福建师范大学康志林硕士学位论文 原问题最优解的一个界值估计当原始问题不好求解时，经常借助对偶问题来分析 原问题。甚至可通过对偶问题获得原问题的解比如，二次( 一1 , 1 ) 整数规划问题 r a i n 互1 z t 啦+ c t z x e - 1 ，1 n 。 其中q 铲，c 俨令人惊奇的是，其对偶问题最终可变为如下简单的线性半定 规划问题： ( a ，1 ) p + 1 st(q+2dtin夕a2rcc2 一e t a ) 三。 、 1 z 7 - 一 1a ， 2 0 世纪9 0 年代考虑的s d p 都是线性半定规划问题( l - s d p ) ，即目标函数是线 性的，随着研究的深入，人们自然而然地要考虑非线性半定规划问题，而线性二次 半定规划( l i n e a r - q u a d r a t i cs e m i - d e f i n i t ep r o g r a m m i n g ，简记为。l - q s d p ) 是二 次规划的推广，同时也是最简单的一种非线性半定规划，而且它在控制论中也有比 较强的应用背景，因此探讨二次半定规划问题的结构及求解算法就显得很有必要也 很有意义在此之前，先给出二次半定规划一般模型【2 5 】： r a i n x q ( x ) + c x x 6 s z 7 s ta x ：b( q s d p ) x 兰0 其中，q 是铲到铲的半正定自伴随算子( s e l f - a d j o i n tp o s i t i v es e m i d e f i n i t e o p e r a t o r ) ，即对任意4 ，b 酽，有 q ( a ) b = a q ( b ) ，q ( a ) a 0 进一步地，若算子q ( x ) 关于x 是线性的，则二次半定规划( q s d p ) 即为线性二 次半定规划( l - q s d p ) 显然，对( q s d p ) ，若不存在二次项，则( q s d p ) 即为线性 半定规划问题( l - s d p ) g u a n 2 5 】考虑了如下二次半定规划s x m i s n 。 ；u e c t ( x ) 少丁岁u e c ( x ) 一矿夕t ，e c ( x ) + c x s ta x = b x 三0 其中夕= ( v e c r f l ，v e c r f , ) t 彤矿，只( i = 1 ，s ) 均为n 阶实对称矩阵 g u s r t 将此二次半定规划问题的最优性条件等价转化为线性变分不等式，将用于求 4 第1 章引言 解单调线性变分不等式的投影收缩算法( p c 算法) ，应用到该二次半定规划问题中 来，但是该算法解决的仍只是一些小规模问题，当( q s d p ) 的规模比较大时，p c 算法收效甚微基于此，x u l 2 6 1 在文献【1 6 】基础上将求解线性半定规划的原始对偶 内点算法推广至文献【2 5 】中讨论的二次半定规划，给出了短步长路径跟踪算法，数 值试验结果也表明基于n t 方向的内点算法优于p c 算法除此之外，k c t o h 等 【2 7 】进一步探讨了一般二次半定规划的不精确原始对偶内点算法 半定最小二乘问题是一类特殊的二次半定规划问题，其标准形式如下： 娜m i n 。 1 1 x c 幢 s t 似= b x 三0 容易发现，该规划是严格凸规划问题，且目标函数具有平方和这种特殊形式，从而 给问题的求解带来了某种方便，对于该问题，除了能够运用一般求解方法( 原始对 偶内点算法) 外，还可以考虑其他一些更为简便有效算法2 0 0 2 年，h i g h 锄【2 8 1 考虑了约柬仿射算子为对角算子( 4 = 出叼) 半定最小二乘问题的求解算法，即校 正交错投影算法。该算法在原来交错投影运算的基础上引入d y k s t r a 校正步例，然 后交错投影到由约束集构成的闭凸集合上，最终保证算法收敛到全局最优点有关 交错投影算法的描述，可进一步查阅文献 3 0 】。在半定矩阵锥投影算子b 竺1 3 , 】的基 础上，2 0 0 5 年，m a l i c k j 1 3 2 1 只对仿射约束求l a g r a n g i a n 对偶，提出了该问胚的 部分对偶方法，并利用对称锥的m o r e a u 分解定理将对偶问题改写为目标函数如下 相对简化的无约束优化问题 7 7 ( ! ，) = - d ( s 7 ) 。( c + a y ) + i l c i | 刍+ y r b = 一；1 1p s 7 ( c + 4 ) j i 斋+ 1 1 c l l ；, 4 - y t b 这种方法可以有效地解决中等规模的( s d l s ) 问题b o y ds ，l i nx i a o l 删在【3 2 】 的基础上进一步考虑了含不等式约束的二次半定规划问题，称之为协方差矩阵校正 问题( l s c a p ) ： 心m i n 。；l l x c 幅 s t4 x = b 纺x 冬d x 三0 其中留x = ( 局x ，昂x ) t ，d r p 易知( l s c a p ) 也是凸二次半定规划问 题，若不考虑约束中不等式，则( l s c a p ) 即为半定最小二乘问题对于此问题，当 5 福建师范大学康志林硕士学位论文 变量个数小于1 0 0 0 ，即对应于n = 4 5 情况，可以由内点算法【1 6 j 得到有效的解决 b o y ds 从问题本身出发，经过化简，得到不含矩阵变量的有约束对偶问题其约束 变量个数为不等式约束的个数，并给出了( l s c a p ) 的对偶投影次梯度算法，同时 讨论了步长选取的条件及算法收敛性问题之后，h o u d u oq i 等f 3 4 l 进一步考虑了 约束仿射算子为对角算子的半定最小二乘问题。通过对偶性理论将规划问题转化为 求解关于半正定锥投影算子的非光滑方程 f ( y ) ：= 4 ( c + a y ) + = b 其中耳定义为c 到半正定矩阵锥毋上的尺度投影同时，作者利用非光滑牛顿 法f 3 5 1 求解该方程，并由半正定锥投影算子的强半光滑性例吲，证明了当初始迭代 点充分靠近最优点时，非光滑牛顿法的二次收敛性 2 0 0 7 年，i g o rg r u b i s i c 等f 3 8 j 进一步强化了仿射和半正定约束，考虑低秩 ( 1 0 w - r a n k ) 矩阵校正问题，即在约束中增加一个秩的约束 挪m i n 。钏x 一哪 s t r a n k ( x ) d 咒 = b i ，i = 1 ，n x 三0 其中d 1 ，n ) ，目标函数中的| | i i 是定义在伊上的哈达玛半范数( h a d a m a r d s e m i n o r m ) ，i e ， 勃x e l l 2 = 去w t j ( x o 一) 2 - i 一o ) ，矩 阵的半正定约束虽然是非线性非光滑的，但也是凸的，故该二次半定规划为凸( 严 格凸) 二次优化问题 若取矩阵变量x = d i a g ( x l ，t 2 ，) ，令= v e c ( x ) ，则x 三0 营v e c ( x ) o 故二次半定规划就等价于如下二次规划问题： 譬m ：i n i 5yt纛tpi：pi，)y：+1v，ec(c，)tyvec(ayb ii m t ，、z z ， s t ) t = ，= 1 ， ， 在讨论该规划的对偶性及最优性条件之前，先给出以下几个有用的引理； 9 福建师范大学康志林硕士学位论文 引理2 1 1 【6 】设a ，b s ”，若a 兰0 ，b 三0 ，则a b 0 ，且a b = 0 当且仅当a 口= 0 引理2 1 2 【6 】设b 是亿n 阶非奇异矩阵，则a 卑当且仅当b r a b 卑j a 卑+ 当且仅当b t a b 肆+ 弓l 理2 1 3 若只= 掣，圣= l ， 则竺掣= 圭只x 最， 证明：由 4 1 】，o ( t 7 ( x 狱a x b ) ) - = ( a x b + b x a ) t ，则 a ( 小ep i x p da ( 扣( x 夏p , x p d ) 荀卜2 静一 a ( 打( x p x p d ) 一劢f 一 8 ( r ( x p t x p d ) 一互刁又一 = j ( 户；x 只+ 只x 只) r2 厶、。1 7 l 4i 。、ol ， f = 只x 只 引入拉格朗日乘子a ，z 辩，则二次半定规划问题的拉格朗日函数为t l ( x ，入，z ) = 去x 只x 只+ c x 一气( a x - h i ) 一x z ， 。 i = ii = l 由引理2 1 3 可求得函数l 关于变量x 的偏导数，并令其为0 ，则有： 装= 妻只x 只+ c 一喜砌t z = 。，z 三。 利用凸规划的对偶理论，可得原二次半定规划的对偶规划： l，孔 m a ，a z x i x - i = i 蹦a + 汹e 九玩 fm s t 只x 只+ c 一九a z = 0 t = 1i = 1 么三0 1 0 - ( 2 3 ) 第2 章二次半定规划f u i 题及其内点算法 显然，原二次半定规划( 2 1 ) 的对偶规划也是二次半定规划，目标函数是拉格 朗日函数在可行域上的简化当然，在一定条件下，可以把对偶规划改写为只含对 偶变量入，z 的规划形式。在此，我们考虑一般情况，即只0 0 = l ，f ) 的情 形，而r o ( i = l ，z ) 是显然的 引理2 1 4 4 1 jp j 若矩阵q ( i = 1 ，z ) 相互正交，即q q = o c i j ) ，则 ( q 1 + q 2 + q f ) = q + q ；+ + q ；， 例对于任意n 阶矩阵q ，r ，有( q 固r ) t = q r t ，( q + ) t = ( q t ) 引理2 1 5 若矩阵掣= 只( i = 1 ，c ) ，则只与弓“j ) 正交当且仅当 只。只与弓 另正交 证明：若只与b 正交，即r 弓= 0 ，则 ( eo 只) ? ( p jpp j ) = ( rqp , ) c 5 弓) = 只弓9r b = 0 反之，若只。只与毋9 另正交，则只弓 p , p j = ( 只p 只) ( b b ) = ( r 只) t ( b p j ) = 0 ，故推得只弓= 0 ， 1 l 假定关于x 的矩阵方程( 2 4 ) 是有解的，用钌e c 算子作用，有( 只o p d v e c ( x ) = l i = l t ，e c ( 印，则取其一特殊解：v e c ( x ) = ( 只。只) u e c ( s ) 因此，当二次半定规划 t = 1 ( 2 1 ) e e l _ 阵只与b 正交，即只局= 0 时，由引理2 1 4 ，引理2 1 5 ，易发现其对 偶目标甬数也具有二次半定规划( 2 ，t ) 的表达形式事实上，对偶规划( 2 3 ) 的目 qp c ，) 垒一g a m 汹 + z= r x r ，僦 记现 福建师范大学康志林硕士学位论文 标函数可进一步改写为： - x 只xr + 人坟 i = li = l fm = 一； e c ( x ) r ( 只 只) v e c ( x ) + 凡瓯 ：一；可e c ( s ) r ( 圭只 只) ( 圭只 r ) ( 圭只。r ) t u e c ( s ) + 曼八机 1 亏1 。1 m 。l 2 1 = 一；可e c ( s ) r ( 只。只) e c ( s ) + 妻a i b i = 一；u e c ( s ) r ( 只。只) 口e c ( 印+ 九机 一 m = 一；可e c ( s ) ? ( 辟固磷) c ( s ) + 玟 仃l = 一j u e c ( s ) t ? j e c ( 日s 辟) + 九兢 tn i = li = 1 m = 一；s 辟s 爿+ a 兢 因而，当二次半定规划( 2 1 ) 中矩阵只与b 正交，即j f ：弓= 0 时，其对偶规划具 有与原规划异常对称的表示式： m 程一抄i = 1 曩s 牟+ i = 1 沁魂 ( 2 5 ) ，o l z 6j s t a ，z 三0 其中s = z + 八4 f c ，曩是矩阵只的m o r r e p e n r o s e 广义逆 = l 设原始问题的目标函数为f ( x ) ，对偶问题的目标函数为叮( a ，z ) = m x i n l ( x ，a ，z ) ， 原问题的可行域为口= f x 铲i4 l x = 仇0 = l ，m ) ，x 艺o ) 由凸规划的 对偶性理论，我们有如下弱对偶定理： 命题2 1 6 设x 为二次半定规划原问题的可行解，a ，z 为对偶问题的 - t 4 r 解，则 s u 。pq ( a ，z ) i n y ff ( x ) a z 证明；设y 为原问题的可行解。 x ，a ，z 为对偶问题的可行解f ( x ) = f ；x 只x 只+ c x 为凸函数，由凸性可知，拟，y 刃，有f ( y ) f ( x ) + i = 1 l v f ( x ) ( y x ) ，其中v f ( x ) = 只x b + c 因为x ，入，z 为对偶问题的可行 ：1 1 2 第2 章二次半定规划问题及其内点算法 解，所以v x l ( x ，a ，z ) = v 尸( x ) 一a i a i z ，z 兰0 i = l f ( y ) 之f ( x ) 十( e 丸a 一z ) ( y x ) 害1仇 = r ( x ) + ea i ( a i y ) + z y 一a i ( a i x ) 一x z = 1t = l m f ( x ) 一a i ( a i x b i ) 一x z = l ( x ，a ，z ) l = 1 故g ( a ，z ) = i n 、，fl ( x ，a ，z ) f ( x ) ，进而q = s u pg ( a ，z ) i n ff ( x ) _ a z “ 命题2 1 7 设一x ，灭，一z 满足二次半定规划( 2 1 ) 的k k t 条件( 2 6 ) ，则叉和 ( 天，z ) 是原问题与对偶问题的最优解，且具有零对偶间隙 证明：由已知叉，页，z 满足二次半定规划( 2 1 ) 的k k t 条件，故又是原始可 行的又l ( x ，- ，一z ) 关于x 是凸函数，由k k 丁条件的第二式知，l ( x ，天，芴在 叉处的梯度为0 ，即v x l ( - z ，页，z ) = 0 ，也即l ( x ，页，一z ) 在叉处取得最小值，因而 有 口( 天，- z ) = l ( 一x ，页，劢 = 尸( 叉) 故叉与( 天，z ) 具有零对偶间隙再由命题2 1 6 知，又是原始最优解，( 天，z ) 是对 偶最优解 注2 1 1 命题2 j 7 给出了二次半定规划的最优性条件，为我们用原始对偶内 点算法解决此二次半定规划问题( 2 1 ) 提供了理论依据 2 2 原始对偶路径跟踪算法 众所周知，在对优化问题( 特别是凸规划问题) 进行求解时，经常从该问题的最 优性条件出发，去求关于最优性条件的非线性方