Solving Optimization Problems via Lagrangian Decomposition

This chapter considers large-scale optimization problems with complicating constraints that can be addressed using Lagrangian decomposition algorithms. Complicating constraints are constraints that if ignored (relaxed) render a decomposable problem, that is, a problem that decomposes into several subproblems. Lagrangian decomposition algorithms decompose the original problem via Lagrangian functions or augmented Lagrangian functions and rely on an iterative procedure to obtain the solution of the original problem by iteratively solving the subproblems resulting from the decomposition. We first introduce the structure of problems with complicating constraints, summarize well-known facts of duality theory that are relevant for the algorithms considered, derive multiplier updating rules if a Lagrangian or an augmented Lagrangian function is used (which is the most common approach), and briefly describe alternative Lagrangian decomposition algorithms. We then consider the optimality conditions decomposition (OCD) algorithm in detail, and the augmented Lagrangian decomposition (ALD) algorithm, also called the alternating direction method of multipliers. We conclude with some final remarks.