nach oben

Erschienen in:

01.12.2023

On Accelerated Coordinate Descent Methods for Searching Equilibria in Two-Stage Transportation Equilibrium Traffic Flow Distribution Model

verfasst von: N. A. Il’tyakov, M. A. Obozov, I. M. Dyshlevski, D. V. Yarmoshik, M. B. Kubentaeva, A. V. Gasnikov, E. V. Gasnikova

Erschienen in: Programming and Computer Software | Ausgabe 6/2023

Einloggen

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

search-config

KI-gestützte Suche

Aus

Abstract

The search for equilibrium in a two-stage traffic flow model reduces to the solution of a special nonsmooth convex optimization problem with two groups of different variables. For numerical solution of this problem, it is proposed to use the accelerated block-coordinate Nesterov–Stich method with a special choice of block probabilities at each iteration. Theoretical estimates of the complexity of this approach can appreciably improve the estimates of previously used approaches. However, in the general case they do not guarantee faster convergence. Numerical experiments with the proposed algorithms are carried out.

Vorheriger Artikel Decentralized Conditional Gradient Method on Time-Varying Graphs

Nächster Artikel Robust Algebraic Connectivity

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

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+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 "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

Note that although the paper by Nesterov and Stich was published in 2017, they first reported this method in a conference dedicated to the 80th anniversary of B.T. Polyak in May 2015. This is important in the context of the Nesterov–Stich priority, since almost at the same time, but a little later, similar works appeared [11, 13].

Here C_λ and C_μ are arbitrary numbers.

All terms in (15), except for the first nontrivial term softmax, are composite. For a number of functions \(\sigma _{e}^{*}({{t}_{e}})\) (including those induced by the BPR cost functions), the composite property is important, since \(\sigma _{e}^{*}({{t}_{e}})\) can have an unbounded Lipschitz constant for the derivative.

It is difficult to say exactly here, because the complexity of the universal accelerated method varies from the convergence rate of the ordinary accelerated method in the smooth case (optimistic scenario) to the convergence rate of the subgradient method in the nonsmooth case (pessimistic scenario) [26]. In particular, under the pessimistic scenario, the number of computations of \(\nabla {{T}_{{ij}}}(t)\) is proportional to \( \sim {\kern 1pt} {{\varepsilon }^{{ - 2}}}\), while in the new approach, \( \sim {\kern 1pt} \mathop {\max }\nolimits_{(i,j) \in {{P}_{{ij}}}} \ln {\text{|}}{{P}_{{ij}}}{\text{|}}{{\varepsilon }^{{ - 1}}}\) computations of \(\nabla T_{{ij}}^{{\tilde {\gamma }}}(t)\) of similar complexity are required, where ε is the desired accuracy.

It is important to note that the convexity of a problem is understood in this paper as convexity in the set of all variables and not simply as convexity in blocks of variables separately. The latter may not be enough for the original problem to be convex, and the discussed numerical methods could be applied to it. Well-known examples of such problems (block convex, but not overall convex) are problems arising in recommender systems, for example, matrix factorization.

Ortúzar, J.D. and Willumsen, L.G., Modelling Transport, West Sussex, England: Wiley and Sons, 2002).

Boyles, S.D., Lownes, N.E., and Unnikrishnan, A., Transportation Network Analysis, Vol. I: Static and Dynamic Traffic Assignment, 2020.

Gasnikov, A.V. and Gasnikova, E.V., Models of Equilibrium Distribution of Flows in Large Networks, Moscow: URSS, 2023.

Evans, S.P., Derivation and analysis of some models for combining trip distribution and assignment, Transp. Res., 1976, vol. 10, no. 1, pp. 37–57.CrossRef

Gasnikov, A.V. et al., On the three-stage version of stable dynamic model, Mat. Model., 2014, vol. 26, no. 6, pp. 34–70.MATH

