Composite optimization for the resource allocation problem

References

• A.S. Anikin, A.V. Gasnikov, P.E. Dvurechensky, A.I. Tyurin and A.V. Chernov, Dual approaches to the minimization of strongly convex functionals with a simple structure under affine constraints, Comput. Math. Math. Phys. 57 (2017), pp. 1262–1276. doi: 10.1134/S0965542517080048
   Web of Science ®Google Scholar
• K.J. Arrow and L. Hurwicz, Decentralization and computation in resource allocation, Stanford University, Department of Economics;1958.
   Google Scholar
• J.P. Aubin, L'analyse non-linéaire et ses motivations économiques, Masson, Paris, 1984.
   Google Scholar
• D.R. Baimurzina, A.V. Gasnikov, E.V. Gasnikova, P.E. Dvurechensky, E.I. Ershov, M.B. Kubentaeva and A.A. Lagunovskaya, Universal method of searching for equilibria and stochastic equilibria in transportation networks, Comput. Math. Math. Phys. 59 (2019), pp. 19–33. arXiv:1701.02473. doi: 10.1134/S0965542519010020
   Web of Science ®Google Scholar
• A. Bayandina, P. Dvurechensky, A. Gasnikov, F. Stonyakin and A. Titov, Mirror descent and convex optimization problems with non-smooth inequality constraints, in Large-Scale and Distributed Optimization, P. Giselsson and A. Rantzer, eds., chap. 8, Springer International Publishing, 2018, pp. 181–215, arXiv:1710.06612.
   Google Scholar
• S. Boyd, N. Parikh, E. Chu, B. Peleato and J. Eckstein, Distributed optimization and statistical learning via the alternating direction method of multipliers, Found. Trends Mach. Learn. 3 (2011), pp. 1–122. http://dx.doi.org/10.1561/2200000016.
   Google Scholar
• D.E. Campbell, Resource allocation mechanisms, Cambridge University Press, Cambridge, 1987.
   Google Scholar
• A. Chernov, P. Dvurechensky and A. Gasnikov, Fast Primal-Dual Gradient Method for Strongly Convex Minimization Problems with Linear Constraints, Discrete Optimization and Operations Research: 9th International Conference, DOOR 2016, Vladivostok, Russia, September 19–23, 2016, Proceedings, Springer International Publishing, 2016, pp. 391–403.
   Google Scholar
• J.C. Duchi, A. Agarwal and M.J. Wainwright, Dual averaging for distributed optimization: Convergence analysis and network scaling, IEEE. Trans. Automat. Contr. 57 (2012), pp. 592–606. doi: 10.1109/TAC.2011.2161027
   Web of Science ®Google Scholar
• D. Dvinskikh, E. Gorbunov, A. Gasnikov, P. Dvurechensky and C.A. Uribe, On Primal–Dual Approach for Distributed Stochastic Convex Optimization over Networks, 2019 IEEE Conference on Decision and Control (CDC), arXiv:1903.098442019.
   Google Scholar
• P. Dvurechensky, A. Gasnikov and A. Kroshnin, Computational Optimal Transport: Complexity by Accelerated Gradient Descent Is Better Than by Sinkhorn's Algorithm, Proceedings of the 35th International Conference on Machine Learning, Proceedings of Machine Learning Research, Vol. 80, arXiv:1802.04367, 2018, pp. 1367–1376.
   Google Scholar
• P. Dvurechensky, A. Gasnikov, E. Gasnikova, S. Matsievsky, A. Rodomanov and I. Usik, Primal-Dual Method for Searching Equilibrium in Hierarchical Congestion Population Games, Supplementary Proceedings of the 9th International Conference on Discrete Optimization and Operations Research and Scientific School (DOOR 2016) Vladivostok, Russia, September 19–23, 2016, arXiv:1606.08988, 2016, pp. 584–595.
   Google Scholar
• P. Dvurechensky, D. Dvinskikh, A. Gasnikov, C.A. Uribe and A. Nedić, Decentralize and Randomize: Faster Algorithm for Wasserstein Barycenters, Advances in Neural Information Processing Systems 31, NeurIPS 2018, arXiv:1806.03915, Curran Associates, Inc., 2018, pp. 10783–10793.
   Google Scholar
• P.E. Dvurechensky, A.V. Gasnikov and A.A. Lagunovskaya, Parallel algorithms and probability of large deviation for stochastic convex optimization problems, Numer. Anal. Appl. 11 (2018), pp. 33–37. arXiv:1701.01830. doi: 10.1134/S1995423918010044
   Web of Science ®Google Scholar
