American Institute of Mathematical Sciences

Advanced
December  2011, 31(4): 1383-1396. doi: 10.3934/dcds.2011.31.1383

Solving strongly monotone variational and quasi-variational inequalities

Yurii Nesterov 1, and  Laura Scrimali 2,

1. 

Center for Operations Research and Econometrics (CORE), Catholic University of Louvain, 34 voie du Roman Pays, 1348 Louvain-la-Neuve, Belgium
2. 

Dipartimento di Matematica e Informatica, Università di Catania, Viale A. Doria 6, 95125 Catania

Received  November 2009 Revised  September 2010 Published  September 2011

In this paper we develop a new and efficient method for variational inequality with Lipschitz continuous strongly monotone operator. Our analysis is based on a new strongly convex merit function. We apply a variant of the developed scheme for solving quasivariational inequalities. As a result, we significantly improve the standard sufficient condition for existence and uniqueness of their solutions. Moreover, we get a new numerical scheme, whose rate of convergence is much higher than that of the straightforward gradient method.
Keywords: quasi-variational inequality, Variational inequality, complexity analysis, monotone operators, efficiency estimate, optimal methods..
Mathematics Subject Classification: Primary: 49J40, 65K05; Secondary: 65Y2.
Citation: Yurii Nesterov, Laura Scrimali. Solving strongly monotone variational and quasi-variational inequalities. Discrete & Continuous Dynamical Systems - A, 2011, 31 (4) : 1383-1396. doi: 10.3934/dcds.2011.31.1383
References:
[1]

C. Baiocchi and A. Capelo, "Variational and Quasivariational Inequalities: Applications to Free Boundary Problems,", A Wiley Interscience Publication, (1984).   Google Scholar

[2]

A. Bensoussan, M. Goursat and J.-L- Lions, Contrôle impulsionnel et inéquations quasi-variationnelle stationnaires,, C. R. Acad. Sci. Paris Sér. A-B, 276 (1973).   Google Scholar

[3]

A. Bensoussan, Points de Nash dans le cas de fontionnelles quadratiques et jeux différentiels linéaires à N personnes,, SIAM J. Control, 12 (1974), 460.  doi: 10.1137/0312037.  Google Scholar

[4]

M. Bliemer and P. Bovy, Quasi-variational inequality formulation of the multiclass dynamic traffic assignment problem,, Transportation Res. Part B, 37 (2003), 501.  doi: 10.1016/S0191-2615(02)00025-5.  Google Scholar

[5]

A. Causa and F. Raciti, Lipschitz continuity results for a class of variational inequalities and applications: A geometric approach,, J. Optim. Theory Appl., 145 (2010), 235.  doi: 10.1007/s10957-009-9622-4.  Google Scholar

[6]

D. Chan and J. S. Pang, The generalized quasivariational inequality problem,, Math. Oper. Res., 7 (1982), 211.  doi: 10.1287/moor.7.2.211.  Google Scholar

[7]

F. Facchinei and J. S. Pang, "Finite-Dimensional Variational Inequalities and Complementarity Problems,", Springer Series in Operations Research, (2003).   Google Scholar

[8]

M. Fukushima, Equivalent differentiable optimization problems and descent methods for asymmetric variational inequality problems,, Math. Program., 53 (1992), 99.  doi: 10.1007/BF01585696.  Google Scholar

[9]

F. Giannessi, A. Maugeri and P. M. Pardalos, eds., "Variational Analysis and Applications,", Kluwer Academic Publishers, (2005).   Google Scholar

[10]

P. T. Harker, Generalized Nash games and quasi-variational inequalities,, Eur. J. Oper. Res., 54 (1991), 81.  doi: 10.1016/0377-2217(91)90325-P.  Google Scholar

[11]

J. Haslinger, Aproximation of the Signorini problem with friction, obeying Coulomb law,, Math. Methods Appl. Sci., 5 (1983), 422.  doi: 10.1002/mma.1670050127.  Google Scholar

