Mirror Descent and Convex Optimization Problems with Non-smooth Inequality Constraints

P. 181–213.

Bayandina A., Dvurechensky P., Gasnikov A., Stonyakin F. S., Titov A.

We consider the problem of minimization of a convex function on a simple set with convex non-smooth inequality constraint and describe first-order methods to solve such problems in different situations: smooth or non-smooth objective function; convex or strongly convex objective and constraint; deterministic or randomized information about the objective and constraint. Described methods are based on Mirror Descent algorithm and switching subgradient scheme. One of our focus is to propose, for the listed different settings, a Mirror Descent with adaptive stepsizes and adaptive stopping rule. We also construct Mirror Descent for problems with objective function, which is not Lipschitz, e.g., is a quadratic function. Besides that, we address the question of recovering the dual solution in the considered problem.

Keywords: Stochastic adaptive mirror descent, Primal-dual methods, Constrained non-smooth convex optimization

In book

Large-Scale and Distributed Optimization

Giselsson P., Rantzer A. Vol. 2227. , Springer, 2018.