research-article

A Method with Convergence Rates for Optimization Problems with Variational Inequality Constraints

Authors:

Harshal D. Kaushik,

Farzad YousefianAuthors Info & Claims

SIAM Journal on Optimization, Volume 31, Issue 3

Pages 2171 - 2198

https://doi.org/10.1137/20M1357378

Published: 01 January 2021 Publication History

Abstract

We consider a class of optimization problems with Cartesian variational inequality (CVI) constraints, where the objective function is convex and the CVI is associated with a monotone mapping and a convex Cartesian product set. This mathematical formulation captures a wide range of optimization problems including those complicated by the presence of equilibrium constraints, complementarity constraints, or an inner-level large scale optimization problem. In particular, an important motivating application arises from the notion of efficiency estimation of equilibria in multi-agent networks, e.g., communication networks and power systems. In the literature, the iteration complexity of the existing solution methods for optimization problems with CVI constraints appears to be unknown. To address this shortcoming, we develop a first-order method called averaging randomized block iteratively regularized gradient (aRB-IRG). The main contributions include the following: (i) In the case where the associated set of the CVI is bounded and the objective function is nondifferentiable and convex, we derive new nonasymptotic suboptimality and infeasibility convergence rate statements in an ergodic sense. We also obtain deterministic variants of the convergence rates when we suppress the randomized block-coordinate scheme. Importantly, this paper appears to be the first work to provide these rate guarantees for this class of problems. (ii) In the case where the CVI set is unbounded and the objective function is smooth and strongly convex, utilizing the properties of the Tikhonov trajectory, we establish the global convergence of aRB-IRG in an almost sure and a mean sense. We provide the numerical experiments for computing the best Nash equilibrium in a networked Cournot competition model.

References

[1]

T. Alpcan and T. Başar, A game-theoretic framework for congestion control in general topology networks, in Proceedings of the 41st IEEE Conference on Decision and Control, 2002, pp. 1218--1224.

[2]

T. Alpcan and T. Başar, Distributed algorithms for Nash equilibria of flow control games, in Advances in Dynamic Games, Annals of the International Society of Dynamic Games 7, Birkhäuser Boston, 2003, pp. 473--498.

[3]

M. Amini and F. Yousefian, An Iterative Regularized Mirror Descent Method for Ill-Posed Nondifferentiable Stochastic Optimization, https://arxiv.org/abs/1901.09506, 2019.

[4]

E. Anshelevich, A. Dasgupta, J. Kleinberg, E. Tardos, T. Wexler, and T. Roughgarden, The price of stability for network design with fair cost allocation, SIAM J. Comput., 38 (2008), pp. 1602--1623.

[5]

A. Beck and S. Sabach, A first order method for finding minimal norm-like solutions of convex optimization problems, Math. Program., 147 (2014), pp. 25--46.

[6]

D. P. Bertsekas, Nonlinear Programming, 3rd ed., Athena Scientific, Bellmont, MA, 2016.

[7]

Y. Censor, A. Gibali, and S. Reich, The subgradient extragradient method for solving variational inequalities in Hilbert space, J. Optim. Theory Appl., 148 (2011), pp. 318--335.

[8]

Y. Censor, A. Gibali, and S. Reich, Extensions of Korpelevich's extragradient method for the variational inequality problem in Euclidean space, Optimization, 61 (2012), pp. 1119--1132.

[9]

Y. Chen, G. Lan, and Y. Ouyang, Accelerated schemes for a class of variational inequalities, Math. Program., 165 (2017), pp. 113--149.

[10]

J. R. Correa, A. S. Schulz, and N. E. Stier-Moses, Selfish routing in capacitated networks, Math. Oper. Res., 29 (2004), pp. 961--976.

[11]

C. D. Dang and G. Lan, On the convergence properties of non-Euclidean extragradient methods for variational inequalities with generalized monotone operators, Comput. Optim. Appl., 60 (2015), pp. 277--310.

[12]

C. D. Dang and G. Lan, Stochastic block mirror descent methods for nonsmooth and stochastic optimization, SIAM J. Optim., 25 (2015), pp. 856--881.

[13]