[12]

J. Haslinger and P. D. Panagiotopoulos, The reciprocal variational approach to the Signorini problem with friction. Approximation results,, Proc. Royal Soc.of Edinburgh, 98 (1984), 365.   Google Scholar

[13]

M. Kocvara and J. V. Outrata, On a class of quasi-variational inequalities,, Optim. Methods Softw., 5 (1995), 275.  doi: 10.1080/10556789508805617.  Google Scholar

[14]

A. Maugeri and L. Scrimali, Global Lipschitz continuity of solutions to parameterized variational inequalities,, Boll. Unione Mat. Ital. (9), 2 (2009), 45.   Google Scholar

[15]

G. J. Minty, On the generalization of a direct method of the calculus of variations,, Bull. Amer. Math. Soc., 73 (1967), 314.  doi: 10.1090/S0002-9904-1967-11732-4.  Google Scholar

[16]

U. Mosco, Implicit variational problems and quasi variational inequalities,, in, 543 (1976), 83.   Google Scholar

[17]

A. Nagurney, "Network Economics: A Variational Inequality Approach," Advances in Computational Economics, 1,, Kluwer Academic Publishers Group, (1993).   Google Scholar

[18]

A. Nemirovski, Prox-method with rate of convergence O(1/t) for variational inequalities with Lipschitz continuous monotone operators and smooth convex-concave saddle point problems,, SIAM J. Optim., 15 (2004), 229.  doi: 10.1137/S1052623403425629.  Google Scholar

[19]

A. Nemirovsky and D. Yudin, "Problem Complexity and Method Efficiency in Optimization,", A Wiley Interscience Publication, (1983).   Google Scholar

[20]

Yu. Nesterov, "Introductory Lectures on Convex Optimization. A Basic Course,", Applied Optimization, 87 (2004).   Google Scholar

[21]

Yu. Nesterov, Smooth minimization of nonsmooth function,, Math. Program., 103 (2005), 127.  doi: 10.1007/s10107-004-0552-5.  Google Scholar

[22]

Yu. Nesterov, Dual extrapolation and its applications to solving variational inequalities and related problems,, Math. Program., 109 (2007), 319.  doi: 10.1007/s10107-006-0034-z.  Google Scholar

[23]

Yu. Nesterov, Minimizing functions with bounded variation of the gradient,, CORE DP 2005/79., (2005).   Google Scholar

[24]

M. A. Noor and Z. A. Memon, Algorithms for general mixed quasi variational inequalities,, J. Inequal. Pure Appl. Math., 3 (2002).   Google Scholar

[25]

M. A. Noor and W. Oettli, On general nonlinear complementarity problems and quasi-equilibria,, Le Matematiche (Catania), 49 (1994), 313.   Google Scholar

[26]

J. Outrata and J. Zowe, A numerical approach to optimization problems with variational inequality constraints,, Math. Program., 68 (1995), 105.  doi: 10.1007/BF01585759.  Google Scholar

[27]

J.-S. Pang and M. Fukushima, Quasi-variational inequalities, generalized Nash equilibria and multi-leader-follower games,, Comput. Manag. Sci., 1 (2005), 21.  doi: 10.1007/s10287-004-0010-0.  Google Scholar

[28]

Salahuddin, Projection methods for quasi-variational inequalities,, Mathematical and Computational Applications, 9 (2004), 125.   Google Scholar

[29]

L. Scrimali, The financial equilibrium problem with implicit budget constraints,, Cent. Eur. J. Oper. Res., 16 (2008), 191.  doi: 10.1007/s10100-007-0046-7.  Google Scholar

[30]

L. Scrimali, Mixed behavior network equilibria and quasi-variational inequalities,, J. Ind. Manag. Optim., 5 (2009), 363.  doi: 10.3934/jimo.2009.5.363.  Google Scholar

[31]

