查看文章

We present several state-of-the-art first-order methods for well-structured large-scale nonsmooth convex programs. In contrast to their black-boxoriented prototypes considered in Chapter 5, the methods in question utilize the problem structure in order to convert the original nonsmooth minimization problem into a saddle-point problem with a smooth convex-concave cost function. This reformulation allows us to accelerate the solution process significantly. As in Chapter 5, our emphasis is on methods which, under favorable circumstances, exhibit a (nearly) dimension-independent convergence rate. Along with investigating the general well-structured situation, we outline possibilities to further accelerate first-order methods by randomization.