Excessive gap technique in non-smooth convex minimization

In this paper we introduce a new primal-dual technique for convergence analysis of gradient schemes for non-smooth convex optimization. As an example of its application, we derive a primal-dual gradient method for a special class of structured non-smooth optimization problems, which ensures a rate of convergence of the order O(1/k), where k is the iteration count. Another example is a gradient scheme which minimizes a non-smooth strongly convex function with known structure with the rate of convergence O(1/k exp2). In both cases the effciency of the methods is higher than the corresponding black-box lower complexity bounds by an order of magnitude.