Yu Du, Xiaodong Lin, Andrzej Ruszczyski
SIAM Journal on Optimization,Vol. 27, Issue 2, Pages: 1102-1117.

We consider the problem of minimizing a sum of several convex nonsmooth functions. We introduce a new algorithm called the selective linearization method, which iteratively linearizes all but one of the functions and employs simple proximal steps. The algorithm is a form of multiple operator splitting in which the order of processing partial functions is not fixed, but rather determined in the course of calculations. Global convergence is proved and estimates of the convergence rate are derived. Specifically, the number of iterations …
[Full Text]

Yu Du, Andrzej Ruszczyski
Journal of Optimization Theory and Applications,Vol. 173, Issue 3, Pages: 908-922.

The number of iterations needed by the bundle method for nonsmooth optimization to achieve a specified solution accuracy can be bounded by the product of the inverse of the accuracy and its logarithm, if the function is strongly convex. The result is true for the versions of the method with multiple cuts and with cut aggregation.
[Full Text]