Mirror Descent and Constrained Online Optimization Problems

A. Titov; Stonyakin F. S.; A. Gasnikov; M. Alkousa

doi:10.1007/978-3-030-10934-9_5

Publications

?

Mirror Descent and Constrained Online Optimization Problems

P. 64–78.

Titov A., Stonyakin F. S., Gasnikov A., Alkousa M.

We consider the following class of online optimization problems with functional constraints. Assume, that a finite set of convex Lipschitz-continuous non-smooth functionals are given on a closed set of n-dimensional vector space. The problem is to minimize the arithmetic mean of functionals with a convex Lipschitz-continuous non-smooth constraint. In addition, it is allowed to calculate the (sub)gradient of each functional only once. Using some recently proposed adaptive methods of Mirror Descent the method is suggested to solve the mentioned constrained online optimization problem with an optimal estimate of accuracy. For the corresponding non-Euclidean prox-structure, the case of a set of n-dimensional vectors lying on the standard n-dimensional simplex is considered.

Language: English

DOI

Text on another site

Keywords: adaptive mirror descent Online convex optimization Non-euclidean prox-structure

In book

Optimization and Applications 9th International Conference, OPTIMA 2018, Petrovac, Montenegro, October 1–5, 2018, Revised Selected Papers

Springer International Publishing, 2019.

Adaptive Mirror Descent Algorithms for Convex and Strongly Convex Optimization Problems with Functional Constraints

Stonyakin F. S., Alkousa M., Stepanov A. N. et al., Journal of Applied and Industrial Mathematics (перевод журналов "Сибирский журнал индустриальной математики" и "Дискретный анализ и исследование операций") 2019 Vol. 13 P. 557–574

Under consideration are some adaptive mirror descent algorithms for the problems of minimization of a convex objective functional with several convex Lipschitz (generally, nonsmooth) functional constraints. It is demonstrated that the methods are applicable to the objective functionals of various levels of smoothness: The Lipschitz condition holds either for the objective functional itself or for ...

Added: October 29, 2020

Mirror descent for constrained optimization problems with large subgradient values of functional constraints

Stonyakin F. S., Stepanov A. N., Gasnikov A. et al., Computer Research and Modeling 2020 Vol. 12 No. 2 P. 301–317

The paper is devoted to the problem of minimization of the non-smooth functional f with a non-positive non-smooth Lipschitz-continuous functional constraint. We consider the formulation of the problem in the case of quasi-convex functionals. We propose new strategies of step-sizes and adaptive stopping rules in Mirror Descent for the considered class of problems. It is ...

Added: October 27, 2020