F. Facchinei and J.-S. Pang, Finite-Dimensional Variational Inequalities and Complementarity Problems, Springer Ser. Oper. Res., Springer-Verlag, New York, 2003.

[14]

G. Garrigos, L. Rosasco, and S. Villa, Iterative regularization via dual diagonal descent, J. Math. Imaging Vision, 60 (2018), pp. 189--215.

[15]

A. N. Iusem, A. Jofré, R. I. Oliveira, and P. Thompson, Extragradient method with variance reduction for stochastic variational inequalities, SIAM J. Optim., 27 (2016), pp. 686--724.

[16]

A. N. Iusem, A. Jofré, and P. Thompson, Incremental constraint projection methods for monotone stochastic variational inequalities, Math. Oper. Res., 44 (2019), pp. 236--263.

[17]

A. N. Iusem and M. Nasri, Korpelevich's method for variational inequality problems in Banach spaces, J. Global Optim., 50 (2011), pp. 59--76.

[18]

H. Jiang and H. Xu, Stochastic approximation approaches to the stochastic variational inequality problem, IEEE Trans. Automat. Control, 53 (2008), pp. 1462--1475.

[19]

R. Johari, Efficiency Loss in Market Mechanisms for Resource Allocation, Ph.D. thesis, MIT, 2004.

[20]

A. Juditsky, A. Nemirovski, and C. Tauvel, Solving variational inequalities with stochastic mirror-prox algorithm, Stoch. Syst., 1 (2011), pp. 17--58.

[21]

A. Kannan and U. V. Shanbhag, Distributed computation of equilibria in monotone Nash games via iterative regularization techniques, SIAM J. Optim., 22 (2012), pp. 1177--1205.

[22]

A. Kannan, U. V. Shanbhag, and H. M. Kim, Strategic behavior in power markets under uncertainty, Energy Systems, 2 (2011), pp. 115--141.

[23]

A. Kannan, U. V. Shanbhag, and H. M. Kim, Addressing supply-side risk in uncertain power markets: Stochastic Nash models, scalable algorithms and error analysis, Optim. Methods Softw., 28 (2013), pp. 1095--1138.

[24]

H. D. Kaushik and F. Yousefian, A randomized block coordinate iterative regularized subgradient method for high-dimensional ill-posed convex optimization, in Proceedings of the American Control Conference, IEEE, 2019, pp. 3420--3425, https://doi.org/10.23919/ACC.2019.8815256.

[25]

H. D. Kaushik and F. Yousefian, An incremental gradient method for large-scale distributed nonlinearly constrained optimization, in Proceedings of the American Control Conference, 2021, pp. 953--958, https://doi.org/10.23919/ACC50511.2021.9483035.

[26]

K. Knopp, Theory and Applications of Infinite Series, Blackie & Son, Glasgow, 1951.

[27]

G. M. Korpelevich, An extragradient method for finding saddle points and for other problems, Eknomika Matematicheskie Metody, 12 (1976), pp. 747--756.

[28]

J. Koshal, A. Nedić, and U. V. Shanbhag, Regularized iterative stochastic approximation methods for stochastic variational inequality problems, IEEE Trans. Automat. Control, 58 (2013), pp. 594--609.

[29]

J. Lei, U. V. Shanbhag, J.-S. Pang, and S. Sen, On synchronous, asynchronous, and randomized best-response schemes for stochastic Nash games, Math. Oper. Res., 45 (2020), pp. 157--190.

[30]

C. E. Lemke and J. T. Howson, Jr., Equilibrium points of bimatrix games, J. SIAM, 12 (1964), pp. 413--423.

[31]

P. Marcotte and D. Zhu, Weak sharp solutions of variational inequalities, SIAM J. Optim., 9 (1998), pp. 179--189.

[32]

A. Nedić, Random algorithms for convex minimization problems, Math. Program., 129 (2011), pp. 225--253.

[33]

A. Nemirovski, Prox-method with rate of convergence $\mathcal{O}(1/t)$ for variational inequalities with Lipschitz continuous monotone operators and smooth convex-concave saddle point problems, SIAM J. Optim., 15 (2004), pp. 229--251.

[34]

