A New Algorithm of the Variational Inequality Problems with Application on the Asymmetric Traffic Equilibrium Problem

Subject Areas : Statistics

Morad Payvand ¹ , Sadigheh Jahdi ² , Hamid Reza maleki sarvestani ³

1 - Faculty of Basic Sciences, Yasouj University, Yasouj, Iran
2 - Faculty of Mathematics, Shiraz University of Technology, Shiraz, Iran
3 - Faculty of Mathematics, Shiraz University of Technology, Shiraz, Iran

Received: 2020-07-19 Accepted : 2021-08-27 Published : 2022-01-21

Keywords: روش گرادیان افزوده, الگوریتم خوبوتو, تولید ستون, جریان مسیر,

Abstract :

In this paper, we introduce a double projection algorithm based on extragradient method for solving the variational inequality problems and we prove the convergence theorem of proposed algorithm. One of the parameters that determine the efficiency and accuracy of the projection method is a properly selected step size. This selection is based on the contractive properties of operator which is projected on the feasible region. For example, if the Lipschitz constant is not known, we have trouble choosing step size of the algorithm. The proposed algorithm eliminates the need to know the Lipschitz constant and provides a method that facilitates step size selection.We formulate the asymmetric traffic equilibrium problem as a variational inequality on the path flows space. According to the decomposable structure of the feasible set of this model, we obtain the traffic network equilibrium state, by using the proposed algorithm. Finally, we present the numerical results of using this algorithm on the Sioux-Falls test traffic network.

References:

[۱] جاهدی، صدیقه و پیوند، مرادعلی، یک الگوریتم تکراری برای مسایل تعادل تعمیم یافته، نامساوی تغییراتی و نقطه ثابت مبتنی بر روش گرادیان افزوده، مجله پژوهش‌های نوین در ریاضی، دوره 2، شماره 7، آذر و دی 1395، صفحه 61-76.

 

[2] Facchinei, F., and Pang, J. S., (2003). Finite Dimensional Variational Inequalities and Complementarity Problems, Volume I, II, New York, Springer.

 

[3] Konnov, I. V. and Laitinen, E., (2002). Theory and Application of Variational Inequalities, University of Oulu, ISBN 951- 4242-6688-9.

 

[4] Patriksson, M., (1999). Nonlinear Programming and Variational Inequality Problems, a Unified Approach, Dordrecht, Kluwer Academic Publishers.

 

[5] Korpelevich, G. M., (1976). The extragradient method for finding saddle points and other problems, Matecon, 12, 747- 756.

 

[6] Dafermos, S., (1980). Traffic equilibrium and variational inequalities, Transportation Science, 14, 42-54.

 

[7] Pang, J. S. and Gabriel, S. A., (1993). A robust algorithm for the nonlinear complementary problem, Mathematical Programming, 60, 295-337.

 

[8] Khobotov, E. N. (1987). Modification of the extra-gradient method for solving variational inequalities and certain optimization problems, U.S.S.R. Computational Mathematics and Matematical Physics, 27(5), 120–127.

 

[9] He, B., Liao, L. Z., and Wang, X. (2012). Proximal-like contraction methods for monotone variational inequalities in a unified framework II: General methods and numerical experiments, Computational Optimization and Application, 51 (2), 681– 708.

 

[10] Marcotte, P., (1991). Application of Khobotov’s algorithm to variational inequalities and network equilibrium problem, Information Systems and Operational Research, 29(4), 258–270.

 

[11] Iusem, A. N., (1994). An iterative algorithm for the variational inequality problem, Computational and Applied Mathematics, 13(2), 103-114.

 

[12] Iusem, A. N., and Svaiter, B. F., (1997). A variant of Korpelevich’s method for variational inequalities with a new search strategy, Optimization, 42,309-321.

 

[13] Solodov, M. V. and Svaiter, B. F., (1999). A new projection method for variational inequality problems, SIAM Journal on Control and Optimization, 37(3), 756-776.

 

[14] Solodov, M. V. and Tseng, P., (1996). Modified projection type methods for monotone variational inequalities, SIAM Journal on Control and Optimization, 34(5), 1914-1830.

 

[15] A. Cegielski, (2011) Iterative Methods for Fixed Point Problems in Hilbert Spaces, Springer, London.

 

[16] Tinti, F. (2005). Numerical solution for pseudomonotone variarional inequality problems by extragradient methods, NOIA Variational Analysis and Applications, 79, 1101-1128.

 

[17] Harker, P. T., (1988). Accelerating the convergence of the diagonalization and projection algorithms for flnite-dimensional variational inequalities, Mathematical Programming, 41, 29-59.

[18] Patriksson, M., (2015). The Traffic Assignment Problem: Models and Methods, New York, Dover Publications.

 

[19] Michelot, C., (1986). A finite algorithm for finding the projection of a point onto the canonical simplex of Rⁿ, Journal of Optimization Theory and Applications, 50, 195–200.

 

[20] Bertsekas, D. P. and Gafni, E. M., (1982). Projection methods for variational inequality with application to the traffic assignment problem, Mathematical Programming Study, 17, 139-159.

 

[21] Chen, A., Lee, D. H. and Nie, Y., (2003). conjugate gradient projection algorithm for the traffic assignment problem'', Mathematical and Computer Modelling, 37, 863–878.

 

[22] Nagurney, A. and Zhang, D., (1996). Projected dynamical systems and variational inequalities with applications, Boston, Kluwer.

 

[23] Leventhal, L., Nemhause, G. and Trotter, L., (1972). A column generation algorithm for optimal traffic assignment, Transportation Science, 7, 168-172.

 

[24] Bar-Gera, H., Transportation Network Test Problems, http://www. bgu.ac.il/~bargera/tntp/.

 

[25] Barbara P., Massimo P., and Mauro P., (2007).  A path-based double projection method for solving the asymmetric traffic network equilibrium problem, Optimization Letters, 1, 171–185.