Fast Multiple Splitting Algorithms for Convex Optimization. (arXiv:0912.4570v1 [math.OC])

We present in this paper two different classes of general $K$-splitting
algorithms for solving convex optimization problems. We prove that the number
of iterations needed by the first class of algorithms to obtain an
$epsilon$-optimal solution is $O(1/epsilon)$. The algorithms in the second
class are accelerated versions of those in the first class, where the
complexity result is improved to $O(1/sqrt{epsilon})$ while the computational
effort required at each iteration is almost unchanged. The algorithms are also
extended to solving convex optimization problems involving linear operators
such as those that arise in variational formulations of partial differential
equations and in optimal control problems. To the best of our knowledge, the
complexity results presented in this paper are the first ones of this type that
have been given for splitting and alternating direction type methods. Moreover,
all algorithms proposed in this paper are parallelizable, which makes them
particularly attractive for solving large-scale problems.

Published by

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