Applications of a Splitting Algorithm to Decomposition in Convex Programming
Paul Tseng · 1988
Recently Han and Lou [18] proposed a highly parallelizable decomposition algorithm for convex programming involving strongly convex costs. We show in this paper that their algorithm, as well as the method of multipliers [17, 19, 34] and the dual gradient method [8, 40], are special cases of a certain multiplier method for separable convex programming. This multiplier method is similar to the alternating direction method of multipliers [10, 15] but uses both Lagrangian and augmented Lagrangian functions. We also apply this method to symmetric linear complementarity problems to obtain a new class of matrix splitting algorithms. Finally, we show that this method is itself a dual application of an algorithm of Gabay [12] for finding a zero of the sum of two maximal monotone operators. We give an extension of Gabay's algorithm that allows dynamic stepsizes and show that, under certain conditions, it has a linear rate of convergence. We also apply this algorithm to variational inequalities.