EN|RU
English version:
Journal of Applied and Industrial Mathematics, 2020, 14:1, 92-103

Volume 27, No 1, 2020, P. 43-60

UDC 519.8
I. V. Konnov, E. Laitinen, and O. V. Pinyagina
Inexact partial linearization methods for network equilibrium problems

Abstract:
We propose some simplified modifications of the partial linearization method for network equilibrium problems with mixed demand. In these modifications, the auxiliary direction choice problem is solved approximately. In the modifications, the basic convergence properties of the original method are preserved, while the inexact solution of the auxiliary problems reduces the computational efforts. Preliminary numerical tests show the advantages and efficiency of our approach as compared with the exact variant of the method.
Tab. 3, illustr. 2, bibliogr. 17.

Keywords: network equilibrium problem, partial linearization method, descent direction, inexact solution.

DOI: 10.33048/daio.2020.27.658

Igor’ V. Konnov 1
Erkki Laitinen 2

Olga V. Pinyagina 1
1. Kazan Federal University,
18 Kremlyovskaya Street, 420008 Kazan, Russia
2. Oulu University,
1 Pentti Kaiteran Street, 90014 Oulu, Finland
e-mail: konn-igor@ya.ru, erkki.laitinen@oulu.fi, olga.piniaguina@kpfu.ru

Received April 23, 2019
Revised November 5, 2019
Accepted November 27, 2019

References

[1] S. Dafermos, Traffic equilibrium and variational inequalities, Transp. Sci. 14 (1), 42–54 (1980).

[2] S. Dafermos, The general multimodal network equilibrium problem with elastic demand, Networks 12 (1), 57–72 (1982).

[3] A. Nagurney, Network Economics: A Variational Inequality Approach (Kluwer Acad. Publ., Dordrecht, 1999).

[4] M. Patriksson, The Traffic Assignment Problem: Models and Methods (Dover, Mineola, NY, 2015).

[5] T. L. Magnanti, Models and algorithms for predicting urban traffic equilibria, in Transportation Planning Models (North–Holland, Amsterdam, 1984), pp. 153–185.

[6] I. Konnov and O. Pinyagina, Partial linearization method for network equilibrium problems with elastic demands, in Discrete Optimization and Op?erations Research (Proc. 9th Int. Conf. DOOR-2016, Vladivostok, Russia,Sept. 19–23, 2016) (Springer, Heidelberg, 2016), pp. 418–429.

[7] I. V. Konnov, Simplified versions of the conditional gradient method, Optimization 67 (12), 2275–2290 (2018).

[8] H. Mine and M. Fukushima, A minimization method for the sum of a convex function and a continuously differentiable function, J. Optim. Theor. Appl. 33, 9–23 (1981).

[9] M. Patriksson, Cost approximation: A unified framework of descent algorithms for nonlinear programs, SIAM J. Optim. 8, 561–582 (1998).

[10] M. Patriksson, Nonlinear Programming and Variational Inequality Problems: A Unified Approach (Kluwer Acad. Publ., Dordrecht, 1999).

[11] K. Bredies, D. A. Lorenz, and P. Maass, A generalized conditional gradient method and its connection to an iterative shrinkage method, Comput. Optim. Appl. 42, 173–193 (2009).

[12] G. Scutari, F. Facchinei, P. Song, D. P. Palomar, and J.-S. Pang, Decomposition by partial linearization: Parallel optimization of multi-agent systems, IEEE Trans. Signal Process. 62, 641-656 (2014).

[13] I. V. Konnov, On auction equilibrium models with network applications, NETNOMICS: Econ. Res. Electron. Networking 16 (1), 107–125 (2015).

[14] O. Pinyagina, On a network equilibrium problem with mixed demand, Discrete Optimization and Operations Research (Proc. 9th Int. Conf. DOOR-2016, Vladivostok, Russia, Sept. 19–23, 2016) (Springer, Heidelberg, 2016), pp. 578–583.

[15] O. V. Pinyagina, The network equilibrium problem with mixed demand, Diskretn. Anal. Issled. Oper. 24 (4), 77–94 (2017) [J. Appl. Ind. Math. 11 (4), 554–563 (2017)].

[16] D. P. Bertsekas and E. M. Gafni, Projection methods for variational inequalities with application to the traffic assignment problem, in Nondifferential and Variational Techniques in Optimization (Springer, Heidelberg, 1982), pp. 139–159.

[17] A. B. Nagurney, Comparative tests of multimodal traffic equilibrium methods, Transp. Res., Part B: Methodological 18 (1), 469–485 (1984).
 © Sobolev Institute of Mathematics, 2015