Subspace correction as a general framework for convex optimization algorithms

Abstract

This paper shows that subspace correction methods provide a common algorithmic and theoretical foundation for several classes of convex optimization algorithms, including operator splitting, alternating projection, and multiplier methods. The underlying principle is to decompose a problem into smaller subproblems and combine their solutions, a strategy that appears throughout iterative algorithms. The main tool is an iterate-level formalism, which we call dualization, that abstracts classical primal--dual correspondences and relates a subspace correction method for a dual problem to an algorithm for the corresponding primal problem via a primal--dual consistency relation. At the algorithmic level, dualizing successive subspace correction yields the Peaceman--Rachford and Douglas--Rachford splitting methods; the von Neumann and Dykstra alternating projection algorithms arise as special cases. Dualizing parallel subspace correction yields a parallel splitting method. Multiplier methods, including the alternating direction method of multipliers (ADMM), are connected to subspace correction through the same mechanism together with equivalent block formulations. In particular, a multi-block ADMM-type algorithm is obtained by dualizing a splitting method derived from successive subspace correction. At the theoretical level, the primal--dual consistency relation transfers convergence estimates from subspace correction to the derived algorithms under suitable assumptions. Thus, these operator splitting, alternating projection, and multiplier algorithms can be derived from subspace correction at both the algorithmic and theoretical levels.

49 pages, 1 figures