作者投稿和查稿 主编审稿 专家审稿 编委审稿 远程编辑

计算机工程 ›› 2011, Vol. 37 ›› Issue (16): 48-50. doi: 10.3969/j.issn.1000-3428.2011.16.016

• 软件技术与数据库 • 上一篇    下一篇

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

李 捷 1,2,李陶深 1,杨林峰 1   

  1. (1. 广西大学计算机与电子信息学院,南宁 530004;2. 广西职业技术学院计算机技术与电子信息工程系,南宁 530226)
  • 收稿日期:2011-01-25 出版日期:2011-08-20 发布日期:2011-08-20
  • 作者简介:李 捷(1979-),女,讲师、硕士研究生,主研方向:并行与分布式计算技术;李陶深,教授、博士;杨林峰(通讯作者),讲师、博士研究生
  • 基金资助:
    国家自然科学基金资助项目(60963022);广西自然科学基金资助项目(0832056);广西研究生教育创新计划基金资助项目(105 930901022)

Parallel Algorithm of Large Scale Structured Quadratic Programming

LI Jie 1,2, LI Tao-shen 1, YANG Lin-feng 1   

  1. (1. School of Computer and Electronics Information, Guangxi University, Nanning 530004, China;2. Department of Computer Electronics and Information, Guangxi Vocational & Technical College, Nanning 530226, China)
  • Received:2011-01-25 Online:2011-08-20 Published:2011-08-20

摘要: 在内点算法(IPM)框架基础上,分析具有分块带边结构系数矩阵与箭形结构二次项的二次规划(QP)问题,导出其既约与最简既约修正方程。对既约修正方程系数矩阵进行置换,使其具有箭形分块结构,并结合该结构与解耦技术给出修正方程的并行求解算法,设计QP问题的并行IPM结构。在集群环境下的数值实验结果表明,该算法具有较好的加速比和可扩展性,适合求解大规模结构化QP问题。

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

Abstract: 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.

Key words: Quadratic Programming(QP), block bordered matrix, parallel algorithm, decoupling, simpler correction equation

中图分类号: