American Institute of Mathematical Sciences

Advanced
  • Previous Article
    A penalty-based method from reconstructing smooth local volatility surface from American options
  • JIMO Home
  • This Issue
  • Next Article
    Bilevel multi-objective construction site security planning with twofold random phenomenon
April  2015, 11(2): 619-630. doi: 10.3934/jimo.2015.11.619

A family of extragradient methods for solving equilibrium problems

Thi Phuong Dong Nguyen 1, , Jean Jacques Strodiot 1, , Thi Thu Van Nguyen 1, and  Van Hien Nguyen 1,

1. 

Institute for Computational Science and Technology (ICST), Ho Chi Minh City, Vietnam, Vietnam, Vietnam, Vietnam

Received  November 2013 Revised  April 2014 Published  September 2014

In this paper we introduce a class of numerical methods for solving an equilibrium problem. This class depends on a parameter and contains the classical extragradient method and a generalization of the two-step extragradient method proposed recently by Zykina and Melen'chuk for solving variational inequality problems. Convergence of each algorithm of this class to a solution of the equilibrium problem is obtained under the condition that the equilibrium function associated with the problem is pseudomonotone and Lipschitz continuous. Some preliminary numerical results are given to compare the numerical behavior of the two-step extragradient method with respect to the other methods of the class and in particular to the extragradient method.
Keywords: variational inequalities., two-step extragradient method, Extragradient method, equilibrium problems.
Mathematics Subject Classification: Primary: 49J40, 90C25; Secondary: 65K1.
Citation: Thi Phuong Dong Nguyen, Jean Jacques Strodiot, Thi Thu Van Nguyen, Van Hien Nguyen. A family of extragradient methods for solving equilibrium problems. Journal of Industrial & Management Optimization, 2015, 11 (2) : 619-630. doi: 10.3934/jimo.2015.11.619
References:
[1]

J. Bello Cruz, P. Santos and S. Scheimberg, A two-phase algorithm for a variational inequality formulation of equilibrium problems,, J. Optim. Theory Appl., 159 (2013), 562.  doi: 10.1007/s10957-012-0181-8.  Google Scholar

[2]

G. Bigi, M. Castellani, M. Pappalardo and M. Passacantando, Existence and solution methods for equilibria,, Eur. J. Oper. Research, 227 (2013), 1.  doi: 10.1016/j.ejor.2012.11.037.  Google Scholar

[3]

E. Blum and W. Oettli, From optimization and variational inequalities to equilibrium problems,, Math. Student, 63 (1994), 123.   Google Scholar

[4]

F. Facchinei and J. Pang, Finite-Dimensional Variational Inequalities and Complementarity Problems,, Vols I and II, (2003).   Google Scholar

[5]

A. Heusinger and C. Kanzow, Relaxation methods for generalized Nash equilibrium problems with inexact line search,, J. Optim. Theory Appl., 143 (2009), 159.  doi: 10.1007/s10957-009-9553-0.  Google Scholar

[6]

K. Fan, A minimax inequality and applications,, in Inequality III (ed. O. Shisha), (1972), 103.   Google Scholar

[7]

E. Khobotov, Modification of the extragradient method for solving variational inequalities and certain optimization problems,, USSR Comput. Math. Math. Phys., 27 (1987), 1462.   Google Scholar

[8]

I. Konnov, Equilibrium Models and Variational Inequalities,, Elsevier, (2007).   Google Scholar

[9]

G. Korpelevich, The extragradient method for finding saddle points and other problems,, Matecon, 12 (1976), 747.   Google Scholar

[10]

J. Krawczyk and S. Uryasev, Relaxation algorithms to find Nash equilibria with economic applications,, Environmental Modeling and Assessment, 5 (2000), 63.   Google Scholar

[11]