Gasnikova, E. et al., An evolutionary view on equilibrium models of transport flows, Mathematics, 2023, vol. 11, no. 4, pp. 858.CrossRef

Kotlyarova, E.V. et al., Finding Equilibriums in two-stage models of tranportation flow distribution over a network, Komput. Issled. Model., 2021, vol. 13, no. 2, pp. 365–379.

Kubentaeva, M. et al., Primal-Dual Gradient Methods for Searching Network Equilibria in Combined Models with Nested Choice Structure and Capacity Constraints. arXive:2307.00427.

Nesterov, Y. and Stich, S., Efficiency of the accelerated coordinate descent method on structured optimization problems, SIAM J. Optim., 2017, vol. 27, no. 1, pp. 110–123.MathSciNetCrossRefMATH

10.

Baimurzina, D.R., Gasnikov, A.V., Gasnikova, E. V., Dvurechensky, P.E., Ershov, E.I., Kubentaeva, M.B., Lagunovskaya, A.A., Universal Method of Searching for Equilibria and Stochastic Equilibria in Transportation Networks, Comput. Math. Math. Phys., 2019, vol. 59, no. 1, pp. 19–33.MathSciNetCrossRefMATH

11.

Gasnikov, A.V., Dvurechensky, P.E., and Usmanova, I.N., On nontriviality of fast (accelerated) randomizes methods, Tr. Mosk. Fiziko-Tekhnich. Inst., 2016, vol. 8, no. 2(30), pp. 67–100.

12.

Gasnikova, E. et al., Sufficient conditions for multi-stages traffic assignment model to be the convex optimization problem, arXiv:2305.09069.

13.

Allen-Zhu, Z. et al., Even faster accelerated coordinate descent using non-uniform sampling, Int. Conference on Machine Learning, PMLR, 2016, pp. 1110–1119.

14.

Gasnikov, A.V., Klenov, S.L., Nurminskii, E.A., Kholodov, Ya.A., and Shamrai, N.B., Introduction to Mathematical Modeling of Transport Flows, Gasnikov, A.V., with appendices by Blank, M.L., Vorontsov, K.V. and Chekhovich, Yu.V., Gasnikova, E.V., Zamyatin, A.A. and Malyshev, V.A., Kolesnikov, A.V., Nesterov, Yu.E. and Shpirko, S.V., and Raigorodskii, Moscow: Mosk. Tsentr Nepreryvnogo Mat. Obrazovaniya, 2013, 2nd ed.

15.

Patriksson, M., The Traffic Assignment Problem: Models and Methods, Courier Dover, 2015.

16.

Stabler, B., Bar-Gera, H., and Sall, E., Transportation Networks for Research Core Team. Transportation Networks for Research. https://github.com/bstabler/TransportationNetworks. Accessed February 16, 2021.

17.

Nesterov, Y. and De Palma, A., Stationary dynamic solutions in congested transportation networks: Summary and perspectives, Networks Spatial Econ., 2003, vol. 3, no. 3, pp. 371–395.CrossRef

18.

Kotlyarova, E.V. et al., Justification of the connection of the Backmann model with degenerate cost functions to the model of stable dynamics, Komput. Issled. Model., 2022, vol. 14, no. 2, pp. 335–342.

19.

Wilson, A.I., Entropy in Urban and Regional Modelling, London: 1970.

20.

Gasnikov, A.V., Gasnikova, E.V., Mendel, M.A., and Chepurchenko, K.V., Evolutionary interpretations of entropy model for correspondence matrix calculation, Mat. Model., 2016, vol. 28, no. 4, pp. 111–124.MathSciNetMATH

21.

Nesterov, Y., Smoothing technique and its applications in semidefinite optimization, Math. Program., 2007, vol. 110, no. 2, pp. 245–259.MathSciNetCrossRefMATH

22.