J. C. Yao, The generalized quasi-variational inequality problem with applications,, J. Math. Anal. Appl., 158 (1991), 139.  doi: 10.1016/0022-247X(91)90273-3.  Google Scholar

[32]

J. Y. Wei and Y. Smeers, Spatial oligopolistic electricity models with Cournot generators and regulated transmission prices,, Oper. Res., 47 (1999), 102.  doi: 10.1287/opre.47.1.102.  Google Scholar

show all references

References:
[1]

C. Baiocchi and A. Capelo, "Variational and Quasivariational Inequalities: Applications to Free Boundary Problems,", A Wiley Interscience Publication, (1984).   Google Scholar

[2]

A. Bensoussan, M. Goursat and J.-L- Lions, Contrôle impulsionnel et inéquations quasi-variationnelle stationnaires,, C. R. Acad. Sci. Paris Sér. A-B, 276 (1973).   Google Scholar

[3]

A. Bensoussan, Points de Nash dans le cas de fontionnelles quadratiques et jeux différentiels linéaires à N personnes,, SIAM J. Control, 12 (1974), 460.  doi: 10.1137/0312037.  Google Scholar

[4]

M. Bliemer and P. Bovy, Quasi-variational inequality formulation of the multiclass dynamic traffic assignment problem,, Transportation Res. Part B, 37 (2003), 501.  doi: 10.1016/S0191-2615(02)00025-5.  Google Scholar

[5]

A. Causa and F. Raciti, Lipschitz continuity results for a class of variational inequalities and applications: A geometric approach,, J. Optim. Theory Appl., 145 (2010), 235.  doi: 10.1007/s10957-009-9622-4.  Google Scholar

[6]

D. Chan and J. S. Pang, The generalized quasivariational inequality problem,, Math. Oper. Res., 7 (1982), 211.  doi: 10.1287/moor.7.2.211.  Google Scholar

[7]

F. Facchinei and J. S. Pang, "Finite-Dimensional Variational Inequalities and Complementarity Problems,", Springer Series in Operations Research, (2003).   Google Scholar

[8]

M. Fukushima, Equivalent differentiable optimization problems and descent methods for asymmetric variational inequality problems,, Math. Program., 53 (1992), 99.  doi: 10.1007/BF01585696.  Google Scholar

[9]

F. Giannessi, A. Maugeri and P. M. Pardalos, eds., "Variational Analysis and Applications,", Kluwer Academic Publishers, (2005).   Google Scholar

[10]

P. T. Harker, Generalized Nash games and quasi-variational inequalities,, Eur. J. Oper. Res., 54 (1991), 81.  doi: 10.1016/0377-2217(91)90325-P.  Google Scholar

[11]

J. Haslinger, Aproximation of the Signorini problem with friction, obeying Coulomb law,, Math. Methods Appl. Sci., 5 (1983), 422.  doi: 10.1002/mma.1670050127.  Google Scholar

[12]

J. Haslinger and P. D. Panagiotopoulos, The reciprocal variational approach to the Signorini problem with friction. Approximation results,, Proc. Royal Soc.of Edinburgh, 98 (1984), 365.   Google Scholar

[13]

M. Kocvara and J. V. Outrata, On a class of quasi-variational inequalities,, Optim. Methods Softw., 5 (1995), 275.  doi: 10.1080/10556789508805617.  Google Scholar

[14]

A. Maugeri and L. Scrimali, Global Lipschitz continuity of solutions to parameterized variational inequalities,, Boll. Unione Mat. Ital. (9), 2 (2009), 45.   Google Scholar

[15]

G. J. Minty, On the generalization of a direct method of the calculus of variations,, Bull. Amer. Math. Soc., 73 (1967), 314.  doi: 10.1090/S0002-9904-1967-11732-4.  Google Scholar

[16]

U. Mosco, Implicit variational problems and quasi variational inequalities,, in, 543 (1976), 83.   Google Scholar