YU. Nesterov, Efficiency of coordinate descent methods on huge-scale optimization problems, SIAM J. Optim., 22 (2012), pp. 341--362.

[35]

N. Nisan, T. Roughgarden, E. Tardos, and V. V. Vazirani, Algorithmic Game Theory, Cambridge University Press, New York, 2007.

[36]

M. J. Osborne and A. Rubinstein, A Course in Game Theory, MIT Press, Cambridge, MA, 1994.

[37]

B. T. Polyak, Introduction to Optimization, Optimization Software, New York, 1987.

[38]

P. Ricktárik and M. Takáč, Iteration complexity of randomized block-coordinate descent methods for minimizing a composite function, Math. Program., 144 (2014), pp. 1--38.

[39]

R. T. Rockafellar and R. J.-B. Wets, Variational Analysis, Springer-Verlag, Berlin, 1998.

[40]

T. Roughgarden, Stackelberg scheduling strategies, SIAM J. Comput., 33 (2004), pp. 332--350.

[41]

S. Sabach and S. Shtern, A first order method for solving convex bilevel optimization problems, SIAM J. Optim., 27 (2017), pp. 640--660.

[42]

H. Scarf, The approximation of fixed points of a continuous mapping, SIAM J. Appl. Math., 15 (1967), pp. 1328--1343.

[43]

G. Scutari, D. P. Palomar, F. Facchinei, and J.-S. Pang, Convex optimization, game theory, and variational inequality theory, IEEE Signal Processing Magazine, 27 (2010), pp. 35--49.

[44]

G. Scutari, D. P. Palomar, F. Facchinei, and J.-S. Pang, Monotone games for cognitive radio systems, in Distributed Decision Making and Control, Springer, New York, pp. 83--112.

[45]

S. Shalev-Shwartz and T. Zhang, Stochastic dual coordinate ascent methods for regularized loss minimization, J. Mach. Learn. Res., 14 (2013), pp. 567--599.

[46]

U. V. Shanbhag, G. Infanger, and P. W. Glynn, A complementarity framework for forward contracting under uncertainty, Oper. Res., 59 (2011), pp. 810--834.

[47]

M. V. Solodov, An explicit descent method for bilevel convex optimization, J. Convex Anal., 14 (2007), pp. 227--237.

[48]

J. Wang, G. Scutari, and D. P. Palomar, Robust MIMO cognitive radio via game theory, IEEE Trans. Signal Process., 59 (2011), pp. 1183--1201.

[49]

M. Wang and D. P. Bertsekas, Incremental constraint projection methods for variational inequalities, Math. Program., 150 (2015), pp. 321--363.

[50]

H.-K. Xu, Viscosity approximation methods for nonexpansive mappings, J. Math. Anal. Appl., 298 (2004), pp. 279--291.

[51]

H. Yin, U. V. Shanbhag, and P. G. Mehta, Nash equilibrium problems with scaled congestion costs and shared constraints, IEEE Trans. Automat. Control, 56 (2011), pp. 1702--1708.

[52]

F. Yousefian, Bilevel distributed optimization in directed networks, in Proceedings of the American Control Conference, 2021, pp. 2230--2235, https://doi.org/10.23919/ACC50511.2021.9483429.

[53]

F. Yousefian, A. Nedić, and U. V. Shanbhag, Optimal robust smoothing extragradient algorithms for stochastic variational inequality problems, in Proceedings of the 53rd IEEE Conference on Decision and Control, 2014, pp. 5831--5836.

[54]

F. Yousefian, A. Nedić, and U. V. Shanbhag, On smoothing, regularization, and averaging in stochastic approximation methods for stochastic variational inequality problems, Math. Program., 165 (2017), pp. 391--431, https://doi.org/10.1007/s10107-017-1175-y.

[55]

F. Yousefian, A. Nedić, and U. V. Shanbhag, On stochastic mirror-prox algorithms for stochastic Cartesian variational inequalities: Randomized block coordinate and optimal averaging schemes, Set-Valued Var. Anal., 26 (2018), pp. 789--819, https://doi.org/10.1007/s11228-018-0472-9.

[56]

