摘要
在内点算法(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.
出处
《计算机工程》
CAS
CSCD
北大核心
2011年第16期48-50,共3页
Computer Engineering
基金
国家自然科学基金资助项目(60963022)
广西自然科学基金资助项目(0832056)
广西研究生教育创新计划基金资助项目(105930901022)
关键词
二次规划
分块带边矩阵
并行算法
解耦
既约修正方程
Quadratic Programming（QP）
block bordered matrix
parallel algorithm
decoupling
simpler correction equation