[17]

A. Nagurney, "Network Economics: A Variational Inequality Approach," Advances in Computational Economics, 1,, Kluwer Academic Publishers Group, (1993).   Google Scholar

[18]

A. Nemirovski, Prox-method with rate of convergence O(1/t) for variational inequalities with Lipschitz continuous monotone operators and smooth convex-concave saddle point problems,, SIAM J. Optim., 15 (2004), 229.  doi: 10.1137/S1052623403425629.  Google Scholar

[19]

A. Nemirovsky and D. Yudin, "Problem Complexity and Method Efficiency in Optimization,", A Wiley Interscience Publication, (1983).   Google Scholar

[20]

Yu. Nesterov, "Introductory Lectures on Convex Optimization. A Basic Course,", Applied Optimization, 87 (2004).   Google Scholar

[21]

Yu. Nesterov, Smooth minimization of nonsmooth function,, Math. Program., 103 (2005), 127.  doi: 10.1007/s10107-004-0552-5.  Google Scholar

[22]

Yu. Nesterov, Dual extrapolation and its applications to solving variational inequalities and related problems,, Math. Program., 109 (2007), 319.  doi: 10.1007/s10107-006-0034-z.  Google Scholar

[23]

Yu. Nesterov, Minimizing functions with bounded variation of the gradient,, CORE DP 2005/79., (2005).   Google Scholar

[24]

M. A. Noor and Z. A. Memon, Algorithms for general mixed quasi variational inequalities,, J. Inequal. Pure Appl. Math., 3 (2002).   Google Scholar

[25]

M. A. Noor and W. Oettli, On general nonlinear complementarity problems and quasi-equilibria,, Le Matematiche (Catania), 49 (1994), 313.   Google Scholar

[26]

J. Outrata and J. Zowe, A numerical approach to optimization problems with variational inequality constraints,, Math. Program., 68 (1995), 105.  doi: 10.1007/BF01585759.  Google Scholar

[27]

J.-S. Pang and M. Fukushima, Quasi-variational inequalities, generalized Nash equilibria and multi-leader-follower games,, Comput. Manag. Sci., 1 (2005), 21.  doi: 10.1007/s10287-004-0010-0.  Google Scholar

[28]

Salahuddin, Projection methods for quasi-variational inequalities,, Mathematical and Computational Applications, 9 (2004), 125.   Google Scholar

[29]

L. Scrimali, The financial equilibrium problem with implicit budget constraints,, Cent. Eur. J. Oper. Res., 16 (2008), 191.  doi: 10.1007/s10100-007-0046-7.  Google Scholar

[30]

L. Scrimali, Mixed behavior network equilibria and quasi-variational inequalities,, J. Ind. Manag. Optim., 5 (2009), 363.  doi: 10.3934/jimo.2009.5.363.  Google Scholar

[31]

J. C. Yao, The generalized quasi-variational inequality problem with applications,, J. Math. Anal. Appl., 158 (1991), 139.  doi: 10.1016/0022-247X(91)90273-3.  Google Scholar

[32]

J. Y. Wei and Y. Smeers, Spatial oligopolistic electricity models with Cournot generators and regulated transmission prices,, Oper. Res., 47 (1999), 102.  doi: 10.1287/opre.47.1.102.  Google Scholar

[1]

Yifan Chen, Thomas Y. Hou. Function approximation via the subsampled Poincaré inequality. Discrete & Continuous Dynamical Systems - A, 2021, 41 (1) : 169-199. doi: 10.3934/dcds.2020296
[2]

Andrew D. Lewis. Erratum for "nonholonomic and constrained variational mechanics". Journal of Geometric Mechanics, 2020, 12 (4) : 671-675. doi: 10.3934/jgm.2020033
[3]

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
[4]

Lingfeng Li, Shousheng Luo, Xue-Cheng Tai, Jiang Yang. A new variational approach based on level-set function for convex hull problem with outliers. Inverse Problems & Imaging, , () : -. doi: 10.3934/ipi.2020070
[5]

