Parallel Subgradient Algorithm with Block Dual Decomposition for Large-scale Optimization

Area of Science:

• Computational Optimization
• Operations Research
• Applied Mathematics

Background:

• Large-scale optimization problems often require efficient solution methods.
• Lagrangian dual reformulation is a common technique, but the choice of reformulation impacts performance.
• Parallel sub-gradient methods are used for solving these reformulations.

Purpose of the Study:

• To investigate how different reformulations affect solution time in large-scale optimization.
• To introduce and analyze block dual decomposition as a method for improving computational efficiency.
• To demonstrate the impact of problem structure on the convergence of sub-gradient methods.

Main Methods:

• Utilizing Lagrangian dual reformulation for large-scale optimization problems.
• Applying parallel sub-gradient methods to solve the dual problem.
• Developing and evaluating block dual decomposition strategies, including using community detection algorithms.
• Analyzing the trade-off between iteration cost and convergence rate.

Main Results:

• Block dual decomposition decomposes problems into smaller, parallelizable sub-problems.
• The choice of block decomposition critically affects the convergence rate of sub-gradient methods.
• Increasing dualized constraints reduces per-iteration cost but increases total iterations.
• Community detection offers an effective approach for block decomposition.

Conclusions:

• Prior knowledge of problem structure is crucial for effective dual decomposition in large-scale optimization.
• Block decomposition strategies, guided by structural insights, can significantly reduce computational effort.
• Balancing the number of dualized constraints is key to optimizing solution time.