F. Yousefian, A. Nedić, and U. V. Shanbhag, On stochastic and deterministic quasi-Newton methods for nonstrongly convex optimization: Asymptotic convergence and rate analysis, SIAM J. Optim., 30 (2020), pp. 1144--1172, https://doi.org/10.1137/17M1152474.

Cited By

Cao JJiang RAbolfazli NHamedani EMokhtari AOh ANaumann TGloberson ASaenko KHardt MLevine S(2023)Projection-free methods for stochastic simple bilevel optimization with convex lower-level problemProceedings of the 37th International Conference on Neural Information Processing Systems10.5555/3666122.3666390(6105-6131)Online publication date: 10-Dec-2023
https://dl.acm.org/doi/10.5555/3666122.3666390
Jalilzadeh AYousefian FEbrahimi M(2023)Stochastic Approximation for Estimating the Price of Stability in Stochastic Nash GamesACM Transactions on Modeling and Computer Simulation10.1145/363252534:2(1-24)Online publication date: 11-Nov-2023
https://dl.acm.org/doi/10.1145/3632525
Xie ZCai GDong Q(2023)Strong convergence of Bregman projection method for solving variational inequality problems in reflexive Banach spacesNumerical Algorithms10.1007/s11075-022-01414-893:1(269-294)Online publication date: 1-May-2023
https://dl.acm.org/doi/10.1007/s11075-022-01414-8
Show More Cited By

Recommendations

A modified Solodov-Svaiter method for solving nonmonotone variational inequality problems
Abstract
In a very interesting paper (SIAM J. Control Optim. 37(3): 765–776, 1999), Solodov and Svaiter introduced an effective projection algorithm with linesearch for finding a solution of a variational inequality problem (VIP) in Euclidean space. They ...
Strong Stationarity Conditions for a Class of Optimization Problems Governed by Variational Inequalities of the Second Kind

We investigate optimality conditions for optimization problems constrained by a class of variational inequalities of the second kind. Based on a nonsmooth primal---dual reformulation of the governing inequality, the differentiability of the solution map ...
Lagrangian Duality and Related Multiplier Methods for Variational Inequality Problems

We consider a new class of multiplier interior point methods for solving variational inequality problems with maximal monotone operators and explicit convex constraint inequalities. Developing a simple Lagrangian duality scheme which is combined with ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image SIAM Journal on Optimization

SIAM Journal on Optimization Volume 31, Issue 3

DOI:10.1137/sjope8.31.3

Issue’s Table of Contents

© 2021, Society for Industrial and Applied Mathematics.

Publisher

Society for Industrial and Applied Mathematics

United States

Publication History

Published: 01 January 2021

Author Tags

Author Tags

Qualifiers

Research-article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

4
Total Citations
View Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 09 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

Cao JJiang RAbolfazli NHamedani EMokhtari AOh ANaumann TGloberson ASaenko KHardt MLevine S(2023)Projection-free methods for stochastic simple bilevel optimization with convex lower-level problemProceedings of the 37th International Conference on Neural Information Processing Systems10.5555/3666122.3666390(6105-6131)Online publication date: 10-Dec-2023
https://dl.acm.org/doi/10.5555/3666122.3666390
Jalilzadeh AYousefian FEbrahimi M(2023)Stochastic Approximation for Estimating the Price of Stability in Stochastic Nash GamesACM Transactions on Modeling and Computer Simulation10.1145/363252534:2(1-24)Online publication date: 11-Nov-2023
https://dl.acm.org/doi/10.1145/3632525
Xie ZCai GDong Q(2023)Strong convergence of Bregman projection method for solving variational inequality problems in reflexive Banach spacesNumerical Algorithms10.1007/s11075-022-01414-893:1(269-294)Online publication date: 1-May-2023
https://dl.acm.org/doi/10.1007/s11075-022-01414-8
Shen LHo-Nguyen NKılınç-Karzan F(2023)An online convex optimization-based framework for convex bilevel optimizationMathematical Programming: Series A and B10.1007/s10107-022-01894-5198:2(1519-1582)Online publication date: 1-Apr-2023
https://dl.acm.org/doi/10.1007/s10107-022-01894-5

View Options

View options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

Media

Figures

Other

Tables

View Issue’s Table of Contents