Composite optimization for the resource allocation problem

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.

Keywords:

• Decentralized pricing
• primal–dual method
• accelerated gradient method
• gradient method
• composite optimization

2010 Mathematics Subject Classifications:

• 90C25
• 68Q25
• 91B32

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

The work of A.V. Gasnikov and P.E. Dvurechensky in the first part of the paper was supported by Russian Foundation for Fundamental Investigations (RFBR) grant 18-29-03071 mk. The work of A.V. Gasnikov in the second part of the paper partially supported by Russian Foundation for Basic Research (RFBR) 18-31-20005 mol-a-ved. The work of A.V. Gasnikov and A.S. Ivanova in Appendix was prepared within the framework of the HSE University Basic Research Program and funded by the Russian Academic Excellence Project ‘5–100’.

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.