分块带边结构线性规划并行算法

基于内点算法(Interior Point Method,IPM)框架,导出具有分块带边结构系数矩阵的线性规划(Linear Pro-gramming,LP)问题的简化和最简修正方程,并证明最简修正方程的对角分块具有正定性。结合正定矩阵的Cholesky分解和解耦技术设计了修正方程的并行求解方法,给出了LP的并行内点算法结构。集群环境下的数值实验表明,所提算法具有很好的加速比和可扩展性,适合求解大规模结构化LP问题。

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

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