Solving strongly monotone variational and quasi-variational inequalities

Previous Article
Radial solutions to energy supercritical wave equations in odd dimensions
DCDS Home
This Issue
Next Article
Quasilinear divergence form parabolic equations in Reifenberg flat domains

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

Abstract
Related Papers

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

American Institute of Mathematical Sciences