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]

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]

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Frank Jochmann. A variational inequality in Bean's model for superconductors with displacement current. Discrete & Continuous Dynamical Systems - A, 2009, 25 (2) : 545-565. doi: 10.3934/dcds.2009.25.545
[17]

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

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

Ren-You Zhong, Nan-Jing Huang. Strict feasibility for generalized mixed variational inequality in reflexive Banach spaces. Numerical Algebra, Control & Optimization, 2011, 1 (2) : 261-274. doi: 10.3934/naco.2011.1.261
[20]

Walter Allegretto, Yanping Lin, Shuqing Ma. On the box method for a non-local parabolic variational inequality. Discrete & Continuous Dynamical Systems - B, 2001, 1 (1) : 71-88. doi: 10.3934/dcdsb.2001.1.71

2018 Impact Factor: 1.143

Tools

Metrics

  • PDF downloads (38)
  • HTML views (0)
  • Cited by (10)

Other articles
by authors

[Back to Top]

Copyright © 2019 American Institute of Mathematical Sciences