Wenmeng Geng, Kai Tao. Large deviation theorems for dirichlet determinants of analytic quasi-periodic jacobi operators with Brjuno-Rüssmann frequency. Communications on Pure & Applied Analysis, 2020, 19 (12) : 5305-5335. doi: 10.3934/cpaa.2020240
[6]

Xin Guo, Lei Shi. Preface of the special issue on analysis in data science: Methods and applications. Mathematical Foundations of Computing, 2020, 3 (4) : i-ii. doi: 10.3934/mfc.2020026
[7]

Wei Ouyang, Li Li. Hölder strong metric subregularity and its applications to convergence analysis of inexact Newton methods. Journal of Industrial & Management Optimization, 2021, 17 (1) : 169-184. doi: 10.3934/jimo.2019105
[8]

Pierluigi Colli, Gianni Gilardi, Jürgen Sprekels. Deep quench approximation and optimal control of general Cahn–Hilliard systems with fractional operators and double obstacle potentials. Discrete & Continuous Dynamical Systems - S, 2021, 14 (1) : 243-271. doi: 10.3934/dcdss.2020213
[9]

Jie Li, Xiangdong Ye, Tao Yu. Mean equicontinuity, complexity and applications. Discrete & Continuous Dynamical Systems - A, 2021, 41 (1) : 359-393. doi: 10.3934/dcds.2020167
[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]

Hassan Mohammad. A diagonal PRP-type projection method for convex constrained nonlinear monotone equations. Journal of Industrial & Management Optimization, 2021, 17 (1) : 101-116. doi: 10.3934/jimo.2019101
[12]

Hao Wang. Uniform stability estimate for the Vlasov-Poisson-Boltzmann system. Discrete & Continuous Dynamical Systems - A, 2021, 41 (2) : 657-680. doi: 10.3934/dcds.2020292
[13]

Predrag S. Stanimirović, Branislav Ivanov, Haifeng Ma, Dijana Mosić. A survey of gradient methods for solving nonlinear optimization. Electronic Research Archive, 2020, 28 (4) : 1573-1624. doi: 10.3934/era.2020115
[14]

Guido Cavallaro, Roberto Garra, Carlo Marchioro. Long time localization of modified surface quasi-geostrophic equations. Discrete & Continuous Dynamical Systems - B, 2020  doi: 10.3934/dcdsb.2020336
[15]

George W. Patrick. The geometry of convergence in numerical analysis. Journal of Computational Dynamics, 2021, 8 (1) : 33-58. doi: 10.3934/jcd.2021003
[16]

Xuefei He, Kun Wang, Liwei Xu. Efficient finite difference methods for the nonlinear Helmholtz equation in Kerr medium. Electronic Research Archive, 2020, 28 (4) : 1503-1528. doi: 10.3934/era.2020079
[17]

Huiying Fan, Tao Ma. Parabolic equations involving Laguerre operators and weighted mixed-norm estimates. Communications on Pure & Applied Analysis, 2020, 19 (12) : 5487-5508. doi: 10.3934/cpaa.2020249
[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]

Shun Zhang, Jianlin Jiang, Su Zhang, Yibing Lv, Yuzhen Guo. ADMM-type methods for generalized multi-facility Weber problem. Journal of Industrial & Management Optimization, 2020  doi: 10.3934/jimo.2020171
[20]

Anton A. Kutsenko. Isomorphism between one-Dimensional and multidimensional finite difference operators. Communications on Pure & Applied Analysis, 2021, 20 (1) : 359-368. doi: 10.3934/cpaa.2020270

2019 Impact Factor: 1.338

Tools

Metrics

  • PDF downloads (112)
  • HTML views (0)
  • Cited by (19)

Other articles
by authors

[Back to Top]

Copyright © 2020 American Institute of Mathematical Sciences