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 and 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-575. doi: 10.1007/s10957-012-0181-8.

[2]

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

[3]

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

[4]

F. Facchinei and J. Pang, Finite-Dimensional Variational Inequalities and Complementarity Problems, Vols I and II, Springer-Verlag, New York, 2003.

[5]

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

[6]

K. Fan, A minimax inequality and applications, in Inequality III (ed. O. Shisha), Academic Press, (1972), 103-113.

[7]

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

[8]

I. Konnov, Equilibrium Models and Variational Inequalities, Elsevier, Amsterdam, 2007.

[9]

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

[10]

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

[11]

G. Mastroeni, On auxiliary principle for equilibrium problems, in Equilibrium Problems and Variational Models (eds. P. Daniele, F. Giannessi and A. Maugeri), Kluwer Academic Publishers, Dordrecht, 68 (2003), 289-298. doi: 10.1007/978-1-4613-0239-1_15.

[12]

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

[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-192. doi: 10.1007/s10898-008-9311-0.

[14]

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

[15]

J. Nocedal and S. Wright, Numerical Optimization, Springer, New York, 2006.

[16]

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

[17]

R. T. Rockafellar, Convex Analysis, Princeton University Press, Princeton, New Jersey, 1970.

[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-397. doi: 10.1007/s10898-011-9814-y.

[19]

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

[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-636. doi: 10.1134/S0005117912040030.

[21]

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

[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-75.

[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-459. doi: 10.3103/S0146411611070170.

[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, Optima-2012, Costa da Caparica, Portugal, (2012), 23-30.

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-575. doi: 10.1007/s10957-012-0181-8.

[2]

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

[3]

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

[4]

F. Facchinei and J. Pang, Finite-Dimensional Variational Inequalities and Complementarity Problems, Vols I and II, Springer-Verlag, New York, 2003.

[5]

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

[6]

K. Fan, A minimax inequality and applications, in Inequality III (ed. O. Shisha), Academic Press, (1972), 103-113.

[7]

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

[8]

I. Konnov, Equilibrium Models and Variational Inequalities, Elsevier, Amsterdam, 2007.

[9]

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

[10]

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

[11]

G. Mastroeni, On auxiliary principle for equilibrium problems, in Equilibrium Problems and Variational Models (eds. P. Daniele, F. Giannessi and A. Maugeri), Kluwer Academic Publishers, Dordrecht, 68 (2003), 289-298. doi: 10.1007/978-1-4613-0239-1_15.

[12]

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

[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-192. doi: 10.1007/s10898-008-9311-0.

[14]

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

[15]

J. Nocedal and S. Wright, Numerical Optimization, Springer, New York, 2006.

[16]

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

[17]

R. T. Rockafellar, Convex Analysis, Princeton University Press, Princeton, New Jersey, 1970.

[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-397. doi: 10.1007/s10898-011-9814-y.

[19]

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

[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-636. doi: 10.1134/S0005117912040030.

[21]

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

[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-75.

[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-459. doi: 10.3103/S0146411611070170.

[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, Optima-2012, Costa da Caparica, Portugal, (2012), 23-30.

[1]

Lateef Olakunle Jolaoso, Maggie Aphane. Bregman subgradient extragradient method with monotone self-adjustment stepsize for solving pseudo-monotone variational inequalities and fixed point problems. Journal of Industrial and Management Optimization, 2022, 18 (2) : 773-794. doi: 10.3934/jimo.2020178
[2]

Gang Cai, Yekini Shehu, Olaniyi S. Iyiola. Inertial Tseng's extragradient method for solving variational inequality problems of pseudo-monotone and non-Lipschitz operators. Journal of Industrial and Management Optimization, 2021  doi: 10.3934/jimo.2021095
[3]

Yekini Shehu, Olaniyi Iyiola. On a modified extragradient method for variational inequality problem with application to industrial electricity production. Journal of Industrial and Management Optimization, 2019, 15 (1) : 319-342. doi: 10.3934/jimo.2018045
[4]

Luchuan Ceng, Qamrul Hasan Ansari, Jen-Chih Yao. Extragradient-projection method for solving constrained convex minimization problems. Numerical Algebra, Control and Optimization, 2011, 1 (3) : 341-359. doi: 10.3934/naco.2011.1.341
[5]

Biao Qu, Naihua Xiu. A relaxed extragradient-like method for a class of constrained optimization problem. Journal of Industrial and Management Optimization, 2007, 3 (4) : 645-654. doi: 10.3934/jimo.2007.3.645
[6]

Francisco J. Ibarrola, Ruben D. Spies. A two-step mixed inpainting method with curvature-based anisotropy and spatial adaptivity. Inverse Problems and Imaging, 2017, 11 (2) : 247-262. doi: 10.3934/ipi.2017012
[7]

Van Hieu Dang. An extension of hybrid method without extrapolation step to equilibrium problems. Journal of Industrial and Management Optimization, 2017, 13 (4) : 1723-1741. doi: 10.3934/jimo.2017015
[8]

Vyacheslav Maksimov. The method of extremal shift in control problems for evolution variational inequalities under disturbances. Evolution Equations and Control Theory, 2021  doi: 10.3934/eect.2021048
[9]

Hongxia Yin. An iterative method for general variational inequalities. Journal of Industrial and Management Optimization, 2005, 1 (2) : 201-209. doi: 10.3934/jimo.2005.1.201
[10]

Gang Qian, Deren Han, Lingling Xu, Hai Yang. Solving nonadditive traffic assignment problems: A self-adaptive projection-auxiliary problem method for variational inequalities. Journal of Industrial and Management Optimization, 2013, 9 (1) : 255-274. doi: 10.3934/jimo.2013.9.255
[11]

EL Hassene Osmani, Mounir Haddou, Naceurdine Bensalem. A new relaxation method for optimal control of semilinear elliptic variational inequalities obstacle problems. Numerical Algebra, Control and Optimization, 2021  doi: 10.3934/naco.2021061
[12]

Lianshuan Shi, Enmin Feng, Huanchun Sun, Zhaosheng Feng. A two-step algorithm for layout optimization of structures with discrete variables. Journal of Industrial and Management Optimization, 2007, 3 (3) : 543-552. doi: 10.3934/jimo.2007.3.543
[13]

Tingting Wu, Yufei Yang, Huichao Jing. Two-step methods for image zooming using duality strategies. Numerical Algebra, Control and Optimization, 2014, 4 (3) : 209-225. doi: 10.3934/naco.2014.4.209
[14]

Angelamaria Cardone, Dajana Conte, Beatrice Paternoster. Two-step collocation methods for fractional differential equations. Discrete and Continuous Dynamical Systems - B, 2018, 23 (7) : 2709-2725. doi: 10.3934/dcdsb.2018088
[15]

O. Chadli, Z. Chbani, H. Riahi. Recession methods for equilibrium problems and applications to variational and hemivariational inequalities. Discrete and Continuous Dynamical Systems, 1999, 5 (1) : 185-196. doi: 10.3934/dcds.1999.5.185
[16]

Grace Nnennaya Ogwo, Chinedu Izuchukwu, Oluwatosin Temitope Mewomo. A modified extragradient algorithm for a certain class of split pseudo-monotone variational inequality problem. Numerical Algebra, Control and Optimization, 2022, 12 (2) : 373-393. doi: 10.3934/naco.2021011
[17]

Jian Hou, Liwei Zhang. A barrier function method for generalized Nash equilibrium problems. Journal of Industrial and Management Optimization, 2014, 10 (4) : 1091-1108. doi: 10.3934/jimo.2014.10.1091
[18]

Yanhong Yuan, Hongwei Zhang, Liwei Zhang. A penalty method for generalized Nash equilibrium problems. Journal of Industrial and Management Optimization, 2012, 8 (1) : 51-65. doi: 10.3934/jimo.2012.8.51
[19]

Zhili Ge, Gang Qian, Deren Han. Global convergence of an inexact operator splitting method for monotone variational inequalities. Journal of Industrial and Management Optimization, 2011, 7 (4) : 1013-1026. doi: 10.3934/jimo.2011.7.1013
[20]

Xiaojun Chen, Guihua Lin. CVaR-based formulation and approximation method for stochastic variational inequalities. Numerical Algebra, Control and Optimization, 2011, 1 (1) : 35-48. doi: 10.3934/naco.2011.1.35

2020 Impact Factor: 1.801

Tools

Metrics

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

Other articles
by authors

[Back to Top]

Copyright © 2022 American Institute of Mathematical Sciences | Privacy Policy