• 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

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.
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]

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 & Management Optimization, 2020  doi: 10.3934/jimo.2020178

[2]

Shipra Singh, Aviv Gibali, Xiaolong Qin. Cooperation in traffic network problems via evolutionary split variational inequalities. Journal of Industrial & Management Optimization, 2020  doi: 10.3934/jimo.2020170

[3]

Ying Liu, Yanping Chen, Yunqing Huang, Yang Wang. Two-grid method for semiconductor device problem by mixed finite element method and characteristics finite element method. Electronic Research Archive, 2021, 29 (1) : 1859-1880. doi: 10.3934/era.2020095

[4]

Kai Zhang, Xiaoqi Yang, Song Wang. Solution method for discrete double obstacle problems based on a power penalty approach. Journal of Industrial & Management Optimization, 2020  doi: 10.3934/jimo.2021018

[5]

Waixiang Cao, Lueling Jia, Zhimin Zhang. A $ C^1 $ Petrov-Galerkin method and Gauss collocation method for 1D general elliptic problems and superconvergence. Discrete & Continuous Dynamical Systems - B, 2021, 26 (1) : 81-105. doi: 10.3934/dcdsb.2020327

[6]

Abdollah Borhanifar, Maria Alessandra Ragusa, Sohrab Valizadeh. High-order numerical method for two-dimensional Riesz space fractional advection-dispersion equation. Discrete & Continuous Dynamical Systems - B, 2020  doi: 10.3934/dcdsb.2020355

[7]

Wenya Qi, Padmanabhan Seshaiyer, Junping Wang. A four-field mixed finite element method for Biot's consolidation problems. Electronic Research Archive, , () : -. doi: 10.3934/era.2020127

[8]

Mehdi Bastani, Davod Khojasteh Salkuyeh. On the GSOR iteration method for image restoration. Numerical Algebra, Control & Optimization, 2021, 11 (1) : 27-43. doi: 10.3934/naco.2020013

[9]

Xiaoxiao Li, Yingjing Shi, Rui Li, Shida Cao. Energy management method for an unpowered landing. Journal of Industrial & Management Optimization, 2020  doi: 10.3934/jimo.2020180

[10]

Zuliang Lu, Fei Huang, Xiankui Wu, Lin Li, Shang Liu. Convergence and quasi-optimality of $ L^2- $norms based an adaptive finite element method for nonlinear optimal control problems. Electronic Research Archive, 2020, 28 (4) : 1459-1486. doi: 10.3934/era.2020077

[11]

Hong Niu, Zhijiang Feng, Qijin Xiao, Yajun Zhang. A PID control method based on optimal control strategy. Numerical Algebra, Control & Optimization, 2021, 11 (1) : 117-126. doi: 10.3934/naco.2020019

[12]

Qing-Hu Hou, Yarong Wei. Telescoping method, summation formulas, and inversion pairs. Electronic Research Archive, , () : -. doi: 10.3934/era.2021007

[13]

Shasha Hu, Yihong Xu, Yuhan Zhang. Second-Order characterizations for set-valued equilibrium problems with variable ordering structures. Journal of Industrial & Management Optimization, 2020  doi: 10.3934/jimo.2020164

[14]

Jingjing Wang, Zaiyun Peng, Zhi Lin, Daqiong Zhou. On the stability of solutions for the generalized vector quasi-equilibrium problems via free-disposal set. Journal of Industrial & Management Optimization, 2021, 17 (2) : 869-887. doi: 10.3934/jimo.2020002

[15]

Anna Canale, Francesco Pappalardo, Ciro Tarantino. Weighted multipolar Hardy inequalities and evolution problems with Kolmogorov operators perturbed by singular potentials. Communications on Pure & Applied Analysis, 2021, 20 (1) : 405-425. doi: 10.3934/cpaa.2020274

[16]

Li-Bin Liu, Ying Liang, Jian Zhang, Xiaobing Bao. A robust adaptive grid method for singularly perturbed Burger-Huxley equations. Electronic Research Archive, 2020, 28 (4) : 1439-1457. doi: 10.3934/era.2020076

[17]

Zexuan Liu, Zhiyuan Sun, Jerry Zhijian Yang. A numerical study of superconvergence of the discontinuous Galerkin method by patch reconstruction. Electronic Research Archive, 2020, 28 (4) : 1487-1501. doi: 10.3934/era.2020078

[18]

Yuxia Guo, Shaolong Peng. A direct method of moving planes for fully nonlinear nonlocal operators and applications. Discrete & Continuous Dynamical Systems - S, 2020  doi: 10.3934/dcdss.2020462

[19]

Noah Stevenson, Ian Tice. A truncated real interpolation method and characterizations of screened Sobolev spaces. Communications on Pure & Applied Analysis, 2020, 19 (12) : 5509-5566. doi: 10.3934/cpaa.2020250

[20]

Yue Feng, Yujie Liu, Ruishu Wang, Shangyou Zhang. A conforming discontinuous Galerkin finite element method on rectangular partitions. Electronic Research Archive, , () : -. doi: 10.3934/era.2020120

2019 Impact Factor: 1.366

Metrics

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

[Back to Top]