Abstract

In the literature of variational inequalities, there has been a lot of studies about the role of gap functions in the development of error bounds specially for the case where the variational inequality is described by a strongly monotone mapping. However the role of the dual gap function in devising error bounds, to the best of our knowledge, has not been thoroughly investigated. In this article we focus on the dual gap function for monotone variational inequalities. We highlight some properties of the dual gap function which are not shared by the other gap functions and also show how it can be used to develop error bounds for strongly monotone variational inequalities with convex and compact feasible sets.

Author information

Contact details are reproduced from the original publication and may be historical.

Didier Aussel

Laboratoire PROMES, Université de Perpignan, 66100 Perpignan, France

aussel@univ-perp.fr

Joydeep Dutta

Dept of Humanities and Social Sciences, Indian Institute of Technology, 208016 Kanpur, India

jdutta@iitk.ac.in

Andrew C. Xu

Massachusetts Institute of Technology, Cambridge, MA 02139, U.S.A.

andrewxu@mit.edu

Keywords

  • Variational inequalities
  • gap functions
  • error bounds
  • strongly monotone maps

Mathematics Subject Classification

90C33, 90C25

References

  1. G. Auchmuty: Variational principles for variational inequalities, Num. Func. Anal. Optim. 10 (1989) 863–874.https://doi.org/10.1080/01630568908816335Google Scholar
  2. D. Aussel: New developments in quasiconvex optimization, in: Recents Advances in Fixed Point Theory and Optimization, Taylor and Francis (2013) 173–208.Google Scholar
  3. A. Auslender: Optimisation: Méthodes Numériques, Masson, Paris (1976).Google Scholar
  4. D. Aussel, J. Dutta: On gap functions for multivalued Stampacchia variational inequalities, J. Optim. Theory Appl. 149 (2011) 513-527.https://doi.org/10.1007/s10957-011-9801-yGoogle Scholar
  5. D. Aussel, N. Hadjisavvas: Adjusted sublevel sets, normal operator and quasiconvex programming, SIAM J. Optim. 16 (2005) 358–367.https://doi.org/10.1137/040606958Google Scholar
  6. D. Aussel, J. Ye: Quasiconvex minimization on locally finite union of convex sets, J. Optim. Theory Appl. 139(1) (2008) 1–16.https://doi.org/10.1007/s10957-008-9431-1Google Scholar
  7. J. M. Borwein, J. Dutta: Maximal monotone inclusions and Fitzpatrick functions, J. Optim. Theory Appl. 171(3) (2016) 757–784.https://doi.org/10.1007/s10957-015-0813-xGoogle Scholar
  8. J. M. Borwein, A. S. Lewis: Convex analysis and nonlinear optimization. Theory and examples (2nd edition), CMS Books in Mathematics 3, Springer, New York (2006).https://doi.org/10.1007/978-0-387-31256-9Google Scholar
  9. F. E. Browder: Multivalued monotone nonlinear mappings and duality mappings in Banach spaces, Trans. Amer. Math. Soc. 71 (1965) 780–785.https://doi.org/10.1090/S0002-9904-1965-11391-XGoogle Scholar
  10. H. Debrunner, P. Flor: Ein Erweiterungssatz fur monotone Mengen, Arch. Math. 15 (1964) 445–447.https://doi.org/10.1007/BF01589229Google Scholar
  11. J. Dutta: Gap functions and error bounds for variational and generalized variational inequalities, Vietnam J. Math. 40(2-3) (2012) 231–253.Google Scholar
  12. F. Facchinei, J.-S. Pang: Finite-Dimensional Variational Inequalities and Complementarity Problems I, Springer Series in Operations Research, Springer, New York (2003).https://doi.org/10.1007/b97544Google Scholar
  13. G. Fichera: Problemi elastostatici con vincoli unilaterali; il problema di Signorini con ambigue al contorno, Atti Acad. Naz. Lincei. Memorie, Cl. Sci. Fis. Mat. Nat. Sez. I 8 (1964) 91–140.Google Scholar
  14. M. Fukushima: A class of gap functions for quasi-variational inequality problems, J. Ind. Manag. Optim. 3(2) (2007) 165–171.https://doi.org/10.3934/jimo.2007.3.165Google Scholar
  15. I. V. Konnov: On convergence properties of a subgradient method, Optim. Methods Softw. 18(1) (2003) 53–62.https://doi.org/10.1080/1055678031000111236Google Scholar
  16. P. Marcotte, D. Zhu: Weak sharp solutions of variational inequalities, SIAM J. Optim. 9(1) (1999) 179–189.https://doi.org/10.1137/S1052623496309867Google Scholar
  17. J. Peng: Equivalence of variational inequality problem to unconstrained minimization, Math. Prog. 78(3) (1997) 347–355.https://doi.org/10.1007/BF02614360Google Scholar
  18. R. T. Rockafellar, R. J.-B. Wets: Variational Analysis, Fundamental Principles of Mathematical Sciences 317, Springer, Berlin (1998).https://doi.org/10.1007/978-3-642-02431-3Google Scholar
  19. G. Stampacchia: Formes bilinéaires coercitives sur le ensembles convexes, C. R. Acad. Sci. Paris 258 (1964) 4413–4416.Google Scholar
  20. L. Tunel: Polyhedral and Semidefinite Programming Methods in Combinatorial Optimization, Fields Institute Monographs 27, American Mathematical Society, Providence (2010).https://doi.org/10.1090/fim/027Google Scholar
  21. N. Yamashita, M. Fukushima: Equivalent unconstrained minimization and global error bounds for variational inequality problems, SIAM J. Control Optim. 35(1) (1997) 273–284.https://doi.org/10.1137/S0363012994277645Google Scholar
  22. N. Yamashita, K. Taji, M. Fukushima: Unconstrained optimization reformulations of variational inequality problems, J. Optim. Theory Appl. 92(3) (1997) 439–456.https://doi.org/10.1023/A:1022660704427Google Scholar
  23. J. Zhang, C. Wan, N. Xiu: The dual gap function for variational inequalities, Appl. Math. Optim. 48(2) (2003) 129–148.https://doi.org/10.1007/s00245-003-0771-9Google Scholar
  24. S. I. Zukhovitskii, R. A. Polyak, M. E. Primak: Two methods of search for equilibrium points of n-person concave games, Soviet Math. Doklady 10 (1969) 279–282.Google Scholar
  25. S. I. Zukhovitskii, R. A. Polyak, M. E. Primak: Concave multiperson games, Matekon 9 ( 1973) 10–30.Google Scholar

Suggested citation

D. Aussel, J. Dutta, A. C. Xu. “The Dual Gap Function and Error Bounds for Strongly Monotone Variational Inequalities.” Journal of Convex Analysis 25 (2018), No. 4, 1121–1138. https://doi.org/10.68381/jca25071

Download BibTeXPublished by Heldermann Verlag.

Published by Heldermann Verlag, 2018. Rights now held by Banach Press LLC.