（应用数学专业论文）二次锥规划的内点算法及光滑牛顿法.pdf

摘要 二次锥规划是在有限个二次锥的笛卡儿乘积的仿射子空间之交上极小化或极 大化一个线性函数其约束是非线性的，但却是凸的，因此二次锥规划是凸规划二次 锥规划包括线性规划和二次约束下的凸二次规划等，却是半定规划的特例由于其 广泛应用及原一对偶内点算法的迅速发展，二次锥规划已经成为数学规划领域的一 个重要的研究方向 本文首先简述了二次锥规划的基本知识。包括二次锥规划的理论、算法和研究 现状，然后介绍了在= 次锥规划的算法方面所傲的一些工作，具体如下： 1 ，本文给出了二次锥规划的一种原一对偶非精确不可行内点算法该算法允许 搜索方向有相对较大的误差，且不要求迭代点的可行性在相对不精确的假设下 利用该算法可找到二次锥规划的e 一近似解 2 ，在光滑f i s c h c r - b u r m e i s t c r 函数的基础上，本文给出了二次锥规划的一种新 的光滑牛顿法该方法所采用的系统不是等价于中心路径条件，而是等价于最优性 条件本身算法对初始点没有任何限制，且具有q - - 阶收敛速度 关键词：= 次锥规划不可行内点算法非精确搜索方向强半光滑 光滑牛顿法 a b s t r a c t t h es e c o n d - o r d e rc o n ep r o g r a m m i n g ( s o c p ) p r o b l e mi st om i n i m i z eo rm a x i m i z e al i n e a rf u n c t i o no v e rt h ei n t e r s e c t i o no f a na f f i n es p a c ew i t ht h ec a r t e s i a np r o d u c to f a f i n i t en u m b e ro fs e c o n d - o r d e rc o n e s i ti sw e l lk n o w nt h a tt h ec o n s t r a i n to ft h e s e c o n d o r d e rc o n ep r o g r a m m i n gi sn o n l i n e a r ，b u tc o n v e x ，s ot h es e c o n d - o r d e rc o n e p r o g r a m m i n gi s ac o n v e xo p t i m i z a t i o np o b l e m n 砖s e c o n d o r d e rc o n ep r o g r a m m i n g u n i f i e ss e v e r a lp r o b l e m s ，s u c ha sl i n e a rp r o g r a m m i n ga n dq u a d r a t i c a l l yc o n s l m i n e d c o n v e xq u a d r a t i cp r o g r a m m i n g ，b u ti ti sas p e c i a lc a s eo fs e m i d e f m i t ep r o g r a m m i n g b e c a u s eo ft h eq u i c kd e v e l o p m e n to fi t sp r i m a l - d u a li n t e r i o r - p o i n ta l g o f i t h m sa n di t s 、v i d e 印p l i c a t i o n s ，t h es e c o n d - o r d e rc o n ep r o g r a m m i n g i sa l li m p o r t a n tr e s e a r c hf i e l di n m a t h e m a t i c a l p r o g r a m m i n g i nt h ep a p e r , f i r s t l yt h et h e o r y , a l g o r i t h m ，a n dr e c e n tr e s e a r c ho ft h es e c o n d - c o n e p r o g r a m m i n g i ss u m m a r i z e d ，t h e no u rs o m ew o r ki na l g o r i t h m si si n t r o d u c e d f o r d e t a i l ， w ec o n c l u d et h e ma sf o l l o w s ： 1 ap r i f n a l - d u a li n e x a c ti n f e a s i b l ei n t e r i o r - p o i n ta l g o r i t h mf o rt h es e c o n d o r d e r c o n ep r o g r a m m i n gi sp r e s e n t e di nt h i sp a p e r t h i sa l g o r i t h ma l l o w st h es e a r c hd i r e c t i o n t h a ti sc a l c u l a t e dw i t ho n l ym o d e r a t ea c c u r a c y , a n dd o e sn o tr e q u i r ef e a s i b i l i t yo ft h e i t e r a t i o np o i n t s ，u n d e ram i l da s s u l n p t i o no l lt h ei n e x a c t n e s s ，w es h o wt h a tt h e a l g o r i t h m c a nf i n da n f - a p p r o x i m a t e s o l u t i o no f t h es e c o n d - o r d e rc o n e p r o g r a m m i n g 2 b a s e do n s m o o t h i n gt h ef i s e h e r - b u r m e i s t e rf u n c t i o n ，an e ws m o o t h i n gn e w t o n m e t h o di sp r e s e n t e di nt h i sp a p e r 职l es y s t e mw h i c hi se m p l o y e di nt h i sm e t h o di s e q u i v a l e n tt ot h eo p t h n a l 时c o n d i t i o n sa n dn o tt ot h ec e n t r a lp a t hc o n d i t i o n s 刚s a l g o r i t h md o e sn o t h a v er e s t r i c t i o n sr e g a r d i n gi t ss t a r t i n gp o h a ta n di ti sq - q u a d r a t i c a l l y c o n v e r g e n t k e y w o r d s ：s e c o n d - o r d e r c o b e p r o l q a m m i n g i n f e a s i b l ei n t e r i o r - p o i n ta l g o r i 馈m i n e a m c ts e a r c hd i r e c t i o n s t r o n g s e m i s m o o t h n m s s m o o t h i n g n e w t o nm e t h o d 独包i 性声明 y 6 9 5 6 6 本人声明所呈交的论文是我个人在导师指导下进行的研究工作及取得的研究 成果。尽我所知，跨了文中特别加以标注和致谢中所罗列的内容以外，论文中不 包含其他人已经发表或撰写过的研究成果；也不包含为获得西安电子科技大学或 其它教育机构的学位或证书而使用过的材料。与我一同工作的同志对本研究所做 的任何贡献均已在论文中做了明确的说明并表示了谢意。 申请学位论文与资料若有不实之处，本人承担一切相关责任。 关于论文使用授权的说明 本人完全了解西安电子科技大学有关保留和使用学位论文的规定，即：研究生 在校攻读学位期阉论文工作的知识产权单位属西安电子科技文学。本人保证毕业 离校后，发表论文或使用论文( 与学位论文相关) 工作成果时署名单位仍然为西 安电子科技大学。学校有权保留送交论文的复印件，允许查阅和借阅论文；学校 可以公布论文的全部或部分内容，可以允许采用影印、缩印或其它复制手段保存 论文。( 保密的论文在解密质遵守此规定) 本人签名：照盥丝 导师签名：盔：i 三仝! 日期盗蝰f ：! 丝 日期丛：! ! 竺 第一章绪论 第一章绪论 本章首先介绍了二次锥规划及其对偶模型和二次锥规划的研究现状； 接着讲述了二次锥规划的基础知识，如二次锥的代数性质，二次锥规划的 对偶理论及原一对偶内点算法的主要思想等；最后列出了本文的内容提要 和章节安排 1 1 二次锥规划的模型和研究现状 二次锥规划是在仿射空间与有限个二次锥的笛卡儿乘积之交上极小化一个线 性函数，因此它是非线性凸规划二次锥规划包括线性规划和二次约束下的凸二次 规划等，却是半定规划的特铡由于二次锥规划在控制、金融、组合优化、工程等 领域有着广泛的应用i l l - 8 1 及二次锥规划原对偶内点算法的迅速发展，使其近年来 备受关注虽然二次锥规划可以转化成半定规划求解，但是那样无论从数值试验还 是从计算复杂度方面考虑都不尽人意，所以对= 次锥规划的研究有非常重要的意 义 在本文中，令科表示k 维实列向量r j , x r 定义为r ”啮，所以 “，) r x r 被看作是露“嘛中的列向量垤r ，8 j 8 为向量，的：2 - 范 数类似于线性规划。二次锥规划的原规划标准形式( p ) 如卞： r a i n 如 如l j j 4 五= 6 扛l ，”，一 ( 1 1 ) 州 l i x l 其中4 r “，q r 和姆r ”是已知量，而乍葺是变量k 是维数为七l 的二次 锥，其定义为 k = 而= ( 西o ，而1 ) e r x r 与| ：一而l i 耻o ) ， 众所周知丘是自对偶的，即 墨= k ； e r i 彳o ，毫k 原规划( 1 1 ) 的对偶规划0 ) ) 为 2二次锥规划的内点算法及光滑牛顿法 m a x b 7 y 5 4 7 y + s s = c ，j = 1 ，l 置k 其中暑e k 为松弛变量，y e 为变量令 ( 1 2 ) a = ( 4 ，4 ) r ”，c = “，巳) r ， z = ( x 1 ，矗) k ，s = ( 丑，s n ) k m 默矿y s j a 7 y + s = c 二次锥规划应用广泛，许多问题如范数极小化、涉及有理幂的不等式、正仿 射函数的调和平均值等，均可转化为二次锥规划求解下面我们给出几个实倒 例1 1 9 凸二次约束下的二次规划是在满足凸二次约束的条件下使线性函数 t x r 彰旦x + 口f x + 属s 0 ，f = l ，一。册 其中ee r 枷的秩为南，i = l ，m 令 吼( 茸) a x b t b f x + 矸x + 属，j = l ，肼 叮( x ) = ，b r b x + a 7 x + p 则凸二次约束窜( x ) s o 等价于嗣，其中 2 宇，石= 妇 ， 即凸二次约束等价于二次锥约束 第一章绪论 3 舰 1 2 1 9 1 范数的极小化：令百= 4 x + 6 fe 舭，f = 1 ， 则问题商n 喜阿8 等价于二 m i n v f 。 “今+ 6 = 虿，江1 ，开 m i n 毪警l l n ( 咖) 一l n ( 岛) | ， ( 1 3 ) 其中包 0 , i = l ，z 若衫x o 时，令h ( x ) 为一注意到 l h ( 咖) 乩( 6 1 ) i 曲一( 譬，去 ， 假定和哪峋渤等价子孙化m a x m a x ( 譬，去) ，或 “兰霉轧f = l ，小 ( 1 4 ) ta “掣乳f ：1 ， 艇；一 8 s r + 警，= t ，托 事实上，许多优化问题都可转化为二次锥规划问题求解，因此近年来它成为数 人们对= 次锥规划的研究已经有很长的历史了，如经典的f e r m a t w 曲盯问题 可追溯到几个世纪以前呲m 由于把二次锥规划转化成半定规划求解，其效果并不 二次锥规划的内点算法及光滑牛顿法 k o r a n y 1 详细论述了这一理论关于= 次锥规划的非退化、严格苴补、最优性条件 等的研究也取得丰硕的成果 1 4 , 1 5 , 2 2 】随着n e s t e r o v 和n e m i r o v s k i i 1 0 谰内点法求解凸 规划的一般理论的提出，怎样将线性规划的内点算法推广到半定规划和二次锥规 划，成为数学规划领域令人瞩目的课题 1 6 , 1 7 】近年来由于其在工程技术、控制论、 金融、组合优化等方面的广泛应用 1 - 8 1 ，二次锥规划问题备受关注目前如何寻找二 次锥规划更好的算法以解决实际问题成为最优化领域的一个新的令人关注的热 点 在求解方法上，主要是将线性规划的内点算法推广到半定规划和二次锥规划 人们最先用内点法求解二次锥规划及其特例( 凸二约束下的二次规划) 是在上世纪 九十年代 1 0 , 1 9 - 2 1 】。自n e s t e m v 和t o d d 2 7 0 8 】第一次用多项式时间原一对偶路径跟踪法 解二次锥规划以来，其原一对偶内点算法才得以长足发展类似于半定规划，二次锥 规划的路径跟踪法对扰动互补松弛条件采用不同的对称技巧可得到不同的原一对 偶搜索方向如n t 方向、a h o 方向、h r v w k s h m 方向等采用不同方向可得到 不伺算法，虽然这些不同的算法有不同的收敛性质，但是已被证明它们都具有多项 式时间复杂度 光滑方法即非内点连续方法，是近年来求解优化问题的一种新方法人们最先 是用光滑法来解决瓦补问题的，如非线性互补，半定互补，二次锥互补问题1 4 6 】等自 从c h r i s m n k a n z o w 和c h r i s t a n n a g c l 【4 7 】把光滑方法引入半定规划中，这一课题引起 了学者们的极大关注虽然半定规划的光滑方法在理论上有许多优越性，但数值试 验效果并不如内点算法理想许多学者正在寻求最佳的解半定规划的光滑方法，试 图使其成为比内点算法更好的方法对于二次锥规划的光滑方法的理论研究口9 ，4 2 】 已取得了一定的成果，但是人们对算法研究的较少，因此二次锥规划的光滑牛顿法 仍然有待于进一步研究 作为数学领域的一个重要分支，二次锥规划的研究有着非常重要的意义首先 二次锥规划有着广泛的应用背景其次，许多数学规划问题( 如线性规划和凸= 次 约束下的二次规划问题) 都可转化成二次锥规划求解，而且一般说来其效果要比转 化成半定规划的效果好些【9 1 因此二次锥规划是数学规划领域的一个值得关注的方 向有关二次锥规划的详细讨论可参阅r a l i z a d e h 和d g o l d f a r b 的综述 9 】 1 2 = 次锥的代数性质和对偶理论 为了更好地设计和分析二次锥规划的算法，我们先在本节中讨论一些基础知识 如与二次锥相伴的欧几里得约当代数的性质，二次锥规划的对偶理论和最优性条 件等 二次锥规划的对偶理论、互补性质、非退化条件、内点算法的设计及收敛性 第一章绪论 分析等均是建立在与二次锥相伴的代数的基础上的为了更加深入地了解二次锥 规划，我们首先介绍与二次锥相伴的代数，这种代数是欧几里得约当代数的特例 在此我们不讨论一般的欧几里得代数，只研究与二次锥相伴的代数 对于v x = ( 而，再) r x r k - t , y = ( y o ，y 1 ) r x r “，定义约当积 x 。y = ( x r y ，y 0 x l4 * x o y l ) 令工2 表示x 。x ，x + y 表示通常的向量分量的加法，则加法、乘法与单位元 e ：( 1 ，o ，o ) 戤构成的代数有如下性质： 引理1 1 协，y ，z er ，有 ( 1 ) e o x = x ( 恒等性) ( 2 ) x o y = y 。x ( 交换性1 ) ( 3 ) 工。xo ) ，) = 。y ) ( 交换性2 ) ( 4 )( x + y ) 。z = 工。z + y 。z ( 分配性) 注意到当疗 2 时，约当积并不是结合的但在内积意义下结合律是成立的，即 协，弘z e 砧，有 = = 下厩我们将介绍与二次锥相伴的向量的谱分解v x = ( x o ，而) r 胄“，令 = + ( 一1 ) m ，i = 1 ，2 “( ) =趣叫翻，觏舢2 * ( 一z ) 。w ) ，抵= o ， 其中w 为r “中任意满足川= l 的向量容易验证 善= 五0 1 + 屯”( 2 ) ，( 1 5 ) 则( 1 5 ) 式称为x 的谱分解， ，五称为工的谱值，u o ) ，分别为善的与 ，五相伴的谱 向量易知当而o 时，x 的谱分解( 1 5 ) 是唯一的r u t ”，2 ) 有如下性质： 5二次锥规划的内点算法及光滑牛顿法 ( 1 ) ”1 ) 。“( 2 ) = o ， ( 2 ) ”| | = | i 删= l 压， ( 3 ) “( 1 ) 。“( 。) = “( ”，i = l ，2 定义向量x 的迹和行列式如下： 护( x ) = + = 2 x o ， d e t ( x ) = 如= 靠一m 2 如果d e t ( x ) 0 ，定义 x 一1 = a - 甜( 1 + 五h ( 引 注意到对于二次锥中的r k , x 的特征值都是非负的，所以定义 x v 2 = 硝2 “( 1 ) + 硝2 “( 孙 且定义 x 2 = 矸+ 石( ” v x = ( x o ，一) e r x r “1 ，定义对称矩阵 m 雄，= 匕辩 s ， 令 k = x = ( x o ，x 1 ) r x r “：x 0 一x 1 l l 0 ， k 。表示k 的内部注意班石足( 或x 仨f ) 当且仅当删( z ) 是半正定( 或正定) 的， 因此= 次锥规划是半定规划的特例由( 1 6 ) 式易得 x 。y = m a t ( x ) y = m a t ( y ) x ，v y e r 对于垤= “，) e 舻“啮，= ，此) i f , ”“，定义 e = ( 毛，) ， x 。y = ( x i 。m ，矗。只) ， x 。= ( 一，) ， 第一章绪论 7 开肼( x ) = 加g ( m 口，“) ，删陬) ) ， ( 1 7 ) 其中对于方阵墨，托，搬( 五，k ) 表示以五，以为对角元的块对角矩阵定义 成= 6 丽，f 1 一 i = 1 ，n ， 令 t = d i a g ( t 自，誓) ， k = ( w l ，嵋) = 正且 关于二次锥的更详细的介绍可参见 1 3 ，此处不再赘述 与线性规划和半定规划类似，二次锥规划的对偶理论和k t 条件在其求解过 程中起着举足轻重的作用 下面给出本文的几个记号令足。表示二次锥置的内部，即 k o = 矸霹， 砰= = ( _ o ，而。) e r r q ：耳。一而i i f o ) ，i = 1 ，巩 则( 1 1 ) 和( 1 2 ) 的可行解集内部分别为 ( p ) = 詹= 6 ，x 芷。 ， f o ( d ) = j ) 1 a r y + s = ”足。 记p 和d + 分别为原规划p ) 和对偶规划) 的最优值，即 p + = i n f c r x l a x = t , ，x e k 。) d + = s u p b 7 y j 一7 y + s ；岛s e 置o 二次锥规划是半定规划的特例，它与半定规划有相似的对偶定理首先我们给 出= 次锥规划的弱对偶定理 定理l 2 嘲( 弱对偶定理) 令x 和( 弘5 ) 分别是二次锥规划原问题( 1 1 ) 和对偶 问题( 1 2 ) 的可行解，则c r xb r y 证明因为 盖m 以 8二次锥规划的内点算法及光滑牛顿法 c o b 7 j ，= ( y 7 a + s 7x - - x 7 a 7 y = x 7 岛 则由k 是自对偶锥知，z s 0 ，从而有f 7 x b r y 我们把灯= x t $ 称为问题( 1 1 ) 和( 1 。2 ) 的对偶闻隙 定理1 3 9 1 ( 强对偶定理) 如果( 1 1 ) 和( 1 2 ) 都存在严格可行解，即 f o ( p ) x f o ( d ) o ，则( 1 1 ) 和( 1 2 ) 分别存在最优解x + 和( y ，s 。) ，且有p + = d + 定理1 4 州( 半强对偶定理) 若( 1 1 ) 存在严格可行解，即f o ( p ) a ，且在可行 域上其目标函数值有界，则( 1 2 ) 可解i j lp * = d 事实上定理1 3 和定理1 4 对于所有定义在全维数的闭凸点锥上的锥线性规划 都成立，可利用f a r k a s 引理| 1 0 1 的一般形式进行证明下面我们给出二次锥规划的互 补条件 引理1 5 对于垤，j k ，则x 7 s = 0 当且仅当x j 。毋= o ，i = l ，刀 引理1 5 作为【9 】的引理1 5 的一部分，其证明过程详见 9 】由引理1 5 及原对偶 可行的假设，我们可得到二次锥规划的最优性条件 定理1 6 州( 最优性条件) 如果( 1 1 ) 和( 1 2 ) 均存在严格可行解，即 f o ( p ) x f o ( d ) o ，则( 工，弘s ) 是( 1 1 ) 和( 1 ，2 ) 的最优解当且仅当 f 爿x = 6 ，x k ， a 7 y + s = c ，j k ，( 1 8 ) i 工。s - - 0 ， 1 3 二次锥规划的原一对偶内点算法 在线性规划中通常有两大类内点算法，一类是仅原方法或仅对偶方法洲，另一 类是原对偶内点方法第一类方法可以很容易地推广到以二次锥规划和半定规划 为特例的对称锥优化问题肚5 】虽然大量的数值试验表明原对偶内点算法比仅原方 法或仅对偶方法有更好的数值效果，但第二类方法鲫并不能直接推广到二次锥规 划因为通常在二次锥中m a t ( x ) 与m a t ( s ) 并不可换，类似的情形也发生在半定规 划和所有对称锥规划闯题中为了克服半定规划中的这一问题，学者们提出了许多 不同的具有多项式时间的原对偶方法，如n t 方法网肛硼，x z 方法或z x 方法【2 9 】 3 1 1 第一章绪论9 a h o 方法【3 2 j 3 1 及以上述所有方法为特例的m z 族方法【3 1 ，3 4 等最近，上述所有方法 都被推广到对称锥优化问题1 1 4 3 5 4 吼 本节将主要介绍基于a h o 方向的原对偶路径跟踪法，并推广到m z 族方法 考虑问题( 1 1 ) 我们在( 1 1 ) 的目标函数中加入罚函数一譬l n d e t ( x ) ( o 是罚 因子) ，可以得到其罚问题 m i n c r x - p 1 n d e t ( x )、， j j a x = b ( 1 9 ) x k 。 当x 的特征值趋于0 即当工趋于可行域( 1 1 ) 的边界时，此罚函数趋向于无穷，从而把 搜索限制在可行域内进行 引进罚因子y r “，把上述约束优化问题( 1 9 ) 转化为无约束优化问题 屯( x ，y ) 如下： 丘( 工，y ) = c r x - - 等l n d e t ( x ) + y r ( 6 一a x ) v x k o ，注意到- l n d e t ( x ) 是凸函数翻，所以l ( x ， y ) 是定义在k o 上的凸函数，其 最优性条件为 v ，l = c 一x 一a 7 y = 0 ， v ，厶= b 一出= 0 令5 = 肼，则有 a x = b ，x k o ， a r y + s = c ，s e k o ， ( 1 1 0 ) x 。j = “p 可以证明弘 o ，( 1 1 0 ) 都有唯一解( ，) 唧当一斗。时( 1 1 0 ) 的解( h ，) 形成 的轨迹称为问题( 1 1 ) 和( 1 2 ) 的中心路径 用牛顿法解决问题( 1 1 ) 和( 1 2 ) ，可求解如下线性系统研口3 1 a 缸= b 一工 a r a y + a s = 口- - s - - 一7 弘 ( 1 1 1 ) ? s 缸+ x & s = c r 2 e x s 其中 ，；【 0二次锥规划的内点算法及光滑牛顿法 y = 卅口f ( x ) ，s = 枷f ( s ) = 小川= 宰，盯e r 我们通常把由该系统得到的搜索方向称为a h o 方向 v ( x ，s ) k o x k o ，z = ( x ，5 ) ，定义如下距离 破( ”) = ( ( ) 一) 2 = 压1 一雕8 ， 、f 措：， 比( ) 2 群i 硝( 心) 一z i - 黔【l ( k ) 一川，i 砰( k ) 一川】 1 0 v y ( o ，1 ) ，则由上述距离确定的中心路径的邻域分别为 2 ( y ) = ( x ，j ，s ) f o ( p ) f o ( d ) 1 4 ( x ，s ) s 彬 ， ：( ，) = ( x ，y ，j ) e f o ( 户) f o ( d ) j 以( x ，j ) 朋) 显然以( 工，j ) 如( 墨s ) ，所以2 ( y ) 虬( y ) 中心路径的邻域的引入既可使每 一步迭代在邻域内采用较大的步长，又能保证对偶间隙充分下降，因此我们可以较 容易地证明算法的多项式复杂度 下面我们给出基于a h o 方向的短步路径跟踪算法【2 3 1 选择，e ( 。专) ，艿( 0 1 ) 且满足下面的条件( 1 1 2 ) 令o f f i i - 忑 ，占( o 1 ) 给定初始点( ，肌，岛) 2 ( ，) ，令胁= ( 而，) = 萼产 ( 1 ) 计算( 1 1 1 ) 求得( 瓴，姒，趣) 和胁 ( 2 ) 令( 坼+ 儿。乱+ ) = ( 以，儿，品) + ( 觇，觇，趣) ( 3 ) 计算胁+ t = ( 黾m 乱“) = 蔓筹纽若胁“s 粕，则已经完成；否则令 k ：= k + l ，转( 1 ) 定理- 1 7 1 2 3 1 如果，e ( o ，；) ，艿( 。，1 ) 满足 等暑s ( 卜去) 协 则上述算法所产生的每一步迭代都满足( 而，儿， ) e 2 ( y ) 且 第一章绪论 粕= ( 1 一去) 岛此外，算法至多在。( 石l n f “) 步内有限终止 证明详见【2 3 】的推论1 下面我们将引入二次锥规划的m _ z 族方向嗍如同在半定规划的内点算法中 m _ z 族方向也是二次锥规划中一族常见的搜索方向札z 族方向是先计算调比问题 的a h o 方向( 1 1 1 ) ，然后再把它映射到原空间中该族中不同的方向取决于构造调 比问题所用的不同的调比矩阵 先定义如下矩阵群 q s 五霉i 旯 o ，霉舭“，霉7 孝= ， k o ， 其中 ；( ： 三) 科咄 众所周知q 是锥墨的自同构群圆，即所有非奇异矩阵巧的集合满足五= 正( 墨) ，其 中l ( k ) ； z 而l 而e 葺 令 o s r = 硪昭( 写，一，乙) i 正q ，f = l ，一 ，( 1 1 3 ) 易知q 是锥k 的自同构子群 任意给定geq 对( 1 1 ) 和( 1 2 ) 中的变量作如下交换 j = g 7 x ，( 歹，j ) = ( y , g “s ) ( 1 ，1 4 ) 令 j = 一g 一7 ，占= 6 ，亡= g 。1 c ， 则( 1 1 ) 可用新交量记作 n f i n 6 q s t 舨= 6 ( 1 1 5 ) i k ， ( 1 2 ) 可用新变量记作 m 积扩 j 上_ 7 夕+ 童= 石 ( 1 1 6 ) 掌k 令见( ，) 和矾【，) 分剐表示( 1 1 5 ) 和( 1 1 6 ) 的2 范数邻域和范数邻域。由 1 2二次锥规划的内点算法及光滑牛顿法 ( x ，j ) = ( 宝，；) 及命题2 2 3 1 可得 ( j ，歹，j ) j c t ( ，) 车( x ，y ，j ) 仨n d r ) ， ( 量，多，j ) 费。( ，) 舒( 工，y ，s ) ：( ，) 任意给定问题( 1 1 ) 和( 1 2 ) 的一可行内点( x ，y ，s ) ，通过变换( 1 ，1 4 ) p - i 得到问题 ( 1 1 5 ) a f l ( 1 1 6 ) 的可行内点( 膏，夕，i ) 在调比点( 最只j ) 计算a h o 方向( 压，母，丛) ， 再通过变换 缸= g 。越，( a y ，a s ) = ( 缈，g 丛) 映射回原空间，得到问题( 1 1 ) 和( 1 2 ) 在( x ，y ，s ) 点的调比a h o 方向 ( 缸，“a s ) = ( 瓴，砒，峨) 一 x = m a t ( 孟) ，s = 肌谢( i ) ， 则( 缸，a y ，血) = ( ，a y o ，峨) 是如下线性系统的解 a a x = b a x ， a 7 a y + a s = c s a 7 y 船7 缸+ 船一a s = a b e 一矗 对于不同的g eq 可得到不同的搜索方向，当g 取遍整个非奇异矩阵集合时。 得到的方向族为m z 族方向特别地，取g = ，g = 瓦，g = 巧可分别得到a h o 方 向，h r v w k s h m 方向和对偶h r v w k s h m 方向令g i 是q 中满足g x = g 。1 s 的唯一对称正定矩阵当g = g i 时可得到n t 方向 由于m z 族的任何方向都可通过变换映射到调比空间的a h o 方向，且其对偶 间隙和距离保持不变，故有关a h o 方向的算法一般均可推广到m z 族方向 1 4 本文主要工作 本文是作者攻读硕士学位期间在刘三阳教授的指导下完成的部分工作，主要 是关于二次锥规划的原一对偶内点算法和光滑牛顿法具体内容如下： 1 第二章基于a h o 方向提出了s o c p 的一种原一对偶非精确不可行内点算 法，并给出了求占一近似解的迭代次数该算法不要求初始点及其迭代点的可行性， 只要每次迭代产生的点在不可行中心路径的某个邻域内即可且搜索方向是非精 第一章绪论 确的，允许计算时有较大的误差，可节省计算机内存，而不影响算法的收敛性 利用此算法解二次锥规划问题只需o ( 一l i l ( 1 s ) ) 次迭代就可找到问题的占一近似 解 2 第三章在光滑f i s c h c r - b u r m c i s t e r 函数的基础上给出了二次锥规划的一种新 的光滑牛顿法先基于光滑f i s c h c r - b u r m e i s t e r 函数构造了一个菲线性等式系统，该 系统不含任何显式的不等式约束如x ek ，j k 或x k o ，s k 。，且它直接等价 于最优性条件本身，而不是等价于中心路径条件。然后我们用牛顿法求解这一非线 性等式系统该算法对初始点的选取没有任何限制，且是q r 二阶收敛的 二次锥规划的内点算法及光滑牛顿法 第二章二次锥规划的非精确不可行内点算法 本章主要给出了二次锥规划的一种基于a h o 方向的原对偶非精确不可行内 点算法该算法允许搜索方向有相对较大的误差，在求解大规模问题时可节省时间 和计算机内存在相对不精确的假设和不要求迭代点的可行性的条件下，利用该算 法可找到二次锥规划的占一近似解 2 1 引言 二次锥规划在实际问题中有着广泛的应用【1 1 ，【1 2 l ，例如雷达阵列设计，滤波器 设计等，故最近这个问题备受关注类似于线性规划和半定规划，原一对偶内点方法 也是求解二次锥规划的非常有效的算法 6 】，在原一对偶内点算法中，每一步迭代 都需要求解一个线性系统以得到搜索方向一般说来其计算量是很大的，特别当求 解大规模二次锥规划时，占用大嚣时间和计算机内存另一方面，由于在计算过程 中存在舍入误差，所以即使直接求解也不太可能得到绝对精确解因此我们考虑用 非精确搜索方向此外，现有的二次锥规划内点算法大多要求初始点的可行性，然 而许多实际问题难以找到初始可行解，所以不可行内点算法的提出是十分必要的 最近g u a n g l uz h o u i l s 】提出的半定规划非精确不可行内点算法对于二次锥规划 也适用，但是其初始点必须在某个最优解附近，而在没求解之前有时很难确定二次 锥规划的一个最优解，利用该算法解本文中的二次锥规划问题需经过 。o ( k 2l n ( 1 占) 1 次迭代才能找到s 一近似解 本章基于a h o 方向提出了二次锥规划的一种原一对偶非精确不可行内点算法， 并给出了求一近似解的迭代次数本算法不要求初始点及其迭代点的可行性，只要 每次迭代产生的点在不可行中心路径的某个邻域内即可且搜索方向是非精确的， 允许计算时有较大的误差，可节省计算机内存。而不影响算法的收敛性本算法只 需d ( 以l n ( 1 ，占) ) ( 其中打蔓七) 次迭代就可找到问题的s 一近似解，大大减少了迭代 的次数 本章做如下假设：( 1 ) f o ( p ) x f o ( d ) 彩 ( 2 ) 矩阵一= ( ，4 ) 的行向量是线性独立的 则由定理l _ 3 知，( 1 1 ) 和( 1 2 ) 都存在最优解且其最优值相等又由定理1 6 知解( 1 1 ) 和( 1 2 ) 等价于解 第二章二次锥规划的非糟确不可行内点算法1 5 其中 2 2 不可行中心路径 ( x o ，y o ，s o ) 是初始点，使得 x n 2s b 2p e ， 且p 0 为常数定义 p = ( q ，巳) r ，巴= ( 1 ，o ，o ) r ，i = 1 ，疗 胁= ：c 0 7 n = p 2 ， = a x o b ， ( 1 8 ) r 。= 爿7 y o + s o c = 驴地 p ； ( ? ，毛”) 且蝤x k o ii 1 血一b = 口r p o ，爿7 y + s - c = o r a o , x 。s = 印b e j 如果p ，墨y ，j ) p r o 斗0 ，则由( 1 8 ) 知红，_ y ，s ) 的聚点为原问题的解 = ( 口 v ，毛y ，j ) rx r + x k 。r ”x k o i v o ， 一x 一6 。曰( 月9 。+ 毒) ，i i 善i i o ，选择适当的，r ”使 得( 岛，v o ，x o ，y o ，而) n 给定当前点( 口，v ，x ，y ，j ) n ( 为方便起见，在此部分省略迭代次数j ) ，我们 给出计算新的迭代点p ) ，v ( 口) ，x ( 口) ，如) ，s ( 口) ) n 的思想可通过解如下线 性系统得到搜索方向( a x ，a j ，a s ) ： 其中 一臻r 。 一哺r 9 r r = ( 1 一仍) 啪e 一船， x = m a t ( x ) ，s = n m t ( s ) 定义 口( 口) = ( 1 一c ? 协) 口，v ( 0 0 = ( 1 一c r 珑) y ， x ( 口) = x + 口a x ，y ( a ) = y + a x y ， s ( 口) = s + 口厶s ( 2 4 ) = 、 x y j a a a ，。l 、， ，0 r 第二章二次锥规划的非精确不可行内点算法1 7 令新的迭代( 幺。1 1 k 。坼。y k 。+ 。) = 陬k ) ，唯 ) ，x k ) ，m 忙) ，& ) ) ，我们选择 口( o ，l 】使得( 日。，u 。黾。儿m & + t ) | 在实际求解过程中往往不能对( 2 4 ) 精确求解，因此我们可用非精确搜索方 向令 q ) 二是( o 1 】中的一个单调下降序列，使得孑q 0 为纯量，则 i i 一既 i 0 为纯量假定( “，r ) e x r ，h r 满足 定义 则 飘+ m = h ，u r t 0 ， 吒；弦甜| l ，4 - - - f a ， 恢x h l 私符希 点捌 。 l f ( 2 1 1 ) ( 2 12 ) 证明由( 2 1 0 ) 易得 d r r 。, d ( 1 一f ) v 8 d 1 2 ( 2 1 3 ) 把( 2 “) 中的第一个式子左乘x 并利用( 2 1 1 ) 的第二个关系式可得 “7 x 一1 s u u t x 一s k + u r t = 材r x 一1 h 令d = 矸u ，由上式，( 2 1 3 ) 2 2 疋，的定义知， ( 1 - r ) v 群= ( 1 一r ) v | 巧1 1 1 2 ( 巧1 ”) 7 如( 巧1 ”) = u r x 一1 s u s 矿x 一1 h = ( 巧1 “) 7 ( 瓦工一1 h ) - o ，满足 1 学l ( w 耵) 一v 阵， 则线性系统( 2 5 ) 有唯一解 证明设( “，q , v ) r x r 。形是与( 2 5 ) 相传的齐次线性系统的一个解，则有 f 爿= o a 7 冒+ v = 0 【妇+ 勋= 0 ， 由前两个式子可锝“7 v = 0 又因为 r 学i 掣( k ) - v 阵r v ， 则由引理2 2 知( 2 1 0 ) 成立，其中f = 3 ， 1 在引理2 3 中令厅= 0 ，可得”= v ：0 周此 a r q = 0 由于矩阵彳的行向量是线性独立的，所以9 = o 因此可得 二次锥规划的内点算法及光滑牛顿法 ( “，q ，v ) = ( o ，0 ，o ) ， 故系统( 2 5 ) 有唯一解 引理2 s 若( x ，y ，j ) n ，( a x ，a y ，s ) 是( 2 5 ) 的唯一解，则对于v 口r 有 巧1 工( 口) 。酗 ) 一v ( 口) 胁p = ( 1 一口) ( w 一竺引一一 佗1 钔 + 口( 阡名一尽盯) a x + 口2 a x 。j ， 、7 其中缸，血的定义为 x 誊7 7 1 厶z ，a j 暑c 6 s ( 2 1 5 ) 证明由( 2 5 ) 的第三个式子可知 s x + x a s = ( 1 一r & ) v # o e - x s ， 又由引理2 1 的( 2 ) 知x _ 1 e = e ，所以 i = t a s = l x 一 ( 1 一玑) v 胁e x s s a 苫 = ( 1 一玑) v 胁e k 一氏五 由引理2 1 及m a t ( x ) 的性质可得 所以 c 。x = 巧1 x e = x t e - - e l “x ( 口) 。t s ( 口) = 巧1 ( 工+ 口a x ) 。t x ( s - b g f z x $ ) = ( 厮) 。( + 口忑) = 屹+ 口( 蚝。磊+ i ) + 口2 磊。忑 = 心+ 口 ( 1 一巩) 啪e _ 以+ ( 呢一氏) _ + 口2 磊。五 将上式左右两端同减去v ( 口) 胁p ，整理可得( 2 1 4 ) 引理2 6 假定( x ，y ，s ) e ，其中，2 ( o ，1 3 ) ，令( a x ，a y ，a s ) 是( 2 5 ) 的唯一解，则 ( 2 1 5 ) 中定义的_ 五满足 其中 磊i 喀导，