Research On Some Parallel Algorithms For Optimization Problems

In this paper, based on the parallel variable distribution(PVD) algorithm proposed by Ferris and Mangasarian in 1994 and the parallel variable transformation (PVT) algorithm presented by Fukushima in 1998, we proposed a modified PVT algorithm and three PVD algorithms, respectively for special structure nonlinear optimization problems.Firstly, we introduced the development and the current research situations of the parallel optimization algorithms as well as some parallel environments and optimization softwares.In the second chapter, an improvement of PVT algorithm for unconstrained optmization problem was discussed and an asynchronous PVT algorithm was presented.In the third and fourth chapter, we mainly concerned PVD algorithms for constrained optimization problem. In the third chapter, not assuming that the constraints are convex, but assuming with block-separable structure, we suggested that each PVD subproblem can be solved inexactly by solving three systems of linear equations with the same coefficient matrix. This makes the computation much less than that by solving a sequential quadratic programming(SQP) for every PVD subproblems presented by Sagastizabal and Solodov in 2002 .In the fourth chapter, we considered the optimization problem with linear constraints. In the constructing of the PVD direction which is responsible for the change of secondary variables in PVD algorithm, we employed the reduced gradient of the objective function instead of the projected gradient proposed by Solodov in 1998, which reduced the computation amount.