（计算数学专业论文）边界约束凸二次规划的求解.pdf

南京航空航天大学硕士学位论文 摘要 本文主要研究边界约束f 定和半正定凸二次规划的求解方法。 用著名的s q p 方法求解非线性规划问题时，搜索方向的确定最终归结为求 解一个边界约束凸二次规划问题。我们考虑严格( 正定) 凸二次规划和半f 定 凸二次规划两种情形。对于严格( f 定) 凸二次规划本文结合已有的矩阵正则 分裂和向量投影的思想，提出了一个改进方法，并对正则分裂的参数选择进行 了讨论同时证明了改进方法的收敛性。半正定凸二次规划，由于奇异性很难 被求解。本文结合矩阵c h o l e s k y 分解和分枝定界思想，给出了一个求解半正定 凸二次规划问题的新算法。文章证明了算法的收敛性，并讨论了算法具体典现 步骤。 本文最后给出了两种方法的数值实验，结果表明这两种方法是有效的。 关键词：凸二次规划， 正则分裂，投影，c h o l e s k y 分解，分枝定界 边界约柬凸二次规划的求解 a b s t t a c t t h i s p a p e r s t u d i e st h em e t h o d sf o rb o u n d e dc o n s t r a i n e dc o n v e x q u a d r a t i c p r o g r a m m i n g i nw e l l k n o w ns q pm e t h o d sf o rn o n l i n e a rp r o g r a m m i n g ，t h es e a r c hd i r e c t i o ni x t h es o l u t i o no fab o u n d e dc o n s t r a i n e dc o n v e xq u a d r a t i cp r o g r a m m i n g w ec o n s i d e l s t r i c tc o n v e xq u a d r a t i c p r o g r a m m i n ga n dp o s i t i v e s e m i d e f i n i t ec o n v e xq u a d r a t i c p r o g r a m m i n g f o rt h ef o r m e r , t h i sp a p e rp r o p o s e dt h em o d i f i e dm e t h o dw h i c h c o m b i n e sr e g u l a r s p l i t t i n ga n dp r o j e c t e ds e a r c h t h ec o n v e r g e n c eo f m o d i f i e dm e t h o d i sp r o v e d f o rt h el a t t e r , t h i sp a p e rc o m b i n e s c h o l e s k yd e c o m p o s i t i o na n db r a n c ha n d b o u n d ，a n d d e v e l o p s am e t h o d f o r p o s i t i v e s e m i d e f i n i t ec o n v e x q u a d r a t i c p r o g r a m m i n gt h ec o n v e r g e n c eo f t h i sm e t h o di sp r o v e d i nt h el a s tp a r to ft h i sp a p e r , n u m e r i c a lr e s u l t sf o rt h et w om e t h o d sa r eg i v e i l a n dt h e s er e s u l t ss h e wt h a tt w om e t h o d sa r e e f f e c t i v e k e y w o r d s ：c o n v e xq u a d r a t i cp r o g r a m m i n g ，r e g u l a rs p l i t t i n g ，p r o j e c t i o n ，c h o l e s k y d e c o m p o s i t i o n ，b r a n c ha n db o u n d 承诺书 本人郑重声明：所呈交的学位论文，是本人在导师指导下，独膏。 进行研究工作所取得的成果。尽我所知，除文中已经注明引用的内容 外，本学位论文的研究成果不包含任何他人享有著作权的内容。对木 论文所涉及的研究工作做出贡献的其他个人和集体，均已在文中以明 确方式标明。 本人授权南京航空航天大学可以有权保留送交论文的复印件，允 许论文被查阅和借阅，可以将学位论文的全部或部分内容编入有笑数 据库进行检索，可以采用影印、缩印或其他复制手段保存论文。 作者签名：主醒童： 日 期：塑区：il 南京航空航天大学硕士学位论文 1 1 问题的来源 第一章基本知识 二次规划是一类非常重要的非线性规划，它既有广泛的实际背景，又有重 要的理论研究价值。当今非线性规划的发展趋势是把许多非线性规划转化为序 列二次规划进行求解。二次规划作为子问题出现在一般非线性规划的算法中， 二次规划算法的好与坏，直接影响到非线性规划算法的好与坏。本文主要针刈 文献 1 】中提出的二次舰划子问题进行讨论。我们考虑文献 1 中的非线性舰划刚 题 m l n ( n l p ) s t ( x ) g ，( x ) = 0 g ，( x ) = 0 j = l ，巩 = m e + 1 ，m 用s q p 方法求解这类问题时，通过解如下的二次规划子问题 m i n 1 d r b d + v f ( x ) 7 d 1， ( q n s t 吲x ) 7d + g j ( x ) = 。m 一，m 。 v g ，( x ) 7d + g ，( x ) o，= + 1 ，m 产生一个搜索方向，其中b 是l a g r a n g i a n 函数( t “) = ，( x ) 一芝“，( x ) 的 h e s s i a n 矩阵的n i 定近似，“是( n l p ) 问题l a g r a n g i a n 乘子向量的近似。 将积极集法应片j _ 于( q p ) 问题可得对偶二次规划问题 ( d q p )嘶n m 。+ c ( x ) i s , t 打0 ， 囊：巾 边界约求凸二次规划的求解 a 。= 乏；：； b 。 爿ic x ，7 ，一：c 一， ，cc x ，= 三 ：； 一 置 ：； 口。v ，1 c 膏，西= 爱 d ，( x ) = ( 譬l ( x ) ，- 一、g 。( x ) ) 7 r ，爿( x ) = v g ( x ) ，- 一，v g 。( x ) ) 。r ”。r ” 口：( x ) = g 叫( x ) ，民( x ) ) 7 r 帆爿：( x ) = t g v ( x ) ，v g ( x 1 ) 。e r 足 ，( 删) = ”，。，k ) = ( 1 ，m 。 u ：cj s 州，g ，( x ) s ；或者v i 2 = k 一，k j i 二( x 、v ) ： 1 ，m ”，( x ，v ) + v ：( ”一，匕) 7 是l a g r a n g i a n 柔子向量， ，2 ( 小) 是罚参数向量，满足0 m 。成 g ，( x ) 0 ，其中x 是最优解，i ，r 。，i ，驴”。 容易看出，经过对偶变换以后形成的是具有简单边界的凸二次规划。 本文针对上迓问题进行讨论和研究。并提出了一些新的算法。本文主要自 三章。第一章讲述与研究相关的理论和知识。第二章主要总结了严格凸二次规 划的求解方法并且在此基础上给出了一个结合矩阵分裂和投影的方法。第三章 总结了一般凸二次规划的求解方法，讨论了无界域上一般凸二次规划最优解的 存在性，并且根据已有的凹二次舰划的求解给出了一种适合一般凸二次舰划的 分枝定界法。 1 2 预备知识 本文主要考虑以f 形式的简单边界约束凸二次规划问题 n l j n ( x ) = 当x 7 a x + 6 7 z s t，工“。 南京航空航天大学硕士学位论文 其中a 尺为对称半正定矩阵，b r ”，x r “a 12 1 正则分裂及投影 下面我们引用文献 3 3 3 4 3 5 3 6 中的正则分裂定义。 定义1 ：假设a r 是对称矩阵。如果 ( 1 ) a 铆， ( 2 ) d - h 是对称正定矩阵， 其中d ，r ”“，则( d ，功称为a 的一个正则分裂。 考虑计算的简便，在实际中一般取d 为对角阵。为了保证得到a 的一个正 则分裂，可以取d = d i a g ( d i ) ，其中d ；= ， 表示爿的第i 行第，列元素。 j = l 在第二章算法执行的过程中为了保证其每一步的可行性，在获得每一个最 速下降方向后，需要通过如下投影公式获得一个新的迭代点： it 如飘 蚝 i = 1 ，。从这个公式可以看出，获得的新的迭代点的分量如果在可行域内则 不变，但是如果超出了可行域，就将其投影到可行域的边界上。从而既实现了 算法的最速下降又保证了算法每一步的可行性。 从文献【7 【8 】【9 】【2 1 】【2 2 2 3 】提到的投影方法中还可以看到投影法能够快速 找到最优的积极约束，每次迭代可以改变多个有效约束，从而提高了算法的收 敛速率。但是在算法的执行过程中每个迭代点都必须为内点，使算法失去了很 大的灵活性。而文献【2 】 1 0 】【1 1 】中提到的分解方法能够将要求解的二次规划问题 的目标函数化为对角形式，但是由于文章中约束为线性约束，没有充分利用分 解后所产生的这一特殊形式，因而使得算法没有达到最好的效果。 在本文第二章中我们结合上述提到的投影方法和正则分裂技术提出了求解 一类具有简单边界约束的二次规划问题新算法。这个新算法既充分利用了投影 方法的快速收敛性，又充分利用了正则分裂方法在几何方面所表现出来的特点， 使得这个算法能适合稍大规模问题的求解。 边界约束凸二次规划的求解 12 2c h o i e s k y 分解 对于正定矩阵4 的c h o l e s k y 分解算法文献 3 中有如下描述 d ( i ，f ) = 觚f ) _ d ( s ，s ) l o ，s ) 2 ， 驯) = 而1 ( 删) _ 霎卿w 一蜘) j f v l ( 1 3 ) 在讨论半正定矩阵a 的c h o l e s k y 分解之前首先给出文献【3 2 7 中的一个相 关结论。 s i 理1 如果4 是秩为，的半正定矩阵，则存在一个排列矩阵 p = ( 勺m ，e p ( 。) ) 使得p r p = 口成立，而且具有下面唯一的形式 三= 雕 其中厶。r 是对角元素为正的下三角阵 根据引理1 - i p a 得到半正定矩阵p 7 a p = 上r 分解式的基本框架如下： o = ( 口。- e l ：) i ， ( 1 4 ) 若l i 0 ，则 上j = ( d 一工* 上一) z “， ( 1 5 ) 否则l = 0 目前对于半正定矩阵的c h o l e s k y 分解已经有很多方法，详细可以参见文献 2 7 。 1 3 本文的工作 本文主要讨论在用s q p 方法求解非线性规划问题时所形成的二次规划子问 题，该子问题是一类具有简单边界约束的凸二次规划子问题。本文主要讨论严 4 南京航空航天大学硕士学位论文 格凸二次规划和半正定凸二次规划问题，共分成下面四种形式： m i n f ( x ) ：1 x r a x + b 7 工 s t ，x u ， ( 1 6 ) 其中4 正定， r a i n 厂( 工) = 去，a x + b 7 石 s tx 0 ( 1 7 ) 其中爿正定， m i n ，( x ) ：昙x r a x + b r 石 s t ，j u ( 1 8 ) 其中a 半正定， r a i n 厂( j ) = 妄j a x + b o s t x 0 ( 1 9 ) 其中a 半正定。 对于严格凸二次规划，本文主要结合矩阵的正则分裂和投影方法产生了一 种适合稍大规模问题的算法。投影方法是比较看好的方法，在很多文章中都有 过应用，但是大部分的文章在用投影方法时往往是与积极集法结合，每次迭代 改变的变量并不是很多。本文从大规模问题入手，采用矩阵的正则分裂技术使 问题( 1 6 ) 转变为一种特殊的形式，然后采用投影方法，使得每次迭代后问题 的规模迅速变小。对于问题( 1 7 ) 只需将求解问题( 1 ，6 ) 时的投影公式改变一 下即可，本文第二章将详细讨论求解这类问题的方法。 对于半正定凸二次规划问题( 1 8 ) ，由于目标函数中二阶导数矩阵存在0 特 征值，因此求解比较困难，目前还没有比较有效的算法。本文基于矩阵的c h o l e s k y 分解，首先给出了半正定矩阵的a = l d l r 形式的分解，然后对( 1 8 ) 进行了一 定的变量替换，产生了一个新的问题。该新问题具有部分可分形式。借用凹二 次规划求解思想，本文对产生的子问题，采用线性插值逼近和分枝定界思想来 求解。从而通过求解一系列的线性规划子问题来获得( 1 8 ) 的近似解。对于问 边界约束凸二次规划的求解 题( 1 9 ) ，在确定有解的情况下采用上述类似的方法进行求解。本文第三章讨论 这些问题。 塑室堕至壁墨查兰堡圭主堡堡苎 一一 第二章严格凸二次规划的求解 2 1 引言 问题( 1 6 ) 称为严格凸二次规划。对于这类问题，已有不少算法。 其中有些 算法要求迭代点为内点，并用有效集策略把原问题化为等式约束问题来求解。 这类算法有投影方法，见文献【7 】【8 【9 【3 0 】；分解方法见文献【2 【1 0 【1 1 】；道路 追踪法见文献 2 9 1 ：二次样条法见文献u 3 等。这些算法在每次迭代时改变个 或多个有效约束，不同程度地提高了算法的收敛速率。 本文所提出的算法不要求迭代点为内点。因为凸二次规划是线性规划向，仆 线性规划的自然过渡，所以它与线性规划有许多相似之处。另一方面，由j j 凸 二次规划目标函数的等值面是超椭球，因此最小值点位于约束函数界面和超椭 球相切点处。本章将结合f 则分裂法使得问题( 1 6 ) 所形成的子问题的目标函数h 有一种特殊的对角形式，在求解浚予问题时充分利用这一特性，就可以迅速的 找到子问题的最优解，然后通过一系列该类型子问题的解来逼近问题( 1 6 、的最仇 解。 2 2 严格凸二次规划的典型方法 对于问题( 1 6 ) 的求解主要有积极集法、子空间投影共轭梯度法以及分斛 法等，这些方法各有特色。下面我们对其进行简单地介绍。 一积极集法 1 9 8 9 年m o r e 和t o r a l d o 在文献 8 】中提出了积极集法。该方法将标准积极 集法和梯度投影法相结合来求解边界约束二次规划问题。所谓标准积极集法足 通过积极集柬确定一个工作集，其中积极集为4 ( x 。) = i ：x = 0 j ，工作集满 足岷亡a ( x k ) 。然后求解子问题m i n g ( 耳+ d ) ：一= o ，f 的全局最优点c ， 得到下一个迭代点为t “= 耳+ c t k d k ，其中必须满足x k + 吒以0 。这种积极 集法能够在有限步内终止。为了减少计算量，文献 8 】把以所在的可行域的面定 义为 x ：，曼x ，一= o ，i 吼 ，而在计算下一个迭代点+ l 时，采用梯度投 影法。通常所用的投影公式为 边界约求凸二次规划的求解 如果一 “， 然后通过投影搜索_ + = p x 。一口。v q ( x k ) 得到耳矿文献【8 中还详细介绍了的 选取以及投影法的具体实现。 二空i 割投影共轭梯度法 文献 7 中提出了子空间投影共轭梯度法。在该方法中，共轭梯度法用来校 f 非积极变量，而投影梯度法用来校正积极变量，在每一步迭代中，搜索方向 由两部分组成，一部分是予空间截断牛顿方向，另一部分是修萨梯度方向。 算法s p c g 步1 ：确定搜索方向，浚搜索方向主要由子空间截断牛顿方向( 校f 自由嵌 量) 和子空削梯度方向( 校正积极变量) 组成。 步2 ：用投影搜索法确定步长口。 步3 ：确定新的积极集。 三分解法 分解法首先对问题( 1 6 ) 进行预处理，即对问题( 1 6 ) 中的矩阵a 进行分 解。目前主要有两种分解途径。 1 、在1 9 9 9 年文献 1 0 o e 提出了边界约束二次规划问题的分解方法，浚方法 主要是从( 1 6 ) 的t a y l o r 展式中得到一个予问题，通过该子问题可得到搜索方向。， 具体过程如下。 首先根据1 2 1 中的理论不妨设a = _ d + 日，则： f ( x ) = f ( x + ( x x ) ) = 厂( ；) + g ( ( x 一；) + = 1 ( x - 矽一( x 一- i ) = 瓜) + 妻( x 一矽j d ( x 一- ) + 9 7 ( x 一；) + i 1 ( x - ；) r h ( x - - ；) 其中g = g ( x ) = a x + 6 。令 南京航空航天火学硕士学位论文 妒( e ；) = 厂( - ) + 当( x 一为7 d o 一7 0 + 9 7 ( x 一；) 假设f d ，h ) 是a 的一个正则分裂，则有下列计算过程。 设x 是第k 步迭代点，s 0 为允许误差，执行下列计算 步1 ：令x = x ，求”= a r g m 弹妒( x ；) ，其中q = f x 掣：挺x s “ 是可行 r i 、 j 域。 步2 ：若肛“一x i s ，则终止算法，+ 5 是( i 6 ) 的一近似解；否则令 七= t + 1 ，转步i 。 2 、s a 以及s s a 算法 文献【1 1 】中提到的s a 算法是直接从目标函数矩阵的币则分裂形成算法。 而s s a 算法是改进的s a 算法。主要差别是在求子问题后，不是以子问题的蛳 作为下一个迭代点t 而是增加了一个选择步长的措施。设一= d + h 为f 则分裂 我们介绍s a 和s s a 算法如下。 s a 算法 步1 ：令x o 是初始可行点，女= 1 。 步2 ：解予问题 1 m i n 厂( x ) = 妻x 7 d x + ( 6 + 胁叫) 7 石 上 s t c x d ， 得x 。 步3 ：如果r 满足终止准则，则停，否则= 七十i ，转步2 。 s s a 算法 步1 ：令y 是初始可行点，= 1 。 步2 ：解子问题； 1 r a i n 厂f x ) = x 7 d x + ( 6 + n y ) 7 x s t c x d 边界约嫩凸二次规划的求解 表示其唯一解。如果( 砂+ 6 ) 7 ( 一y k ) 坼 ， 得x 。具体算法如下。 算法2 1 ( 求解问题( 1 6 ) ) 步o ：( 初始化) 选取x o r ”k = 0 。选取一个i e n 分裂a a 抖| v ，其中胁，v f 定，m 为对角阵。 步1 ：用上面的方法求子问题： m i n ，( x ) = 妻x 7 m x + ( 6 十( 爿一吖) x ) 7 z s t ，x s “，( 2 3 ) 得解为x “l 。 步2 ： 判断终i 条件。如果肛“1 一x 2 | c s ，则停止；否则令k = k + 1 转步l 。 南京航空航天大学硕士学位论文 如何选择算法21 步0 中的正则分裂，将在后面作详细讨论。现在我们先 讨论算法2 1 的收敛性。由线性代数知识得下面引理。 引理2 2 设a 为对称正定阵，并且满足a = 舟，m 是正定对角阵，m 为f 定阵，则p ( m “n ) l 。 一三一! 证明：因为是对称阵，m 1 与m2 n m2 相似，并且 m 一7 n m j = m j f 爿一m ) m i = m 一7 a m i 一， 又因为m 一7 a m j 是_ f 定阵，所以m 一。n 的特征值大于一1 。此外，同理有 一m ! n m2 = j m2 n m2 一f 一! 一! = m 2 ( 吖一n ) m2 一j ， 因m 一_ 正定，所以一m 。的特征值也大于一1 。综合可知：p ( m 。n 1 1 证毕。 定理2 3 设a 为对称正定矩阵，a = m + n 是a 的正则分裂。其中m 是对角 正定矩阵，那么对于任何初始点工。，由算法2 1 产生的序列& * 线性收敛到问题 ( 1 6 ) 的唯一解。 证明：由a 和m 的f 定性，可知问题( 1 6 ) 有唯一的解z ，算法2 1 第k 步中 问题( 2 3 ) 有唯一解x “1 。从面可知对于任何向量x o ，由算法产生的序列k 是 唯一确定的。由于+ 是( 1 6 ) 的最优解，因此一阶最优性必要条件成立，即 1 ，( x ) 。( 工一x + ) 0 ， 对于问题( 1 6 ) 的任何可行点x 成立。因此有 ( 4 x + 6 ) 7 ( x 一x ) 0 ， ( 2 4 ) 其中x i 是算法2 1 第0 步中问题( 23 ) 的解，因此也是问题( 1 6 ) 的可行点。又 因为x + 也是问题( 2 3 ) 的可行点，而问题( 2 3 ) 在x 1 有一阶最优性必要条件为 - 0 ， ( 2 6 ) 忖一r | f ；，s ( 一。) 。v ( x l x ) = ( x + 一x 。) 7m m “2 n m “2 m ( x 1 一x ) ( 2 7 ) s 0 x x 。j i ，| i x 一x 1 j 。i i m 。“n m 。”j i ： 由于爿州十是证则分裂，m “2 n m “2 相似于m n ，根掘引理p ( m ta ，) 1 因此，p = p ( m “) = i i m 2 n m “! i | 2 l 。从( 2 7 ) 可得： i 卜一j 。i ，sp i i x 一x 。f i 吖 同理可证( 2 8 ) 对于x 也成立 4 x 一x “，p i x 一x n ，- t - p 。f f x 0 - - x n ， ( 2 8 ) ( 2 9 ) 因为p 收敛到0 ，因此当女呻m 时，x k 收敛到x 。证牛。 考虑一种诈则分裂a = m + na 设爿的特征值为 以 ， 丑， m = ( 去t r ( 爿) ) ，。要选取参数t 使得m 正定，并且p ( m 一，) 尽可能小。直线 计算得肛= 2 m - - a 的特征值为昙t r ( 爿) 一丑，f _ l ，2 ，玎。要使肛正定，则寥 数k 需要满足 南京航空航天大学硕士学位论文 0 2 t r ( a ) 。 p ( 爿) 由计算得烈们“) 2 m a x m 。j 1 _ 羔j a 要使p ( “) 尽可能小，则取 = 雨2 t r ( a ) 嬲看出丽2 t r ( a ) 半= 筹a 删凇州葫足 + ， + 以， ，p lj 0 七 2 t r ( a ) + 在实际计算中可以适当估算出矩阵的最大最小特征值的界，就可以找出收 敛速度较快的诈则分裂，从而找到求解问题( 1 6 ) 的有效算法。 考虑问题f 1 7 ) m i n 八班吉x t 血+ 6 7 x 其中a 正定。我们只需将算法2 1 中步1 的求子问题( 2 3 ) 时所用的投影( 2 2 ) 改 为 ，： ? j ：o 即可。 【暑暑0 ” 下面我们讨论诉则分裂的几何意义。以二维为例考虑如下图。 幽2 i 问题( 1 6 ) 图2 2 子问题( 2 3 ) 望墨丝墨鱼三姿塑型塑查塑 图21 表示( 16 ) 所要求解的问题，由于a 为一般的对称正定矩阵，因此所 对应的超椭球的对称轴与坐标轴不一定平行。算法2 1 中步1 是对无约束二次引 标函数求最小值后进行投影。从图2 1 中可以看出没有进行f 则分裂由投影求出 的最优解x 不等于( 1 6 ) 的最优解x 。图2 2 表示正则分裂后子问题( 2 3 ) 所对 应的图形，由于m 为对角矩阵，从几何图形可以看出这时所对应的超椭球的对 称轴与坐标轴平行，经过计算所得的最优解x 等于( 2 3 ) 的最优解x 。算法 2 1 的基本思想是把一般严格& - - 次规划边界约束问题化成一系列可分的对角形 二次规划边界约束子问题。 2 4 数值试验 以下数值试验均在c 4 1 7 g ，r a m 为2 5 6 m 的微机上用m a t l a b 6 5 编程实现。 表中n 代表问题的维数，t i m e 是算法2 1 运行过程中c p u 的运行时间( 以秒汁) ， i t e r a t i o n 是迭代次数。为了观察矩阵不同的正则分裂对算法2 1 的影响，由上研 m = 丢t r ( 爿) ，的选取分析可知= 署竿等时收敛速度最快，在数值试验时数值 算例我们选取由固定特征值生成的随机矩阵，首先取特征值均在( 0 ，1 1 范围内的 对角阵。= 螈，吉) ，然后与随机产生的h o u s e h o l d e r 雠肚t 2 u u i r 名i i 合得到实对称f 定阵a = p d 尸7 ，由子程序m a t r i x f o u n d e d 3 ( n ) 实现。容易看出划 于不同规模的问题当：胃2 t r ( a ) ：等嫂时算法2 i 收敛速度最快，以下将通过 十 三4 - 1 不同k 的选取来进行比较，由于m a t l a b 语言精度的限制，在数值试验时我们l 进行到n = 1 0 0 0 ，取控制变量s = o 0 l 。 表2 1 问题( 1 6 ) 执行情况 n项目 k = k ok = 0 9 k = 0 8 k ok = o 7 k o女= o 6 k 。 t i m e0 0 4 0 0o 0 5 1 00 0 3 0 00 0 3 0 0o0 5 0 0 5 0 l i t e r a t i o n9991 012 】 壹銮堕皇堕盔盔堂堡主兰垡堡壅 表2 1 ( 续) t i m e0 1 4 0 0o 1 7 0 0 0 1 8 0 00 2 0 0 00 3 1 0 0 il 。 i t e r a t i o nl o1 21 3 1 41 4 t i m e0 4 1 1 0o 5 2 1 0o 5 0 l oo 7 2 l o06 1 1 0 2 0 0 i t e r a t i o n1 21 31 21 91 6 y i m e4 7 1 7 05 7 5 8 06 8 2 0 07 5 0 1 082 2 2 0 5 0 0 i t e r a t i o n1 2151 82 02 l t i m e2 2 3 0 2 02 6 2 9 8 03 1 4 6 5 04 0 8 1 9 0 2 8 8 5 1 0 8 0 0 i t e r a t i o n1 61 92 33 02 1 t i m e4 3 8 3 3 05 5 9 9 1 06 5 6 0 5 07 58 3 9 0 8 5 0 8 2 0 1 0 0 0 i t e r a t i o n1 72 22 63 0 3 4 从上表可以看出算法2 1 随着问题规模的增大迭代次数变化不是很大，也可 以看出正则分裂时对角矩阵m 的选择十分重要，当k = 七。时对于不同规模的问 题，无论是运行时间还是迭代次数都是比较好的。 丝墨丝坐曼三鲨塑型塑銮堑 一一一 第三章一般凸二次规划的求解 3 1 一般凸二次规划的典型方法 对于问题( 1 8 ) 目前已经有一些求解的算法，如通过对目标函数的h e s s i a n 阵增加一扰动项使其变为严格凸二次规划问题 1 m i n f ( x ) = - g - x7 ( a 十c k ，) x + ( b c k 工。) 。z 二 s t，x s “ 以及一系列矩阼分解的存储和校币方法，整标集方法等。但是这些方法都有 定的局限性，计算量大是一个主要问题。内点算法通常又称为严格可行内点算 法，原因是算法从一个严格可行初始内点开始迭代，产生一系列严格可行内，矗， 这种对迭代点的严格爱求给算法的实现带来很大的困难。为了克服可行内点算+ 法的不足。从9 0 年代仞开始了不可行内点算法的研究。不可行内点算法虽然已 经有了多项式时恻算法，但是该算法只能有效的求解一类特殊的问题。由于当4 为半正定时，问题( 1 9 ) 存在无解、多锯、以及唯解的多种情形，因而如果 能事先对( 1 9 ) 的解的情况有所了解往往会达到更好的效果。本章将主要参考应用 在凹二次规划问题上的分技定界法的思想，荠结合矩阵的c h o l e s k , j 分解束求解 问题( 1 8 ) ，并且在判断( 1 9 ) 有解的情况下给出其相应的求解方法。下面首先介 绍目前已有的求解一般凸二次规划问题的算法：内点法、不可行内点法、分枝 定界法，分解法，对偶积极集法等。而对于解大规模非凸二次规划的一些方法 可参见文献 3 2 1 。 一内点法以及不可行内点法 在内点法中用得较多的是仿射变换法和原始对偶法。文献 1 4 1 5 】 1 6 儿2 8 】【2 9 】 3 1 】中主要讨论了内点法和不可行内点法。 仿射变换法是在算法的每一步求解一系列球( 椭球) 约束的二次舰划问题， 即将一个一般约束的问题转化为个容易求解的问题。但是浚类算法要求可行 域是有界的。 原始对偶法就是通过二次规划原问题及其对偶问题的k t 点获得一个力 南京航空航天大学硕士学位论文 程组，在解此方程组的情况下获得搜索方向，从而获得新的迭代点。该类算法 由于需要求解方程组因此计算量有时候也是相当大的。 不可行内点法也是内点法，由于它放宽了对初始点x 的选择要求，因而具 有很大的灵活性，尤其适用于初始可行点不好寻找的情况，同时由于z 的选择的 自由性，可能会使算法变得复杂。 二分枝定界法 文献【1 7 18 】 3 7 3 8 】 3 9 】 4 0 中主要讨论了分枝定界法。目前，分枝定界法 主要用于简单边界约束的情况。该类算法主要是对边界约束所形成的区域进行 分割。通过这区域的外接球( 椭球) 和内切球( 椭球) 来逼近原可行域。出 于球约束二次规划问题实际上是非线性优化中信赖域方法的一个子问题，埘它 已经有了较为广泛的研究，产生了很多实用的算法，因此可以充分利用球约束 二次规划问题的现有算法来求解问题( 1 8 ) 。 三其它方法 文献 1 9 】中讨论的数值稳定方法实际是半正定二次规划问题的积极集法，该 方法通过一系列矩阵分解的存储和校正，较好的克服了半f 定矩阵奇异性带来 的数值求解的困难。另一类算法主要是通过目标函数的h e s s i a n 阵增加一扰动项 使半正定问题转化为f 定问题。在文献【1 】中求解二次规划子问题时用到的主要 是这种方法： r a i n f ( x ) = 去x 7 ( a + c i i ) x + ( b c x 。) 7 x o s t工0 经过这样的转换原来的凸二次规划变成了严格凸二次规划。在用这类算法求解 时效果不是很理想，主要是由于在半正定时，问题( 1 9 ) 的解不唯一。无解、多解、 唯一解的情况都存在，而转换后的严格凸二次舰划只有唯一解。尽管为了使得 转换前后两个问题非常接近可以任意小的调整q ，但还是没有达到理想的效果。 文献 1 2 】中提到的对偶积极集法主要是将g o l d f a r b 和i d n a n i 在1 9 8 3 年提出 的求解证定二次舰划的思想推广到了半正定的情况。 除了上述些方法以外还有罚函数法、非线性可微罚函数法【4 2 】等。本t 主要是在现有的求解凹二次规划的分枝定界法的基础上，结合矩阵的三角分斛 边界约束凸二次规划的求解 给出- 9 十不同于上述方法的分枝定界算法。 3 2 新方法 对于一般半正定二次规划问题，由于其解的复杂性，我们参考文献 43 5 6 的思想t 首先通过对问题( 1 8 ) 中目标函数的h e s s i a n 阵进行c h o l e s k y 分解， 化成部分可分的形式，然后用分枝定界法来求解。 对于问题( 1 8 ) ，根据1 2 2 中半正定矩阵的c h o l e s k y 分解对其进行预处 理t 不妨设由c h o l e s k y 分解得a = l d l 7 ，其中三为单位下三角阵，d 为对角阵， 上= 上 j上们 d = o o 如果令j ，= x ，则问题( 1 8 ) 变为： m i n 厂( x ) ：三y r d y + ( z - t 6 ) ，y s t ，l - 7 y s “， 如果令1 5 。b = c ，l “= b 则上述问题变为： m i n 厂( x ) = 三y r d y + c r y s t ，砂s “， ( 3 1 ) 下面主要讨论( 3 1 ) 的求解过程。 由于d 为半下定阵且可行域有界，所以( 3 1 ) 解是存在的。 将( 3 1 ) 中的矩阵和向量进行分块 0l 南京航空航天大学硕士学位论文 d = b = 吐l - 一，j “1 卜。 1 ：引。b l ，i l 一+ l _ t 贝t j ( 3 1 ) 式可以写成 问题( p ) ：m i n 妒( 只，见) s t ( 一，只) q ”= c ， c r + l = 瞄小= 悟 = 团 ：闭。： l ，2 j 其中：妒( 多，兄) = 矽( 多，) + 只，( 多，) = 哿歹。+ 丢拜d i ) 5 1 ，日f 定 y ， y ，+ 1 ) ? “ “， 甜，+ i = 斟 = 豳 q = ( 只，豆) ：f 骂曩+ b 见羁五s 歹：- 5 ： 我们定义2 r 个l p 子问题： 益= m i n 夕l _ ( 只，兄) q ( f = 1 ，) ， ( 3 2 a ) 专2 m a x 罗：“：( 歹。，夕：) q ( i = l ，r ) ( 32 b ) 如果令只2 ：+ 主，即：| = 歹 “一曼，其中z r ，令屈= 手，一夤，：1 ，则雨 问题( s p ) ： m i n 痧( ：歹：) = 歹( ：) + 霹兄 s t ( = y 2 ) 磊，z b ， 其中 阳h = 边界约求凸二次规划的求解 万( z ) = 吼( ) ，吼( 互) = ( t + z ，当) t + i 1d 。彳，f = 1 ， r z = ：0 = ，屈，i = 1 - ， ， 五= ( = ，j ! ) ：f 一日圭b i z + 最歹：s i 。一旦圭丘s 歹：i ： ， 同时我们有 ( ：+ 圭，见) = i f ( 毛歹：) + f 圭+ i 1 圭7 q 圭 令 其中 r ( ：) = 一( 0 y 心? ? 卜迂啪托堪心z j 一誊或 ( 3 3 a ) ( 3 3 b ) ( 3 3 c ) ( 3 4 a ) 是吼c 列在 o 屈】上的线性逼近，它是过( 譬，三以( 譬 2 + ( t + 一考) 譬 点，斜率 等于两边界点连线的斜率的一条直线，则问题( s p ) 的最优目标函数值的下界 为下列线性规划问题。 问题( l u ) ： m i n 中( ：，歹2 ) = r ( ：) + 兄 s , t ( ：、多：) 最，= r z ， 容易看出，矿( = ，歹! ) 中( ：，只) ，对于所有( z ，歹2 ) 磊，z r ，成立。因为 万( ：) 一r ( ：) 2 喜( 玑( 互) 一一( 磊) ) = 兰喜( z ，( 暑一圭属) 2 。 问题( l u ) 的求解可以近似代替问题( s p ) 的求解。令痧表示问题( s p ) 的最优值， ( ：+ 或) 是问题( l u ) 的个最优解点。那么有： r ( ：+ ) + 歹：茎妒+ 歹( ：+ ) + 或= 矿( ：+ ，兄) ，定义e ( z ) = 歹( ：+ ) 一r 1 ( ：+ ) 可以肴 南京航空航大大学硕士学位论文 出 妒p ，或) 一妒+ e p ) ( 35 ) 当( ：) 充分小时矿( ：，多；) 可以看成问题s p 的全局极小值矿的可接受的 近似值，而( 2 + 一歹；) 是对应的近似全局极小点，从而l z + 圭，歹：) 是问题p 近似全 局极小点。 现在我们来推导( z + ) 的上界。 吼( 弓) 一y ( ) = ( q + z ，当) + 吉z ，z ? 一( 圭矗属+ q + z ，五 + ；一，屈! = 引一纠， 很明显当= 时取得最大值。不失一般性，假设一p - 如历砖，则 p = 筹虬h ，r ( z ) = 歹( = ) 一r ( z ) ；喜谚，群= ；碣，群喜屏， c 。剐 因此e ( ：+ ) 吉函群b o 一i 实际上( ：) 与万( ：) 在史。上的变化范围有关。下面我们首先看一下石f ：) i ! 。 变化情况，然后给出e ( z ) 与歹( z ) 在r ：上的变化范围之问的关系。 令无。= m a x 歹( ：) ：z r z ，无。、- - m i n 万( z ) ：z r ： ，则歹在足：( 见( 3 3 a ) ) 上的变化范围是 无。，j ：、。、 。首先，确定 = 瓦。一无m ， 鲨墨丝坐璺三姿塑型塑查塑一 前面己假设“所如廖厶群，从而只= 毒筹l ，f _ 1 ，h 函数 玑( i ) 在点 掣 ( 3 7 a ) f - 1 ，r ，取到其无约束极小值。当i 【o ，尼】时，矿的下界依赖于i 和 o ，屈】 的中点之间的距离f p , 2 l ，可以用 一i n 惰一，n ( 3 7 b ) h ，慷示这种依赖性。这旱呦，虬并且研= 防卜仅当纠啪 引理3 ，d l i , 口1 2 喜一( + 仇) 2 = 司 证明：对于1 i ，令i = m a ) ( g ，( z ，) ：o 乙屈) ，q 。= m i n q ，( 暑) ：o 属 ， 玑= 百一g ，需要考虑下列4 种情形。 ( 1 ) i 【o ，屈2 】，则从( 3 3 a ) ，( 3 7 a ) 和( 3 7 b ) 得 吼( 屈) ：一屈f ；屈一i o ，生= 吼( i ) ，i = 吼( 屈) ，i = j 1 届一j 1 屈，7 因此我们有 吼= i 一生= 圭一，( 属一i ) 2 = d r i f t , 2 一( 1 + 啊) 2 ( 2 ) i 【2 】，- q ( 1 ) 同理有 南京航空航天人学硕士学位论文 于是 吼( 屈) = 矿，屈( 吉屈一i j 。，i = 吼( 。) = 。，生= 吼( i ) ，i = 吉屈+ 圭屈- 姐= 孑一生= 扣i 2 = i i d ，。屏p ( i + 矾) ( 3 ) z ，- 0 步2 ：求解l p 子问题( 3 2 a ) 和( 3 2 b ) ，i = 1 ，计算旷( ：o ，篼) 的值，令 o p t = 矿( ：”奠) 步3 ：求解问题( l u ) 得解( z ，罗；) ，计算庐( 具体计算见引理3 1 的汪明) 步4 ：若妒( z + ，歹；) c o p t ，置叩，= 妒( z + 。弼) 步5 ： o p t r ( ：+ ) 一兵如妒，则停止 步6 ：否则，对砭适当剖分后( 具体剖分见下面说明) ，转步3 说明：在算法3 3 步6 中对r z 的剖分过程具体如f 。在区i h j 【o ，屈j ，i = 1 ， 中选择一个，比如满足尼2 。m a x ，3 ，将区间【o ，属】对分成 o ，屈2 】和 2 ，屈 ， 这样就把r z 剖分成体积相等的两个矩形。将q ，( ：，) 的线性逼近 ，1 、， 只( 。) 2 【主z - + 。，+ 一，圭户一；z ，届2 分别替换成两个 = ( 知 巩圭 铲警 s a ， 和 舻m 胂，城姜 。一量埘， 它们分别对应着g ，( = ，) 在 o ，屈，2 】和 屈2 ，肛】上的线性插值( 具体插值将在阿j i 讨论) 。对于这两个区问，求解( l u ) ，并且只要遇到解能改进o p t ，就修正o p t 。 用( ：+ ，歹；) 表示两个线性规划( l u ) 中对应最小目标函数值的解，并且根据步5 验证能否停止，若无法终止，则将两个矩形之一平分，利用线性插值继续进行 一和一：的线性插值与问题( s p ) 的一( 五) 相同均采用过插值区间的中点， 斜率等于两边界点的剁率点处