nach oben

Erschienen in:

2019 | OriginalPaper | Buchkapitel

Mirror Descent and Constrained Online Optimization Problems

verfasst von : Alexander A. Titov, Fedor S. Stonyakin, Alexander V. Gasnikov, Mohammad S. Alkousa

Erschienen in: Optimization and Applications

Verlag: Springer International Publishing

Einloggen

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config

KI-gestützte Suche

Aus

Abstract

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.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Vorheriges Kapitel Subgradient Method with Polyak’s Step in Transformed Space

Nächstes Kapitel Primal-Dual Newton’s Method with Steepest Descent for Linear Programming

Bayandina, A., Gasnikov, A., Gasnikova, E., Matsievsky, S.: Primal-dual mirror descent for the stochastic programming problems with functional constraints. Comput. Math. Math. Phys. (2018, accepted). https://arxiv.org/pdf/1604.08194.pdf. (in Russian)

Bayandina, A., Dvurechensky, P., Gasnikov, A., Stonyakin, F., Titov, A.: Mirror descent and convex optimization problems with non-smooth inequality constraints. In: Large-Scale and Distributed Optimization, pp. 181–213. Springer, Cham (2018)CrossRef

Beck, A., Ben-Tal, A., Guttmann-Beck, N., Tetruashvili, L.: The comirror algorithm for solving nonsmooth constrained convex problems. Oper. Res. Lett. 38(6), 493–498 (2010)MathSciNetCrossRef

Beck, A., Teboulle, M.: Mirror descent and nonlinear projected subgradient methods for convex optimization. Oper. Res. Lett. 31(3), 167–175 (2003)MathSciNetCrossRef

Ben-Tal, A., Nemirovski, A.: Lectures on Modern Convex Optimization. Society for Industrial and Applied Mathematics, Philadelphia (2001)CrossRef

Ben-Tal, A., Nemirovski, A.: Robust Truss Topology Design via semidefinite programming. SIAM J. Optim. 7(4), 991–1016 (1997)MathSciNetCrossRef

Boyd, S., Vandenberghe, L.: Convex Optimization. Cambridge University Press, New York (2004)CrossRef

Bubeck, S., Eldan, R.: Multi-Scale Exploration of Convex Functions and Bandit Convex Optimization. e-print (2015). http://research.microsoft.com/en-us/um/people/sebubeck/ConvexBandits.pdf

Bubeck, S., Cesa-Bianchi, N.: Regret analysis of stochastic and nonstochastic multi-armed bandit problems. Found. Trends Mach. Learn. 5(1), 1–122 (2012)CrossRef

10.

Gasnikov, A.V., Lagunovskaya, A.A., Morozova, L.E.: On the relationship between simulation logit dynamics in the population game theory and a mirror descent method in online optimization using the example of the shortest path problem. Proc. MIPT 7(4), 104–113 (2015). (in Russian)

11.

Gasnikov, A.V., Lagunovskaya, A.A., Usmanova, I.N., Fedorenko, F.A., Krymova, E.A.: Stochastic online optimization. Single-point and multi-point non-linear multi-armed bandits. Convex and strongly-convex case. Autom. Remote Control 78(2), 224–234 (2017)MathSciNetCrossRef

12.

Hazan, E., Kale, S.: Beyond the regret minimization barrier: optimal algorithms for stochastic strongly-convex optimization. JMLR 15, 2489–2512 (2014)MathSciNetMATH

13.

Hazan, E.: Introduction to online convex optimization. Found. Trends Optim. 2(3–4), 157–325 (2015)

14.

Jenatton, R., Huang, J., Archambeau, C.: Adaptive Algorithms for Online Convex Optimization with Long-term Constraints (2015). https://arxiv.org/abs/1512.07422

15.

Kalai, A., Vempala, S.: Efficient algorithms for online decision problems. J. Comput. Syst. Sci. 71, 291–307 (2005)MathSciNetCrossRef

16.

Lugosi, G., Cesa-Bianchi, N.: Prediction, Learning and Games. Cambridge University Press, New York (2006)MATH

17.

Nemirovskii, A.: Efficient methods for large-scale convex optimization problems. Ekonomika i Matematicheskie Metody (1979). (in Russian)

18.

Nemirovsky, A., Yudin, D.: Problem Complexity and Method Efficiency in Optimization. Wiley, New York (1983)

19.

Nesterov, Y.: Introductory Lectures on Convex Optimization: A Basic Course. Kluwer Academic Publishers, Massachusetts (2004)CrossRef

20.

Polyak, B.: A general method of solving extremum problems. Sov. Math. Dokl. 8(3), 593–597 (1967). (in Russian)MATH

21.

Shor, N.Z.: Generalized gradient descent with application to block programming. Kibernetika 3(3), 53–55 (1967). (in Russian)MathSciNet

22.

Stonyakin, F.S., Alkousa, M.S., Stepanov, A.N., Barinov, M.A.: Adaptive mirror descent algorithms in convex programming problems with Lipschitz constraints. Trudy Instituta Matematiki i Mekhaniki URO RAN 24(2), 266–279 (2018)CrossRef

23.

Shpirko, S., Nesterov, Y.: Primal-dual subgradient methods for huge-scale linear conic problem. SIAM J. Optim. 24(3), 1444–1457 (2014)MathSciNetCrossRef

24.

Vasilyev, F.: Optimization Methods. Fizmatlit, Moscow (2002). (in Russian)

Titel: Mirror Descent and Constrained Online Optimization Problems
verfasst von: Alexander A. Titov
Fedor S. Stonyakin
Alexander V. Gasnikov
Mohammad S. Alkousa
Verlag: Springer International Publishing
Buch: Optimization and Applications
Print ISBN: 978-3-030-10933-2

Electronic ISBN: 978-3-030-10934-9

Copyright-Jahr: 2019
DOI: https://doi.org/10.1007/978-3-030-10934-9_5

Springer Professional

Abstract

Bitte loggen Sie sich ein, um Zugang zu Ihrer Lizenz zu erhalten.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Technik"

Springer Professional "Wirtschaft"