G. Mastroeni, On auxiliary principle for equilibrium problems,, in Equilibrium Problems and Variational Models (eds. P. Daniele, 68 (2003), 289.  doi: 10.1007/978-1-4613-0239-1_15.  Google Scholar

[12]

A. Nagurney, Network Economics: A Variational Inequality Approach,, Kluwer Academic Publishers, (1993).  doi: 10.1007/978-94-011-2178-1.  Google Scholar

[13]

T. T. V. Nguyen, J. J. Strodiot and V. H. Nguyen, The interior proximal extragradient method for solving equilibrium problems,, J. Glob. Optim., 44 (2009), 175.  doi: 10.1007/s10898-008-9311-0.  Google Scholar

[14]

T. T. V. Nguyen, J. J. Strodiot and V. H. Nguyen, A bundle method for solving equilibrium problems,, Math. Program., 116 (2009), 529.  doi: 10.1007/s10107-007-0112-x.  Google Scholar

[15]

J. Nocedal and S. Wright, Numerical Optimization,, Springer, (2006).   Google Scholar

[16]

, Optimization Toolbox User's Guide. For Use with MATLAB, The Math Works Inc.,, 2014., ().   Google Scholar

[17]

R. T. Rockafellar, Convex Analysis,, Princeton University Press, (1970).   Google Scholar

[18]

J. J. Strodiot, T. T. V. Nguyen and V. H. Nguyen, A new class of hybrid extragradient algorithms for solving quasi-equilibrium problems,, J. Global Optim., 56 (2013), 373.  doi: 10.1007/s10898-011-9814-y.  Google Scholar

[19]

D. Q. Tran, L. D. Muu and V. H. Nguyen, Extragradient algorithms extended to equilibrium problems,, Optimization, 57 (2008), 749.  doi: 10.1080/02331930601122876.  Google Scholar

[20]

D. Zaporozhets, A. Zykina and N. Melen'chuk, Comparative analysis of the extragradient methods for solution of the variational inequalities of some problems,, Automation and Remote Control, 73 (2012), 626.  doi: 10.1134/S0005117912040030.  Google Scholar

[21]

A. Zykina and N. Melen'chuk, A two-step extragradient method for variational inequalities,, Russian Mathematics, 54 (2010), 71.  doi: 10.3103/S1066369X10090082.  Google Scholar

[22]

A. Zykina and N. Melen'chuk, A doublestep extragradient method for solving a resource management problem,, Modeling and Analysis of Information Systems, 17 (2010), 65.   Google Scholar

[23]

A. Zykina and N. Melen'chuk, A doublestep extragradient method for solving a problem of the management of resources,, Automatic Control and Computer Science, 45 (2011), 452.  doi: 10.3103/S0146411611070170.  Google Scholar

[24]

A. Zykina and N. Melen'chuk, Convergence of the two-step extragradient method in a finite number of iterations,, III International Conference: Optimization and Applications, (2012), 23.   Google Scholar

show all references

References:
[1]

J. Bello Cruz, P. Santos and S. Scheimberg, A two-phase algorithm for a variational inequality formulation of equilibrium problems,, J. Optim. Theory Appl., 159 (2013), 562.  doi: 10.1007/s10957-012-0181-8.  Google Scholar

[2]

G. Bigi, M. Castellani, M. Pappalardo and M. Passacantando, Existence and solution methods for equilibria,, Eur. J. Oper. Research, 227 (2013), 1.  doi: 10.1016/j.ejor.2012.11.037.  Google Scholar

[3]

E. Blum and W. Oettli, From optimization and variational inequalities to equilibrium problems,, Math. Student, 63 (1994), 123.   Google Scholar

[4]

F. Facchinei and J. Pang, Finite-Dimensional Variational Inequalities and Complementarity Problems,, Vols I and II, (2003).   Google Scholar

[5]

A. Heusinger and C. Kanzow, Relaxation methods for generalized Nash equilibrium problems with inexact line search,, J. Optim. Theory Appl., 143 (2009), 159.  doi: 10.1007/s10957-009-9553-0.  Google Scholar

[6]

K. Fan, A minimax inequality and applications,, in Inequality III (ed. O. Shisha), (1972), 103.   Google Scholar

[7]

E. Khobotov, Modification of the extragradient method for solving variational inequalities and certain optimization problems,, USSR Comput. Math. Math. Phys., 27 (1987), 1462.   Google Scholar

[8]

I. Konnov, Equilibrium Models and Variational Inequalities,, Elsevier, (2007).   Google Scholar

[9]

G. Korpelevich, The extragradient method for finding saddle points and other problems,, Matecon, 12 (1976), 747.   Google Scholar

[10]

J. Krawczyk and S. Uryasev, Relaxation algorithms to find Nash equilibria with economic applications,, Environmental Modeling and Assessment, 5 (2000), 63.   Google Scholar

[11]

G. Mastroeni, On auxiliary principle for equilibrium problems,, in Equilibrium Problems and Variational Models (eds. P. Daniele, 68 (2003), 289.  doi: 10.1007/978-1-4613-0239-1_15.  Google Scholar

[12]

A. Nagurney, Network Economics: A Variational Inequality Approach,, Kluwer Academic Publishers, (1993).  doi: 10.1007/978-94-011-2178-1.  Google Scholar

[13]

T. T. V. Nguyen, J. J. Strodiot and V. H. Nguyen, The interior proximal extragradient method for solving equilibrium problems,, J. Glob. Optim., 44 (2009), 175.  doi: 10.1007/s10898-008-9311-0.  Google Scholar

[14]

T. T. V. Nguyen, J. J. Strodiot and V. H. Nguyen, A bundle method for solving equilibrium problems,, Math. Program., 116 (2009), 529.  doi: 10.1007/s10107-007-0112-x.  Google Scholar

[15]

J. Nocedal and S. Wright, Numerical Optimization,, Springer, (2006).   Google Scholar

[16]

, Optimization Toolbox User's Guide. For Use with MATLAB, The Math Works Inc.,, 2014., ().   Google Scholar

[17]

R. T. Rockafellar, Convex Analysis,, Princeton University Press, (1970).   Google Scholar

[18]

J. J. Strodiot, T. T. V. Nguyen and V. H. Nguyen, A new class of hybrid extragradient algorithms for solving quasi-equilibrium problems,, J. Global Optim., 56 (2013), 373.  doi: 10.1007/s10898-011-9814-y.  Google Scholar

[19]

D. Q. Tran, L. D. Muu and V. H. Nguyen, Extragradient algorithms extended to equilibrium problems,, Optimization, 57 (2008), 749.  doi: 10.1080/02331930601122876.  Google Scholar

[20]

D. Zaporozhets, A. Zykina and N. Melen'chuk, Comparative analysis of the extragradient methods for solution of the variational inequalities of some problems,, Automation and Remote Control, 73 (2012), 626.  doi: 10.1134/S0005117912040030.  Google Scholar

[21]

A. Zykina and N. Melen'chuk, A two-step extragradient method for variational inequalities,, Russian Mathematics, 54 (2010), 71.  doi: 10.3103/S1066369X10090082.  Google Scholar

[22]

A. Zykina and N. Melen'chuk, A doublestep extragradient method for solving a resource management problem,, Modeling and Analysis of Information Systems, 17 (2010), 65.   Google Scholar

[23]

A. Zykina and N. Melen'chuk, A doublestep extragradient method for solving a problem of the management of resources,, Automatic Control and Computer Science, 45 (2011), 452.  doi: 10.3103/S0146411611070170.  Google Scholar

[24]

A. Zykina and N. Melen'chuk, Convergence of the two-step extragradient method in a finite number of iterations,, III International Conference: Optimization and Applications, (2012), 23.   Google Scholar

[1]

Deren Han, Zehui Jia, Yongzhong Song, David Z. W. Wang. An efficient projection method for nonlinear inverse problems with sparsity constraints. Inverse Problems & Imaging, 2016, 10 (3) : 689-709. doi: 10.3934/ipi.2016017
[2]

Petra Csomós, Hermann Mena. Fourier-splitting method for solving hyperbolic LQR problems. Numerical Algebra, Control & Optimization, 2018, 8 (1) : 17-46. doi: 10.3934/naco.2018002
[3]

Christina Surulescu, Nicolae Surulescu. Modeling and simulation of some cell dispersion problems by a nonparametric method. Mathematical Biosciences & Engineering, 2011, 8 (2) : 263-277. doi: 10.3934/mbe.2011.8.263
[4]

Xiaomao Deng, Xiao-Chuan Cai, Jun Zou. A parallel space-time domain decomposition method for unsteady source inversion problems. Inverse Problems & Imaging, 2015, 9 (4) : 1069-1091. doi: 10.3934/ipi.2015.9.1069
[5]

Xue-Ping Luo, Yi-Bin Xiao, Wei Li. Strict feasibility of variational inclusion problems in reflexive Banach spaces. Journal of Industrial & Management Optimization, 2020, 16 (5) : 2495-2502. doi: 10.3934/jimo.2019065
[6]

Armin Lechleiter, Tobias Rienmüller. Factorization method for the inverse Stokes problem. Inverse Problems & Imaging, 2013, 7 (4) : 1271-1293. doi: 10.3934/ipi.2013.7.1271
[7]

M. Mahalingam, Parag Ravindran, U. Saravanan, K. R. Rajagopal. Two boundary value problems involving an inhomogeneous viscoelastic solid. Discrete & Continuous Dynamical Systems - S, 2017, 10 (6) : 1351-1373. doi: 10.3934/dcdss.2017072
[8]

Qiang Guo, Dong Liang. An adaptive wavelet method and its analysis for parabolic equations. Numerical Algebra, Control & Optimization, 2013, 3 (2) : 327-345. doi: 10.3934/naco.2013.3.327
[9]

Tao Wu, Yu Lei, Jiao Shi, Maoguo Gong. An evolutionary multiobjective method for low-rank and sparse matrix decomposition. Big Data & Information Analytics, 2017, 2 (1) : 23-37. doi: 10.3934/bdia.2017006
[10]

Boris Kramer, John R. Singler. A POD projection method for large-scale algebraic Riccati equations. Numerical Algebra, Control & Optimization, 2016, 6 (4) : 413-435. doi: 10.3934/naco.2016018
[11]

Min Li. A three term Polak-Ribière-Polyak conjugate gradient method close to the memoryless BFGS quasi-Newton method. Journal of Industrial & Management Optimization, 2020, 16 (1) : 245-260. doi: 10.3934/jimo.2018149
[12]

Manfred Einsiedler, Elon Lindenstrauss. On measures invariant under diagonalizable actions: the Rank-One case and the general Low-Entropy method. Journal of Modern Dynamics, 2008, 2 (1) : 83-128. doi: 10.3934/jmd.2008.2.83
[13]

Marion Darbas, Jérémy Heleine, Stephanie Lohrengel. Numerical resolution by the quasi-reversibility method of a data completion problem for Maxwell's equations. Inverse Problems & Imaging, 2020, 14 (6) : 1107-1133. doi: 10.3934/ipi.2020056
[14]

Sergi Simon. Linearised higher variational equations. Discrete & Continuous Dynamical Systems - A, 2014, 34 (11) : 4827-4854. doi: 10.3934/dcds.2014.34.4827
[15]

Jean Dolbeault, Maria J. Esteban, Michał Kowalczyk, Michael Loss. Improved interpolation inequalities on the sphere. Discrete & Continuous Dynamical Systems - S, 2014, 7 (4) : 695-724. doi: 10.3934/dcdss.2014.7.695
[16]

Junichi Minagawa. On the uniqueness of Nash equilibrium in strategic-form games. Journal of Dynamics & Games, 2020, 7 (2) : 97-104. doi: 10.3934/jdg.2020006
[17]

V. V. Zhikov, S. E. Pastukhova. Korn inequalities on thin periodic structures. Networks & Heterogeneous Media, 2009, 4 (1) : 153-175. doi: 10.3934/nhm.2009.4.153
[18]

Hong Seng Sim, Wah June Leong, Chuei Yee Chen, Siti Nur Iqmal Ibrahim. Multi-step spectral gradient methods with modified weak secant relation for large scale unconstrained optimization. Numerical Algebra, Control & Optimization, 2018, 8 (3) : 377-387. doi: 10.3934/naco.2018024
[19]

Andrea Cianchi, Adele Ferone. Improving sharp Sobolev type inequalities by optimal remainder gradient norms. Communications on Pure & Applied Analysis, 2012, 11 (3) : 1363-1386. doi: 10.3934/cpaa.2012.11.1363
[20]

Marcelo Messias. Periodic perturbation of quadratic systems with two infinite heteroclinic cycles. Discrete & Continuous Dynamical Systems - A, 2012, 32 (5) : 1881-1899. doi: 10.3934/dcds.2012.32.1881

2019 Impact Factor: 1.366

Tools

Metrics

  • PDF downloads (61)
  • HTML views (0)
  • Cited by (6)

Other articles
by authors

[Back to Top]

Copyright © 2021 American Institute of Mathematical Sciences