Fast Multiple Splitting Algorithms for Convex Optimization

Understand

We present in this paper two different classes of general $K$-splitting algorithms for solving finite-dimensional convex optimization problems.

• Under the assumption that the function being minimized has a Lipschitz continuous gradient, 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.
• 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.