Fast Multiple Splitting Algorithms for Convex Optimization

Details Fast Multiple Splitting Algorithms for Convex Optimization Fast Multiple Splitting Algorithms for Convex Optimization

2009-12-23

arxiv.org/abs/0912.4570v2

Mathematics

Optimization and Control

Scientific paper

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. Moreover, all algorithms proposed in this paper are parallelizable, which makes them particularly attractive for solving certain large-scale problems.

Affiliated with

Also associated with

No associations

Rating

Fast Multiple Splitting Algorithms for Convex Optimization does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Fast Multiple Splitting Algorithms for Convex Optimization, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Fast Multiple Splitting Algorithms for Convex Optimization will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-362773