Research And Implementation Of Parallel Ipm For Optimization On Cluster

Cluster computing is a powerful tool for solving large scale and vary large scale applications, and it is currently a hot subject of research in computing science. With the developing of cluster computing, in the past10years, the research of parallel algorithms for optimization caused extensive attention of scholars, especially the parallel algorithms for some special structured optimizations, and has made great achievements.Interior Point Methods (IPM), with polynomial time complexity, connected Linear Programming (LP) and Nonlinear Programming (NLP) in theory and algorithm. It has shown its power in solving large-scale optimization problems. After considering the architecture of Cluster and data structure of optimization problems in IPM, a novel parallel IPM based on message passing and shared storage will been designed, and the new parallel algorithm will own the characteristics in lower communications and higher speedup. Therefore, research and design more rapid parallel IPM based on IPM theory and platforms characteristics is important for study in parallel algorithm and applications.After integrating the framework of interior point method (IPM) and the blocked border correction equation, the simpler and simplest correction equation has been given and the coefficient matrix of the simplest correction equation is a positive definite symmetric matrix. A parallel factorization-backsolve method for correction equation is proposed by integrating decoupling, and then a parallel IPM for linear programming (LP) has been given. For quadratic programming (QP) problems with special structure, we get the parallel IPM for it after rearranging the coefficient matrix of its correction equation in blocked border structure. At last, the implementations of parallel IPM for structure LP and QP based on Matlab PCT have been given, and some simulations have been show. The simulations show that the two algorithms?good speedup and scalability and powerful for solving blocked border linear programming and structure QP problems.In conclusion, this thesis presents a novel method for designing parallel algorithm for structure LP and QP, and the implementations of parallel IPM for these two kinds of special problems. All of these give the new ideas for the designing and implementation of parallel optimization.