大规模结构化二次规划并行算法  

Parallel Algorithm of Large Scale Structured Quadratic Programming

作　　者：李捷[1,2] 李陶深[1] 杨林峰[1] 

机构地区：[1]广西大学计算机与电子信息学院,南宁530004 [2]广西职业技术学院计算机技术与电子信息工程系,南宁530226

出　　处：《计算机工程》2011年第16期48-50,共3页Computer Engineering

基　　金：国家自然科学基金资助项目(60963022);广西自然科学基金资助项目(0832056);广西研究生教育创新计划基金资助项目(105930901022)

摘　　要：在内点算法(IPM)框架基础上,分析具有分块带边结构系数矩阵与箭形结构二次项的二次规划(QP)问题,导出其既约与最简既约修正方程。对既约修正方程系数矩阵进行置换,使其具有箭形分块结构,并结合该结构与解耦技术给出修正方程的并行求解算法,设计QP问题的并行IPM结构。在集群环境下的数值实验结果表明,该算法具有较好的加速比和可扩展性,适合求解大规模结构化QP问题。According to the framework of Interior Point Method（IPM）,this paper presents the simpler and simplest correction equation of Quadratic Programming（QP）,which has block bordered coefficient and arrow quadratic term matrix.And the arrow structured coefficient matrix of simpler correction equation is formed after rearranging the matrix.A parallel solver for correction equation is proposed by integrating decoupling and the arrow matrix,and the parallel IPM algorithm of QP is presented.Experimental results in the cluster system show that the proposed algorithm is very promising for large structured QP problems due to its excellent speed-up ratio and scalability.

关 键 词：二次规划 分块带边矩阵 并行算法 解耦 既约修正方程 

分 类 号：TP311[自动化与计算机技术—计算机软件与理论]