Mirror Descent Methods with a Weighting Scheme for Outputs for Optimization Problems with Functional Constraints

This paper is devoted to new mirror descent-type methods with switching between two types of iteration points (productive and nonproductive) for constrained convex optimization problems with several convex functional (inequality-type) constraints. We propose two methods (a standard one and its modification) with a new weighting scheme for points in each iteration of methods, which assigns smaller weights to the initial points and larger weights to the most recent points. Thus, as a result, it improves the convergence rate of the proposed methods (empirically). The proposed modification makes it possible to reduce the running time of the method due to skipping some of the functional constraints at nonproductive steps. We derive bounds for the convergence rate of the proposed methods with time-varying step sizes, which show that the proposed methods are optimal from the viewpoint of lower oracle estimates. The results of some numerical experiments, which illustrate the advantages of the proposed methods for some examples, such as the best approximation problem, the Fermat – Torricelli – Steiner problem, the smallest covering ball problem, and the maximum of a finite collection of linear functions, are also presented.