（应用数学专业论文）两个具有特殊结构的正定二次规划问题的求解算法.pdf

摘要摘要二次规划是非线性规划中重要的一个研究分支这类问题不仅在实际生活中被广泛应用。而且还对整个最优化理论的发展起着巨大的推动作用所以，对此类问题的研究有很重要的意义本文主要针对两种特殊结构的正定二次规划同题进行了研究在第一章，我们主要回顾了二次规划问题的研究背景和它的一些基本概念和性质，并对正定二次规划问题的研究现状作了简要介绍在第二章，我们提出了一种解决具有原方块角形结构正定二次规划问题的分解协调算法利用k u h n - t u c k 条件，我们把原问题分解为一个高级问题和若干个相互独立的低级子问题，通过高级问题和低级子问题之间的信息传递，最终可以得到原问题的最优解这一方法是d a n t z i g - w o l f e 分解方法的一个推广在第三章，我们提出了一种解决具有边界约束的正定二次规划问题的对偶方法这一方法的主要思想是寻找对偶问题最优解的积极集合在每次迭代中。我们需要求解一个等式约束的二次规划子问题，若求解结果不满足最优性条件，则从这个子问题中增加或者删除个约束后重新求解在经过有限次迭代之后，可以求得原问题的最优解在第五章，我们提出了两个可以进一步研究的问题关键词，正定二次规划，k - t 点，对偶问题，d a n t z i g - w o l f e 分解方法，原方块角形结构，高级问题，低级子问题，边界约束，积极集方法，对偶方法a b s t r a c ta b s t r a c tq u a d r a t i co p t i m i z a t i o nc o m p r i s e so n eo ft h em o s ti m p o r t a n ta r e ai nn o n l i n -c a rp r o g r a m m i n g n u m e r o u sp r o b l e m si nr e a lw o r l da p p l i c a t i o n sc a nb ee x p r e s s e da sq u a d r a t i cp r o g r a m m i n gp r o b l e m s m o r e o v e r ，m a n ya l g o r i t h m sf o rn o n l i n e a rp r o g r a m m i n gt a k et h eq u a d r a t i cp r o b l e m sa st h e i rs u b p r o b l e m s s o ，t h er e s e a r c ho nq u a d r a t i co p r i m i z a t i o nh a sag r e a ts i g n i f i c a n c e i nc h a p t e r1 ，w eg a v eab r i e fo v e r v i e wo fq u a d r a t i cp r o g r a m m i n gp r o b l e m s ，i n c l u d i n gt h e i rp r a c t i c a la p p l i c a t i o na n ds o m ei m p o r t a n tp r o p e r t i e s t h e n w ei n t r o d u c e ds o m ei m p o r t a n tt e c h n i q u e sf o rs o l v i n gp o s i t i v ed e f i n i t eq u a d r a t i cp r o -g r a m m i n g i nc h a p t e r2 ，w ep r e s e n t e dam e t h o df o rs o l v i n gp o s i t i v ed e f i n i t eq u a d r a t i cp r o g r a m m i n gw i t hc o u p l e d - b l o c ks t r u c t u r e t h ep r i m a lp r o b l e mi ss p l i ti n t ot w op a r t s ：am a s t e rp r o b l e ma n ds e v e r a ls u b p r o b l e m s w i t ht h ei n f o r m a t i o nc o n l m u -n i c a t i o nb e t w e e nt h e s et w op a r t s ，w ec a nf i n a l l yg e tt h eo p t i m a ls o l u t i o no ft h ep r i m a lp r o b l e m a l g o r i t h mi sag e n e r a l i z a t i o no fd a n t z i g - w o l f ed e c o m p o s i -t i o nm e t h o d i nc h a p t e r3 ，w ep r e s e n t e dad u a lm e t h o df o rs o l v i n gp o s i t i v ed e f i n i t eq u a d r a t i cp r o g r a m m i n gw i t hb o xc o n s t r a i n t s w et r i e dt of i n dt h ea c t i v ec o n s t r a i n t so ft h ed u a lp r o b l e m i ne a c hi t e r a t i o n ，aq u a d r a t i cs u b p r o b l e mw i t he q u a l i t yc o n s t r a i n t si st ob es o l v e df i r s t l y , i ft h eo p t i m a lc o n d i t i o n si sn o ts a t i s f i e d w en e e dt oa d dac o n s t r a i n ti n t ot h es u b p r o b l e mo rr e m o v eo n ef r o mi t a f t e ral i m i t e dn u m b e ro fi t e r a t i o n s ，w ec a ng e tt h eo p t i m a ls o l u t i o no ft h ep r i m a lp r o b l e m w ec o n c l u d e dt h et h e s i sw i t hc h a p t e r4b yp r o p o s i n gt w op o s i t i v ed e f i n i t eq u a d r a t i cp r o b l e m sf o rf u r t h e rr e s e a r c h k e y w o r d s ：p o s i t i v ed e f i n i t eq u a d r a t i cp r o g r a m m i n g ，k - tp o i n t ，d u a lp r o b l e m ，d a n t z i g - w o l f ed e c o m p o s i t i o nm e t h o d ，c o u p l e d - b l o c ks t u r c t u r e ，m a s t e rp r o b l e m ，s u b p r o b l e m ，b o xc o n s t r a i n t ，a c t i v es e tm e t h o d ，d u a lm e t h o d西北工业大学学位论文知识产权声明书本人完全了解学校有关保护知识产权的规定，即：研究生在校攻读学位期间论文工作的知识产权单位属于西北工业大学。学校有权保留并向国家有关部门或机构送交论文的复印件和电予版。本人允许论文被查阅和借阅。学校可以：降本学位论文的全部或部分内容编入有关数据库进行检索，可以采用影印、缩印或扫描等复制手段保存和汇编本学位论文。同时本人保证，毕业后结合学位论文研究课题再撰写的文章一律注明作者单位为西北工业大学。保密论文待解密后适用本声明。学位论文作者签名：蔓鱼_指导教师签名：曼4 竺兰兰b 卞弓月8 日妒9 7 年；再够日西北工业大学学位论文原创性声明秉承学校严谨的学风和优良的科学道德，本人郑重声明：所呈交的学位论文，是本人在导师的指导下进行研究工作所取得的成果。尽我所知，除文中已经注明引用的内容和致谢的地方外，本论文不包含任何其他个人或集体已经公开发表或撰写过的研究成果，不包含本人或他人已申请学位或其它用途使用过的成果。对本文的研究做出重要贡献的个人和集体，均已在文中以明确方式标明。本人学位论文与资料若有不实，愿意承担一切相关的法律责任。学位论文作者签名：i 萎蓝。2 叼年j 月多日第一章绪论第一章绪论1 1 = 次规划的研究背景运筹学的思想在中国古代就已经产生了，运筹一词出自中国古代史书鬈史记高祖本纪t。夫运筹帷幄之中，决胜于千里之外。中国春秋末期军事家孙武在孙子兵法计篇中也说道t 。夫未战而庙算胜者，得算多也；未战而庙算不胜者，得算少也多算胜，少算不胜，而况于无算乎1 4 这里的。算”就是计算筹划之意运筹学作为一门学科，是在第二次世界大战中由于军事上的需要而逐渐发展形成的随着科学技术和生产的发展，运筹学已渗入到很多领域里，发挥了越来越重要的作用运筹学本身也形成了好多分支，比如；数学规划( 又包含线性规划；非线性规划；整数规划i 组合规划等) 、图论网络流、决策分析、排队论、可靠性数学理论等等二次规划是最简单、也是最早被人们研究的一类非线性规划问题，同时它也是个n p 困难问题【1 】许多工程优化问题可以被直接归结为二次规划问题，例如，上如z 1 混合优化问题【2 】、控制系统在存在参数区间摄动情况下的故障诊断问题【3 】等另外，物理学中关于塑性力学【4 】、接触力学【5 】等经典变分法难以适应的问题，也可以被转化为二次规划问题二次规划问题不仅在工程优化问题中具有重要的应用价值，而且它在一般的非线性规划问题的算法中常作为子问题出现，特别是序列二次规划方法的发展更使得二次规划的研究尤为重要序列二次规划方法是从1 9 6 3 年w i l s o n 的研究开始到1 9 7 7 年经过h a l l 和p o w e l l 的发展形成的一个比较完善的方法( 【6 】一8 】) ，它被公认为目前解决非线性约束最优化问题的最优效的方法之一，这种方法的主要思想是将形式复杂的非线性规划问题转化为一系列二次规划子问题，以这一系列子同题的最优解逼近原问题的最优解在序列二次规划方法的应用中，我们需要对子二次规划问题中的海赛矩阵进行更新和存储，于是在8 0 年代末又兴起了简约海赛序列二次规划方法，并得到了很大的发展 9 】另外，序列- t k 规划方法有很重要的应用价值，在日常生活中遇到的城市供水管网优化闯题【1 0 】、石油化工过程优化问题f l l 】以及无约束连续最优控制【1 2 】等问题都可l第一章绪论以用序列二次规划方法求解因此，无论从最优化理论发展的角度还是从实际应用的角度，二次规划问题的研究都有十分重要的意义1 2 二次规划的基本概念和性质r a i n ，( 茁) = 9 z + 去z h xs 五a i t x = h i , i = 1 , - , m e ；- m ( 1 圳其中2 g 和a i 为礼维列向量，为n 扎对称矩阵定义1 2 1 ( 【1 3 】) ；集合x = 伽ia i t x = 玩，i = 1 ，m 。；a i 2 z 玩， =m 。+ 1 ，m 被称为问题( 1 2 1 ) 的可行域，x 中的每一点被称为问题( 1 2 1 )定义1 2 2 ( 1 3 1 ) t 记e = l ，m 。 ，i = 仳+ 1 ，m ) ，f 扛) = 刮o i 霉= 玩，t n ，我们称集合el j i ( x ) 是在可行点霉的积极集合( 或有效集合) ，下标位于集合e u l ( z ) 中的约束被称为在霉点的积极约束( 或有效约束) ，下标不伍于集合e u i ( x ) 中的约束被称为在$ 点的非积极约束 0 ，有，( z ) ，( z ) ，v 茁x n b ( ，占)成立，则称矿是a , l 题( 1 2 1 ) 的局部极小点，其中b ( 茁+ ，6 ) = 茁ii | 茁一。1 1 2 6 )21 2 二次规划的基本概念和性质得定义1 2 5 ( 【1 3 】) t 记a = ( ( 2 1 ，口。) ，若存在矿形和”尼”，使h x 上g = a a 甜= 魄，i = 1 ，m ea i 霉瓯，t = 1 t $ e + 1 ，m( 1 2 2 )k ( 口i z 一玩) = 0 ，i = m 。+ 1 ，e r $智0 ，i = m 。+ 1 ，仇则称矿是问题( 1 2 1 ) 的k u h n - t u c k e r 点( 简称k - t 点) ，称是在矿处的l a g r a n g e 乘子如果日为半正定矩阵，那么问题( 1 2 1 ) 的目标函数， ) 为凸函数，该问题被称为凸二次规划问题关于凸二次规划问题，有下面一个非常重要的性质t引理1 2 6 ( 【1 3 】) ，若二次规划问题( 1 2 1 ) 的海赛矩阵是半正定矩阵，则矿是它的全局极小点当且仅当它是一个局部极小点，也当且仅当它是一个k - t点如果日为正定矩阵，那么问题( 1 2 1 ) 的目标函数，( z ) 为严格凸函数，这时该问题被称为严格凸二次规划问题，也被称为正定二次规划问题当日为正定矩阵时，那么日是可逆的，故正定二次规划问题的l a g r a n g e对偶问题可以被表示为【1 3 】m i n 一( b + a t h - l g ) 。入+ 2 a t ( 肌1 ，4 胁( 1 2 3 )s t 九0 ，i = m e + l ，m 下面两个引理阐述了正定二次规划问题和它的对偶问题( 1 2 3 ) 之间的关系引理1 2 7 ( 【1 3 】) 。设海赛矩阵h 正定，如果原始问题( 1 2 1 ) 有可行点，则矿是它的最优解当且仅当存在”是对偶问题( 1 2 3 ) 的最优解，并且”是原始问题在z 处的l a g r a n g e 乘子引理1 2 8 ( 【1 3 】) ，设海赛矩阵h 正定，则原始问题( 1 2 1 ) 无可行点当且仅当对偶问题( 1 2 3 ) 无界3第一章绪论1 3 正定二次规划的研究现状根据上节的内容，我们知道正定二次规划有两个良好的性质；首先，它的最优解与它的k - t 点是等价的；其次，我们可以通过求解对偶问题来得到原问题的最优解所以，正定二次规划是比较容易求解的一类二次规划问题而且正定二次规划的研究会对一般二次规划的发展起推动作用，例如t 在高岳林等( 1 4 】一【1 5 】) 提出的一种解决一般二次规划的分枝定界方法中，他们就是通过求解正定二次规划子问题来达到定界目的的本节对一般形式的正定二次规划问题和几种具有特殊结构的正定二次规划问题的已有算法作了简单介绍1 3 1一般形式的正定二次规划问题对于一般形式的正定二次规划问题( 1 2 1 ) ，比较常见的两种算法是积极集法【1 3 】和对偶方法【1 6 】一、积极集法积极集法的理论基础是下面的引理z引理1 3 1 ( 1 3 】) ：设矿是二次规划问题( 1 2 1 ) 的局部极小点，则矿也必是问题幽他2 9 z + 秒1z( 1 3 1 )s t 毗。= 玩，i e u j - ( + )的局部极小点反之，如果矿是( 1 2 1 ) 的可行点，且是( 1 3 1 ) 的k - t 点，而且相应的l a g r a n g e 乘子”满足k 0 ，t i ( x + )( 1 3 2 )则z 也是( 1 2 1 ) 的k - t 点积极集法的主要思想是寻找原问题最优解的积极集合在每次迭代中，我们需要求解一个等式约束的二次规划问题( 1 3 1 ) ，如果该问题的最优解z + 是原问题( 1 2 1 ) 的可行点并且条件( 1 3 2 ) 成立，那么根据引理1 3 1 ，矿就是原问41 3 正定二次规划的研究现状题( 1 2 1 ) 的最优解；否则，我们需要从( 1 3 1 ) 中增加或者减少一个约束，重新求解新的等式约束问题二对偶方法积极集法是可行点算法，需要一个初始可行点g o l d f a r b 和i d i n a n i 又提出了一种对偶算法。他们用积极集法求解原问题( 1 2 1 ) 的i , a g r a n g e 对偶问题( 1 2 3 ) ，并且给出了从一个子问题的最优解得到下一个子问题的最优解的迭代公式刘小冬等【1 7 】对此对偶问题作了一些改进，他们提出的新对偶算法是在满足w o l f e 对偶问题可行的基础上，逐步向原问题的最优解逼近的，并且一旦一个约束成为可行约束，以后将永远可行1 3 2 几种具有特殊结构的正定二次规划问题除了具有般形式的正定二次规划问题，人们还对很多具有特殊结构的正定二次规划问题作了研究，得到了很多优秀的算法一，具有等式约束和非负约束的问题m i n 9 。茁+ ；刃。h 茁鲥 羞。3 3 其中，z 和9 为n 维列向量，h 为n 佗对称正定阵，a 为m n 阵，b 为仇维列向量w o l f e 算法【1 8 】是求解( 1 3 3 ) 的较早的一个方法，它利用正定二次规划的最优解与它k - t 点的等价性，把原问题转化为一个非线性规划问题，再把解决线性规划的单纯形法【1 9 】加以修改来求解此问题另外，随着线性规划内点方法的发展( 【2 0 】一【2 3 ) ，人们也开始研究求解问题( 1 3 3 ) 的内点方法，并取得了很大的进展( 【2 4 】一【2 8 】) 但是内点方法需要一个初始严格可行内点z o ( a z o = b ，x o 0 ) ，于是，又出现了一系列求解( 1 3 3 ) 的不可行内点方法( 【2 9 】一【3 1 】) ，这类方法只要求初始点知满足霉o 0 即可，但是它的计算过程中的一些参量( 如迭代步长) 尚缺乏有效的确定方法5第一章绪论二具有不等式约束和非负约束的问题r a i n g 霉+ 去霉。“f 触( 6 ，( 1 删【霉20 问题( 1 3 4 ) 中的参量的描述和( 1 3 3 ) 相同l e m a k e 互补转轴算法【1 8 】是求解问题( 1 3 4 ) 的一种常见算法，与w o l f e 算法一样，它也是利用正定二次规划的k - t 点与其最优解的等价性，再把求解线性规划的单纯形法加以推广得到的徐君开【3 2 】把问题( 1 3 4 ) 转化为一系列可用l e m a k e 互补转轴算法求解的维数较低的子问题，提出了求解它的一个可行方向法梁昔明【3 3 】结合k u h n - t u c k e r 条件【3 4 】，构造了个势函数，提出了求解( 1 3 4 ) 的一个势下降内点算法本文对一种特殊形式的具有不等式约束和非负约束的正定二次规划问题进行了研究，它具有如下形式：m i n 芝毫，( q 。吻+ ；。q 奶)鲥碌a 即组( 1 删i 岛幻，奶0 ，j = 1 ，t 1 其中，q 和q 是吩维列向量，口和易分别是m 维列向量和缈j 维列向量，4 和弓分别是m 吩阵和吻阵，q 是吩吩对称正定阵我们把问题( 1 3 5 ) 称为具有原方块角形结构的正定二次规划问题，据我的查看，国内外还没有人提出求解它的算法但是，人们对具有原方块角形结构的线性规划问题进行了大量的研究，该线性规划问题具有如下形式tm i n 肇。勺“j 跺，柏鲺( 1 矗6 )i 弓哟b ，20 ，j = 1 ，扎d a n t z i g 和w o l f e 3 5 利用凸多面体表示定理【1 9 1 ，把( 1 3 6 ) 分解成一个主导问题和若干个相互独立的子问题，提出了著名的d a n t z i g - w o l f e 分解方法另61 4 本文的主要内容外一种可以有效求解( 1 3 6 ) 的方法是b e n d e m 分解方法【3 嘲，其主要思想是利用f d 庸引理f 3 4 】和对偶理论把原问题分解成个主导问题和若干个独立的子问题进行求解蓝伯雄【3 7 】提出了一种更具普遍性的求解( 1 3 6 ) 的原始一对偶分解方法，d a n t z i g - w b 如分解方法和b e n d e r s 分解方法都是这种方法的一个特例所以，我们可以参考以上求解问题( 1 3 6 ) 的算法，对问题( 1 3 5 ) 的求解算法进行探讨三、具有边界约束的问题本文还研究了如下形式的二次规划问题；m i ng 。+ 矿t h x( 1 3 7 )8 t z z 其中，l 和牡是住维列向量，霉，9 和h 的描述与( 1 3 3 ) 相同相比于( 1 3 3 ) ，问题( 1 3 7 ) 的初始严格可行内点茁0 0 u ) 很容易得到，所以内点方法是解决此类同题的很有效的一类方法( 3 8 】一【4 0 】) 问题( 1 3 7 ) 的另个研究热点是投影梯度方法( 4 1 】一【4 2 】) ，这种方法很容易编程实现，并且不需要求解矩阵的逆，所以特别适合求解大规模的此类问题1 4 本文的主要内容本文主要针对两种形式的正定二次规划问题进行了研究，它们分别是t 具有原方块角形结构的正定二次规划问题( 1 3 5 ) 和具有边界约束的正定二次规划问题( 1 3 7 ) 针对这两种问题的特殊结构，我们分别对之设计了求解算法另外，为了验证算法的有效性。我们还给出了相应的算例一、具有原方块角形结构的正定二次规划问题从同题( 1 3 5 ) 的约束结构可以看出，如果没有耦合约束警l 奶sa 。那么该问题可以被分成n 个独立的较小规模的二次规划子问题我们从解决线性规划问题的d a n t z i 乎w j 分解方法中受到启发，利用施m 佗一死c k e r 条件把原同题分解成一个高级问题和若干个低级子问题，提出了求解( 1 3 5 ) 的个分解协调算法该算法是有限步终止的，并且由于高级问题和低级子问题都是可以有7第一章绪论效求解的，所以该算法比较适合于求解大规模的此类问题= 、具有边界约束的正定二次规划问题我们在积极集法和对偶方法的基础上，通过寻找问题( 1 3 7 ) 的对偶问题最优解的积极集合，提出了求解它的一种对偶算法我们充分利用了( 1 3 7 ) 的特殊约束结构，使算法的迭代步骤得以简化，提高了算法的运算效率。该算法也是有限步终止的本文在第二、三两章分别对这两种算法进行了详细的讨论，在第四章提出了两个可以进一步研究的问题8第二章具有原方块角形结构的可分凸二次规戈f j 的一个分解算法第二章具有原方块角形结构的正定二次规划的一个分解协调算法2 1 引言在工j 的大型生产计划中，经常会遇到具有原方块角形结构的大规模线性规划问题，如下所示tr a i n ：。勺哟“ 吕1 a 奶 o ，( 2 工”【弓吻s ，即0 ，歹= 1 ，疗，其中，勺和吻是吻维列向量，口和分别是m 维列向量和竹巧维列向量，a 和岛分别是m 码阵和吩阵关于问题( 2 1 1 ) ，比较常见的算法有d a n t z i g - w o l f e 分解方法和b e n d e r s 分解方法等方法本章把d a n t z i g - w o l f e 分解方法加以推广，再结合k u h n - t u c k e r条件，提出了一种求解具有如下形式的正定二次规戈! i 问题的分解协调算法，m i n 象1 ( q + 互1 g )时 蹂- 俩如，( 2 工2 )【毋6 j ，即0 ，j = 1 ，n 其中，白是吩对称正定矩阵，其余参量的说明与( 2 1 1 ) 相同2 2 算法的推导2 2 1 问题的转化对于凸多面体s = z i b 霉b ，o ) 。有下面一个非常著名的凸多面体表示定理9第二章具有原方块角形结构的正定二次规划的一个分解协调算法引理2 2 1 ( 1 9 1 ) t 设有界凸多面体s 有口个极点，1 ，扩，那么向量霉s 的充要条件是存在 0 ( 1 q q ) ，使得。= ：，姚a并且名l ”= 1 另外，若s 无界，则它还有r 个极方向，暑，1 ，一，此时向量s 的充要条件是还存在矿0 ( 1 r r ) ，使得霉= ：，”茁a + 三= 。扩旷厶- ，口= l 厶_ ，r = l一如果没有耦合约束饕la 畅口，那么问题( 2 1 2 ) 是由n 个子系统组成的，每个子系统j 的可行域为岛= q i 弓幻，畅20 ) ，本节假设毋都是有界的，对于岛无界的情形，将在2 2 7 节讨论根据引理2 2 1 ，岛中任意个元素可以表示为奶= 兰碍碍( 2 2 1 )其中，( 1 q q 0 ) ) 是毋的极点。产0 0 1 ) 碍= 1 且碍0 把( 2 2 1 ) 代入( 2 ，1 2 ) ，得到下面的二次规划问题tr a i n 基。( q 。知+ 互1 。吩)“j 跺o 如，( 2 。2 2 )【q = l 碍= 1 ，0 ，j = 1 ，其中，= ( 碍，譬) ，嘶= ( 叫，哼) 。，q = q 蟛，= ( q ，正；a ) ，碍= 碍( 1 口q o ) ) ；巧= ( ( ) 。弓霉；2 ) 。口( 1sq l , q 2 q 0 ) ，1 j 曲定理2 2 2 。问题( 2 1 2 ) 与问题( 2 2 2 ) 是等价的，即1 ) 问题( 2 1 2 ) 有可行解的充要条件是问题( 2 2 2 ) 有可行解2 ) 问题( 2 1 2 ) 和问题( 2 2 2 ) 都有有限最优解3 ) 若z = 仕1 ，z 。) 是( 2 1 2 ) 的最优解，那么对于每个子系统j ( 1sjsn ) ，存在= ( 对，碍o ) 之0 ，使得 x j = 掣纠( 2 2 3 )i 俨q 0 1 ) 碍= 1】02 2 算法的推导并且入= ( 入l ，x ；。) 是( 2 2 2 ) 的最优解；反之，若入= ( a 1 ，a 。) 是( 2 2 2 ) 的最优解，那么由( 2 2 3 ) 式得到的2 = ( x l ，茁0 ) 是( 2 1 2 ) 的最优解证明：1 ) 根据引理2 2 1 可证2 ) 由于矩阵g ，是正定的，所以，勺+ ；吻e z j 一；q 。白q 勺再根据引理2 2 1 ，对( 2 2 2 ) 的任一可行点( 1 歹sn ) ，都有( 2 1 2 ) 的可行点( 1 歹s n ) 与之对应，并且嘶+ ；吩= 勺q + ；吻。q 畅一；勺弓- 1 勺由此可知，问题( 2 1 2 ) 和( 2 2 2 ) 都有有限最优解3 ) 设( a ，c 竹。) 。是( 2 2 2 ) 的任一可行点，再设与之对应的( 2 1 2 ) 的可行点为名= ( ：1 ，) 。，那么有芝亲。( 嘶白+ j 1 白吩白)= 二。( 勺乃+ j 1 乃弓乃) 2 二。( 勺。即+ ；吻白吻)= 二，( 吻+ 互1 巧)故入是( 2 2 2 ) 的最优解类似的，可以证明，若a 是( 2 2 2 ) 的最优解，那么由( 2 2 3 ) 式得到的刃是( 2 1 2 ) 的最优解口这样，我们就把原问题转化为一个与之等价的问题( 2 2 2 ) ，把( 2 2 2 ) 称为主导问题2 2 2 基本定理由于g 是正定的，那么巧至少是半正定的，所以主导问题( 2 2 2 ) 是个凸二次规划问题根据引理1 2 6 ，凸二次规划的最优解与它的k - t 点是等价的，所以我们可以得到问题( 2 2 2 ) 的最优解的充要条件t定理2 2 3 ，a = ( 入l ，i t ) 是( 2 2 2 ) 的最优解当且仅当a 是它的可行解，且存在列向量让= ( t l ，t 。) 。，使得( ，o 一n ) - 0( 2 2 4 )】1第二章具有原方块角形结构的正定二次规划的一个分解协调算法u 0( 2 2 5 )并且对每个子系统歹，存在标量和列向量乃= ( 口，学“) ，使得h i 入 + j = r i l l + f j 一0 t i| 沁= 0乃0( 2 2 6 )( 2 2 7 )( 2 2 8 )其中，是每个分量都为1 的q ( j ) 维列向量证明：根据引理1 2 6 ，问题( 2 2 2 ) 的最优解与它的( - t 点等价而问题( 2 2 2 ) 的k - t 点应该满足如下条件，( 竺；二二：) = 一( ：3 + ( 口? 0 1 ) + + 匕j + ( 羔)舻( e j l 。j a j - a ) = o ，u 2o对上式加以整理，就可以得到( 2 2 4 ) 一( 2 2 8 ) 式口定理2 2 3 中的t ，和乃是在( 2 2 2 ) 的最优解入处的l 叼啪9 e 乘子，这个定理是我们后面判断算法是否迭代到主导问题最优解和建立低级子问题的基础2 2 3高级问题和低级子问题由于每个子系统的约束集合马= 奶f 弓，即o ) 的极点数目q ( j )很大，导致主导问题( 2 2 2 ) 的规模( 列数，矩阵吩的维数等) 很大另外，我们也不可能把毋的所有极点都求出来因此，采用列生成方法求解( 2 2 2 ) 一、高级问题和低级子问题的建立假设对每个子系统j ，已知马的虿( j ) 个极点( 虿( j ) q ( j ) ) ，把它们记为；，中再记瓦= ( 弓，霹。) ，砺= ( 啄，皆) ，己=( l i ，工 ) ，弓= ( ( 乎) q 吻q 2 ) 私小识，( 1 q l 啦虿) 这样，就可以】22 2 算法的推导得到主导同题( 2 2 2 ) 的一个限制问题。m i n ：。( 码习+ ；瓦弓瓦)“j 跺己习 口但删i 翟碍= 1 ，j 0 ，歹= 1 ，n 我们把( 2 2 9 ) 称为高级问题设问题( 2 2 9 ) 的最优解为天= ( x 1 。，k ) ，由于矩阵而也是半正定的，根据定理2 2 3 ，存在面，乃和乃使得铲( 。辆一。) = o面20巧弓+ 砀= 巧弓+ 乃一己面| i 、= 0，j20其中，b 是分量全为1 的虿0 ) 维列向量另外，我们令( 2 2 1 0 )( 2 2 1 1 )( 2 2 1 2 )( 2 2 1 3 )( 2 2 1 4 )对： 焉，1 虿( 2 2 1 5 )10 ，虿0 ) + 1 i q 0 )那么入= ( 入1 ，a 。) 是主导问题( 2 2 2 ) 的一个可行解再令让= 西，码= - j ，办= ，俨“，锣) 我们通过比较式( 2 2 4 ) 一( 2 2 8 ) 和式( 2 2 1 0 ) 一( 2 2 1 4 ) 来找出a 和( 2 2 2 ) 的最优解之间的差距由于白= 己瓦，= _ j 。瓦，所以式( 2 , 2 4 ) ，( 2 2 5 ) 和( 2 2 7 ) 成立若要使( 2 2 6 ) 成立，则鼻( 虿+ 1 q o ) ) 必须满足疗= ：写( 哆) 白z ；+ 吗+ ( 巧) 面一巧( 2 2 1 6 )同时，为了满足( 2 2 8 ) ：还必须有露0 ，即：碍( ) q z ；+ 叫+ ( 巧) 一弓o( 2 2 1 7 )1 3第二章具有原方块角形结构的正定二次规划的一个分解协调算法所以，若对于所有的子系统j ，都有( 2 2 1 7 ) 成立，那么根据定理2 2 3 ，a =( 入1 ，入0 ) 就是主导问题( 2 2 2 ) 的最优解由于叫= q ，巧= a ，所以( 2 2 1 7 ) 可以写成如下关于集合岛的极点的线性表达式，( 茎：碍白碍+ 勺+ a 西) 。一_ j o( 2 2 1 8 )另外我们注意到线性规划的最优解总是可以在它的极点上达到，所以可以通过解线性规翅i 问题m i nd f z i。j 弓幻，( 2 2 1 9 )& i 之0来判断( 2 2 1 7 ) 是否成立其中，由= 劭q = l 勺w * j q + 勺+ 嘧我们把( 2 2 1 9 )称为低级子问题二、高级问题和低级子问题之间的信息传递通过高级问题和低级子问题之间的信息传递，我们可以建立求解主导问题( 2 2 2 ) 的个分解协调算法在算法的每次迭代中，先求解高级问题( 2 2 9 ) 得到由( 1 j n ) ，然后利用而建立n 个相互独立的低级子问题( 2 2 1 9 ) ，设它们的解为哆( 1 j 佗) 若对所有的子系统j ，都有嘞茁；一巧0 ，那么根据前面的分析，主导问题( 2 2 2 ) 的最优解已经达到否则，若对于某个子系统j ，有由z ；一巧 吼r a i nz = 。鲋降嚣”一m ( 2 2 2 2 )其中，霉4 = ( $ 。1 ，z 景) 是我们引进的人工变量显然。( 2 2 2 2 ) 一定有可行解，并且如果它的最优值矿 0 ，那么主导问题( 2 2 2 ) 无可行解根据线性规划的最优解与k - t 点的等价性，可以得到问题( 2 2 2 2 ) 的最优解的充要条件定理2 2 4 ：7 = ( 入l ，p o ) ) 是( 2 2 2 2 ) 的最优解当且仅当7是它的可行解，且存在列向量缸= ( u l ，t ，1 ) ，r = ( r l ，r m ) 和无=1 5第二章具有原方块角形结构的正定二次规划的一个分解协调算法( 劈，学) 以及标量v j ，使得，z = 一k 2 t + ，l j t 弘= ”籼+ 厶u 。( ll i , j + k z a d ) = o ，仳o( 2 2 2 3 )| 于k = 0 。| 2 0f 0 4 = 0 ，f 0m i n 虿= ：，st鎏：i；三=：，n( 2 2 2 4 )鲥黯( 2 2 2 5 f 。弓习so i 翟碍：1 ，弓。，j ：”一，佗2 2 算法的推导值矿 0 ，那么主导问题( 2 2 2 ) 没有- - i 行解；反之，若对于某个子系统，仍然有嘞巧一乃 0 ，应该把哆添加到高级问题( 2 2 2 4 ) 中，重新对之求解这样，通过高级问题( 2 2 2 4 ) 和低级子问题( 2 2 2 5 ) 之间的信息传递，我们可以得到个可行的( 2 2 9 ) ，或者判断出主导问题( 2 2 2 ) 没有可行解2 2 5 算法的描述根据前面的分析，求解主导问题( 2 2 2 ) 的分解协调算法实际上是一个两阶段算法，在第一阶段，对每个子系统j ，我们需要求出其约束集合g 的一定数目的极点，以得到一个可行的高级问题( 2 2 9 ) ，或者判断出主导问题( 2 2 2 ) 没有可行解；在第二阶段。我们从第一阶段得到的可行的高级同题( 2 2 9 ) 出发，继续甩分解协调算法进行迭代，可以得到主导问题( 2 2 2 ) 的最优解它的具体步骤可以被叙述如下；分解协调算法1初始化t 利用上节介绍的方法反复求解( 2 2 2 4 ) 和( 2 2 2 5 ) 若主导问题( 2 2 2 ) 无可行解，算法终止；否则，可以得到一个可行的高级问题( 2 2 9 ) ，转步1 步1t 求解高级问题( 2 2 。9 ) ，得到它的最优解灭= 风，瓦) 。以及对应的l a g r a n g e 乘子西，码和无步2t 对每个子系统歹，分别求解低级子问题( 2 2 1 9 ) ，得到其最优解哆步3 ，如果对c s - q 子系统j ，都有d j z ：一码0 ，那么由式( 2 2 1 5 ) 得到的a = ( a x 。，) 就是主导问题( 2 2 2 ) 的最优解，算法终止；否则，对于嘞霉：一- j 0 的子系统j ，按照式( 2 2 ，2 0 ) 把它的极点z ：添加到高级问题( 2 2 9 ) 中，返回步1 可以看到，在任何一次迭代里，最多有n 个子系统的极点被添加到高级问题中，而每个子系统的极点数目是有限的，所以，该算法是有限步收敛的另外，利用主导问题( 2 2 2 ) 的最优解a = ( 入1 ，入，) 。由式( 2 2 1 ) 。就可以得到原问题( 2 1 2 ) 的最优解1 7第二章具有原方块角形结构的正定二次规划的一个分解协调算法2 2 6 数值测试为了验证本算法的有效性，我们用m a l a b 编程，并实际求解了两个算例第一个算例含有8 个变量，1 个耦合约束，2 个对角块，其中每个对角块分别含有4 个变量和2 个约束条件；第二个算例含有1 3 个变量，2 个耦合约束，3个对角块，其中第一个对角块含有5 个变量和3 个约束条件，另外两个对角块分别含有4 个变量和2 个约束条件同时，出于比较的目的，我们还用积极集法对以上两个算例进行了运算把本算法求得的最优解记为- 把积极集法求得的最优解记为刃程序运行结果如下。甩到的极点数l | - 一2 。l | 2算例1对角块l 对角块28 1 9 6 1 1 0 一1 654用到的极点数l | - 一z 。0 2算例2对角块1对角块2对危块33 】0 3 0x1 0 _ 1 5656从上表可以看出，面和霉之间偏差的1 2 范数0 面一+ 2 表明本算法求得了问题的最优解2 2 7 无界子系统约束问题在前面的章节中，讨论了具有有界子系统约束的问题( 2 1 2 ) 的一个分解协调算法当子系统的约束集合岛= 吻f 弓z js 吻，哟o ) 无界时，我们需要对这种算法作一些必要的修改一，问题的转化记每个子系统的约束集合岛的极方向为谚，谚，根据引理2 2 1 ，岛中的任意一个元素吻可以表示为；r q = l 地 7 ；+ = 巧嵋( 2 2 2 6 )再记白= ( 碍，够o ) ，奶= ( 磅，霹o ) ，己= ( 弓，霹“) ，乃=1 82 2 算法的推导( 芬盏) ，其中，碍= 嘭孵，弓= a 孵，巧= ( ( 疗) 白( 妒) ) 。州而=( ( 碍) 。q 蟛) 。o ) 。础，( 1 r ，r 1 ，r 2 r 0 ) 另外，嘶，白，屿与2 2 l 节的记法相同把( 2 2 2 6 ) 代入( 2 1 2 ) ，得主导问题曲譬。卜知倒聃扣确乃( 2 ) 一路1 ( 白+ l j j j ) 9 ，2 22 7，( )l 搿碍= 1 ，0 ，易20 ，j = 1 ，n 二，基本定理由于矩阵乃也是半正定的，根据引理1 2 6 ，可以得出主导问题( 2 2 2 7 ) 最优解的充要条件。定理2 2 5 。7 = ( a 1 ，以，a 0 ，k ) 2 是( 2 2 2 7 ) 的最优解当且仅当叩是它的可行解，且存在列向量= ( t l ，) ，使得乱 ：。( o + 己而) 一a j = o缸0( 2 2 2 8 )( 2 2 2 9 )并且对每个子系统j 。存在标量，列向量，j ；( 疗，露) 和毋=( 谚，矿) ，使得h i x j + k 芦i + w j = t i + | 一l u吩+ 绣如+ 奶= 彩一弓缸| f x 一0 。g 子6 = 0如之0 ，毋20其中，b 是每个分量都为l 的q u ) 维列向量该定理的证明与定理2 2 3 类似，不再赘述三，高级问题和低级子问题】9( 2 2 3 0 )( 2 2 3 1 )( 2 2 3 2 )( 2 2 3 3 )第二章具有原方块角形结构的正定二次规划的一个分解协调算法与前面类似，我们可以建立求解主导问题( 2 2 2 7 ) 的分解协调算法在算法的每次迭代中。用已知的每个子系统的极点和极方向建立高级问题t曲肇。陋耐聃渺1 机( 乏) 鲋丁岛隔+ 毒弧 2 3 4 【翟碍= 1 ，_ j 0 ，而20 ，j = l ，：一m设它的最优解为丽= ( _ 1 。，- 1 ，瓦。) ，相应的l a g r a n g e 乘子为西，弓乃和功再记吗= 酌q = l 碍弓碍+ 鬻巧弓孵+ 勺+ 4 面，建立每个子系统的低级子问题。m i n 专2 鲥黔( 2 2 3 5 )若( 2 2 3 5 ) 的最优解为霉；，且对每个子系统j ，都有由哆一乃0 ，那么根据定理2 2 5 ，我们已求得了主导问题( 2 2 2 7 ) 的最优解否则，对某个子系统仍然有奶。哆一巧 0 ，那么应该把哆添加到高级问题( 2 2 3 4 ) 中，具体操作如下，h j 。( 哆) 。白霉；l巧一i( 茁；) q 田巧一溉，叼) 。己一( 弓，q )02、l啊昏啊哂；产啕护护沪白q，r哆唠可可2 2 算法的推导另外，若对某个子系统j ，( 2 2 3 5 ) 无有限最优解，那么必然存在s j 的一条极方向孵，使得嵋 0 把孵添加到高级问题( 2 2 3 4 ) 中，具体操作如下t瓦一。蟛，。q刃?。彬，。白俨，巧一”奶一( 奶，霹) = 一( 白，譬)( 白嵋、；i( 俨，) 白蟛l( 孵) t q 孵j( 2 2 3 7 )这样，我们就得到了个新的高级问题( 2 2 3 4 ) ，进入算法的下次迭代，重新对之求解这样，通过高级问题( 2 2 3 4 ) 和低级子问题( 2 2 3 5 ) 之间的信息传递，最终可得到主导问题( 2 2 2 7 ) 的最优解四、算法的描述该算法也是一个两阶段算法，第一阶段的算法( 初始化过程) 与2 2 4 节类似，不再赘述根据前面的分析，可以把该算法的具体步骤叙述如下；分解协调算法2初始化：调用第一阶段算法，若主导问题( 2 2 2 7 ) 无可行解，算法终止；否则，得到一个可行的高级同题( 2 2 3 4 ) ，转步1 步1 ；求解高级问题( 2 2 3 4 ) ，得到它的最优解可= ( - 1 ，- 1 ，j 0 ，瓦。) t以及对应的l a g r a n g e 乘子面，码，厶和功步2 ：对每个子系统j ，分别求解低级子问题( 2 2 3 5 ) ，得到它的最优解z ；或极方向孵步3 。若所有的低级子问题都有有限最优解且嘞z ；一乃20 ，那么我们已求得主导问题( 2 2 2 7 ) 的最优解否则，对奶。茁：一弓 0 的子系统，按式( 2 2 3 6 ) 把极点茹：添加到高级问题( 2 2 3 4 ) 中；对有2 1第二章具有原方块角形结构的正定二次规划的一个分解协调算法无限最优解的子系统，把极方向引按式( 2 2 3 7 ) 添加到高级问题( 2 2 3 4 ) 中转步1 由于每个子系统的极点和极方向的数目都是有限的，所以上述算法是有限步收敛的五，数值测试我们用m a t l a b 编程，应用本算法求解了两个算例第一个算例含有8 个变量，1 个耦合约束，2 个对角块，其中每个对角块分别含有4 个变量和2 个约束条件；第二个算例含有1 3 个变量，2 个耦合约束，3 个对角块，其中第一个对角块含有5 个变量和3 个约束条件，另外两个对角块分别含有4 个变量和2 个约束条件把本算法求