Peyré, G. and Cuturi, M., Computational optimal transport: With applications to data science, Found. Trends Mach. Learn., 2019, vol. 11, nos. 5–6, pp. 355–607.CrossRefMATH

23.

Guminov, S. et al., Accelerated alternating minimization, ICML, 2021.

24.

Tupitsa, N. et al., Numerical methods for large-scale optimal transport. arXiv:2210.11368.

25.

Nesterov, Y., Universal gradient methods for convex optimization problems, Math. Program., 2015, vol. 152, nos. 1–2, pp. 381–404.MathSciNetCrossRefMATH

26.

Gasnikov, A.V. and Nesterov, Yu.E., Universal method for stochastic composite optimization problems, Comput. Math. Math. Phys., 2018, vol. 58, no. 1, pp. 48–64.MathSciNetCrossRefMATH

27.

Kovalev, D., Gasnikov, A., and Malinovsky, G., An optimal algorithm for strongly convex min-min optimization. arXiv:2212.14439.

28.

Gasnikov–Nesterov, A universal method for stochastic problems composite optimization. arxiv preprint arXiv:1604.05275. 2016.

29.

Kubentayeva, Meruza et al., Primal-dual gradient methods for searching network equilibria in combined models with nested choice structure and capacity constraints. arXiv:2307.00427.

30.

Gasnikov, A.V., Dvurechenskii, P.E, and Usmanova, I.N., On nontriviality of fast (accelerated) randomized methods. arxiv preprint arXiv:1508.02182. 2015.

31.

Aliev, A.S., Mazurin, D.S., Maksimova, D.A., and Shvetsov, V.I., The structure of complex model of the Moscow transportation system, Tr. Inst. Sist. Issled. RAS, 2015, vol. 65, no. 1, pp. 3–15.

32.

Gasnikov, A.V., Modern numerical optimization methods: Universal gradient descent method. arXiv:1711.00394.

33.

Source codes of numerical experiments. https://github.com/Lareton/transport_network_optimization.

34.

Nemirovskii A.S. and Yudin, D.B., Problem Complexity and Method Efficiency in Optimization, Interscience Series in Discrete Mathematics (Nauka, Moscow, 1979; Wiley, 1983), Vol. XV.

35.

Nesterov, Y., Efficiency of coordinate descent methods on huge-scale optimization problems, SIAM J. Optim., 2012, vol. 22, no. 2, pp. 341–362.MathSciNetCrossRefMATH

36.

De Cea, J., Fernandez, J. E., Dekock, V., and Soto, A., Solving network equilibrium problems on multimodal urban transportation networks with multiple user classes, Transport Rev., 2005., vol. 25, no. 3, pp. 293–317.CrossRef

Titel: On Accelerated Coordinate Descent Methods for Searching Equilibria in Two-Stage Transportation Equilibrium Traffic Flow Distribution Model
verfasst von: N. A. Il’tyakov
M. A. Obozov
I. M. Dyshlevski
D. V. Yarmoshik
M. B. Kubentaeva
A. V. Gasnikov
E. V. Gasnikova
Publikationsdatum: 01.12.2023
Verlag: Pleiades Publishing
Erschienen in: Programming and Computer Software / Ausgabe 6/2023
Print ISSN: 0361-7688
Elektronische ISSN: 1608-3261
DOI: https://doi.org/10.1134/S036176882306004X

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 "Technik"

Springer Professional "Wirtschaft+Technik"

Springer Professional "Wirtschaft"

Weitere Artikel der Ausgabe 6/2023

Gradient-Free Algorithms for Solving Stochastic Saddle Optimization Problems with the Polyak–Łojasiewicz Condition

Robust Algebraic Connectivity

Adaptive Variant of the Frank–Wolfe Algorithm for Convex Optimization Problems

Decentralized Conditional Gradient Method on Time-Varying Graphs

Adaptive Methods for Variational Inequalities with Relatively Smooth and Reletively Strongly Monotone Operators

Premium Partner