Fast Alternating Linearization Methods for Minimizing the Sum of Two Convex Functions. (arXiv:0912.4571v1 [math.OC])

Splitting and alternating direction methods have been widely used for solving
convex optimization problems. We present in this paper two first-order
alternating linearization algorithms based on variable splitting and
alternating linearization techniques for minimizing the sum of two convex
functions. We prove that the number of iterations needed by the first algorithm
is $O(1/epsilon)$ to obtain an $epsilon$-optimal solution. The second
algorithm is an accelerated version of the first one, where the complexity
result is improved to $O(1/sqrt{epsilon})$, while the computational effort
required at each iteration is almost unchanged. Our algorithms and complexity
results can also be extended to more general problems involving linear
operators. Algorithms in this paper are Gauss-Seidel type methods, so they are
different with the ones proposed by Goldfarb and Ma in [12] where the
algorithms are all Jacobi type methods. Preliminary numerical results are
reported to support our theoretical conclusions and demonstrate the practical
potential of our algorithms.

Published by

Original source : http://arxiv.org/abs/0912.4571...