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, 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, John Wiley & Sons, Inc., New York, 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), A1279-A1284.  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-499. 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-519. 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-248. 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-222. 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, Springer-Verlag, New York, 2003. Google Scholar

[8]

M. Fukushima, Equivalent differentiable optimization problems and descent methods for asymmetric variational inequality problems, Math. Program., 53 (1992), 99-110. 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-94. 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-437. 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, Sect.A, 98 (1984), 365-383.  Google Scholar

[13]

M. Kocvara and J. V. Outrata, On a class of quasi-variational inequalities, Optim. Methods Softw., 5 (1995), 275-295. 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-69.  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-321. doi: 10.1090/S0002-9904-1967-11732-4.  Google Scholar

[16]

U. Mosco, Implicit variational problems and quasi variational inequalities, in "Nonlinear Operators and Calculus of Variations" (Summer School, Univ. Libre Bruxelles, Brussels, 1975), Lectures Notes Math, 543, Springer, Berlin, (1976), 83-156.  Google Scholar

[17]

A. Nagurney, "Network Economics: A Variational Inequality Approach," Advances in Computational Economics, 1, Kluwer Academic Publishers Group, Dordrecht, 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-251. doi: 10.1137/S1052623403425629.  Google Scholar

[19]

A. Nemirovsky and D. Yudin, "Problem Complexity and Method Efficiency in Optimization," A Wiley Interscience Publication, Wiley-Interscience Series in Discrete Mathematics, John Wiley & Sons, Inc., New York, 1983.  Google Scholar

[20]

Yu. Nesterov, "Introductory Lectures on Convex Optimization. A Basic Course," Applied Optimization, 87, Kluwer Academic Publishers, Boston, MA, 2004.  Google Scholar

[21]

Yu. Nesterov, Smooth minimization of nonsmooth function, Math. Program., 103 (2005), 127-152. 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-344. doi: 10.1007/s10107-006-0034-z.  Google Scholar

[23]

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

[24]

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

[25]

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

[26]

J. Outrata and J. Zowe, A numerical approach to optimization problems with variational inequality constraints, Math. Program., 68 (1995), 105-130. 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-56. doi: 10.1007/s10287-004-0010-0.  Google Scholar

[28]

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

[29]

L. Scrimali, The financial equilibrium problem with implicit budget constraints, Cent. Eur. J. Oper. Res., 16 (2008), 191-203. 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-379. 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-160. 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-112. 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, John Wiley & Sons, Inc., New York, 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), A1279-A1284.  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-499. 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-519. 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-248. 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-222. 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, Springer-Verlag, New York, 2003. Google Scholar

[8]

M. Fukushima, Equivalent differentiable optimization problems and descent methods for asymmetric variational inequality problems, Math. Program., 53 (1992), 99-110. 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-94. 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-437. 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, Sect.A, 98 (1984), 365-383.  Google Scholar

[13]

M. Kocvara and J. V. Outrata, On a class of quasi-variational inequalities, Optim. Methods Softw., 5 (1995), 275-295. 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-69.  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-321. doi: 10.1090/S0002-9904-1967-11732-4.  Google Scholar

[16]

U. Mosco, Implicit variational problems and quasi variational inequalities, in "Nonlinear Operators and Calculus of Variations" (Summer School, Univ. Libre Bruxelles, Brussels, 1975), Lectures Notes Math, 543, Springer, Berlin, (1976), 83-156.  Google Scholar

[17]

A. Nagurney, "Network Economics: A Variational Inequality Approach," Advances in Computational Economics, 1, Kluwer Academic Publishers Group, Dordrecht, 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-251. doi: 10.1137/S1052623403425629.  Google Scholar

[19]

A. Nemirovsky and D. Yudin, "Problem Complexity and Method Efficiency in Optimization," A Wiley Interscience Publication, Wiley-Interscience Series in Discrete Mathematics, John Wiley & Sons, Inc., New York, 1983.  Google Scholar

[20]

Yu. Nesterov, "Introductory Lectures on Convex Optimization. A Basic Course," Applied Optimization, 87, Kluwer Academic Publishers, Boston, MA, 2004.  Google Scholar

[21]

Yu. Nesterov, Smooth minimization of nonsmooth function, Math. Program., 103 (2005), 127-152. 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-344. doi: 10.1007/s10107-006-0034-z.  Google Scholar

[23]

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

[24]

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

[25]

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

[26]

J. Outrata and J. Zowe, A numerical approach to optimization problems with variational inequality constraints, Math. Program., 68 (1995), 105-130. 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-56. doi: 10.1007/s10287-004-0010-0.  Google Scholar

[28]

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

[29]

L. Scrimali, The financial equilibrium problem with implicit budget constraints, Cent. Eur. J. Oper. Res., 16 (2008), 191-203. 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-379. 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-160. 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-112. doi: 10.1287/opre.47.1.102.  Google Scholar

