Abstract
In this paper, we consider resource allocation problem stated as a convex minimization problem with linear constraints. To solve this problem, we use gradient and accelerated gradient descent applied to the dual problem and prove the convergence rate both for the primal iterates and the dual iterates. We obtain faster convergence rates than the ones known in the literature. We also provide economic interpretation for these two methods. This means that iterations of the algorithms naturally correspond to the process of price and production adjustment in order to obtain the desired production volume in the economy. Overall, we show how these actions of the economic agents lead the whole system to the equilibrium.
Acknowledgements
We would like to thank Yu. Nesterov for fruitful discussions.
Disclosure statement
No potential conflict of interest was reported by the authors.
Additional information
Funding
Notes on contributors
Anastasiya Ivanova
Anastasia Ivanova got BSc degree from the Faculty of Control and Applied Mathematics of Moscow Institute of Physics and Technology (MIPT) in 2018. Since 2018 a master student in MIPT.
Pavel Dvurechensky
Pavel Dvurechensky got BSc and MSc degrees from the Faculty of Control and Applied Mathematics of Moscow Institute of Physics and Technology in 2008 and 2010, respectively. He obtained a PhD from the same university in 2014. Since 2015 he has been a research associate at Weierstrass Institute for Applied Analysis and Stochastics in Berlin.
Alexander Gasnikov
Alexander V. Gasnikov received the BSc, MSc, PhD, Dr habil. degrees from the Department of Control and Applied Mathematics of Moscow Institute of Physics and Technology (Russia) in 2004, 2006, 2007, and 2016, respectively. Since 2011, he has been an Associate Professor with the Department of Mathematical Foundations of Control, MIPT. Also, since 2015, he has been the Lead Researcher with the Institute for Information Transmission Problems of Russian Academy of Science, Moscow, Russia, and an Associate Professor with the Faculty of Computer Science High school of economics.
Dmitry Kamzolov
Dmitry Kamzolov got BSc and MSc degrees from the Faculty of Control and Applied Mathematics of Moscow Institute of Physics and Technology (MIPT) in 2016 and 2018, respectively. Also, he obtained an MSc in Operations Research, Combinatorics and Optimization from the University of Grenoble Alpes. Since 2018 he has been pursuing a PhD in MIPT.