Parallel algorithms with feasible set partitioning for large-scale optimization problems

We consider parallel algorithms for the class of constrained optimization problems. The algorithms are based on the two ideas: gradient projection method and decomposition of the set of constraints into disjoint subsets with different number of constraints. The proposed approach is used for a class of large-scale linear programming problems. A number of simulations was made to analyze computational complexity, convergence speed and the parallelization efficiency. The algorithms show a good performance for the special special computationally difficult benchmark problem. The most efficient decomposition strategy is to partition the feasible set into a relatively small number of subsets. The decomposition by separate constraints demonstrates less efficiency of parallelization.