[1]

Masao Fukushima. A class of gap functions for quasi-variational inequality problems. Journal of Industrial & Management Optimization, 2007, 3 (2) : 165-171. doi: 10.3934/jimo.2007.3.165
[2]

Takeshi Fukao, Nobuyuki Kenmochi. Quasi-variational inequality approach to heat convection problems with temperature dependent velocity constraint. Discrete & Continuous Dynamical Systems, 2015, 35 (6) : 2523-2538. doi: 10.3934/dcds.2015.35.2523
[3]

Lori Badea. Multigrid methods for some quasi-variational inequalities. Discrete & Continuous Dynamical Systems - S, 2013, 6 (6) : 1457-1471. doi: 10.3934/dcdss.2013.6.1457
[4]

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 & Management Optimization, 2021  doi: 10.3934/jimo.2021095
[5]

Yusuke Murase, Atsushi Kadoya, Nobuyuki Kenmochi. Optimal control problems for quasi-variational inequalities and its numerical approximation. Conference Publications, 2011, 2011 (Special) : 1101-1110. doi: 10.3934/proc.2011.2011.1101
[6]

Augusto VisintiN. On the variational representation of monotone operators. Discrete & Continuous Dynamical Systems - S, 2017, 10 (4) : 909-918. doi: 10.3934/dcdss.2017046
[7]

Yusuke Murase, Risei Kano, Nobuyuki Kenmochi. Elliptic Quasi-variational inequalities and applications. Conference Publications, 2009, 2009 (Special) : 583-591. doi: 10.3934/proc.2009.2009.583
[8]

Martin Brokate, Pavel Krejčí. Optimal control of ODE systems involving a rate independent variational inequality. Discrete & Continuous Dynamical Systems - B, 2013, 18 (2) : 331-348. doi: 10.3934/dcdsb.2013.18.331
[9]

Takeshi Fukao. Variational inequality for the Stokes equations with constraint. Conference Publications, 2011, 2011 (Special) : 437-446. doi: 10.3934/proc.2011.2011.437
[10]

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 & Optimization, 2021  doi: 10.3934/naco.2021011
[11]

Nobuyuki Kenmochi. Parabolic quasi-variational diffusion problems with gradient constraints. Discrete & Continuous Dynamical Systems - S, 2013, 6 (2) : 423-438. doi: 10.3934/dcdss.2013.6.423
[12]

Laura Scrimali. Mixed behavior network equilibria and quasi-variational inequalities. Journal of Industrial & Management Optimization, 2009, 5 (2) : 363-379. doi: 10.3934/jimo.2009.5.363
[13]

Zijia Peng, Cuiming Ma, Zhonghui Liu. Existence for a quasistatic variational-hemivariational inequality. Evolution Equations & Control Theory, 2020, 9 (4) : 1153-1165. doi: 10.3934/eect.2020058
[14]

S. J. Li, Z. M. Fang. On the stability of a dual weak vector variational inequality problem. Journal of Industrial & Management Optimization, 2008, 4 (1) : 155-165. doi: 10.3934/jimo.2008.4.155
[15]

Junkee Jeon, Jehan Oh. Valuation of American strangle option: Variational inequality approach. Discrete & Continuous Dynamical Systems - B, 2019, 24 (2) : 755-781. doi: 10.3934/dcdsb.2018206
[16]

Wenyan Zhang, Shu Xu, Shengji Li, Xuexiang Huang. Generalized weak sharp minima of variational inequality problems with functional constraints. Journal of Industrial & Management Optimization, 2013, 9 (3) : 621-630. doi: 10.3934/jimo.2013.9.621
[17]

Li Wang, Yang Li, Liwei Zhang. A differential equation method for solving box constrained variational inequality problems. Journal of Industrial & Management Optimization, 2011, 7 (1) : 183-198. doi: 10.3934/jimo.2011.7.183
[18]

T. A. Shaposhnikova, M. N. Zubova. Homogenization problem for a parabolic variational inequality with constraints on subsets situated on the boundary of the domain. Networks & Heterogeneous Media, 2008, 3 (3) : 675-689. doi: 10.3934/nhm.2008.3.675
[19]

Junfeng Yang. Dynamic power price problem: An inverse variational inequality approach. Journal of Industrial & Management Optimization, 2008, 4 (4) : 673-684. doi: 10.3934/jimo.2008.4.673
[20]

Hui-Qiang Ma, Nan-Jing Huang. Neural network smoothing approximation method for stochastic variational inequality problems. Journal of Industrial & Management Optimization, 2015, 11 (2) : 645-660. doi: 10.3934/jimo.2015.11.645

2020 Impact Factor: 1.392

Tools

Metrics

  • PDF downloads (218)
  • HTML views (0)
  • Cited by (22)

Other articles
by authors

[Back to Top]

Copyright © 2021 American Institute of Mathematical Sciences