SpringerLink
Log in

A new low-cost double projection method for solving variational inequalities

  • Research Article
  • Published:
Optimization and Engineering Aims and scope Submit manuscript

Abstract

In this work we are concerned with variational inequalities in real Hilbert spaces and introduce a new double projection method for solving it. The algorithm is motivated by the Korpelevich extragradient method, the subgradient extragradient method of Gibali et al. and Popov’s method. The proposed scheme combines some of the advantages of the methods mentioned above, first it requires only one orthogonal projection onto the feasible set of the problem while the next computation has a closed formula. Second, only one map** evaluation is required per each iteration and there is also a usage of an adaptive step size rule that avoids the need to know the Lipschitz constant of the associated map**. We present two convergence theorems of the proposed method, weak convergence result which requires pseudomonotonicity, Lipschitz and sequentially weakly continuity of the associated map** and strong convergence theorem with rate of convergence which requires Lipschitz continuity and strongly pseudomonotone only. Primary numerical experiments and comparisons demonstrate the advantages and potential applicability of the new scheme.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
EUR 32.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or Ebook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price includes VAT (France)

Instant access to the full article PDF.

Institutional subscriptions

Fig. 1
Fig. 2
Fig. 3

Similar content being viewed by others

References

  • Anh PK, Hieu DV (2016) Parallel hybrid iterative methods for variational inequalities, equilibrium problems, and common fixed point problems. Vietnam J Math 44:351–374

    MathSciNet  MATH  Google Scholar 

  • Antipin AS (1976) On a method for convex programs using a symmetrical modification of the Lagrange function. Ekon Mat Metody 12:1164–1173

    Google Scholar 

  • Arrow KJ, Hurwicz L, Uzawa H (1958) Studies in linear and non-linear programming. Stanford University Press, Stanford

    MATH  Google Scholar 

  • Bauschke HH, Combettes PL (2011) Convex analysis and monotone operator theory in Hilbert spaces, 2nd edn. Springer, New York

    MATH  Google Scholar 

  • Cai X, Gu G, He B (2014) On the $O(1/t)$ convergence rate of the projection and contraction methods for variational inequalities with Lipschitz continuous monotone operators. Comput Optim Appl 57:339–363

    MathSciNet  MATH  Google Scholar 

  • Ceng L-C, Qin X, Shehu Y, Yao J-C (2019) Mildly inertial subgradient extragradient method for variational inequalities involving an asymptotically nonexpansive and finitely many nonexpansive map**s. Mathematics 7:881

    Google Scholar 

  • Censor Y, Gibali A, Reich S (2011a) The subgradient extragradientmethod for solving variational inequalities in Hilbert space. J Optim Theory Appl 148:318–335

    MathSciNet  MATH  Google Scholar 

  • Censor Y, Gibali A, Reich S (2011b) Strong convergence of subgradient extragradient methods for the variational inequality problem in Hilbert space. Optim Methods Softw 26:827–845

    MathSciNet  MATH  Google Scholar 

  • Censor Y, Gibali A, Reich S (2011c) Extensions of Korpelevich’s extragradient method for the variational inequality problem in Euclidean space. Optimization 61:1119–1132

    MathSciNet  MATH  Google Scholar 

  • Cegielski A (2012) Iterative methods for fixed point problems in Hilbert spaces. Lecture notes in mathematics, vol 2057. Springer, Berlin

    MATH  Google Scholar 

  • Cottle RW, Yao JC (1992) Pseudo-monotone complementarity problems in Hilbert space. J Optim Theory Appl 75:281–295

    MathSciNet  MATH  Google Scholar 

  • Denisov SV, Semenov VV, Chabak LM (2015) Convergence of the modified extragradient method for variational inequalities with non-Lipschitz operators. Cybern Syst Anal 51:757–765

    MathSciNet  MATH  Google Scholar 

  • Dong QL, Gibali A, Jiang D, Ke SH (2018) Convergence of projection and contraction algorithms with outer perturbations and their applications to sparse signals recovery. J Fixed Point Theory Appl 20:16

    MathSciNet  MATH  Google Scholar 

  • Facchinei F, Pang JS (2003) Finite-dimensional variational inequalities and complementarity problems. Springer series in operations research, vol I and II. Springer, New York

    MATH  Google Scholar 

  • Fichera G (1963) Sul problema elastostatico di Signorini con ambigue condizioni al contorno. Atti Accad Naz Lincei VIII Ser Rend Cl Sci Fis Mat Nat 34:138–142

    MathSciNet  MATH  Google Scholar 

  • Fichera G (1964) Problemi elastostatici con vincoli unilaterali: il problema di Signorini con ambigue condizioni al contorno. Atti Accad Naz Lincei Mem Cl Sci Fis Mat Nat Sez I VIII Ser 7:91–140

    MathSciNet  MATH  Google Scholar 

  • Goebel K, Reich S (1984) Uniform convexity, hyperbolic geometry, and nonexpansive map**s. Marcel Dekker, New York

    MATH  Google Scholar 

  • Gibali A (2018) A new Bregman projection method for solving variational inequalities in Hilbert spaces. Pure Appl Funct Anal 3:403–415

    MathSciNet  Google Scholar 

  • Hieu DV, Thong DV (2018) New extragradient-like algorithms for strongly pseudomonotone variational inequalities. J Glob Optim 70:385–399

    MathSciNet  MATH  Google Scholar 

  • Hieu DV, Anh PK, Muu LD (2019) Modified extragradient-like algorithms with new stepsizes for variational inequalities. Comput Optim Appl 73:913–932

    MathSciNet  MATH  Google Scholar 

  • Iusem AN, Nasri M (2011) Korpelevichś method for variational inequality problems in Banach spaces. J Glob Optim 50:59–76

    MathSciNet  MATH  Google Scholar 

  • Iusem AN, Svaiter BF (1997) A variant of Korpelevichś method for variational inequalities with a new search strategy. Optimization 42:309–321

    MathSciNet  MATH  Google Scholar 

  • Kanzow C, Shehu Y (2018) Strong convergence of a double projection-type method for monotone variational inequalities in Hilbert spaces. J Fixed Point Theory Appl 20:51

    MathSciNet  MATH  Google Scholar 

  • Kanzow C, Steck D (2019) Quasi-variational inequalities in banach spaces: theory and augmented Lagrangian methods. SIAM J Optim 29(4):3174–3200

    MathSciNet  MATH  Google Scholar 

  • Khanh PD (2016) A new extragradient method for strongly pseudomonotone variational inequalities. Numer Funct Anal Optim 37:1131–1143

    MathSciNet  MATH  Google Scholar 

  • Khanh PD, Vuong PT (2014) Modified projection method for strongly pseudo-monotone variational inequalities. J Glob Optim 58:341–350

    MATH  Google Scholar 

  • Konnov IV (2001) Combined relaxation methods for variational inequalities. Springer, Berlin

    MATH  Google Scholar 

  • Korpelevich GM (1976) The extragradient method for finding saddle points and other problems. Ekon Mat Metody 12:747–756

    MathSciNet  MATH  Google Scholar 

  • Kraikaew R, Saejung S (2014) Strong convergence of the Halpern subgradient extragradient method for solving variational inequalities in Hilbert spaces. J Optim Theory Appl 163:399–412

    MathSciNet  MATH  Google Scholar 

  • Maingé PE (2008) A hybrid extragradient-viscosity method for monotone operators and fixed point problems. SIAM J Control Optim 47:1499–1515

    MathSciNet  MATH  Google Scholar 

  • Malitsky YV (2015) Projected reflected gradient methods for monotone variational inequalities. SIAM J Optim 25:502–520

    MathSciNet  MATH  Google Scholar 

  • Malitsky YV, Semenov VV (2014) An extragradient algorithm for monotone variational inequalities. Cybern Syst. Anal 50:271–277

    MathSciNet  MATH  Google Scholar 

  • Malitsky YV, Semenov VV (2015) A hybrid method without extrapolation step for solving variational inequality problems. J Glob Optim 61:193–202

    MathSciNet  MATH  Google Scholar 

  • Lyashko SI, Semenov VV, Voitova TA (2011) Low-cost modification of Korpelevich’s methods for monotone equilibrium problems. Cybern Syst Anal 47:631–640

    MathSciNet  MATH  Google Scholar 

  • Opial Z (1967) Weak convergence of the sequence of successive approximations for nonexpansive map**s. Bull Am. Math Soc 73:591–597

    MathSciNet  MATH  Google Scholar 

  • Popov LD (1980) A modification of the Arrow–Hurwicz method for searching for saddle points. Mat Zametki 28:777–784

    MathSciNet  MATH  Google Scholar 

  • Solodov MV, Svaiter BF (1999) A new projection method for variational inequality problems. SIAM J Control Optim 37:765–776

    MathSciNet  MATH  Google Scholar 

  • Tawhid MA (2012) Special issue on applications of variational inequality problems. Optim Eng 13:371–543

    MathSciNet  MATH  Google Scholar 

  • Vuong PT (2018) On the weak convergence of the extragradient method for solving pseudo-monotone variational inequalities. J Optim Theory Appl 176:399–409

    MathSciNet  MATH  Google Scholar 

  • Vuong PT, Shehu Y (2018) Convergence of an extragradient-type method for variational inequality with applications to optimal control problems. Numer Algorithms 81:269–291

    MathSciNet  MATH  Google Scholar 

  • Yang J, Liu H (2018) A modified projected gradient method for monotone variational inequalities. J Optim Theory Appl 179:197–211

    MathSciNet  MATH  Google Scholar 

  • Yang J, Liu H, Liu Z (2018) Modified subgradient extragradient algorithms for solving monotone variational inequalities. Optimization 67:2247–2258

    MathSciNet  MATH  Google Scholar 

Download references

Acknowledgements

We are very grateful to the anonymous referees and Editor whose insightful comments helped to considerably improve an earlier version of this paper. This work is supported by Vietnam (National Foundation for Science and Technology Development (NAFOSTED)) under the project: 101.01-2019.320.

Author information

Authors and Affiliations

  1. Department of Mathematics, ORT Braude College, 2161002, Karmiel, Israel

    Aviv Gibali

  2. The Center for Mathematics and Scientific Computation, University of Haifa, Mt. Carmel, 3498838, Haifa, Israel

    Aviv Gibali

  3. Applied Analysis Research Group, Faculty of Mathematics and Statistics, Ton Duc Thang University, Ho Chi Minh City, Vietnam

    Duong Viet Thong

Authors
  1. Aviv Gibali
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Duong Viet Thong
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Duong Viet Thong.

Additional information

Publisher's Note

Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.

Rights and permissions

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Gibali, A., Thong, D.V. A new low-cost double projection method for solving variational inequalities. Optim Eng 21, 1613–1634 (2020). https://doi.org/10.1007/s11081-020-09490-2

Download citation

  • Received:

  • Revised:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s11081-020-09490-2

Keywords

Mathematics Subject Classification

Search

Navigation