• E.J. Friedman and S.S. Oren, The complexity of resource allocation and price mechanisms under bounded rationality, Economic Theory 6 (1995), pp. 225–250. doi: 10.1007/BF01212489
   Web of Science ®Google Scholar
• A. Gasnikov, Universal gradient descent, arXiv preprint arXiv:1711.00394 (2017).
   Google Scholar
• S.V. Guminov, Y.E. Nesterov, P.E. Dvurechensky and A.V. Gasnikov, Accelerated primal-dual gradient descent with linesearch for convex, nonconvex, and nonsmooth optimization problems, Doklady Mathematics 99 (2019), pp. 125–128. doi: 10.1134/S1064562419020042
   Web of Science ®Google Scholar
• A. Ivanova, A. Gasnikov, E. Nurminski and E. Vorontsova, Walrasian equilibrium and centralized distributed optimization from the point of view of modern convex optimization methods on the example of resource allocation problem, Siberian J. Num. Math. 22 (2019), pp. 411–432. Sib. Branch of Russ. Acad. of Sci. Novosibirsk.
   Google Scholar
• A. Ivanova, D. Pasechnyuk, P. Dvurechensky, A. Gasnikov and E. Vorontsova, Numerical methods for the resource allocation problem in networks, Comput. Math. Math. Phys. (2020), arXiv:1909.13321.
   Web of Science ®Google Scholar
• D. Jakovetić, J. Xavier and J.M.F. Moura, Fast distributed gradient methods, IEEE. Trans. Automat. Contr. 59 (2014), pp. 1131–1146. doi: 10.1109/TAC.2014.2298712
   Web of Science ®Google Scholar
• A. Kakhbod, Resource allocation in decentralized systems with strategic agents: an implementation theory approach, Springer Science & Business Media, New York, 2013.
   Google Scholar
• A. Kroshnin, N. Tupitsa, D. Dvinskikh, P. Dvurechensky, A. Gasnikov and C. Uribe, On the Complexity of Approximating Wasserstein Barycenters, Proceedings of the 36th International Conference on Machine Learning, Proceedings of Machine Learning Research, Vol. 97, 09–15 Jun, arXiv:1901.08686, PMLR, Long Beach, CA, 2019, pp. 3530–3540.
   Google Scholar
• A. Nedic and A. Ozdaglar, Distributed subgradient methods for multi-agent optimization, IEEE. Trans. Automat. Contr. 54 (2009), pp. 48–61. doi: 10.1109/TAC.2008.2009515
   Web of Science ®Google Scholar
• Y. Nesterov, Smooth minimization of non-smooth functions, Math. Program. 103 (2005), pp. 127–152. doi: 10.1007/s10107-004-0552-5
   Web of Science ®Google Scholar
• Y. Nesterov and V. Shikhman, Dual subgradient method with averaging for optimal resource allocation, Eur. J. Oper. Res. 270 (2018), pp. 907–916. doi: 10.1016/j.ejor.2017.09.043
   Web of Science ®Google Scholar
• B. Polyak, A general method of solving extremum problems, Soviet Math. Doklady 8 (1967), pp. 593–597.
   Google Scholar
• D.B. Rokhlin, Resource allocation in communication networks with large number of users: stochastic gradient descent, Theory Probab. Appl. (2019), accepted.
   Web of Science ®Google Scholar
• K. Scaman, F. Bach, S. Bubeck, Y.T. Lee and L. Massoulié, Optimal Algorithms for Smooth and Strongly Convex Distributed Optimization in Networks, Proceedings of the 34th International Conference on Machine Learning, Proceedings of Machine Learning Research, Vol. 70, 06–11 Aug, PMLR, International Convention Centre, Sydney, Australia, 2017, pp. 3027–3036. Available at http://proceedings.mlr.press/v70/scaman17a.html.
   Google Scholar
• K. Scaman, F. Bach, S. Bubeck, Y.T. Lee and L. Massoulié, Optimal convergence rates for convex distributed optimization in networks, J. Mach. Learn. Res. 20 (2019), pp. 1–31. , http://jmlr.org/papers/v20/19-543.html.
   Web of Science ®Google Scholar
• C.A. Uribe, D. Dvinskikh, P. Dvurechensky, A. Gasnikov and A. Nedić, Distributed Computation of Wasserstein Barycenters Over Networks, 2018 IEEE Conference on Decision and Control (CDC), arXiv:1803.02933, 2018, pp. 6544–6549.
   Google Scholar