×

Optimal stochastic extragradient schemes for pseudomonotone stochastic variational inequality problems and their variants. (English) Zbl 1439.90069

Summary: We consider the stochastic variational inequality problem in which the map is expectation-valued in a component-wise sense. Much of the available convergence theory and rate statements for stochastic approximation schemes are limited to monotone maps. However, non-monotone stochastic variational inequality problems are not uncommon and are seen to arise from product pricing, fractional optimization problems, and subclasses of economic equilibrium problems. Motivated by the need to address a broader class of maps, we make the following contributions: (1) we present an extragradient-based stochastic approximation scheme and prove that the iterates converge to a solution of the original problem under either pseudomonotonicity requirements or a suitably defined acute angle condition. Such statements are shown to be generalizable to the stochastic mirror-prox framework; (2) under strong pseudomonotonicity, we show that the mean-squared error in the solution iterates produced by the extragradient SA scheme converges at the optimal rate of \({{\mathcal{O}}}\left( \frac{1}{{K}}\right)\), statements that were hitherto unavailable in this regime. Notably, we optimize the initial steplength by obtaining an \(\epsilon \)-infimum of a discontinuous nonconvex function. Similar statements are derived for mirror-prox generalizations and can accommodate monotone SVIs under a weak-sharpness requirement. Finally, both the asymptotics and the empirical rates of the schemes are studied on a set of variational problems where it is seen that the theoretically specified initial steplength leads to significant performance benefits.

MSC:

90C33 Complementarity and equilibrium problems and variational inequalities (finite dimensions) (aspects of mathematical programming)
90C15 Stochastic programming
90C59 Approximation methods and heuristics in mathematical programming
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] Facchinei, F., Pang, J.-S.: Finite Dimensional Variational Inequalities and Complementarity Problems, vol. 1, 2. Springer, New York (2003) · Zbl 1062.90001
[2] Konnov, I.V.: Equilibrium Models and Variational Inequalities. Elsevier, Amsterdam (2007) · Zbl 1140.91056
[3] Brighi, L.; John, R., Characterizations of pseudomonotone maps and economic equilibrium, J. Stat. Manag. Syst., 5, 253-273 (2002) · Zbl 1079.91547
[4] Kihlstrom, R.; Mas-Colell, A.; Sonnenschein, H., The demand theory of the weak axiom of revealed preference, Econometrica, 44, 971-978 (1976) · Zbl 0331.90004
[5] Elizarov, AM, Maximizing the lift-drag ratio of wing airfoils with a turbulent boundary layer: exact solutions and approximations, Dokl. Phys., 53, 221-227 (2008) · Zbl 1255.76039
[6] Rousseau, A., Sharer, P., Pagerit, S., Das, S.: Trade-off between fuel economy and cost for advanced vehicle configurations. In: Proceedings of the 20th International Electric Vehicle Symposium, Monaco (2005)
[7] Duensing, GR; Brooker, HR; Fitzsimmons, JR, Maximizing signal-to-noise ratio in the presence of coil coupling, J. Magn. Reson. Ser. B, 111, 230-235 (1996)
[8] Shadwick, W.; Keating, C., A universal performance measure, J. Perform. Meas., 6, 59-84 (2002)
[9] Hossein, K., Thomas, S., Raj, G.: Omega as a Performance Measure. Preliminary Report, Duke University (2003)
[10] Chandra, S., Strong pseudo-convex programming, Indian J. Pure Appl. Math., 3, 278-282 (1972) · Zbl 0242.90048
[11] Hobbs, BF, Mill pricing versus spatial price discrimination under Bertrand and Cournot spatial competition, J. Ind. Econ., 35, 173-191 (1986)
[12] Choi, SC; Desarbo, WS; Harker, PT, Product positioning under price competition, Manag. Sci., 36, 175-199 (1990) · Zbl 0703.90054
[13] Garrow, LA; Koppelman, FS, Multinomial and nested logit models of airline passengers’ no-show and standby behaviour, J. Revenue Pricing Manag., 3, 237-253 (2004)
[14] Newman, JP, Normalization of network generalized extreme value models, Transp. Res. Part B Methodol., 42, 958-969 (2008)
[15] Cliquet, G., Implementing a subjective MCI model: an application to the furniture market, Eur. J. Oper. Res., 84, 279-291 (1995) · Zbl 0927.90081
[16] Nakanishi, M.; Cooper, LG, Parameter estimation for a multiplicative competitive interaction model: least squares approach, J. Market. Res., 11, 303-311 (1974)
[17] Gallego, G.; Hu, M., Dynamic pricing of perishable assets under competition, Manag. Sci., 60, 1241-1259 (2014)
[18] Ewerhart, C., Cournot games with biconcave demand, Games Econ. Behav., 85, 37-47 (2014) · Zbl 1290.91115
[19] Shapiro, A., Dentcheva, D., Ruszczynski, A.: Lectures on Stochastic Programming: Modeling and Theory. The Society for Industrial and Applied Mathematics and the Mathematical Programming Society, Philadelphia (2009) · Zbl 1183.90005
[20] Xu, H., Sample average approximation methods for a class of stochastic variational inequality problems, Asia-Pac. J. Oper. Res., 27, 103-119 (2010) · Zbl 1186.90083
[21] Lu, S.; Budhiraja, A., Confidence regions for stochastic variational inequalities, Math. Oper. Res., 38, 545-568 (2013) · Zbl 1291.90262
[22] Lu, S., Symmetric confidence regions and confidence intervals for normal map formulations of stochastic variational inequalities, SIAM J. Optim., 24, 1458-1484 (2014) · Zbl 1304.49022
[23] Robbins, H.; Monro, S., A stochastic approximation method, Ann. Math. Stat., 22, 400-407 (1951) · Zbl 0054.05901
[24] Kushner, H.J., Yin, G.G.: Stochastic Approximation and Recursive Algorithms and Applications. Springer, New York (2003) · Zbl 1026.62084
[25] Borkar, V.S.: Stochastic Approximation: A Dynamical Systems Viewpoint. Cambridge University Press, Cambridge (2008) · Zbl 1181.62119
[26] Spall, J.C.: Introduction to Stochastic Search and Optimization: Estimation, Simulation, and Control. Wiley Series in Discrete Mathematics and Optimization. Wiley, New York (2005) · Zbl 1088.90002
[27] Nemirovski, A.S., Judin, D.B.: On Cezari’s convergence of the steepest descent method for approximating saddle point of convex-concave functions. In: Soviet Mathematics-Doklady, vol. 19 (1978) · Zbl 0413.90061
[28] Ruppert, D.: Efficient Estimations from a Slowly Convergent Robbins-Monro Process. Cornell University Technical Report, Operations Research and Industrial Engineering (1988)
[29] Polyak, BT, New stochastic approximation type procedures, Autom. Telem., 7, 98-107 (1990)
[30] Polyak, BT; Juditsky, A., Acceleration of stochastic approximation by averaging, SIAM J. Control Optim., 30, 838-855 (1992) · Zbl 0762.62022
[31] Kushner, HJ; Yang, J., Stochastic approximation with averaging of the iterates: optimal asymptotic rate of convergence for general processes, SIAM J. Control Optim., 31, 1045-1062 (1993) · Zbl 0788.62078
[32] Kushner, HJ; Yang, J., Analysis of adaptive step-size SA algorithms for parameter tracking, IEEE Trans. Autom. Control, 40, 1403-1410 (1995) · Zbl 0839.93071
[33] Nemirovski, A.S., Yudin, D.B.: Problem Complexity and Method Efficiency in Optimization. Wiley-Interscience, New York, Translated by E. R. Dawson (1983) · Zbl 0501.90062
[34] Nemirovski, A.; Juditsky, A.; Lan, G.; Shapiro, A., Robust stochastic approximation approach to stochastic programming, SIAM J. Optim., 19, 1574-1609 (2009) · Zbl 1189.90109
[35] Ghadimi, S.; Lan, G., Optimal stochastic approximation algorithms for strongly convex stochastic composite optimization, I: a generic algorithmic framework, SIAM J. Optim., 22, 1469-1492 (2012) · Zbl 1301.62077
[36] Ghadimi, S.; Lan, G., Optimal stochastic approximation algorithms for strongly convex stochastic composite optimization, II: shrinking procedures and optimal algorithms, SIAM J. Optim., 23, 2061-2089 (2013) · Zbl 1293.62167
[37] Bertsekas, D.; Tsitsiklis, J., Gradient convergence in gradient methods with errors, SIAM J. Optim., 10, 627-642 (2000) · Zbl 1049.90130
[38] Ghadimi, S.; Lan, G., Stochastic first- and zeroth-order methods for nonconvex stochastic programming, SIAM J. Optim., 23, 2341-2368 (2013) · Zbl 1295.90026
[39] Jiang, H.; Xu, H., Stochastic approximation approaches to the stochastic variational inequality problem, IEEE Trans. Autom. Control, 53, 1462-1475 (2008) · Zbl 1367.90072
[40] Koshal, J.; Nedić, A.; Shanbhag, UV, Regularized iterative stochastic approximation methods for stochastic variational inequality problems, IEEE Trans. Autom. Control, 58, 594-609 (2013) · Zbl 1369.49012
[41] Yousefian, F., Nedić, A., Shanbhag, U.V.: A regularized smoothing stochastic approximation (RSSA) algorithm for stochastic variational inequality problems. In: Proceedings of the Winter Simulation Conference (WSC), pp. 933-944 (2013)
[42] Juditsky, A.; Nemirovski, A.; Tauvel, C., Solving variational inequalities with stochastic mirror-prox algorithm, Stoch. Syst., 1, 17-58 (2011) · Zbl 1291.49006
[43] Yousefian, F., Nedić, A., Shanbhag, U.V.: Optimal robust smoothing extragradient algorithms for stochastic variational inequality problems. In 53rd IEEE Conference on Decision and Control, pp. 5831-5836 (2014)
[44] Chen, Y.; Lan, G.; Ouyang, Y., Accelerated schemes for a class of variational inequalities, Math. Program., 165, 113-149 (2017) · Zbl 1386.90102
[45] Kannan, A., Shanbhag, U.V.: The pseudomonotone stochastic variational inequality problem: analytical statements and stochastic extragradient schemes. In: American Control Conference, ACC 2014, Portland, OR, USA, June 4-6, 2014, pp. 2930-2935. IEEE (2014)
[46] Iusem, AN; Jofré, A.; Oliveira, RI; Thompson, P., Extragradient method with variance reduction for stochastic variational inequalities, SIAM J. Optim., 27, 686-724 (2017) · Zbl 1365.65179
[47] Yousefian, F.; Nedić, A.; Shanbhag, UV, On stochastic mirror-prox algorithms for stochastic Cartesian variational inequalities: randomized block coordinate and optimal averaging schemes, Set-Valued Var. Anal., 26, 789-819 (2018) · Zbl 07002699
[48] Yousefian, F.; Nedić, A.; Shanbhag, UV, Self-tuned stochastic approximation schemes for non-Lipschitzian stochastic multi-user optimization and Nash games, IEEE Trans. Autom. Control, 61, 1753-1766 (2016) · Zbl 1359.91010
[49] Iusem, AN; Jofré, A.; Thompson, P., Incremental constraint projection methods for monotone stochastic variational inequalities, Math. Oper. Res. (2018) · Zbl 1477.65101 · doi:10.1287/moor.2017.0922
[50] Yousefian, F.; Nedić, A.; Shanbhag, UV, On smoothing, regularization, and averaging in stochastic approximation methods for stochastic variational inequality problems, Math. Program., 165, 391-431 (2017) · Zbl 1457.90102
[51] Polyak, B.T.: Introduction to Optimization. Optimization Software Inc., New York (1987) · Zbl 0708.90083
[52] Nemirovski, A., Prox-method with rate of convergence \[{O}(1/{T})O\](1/T) for variational inequalities with Lipschitz continuous monotone operators and smooth convex-concave saddle point problems, SIAM J. Optim., 15, 229-251 (2005) · Zbl 1106.90059
[53] Dang, CD; Lan, G., On the convergence properties of non-Euclidean extragradient methods for variational inequalities with generalized monotone operators, Comput. Optim. Appl., 60, 277-310 (2015) · Zbl 1311.49020
[54] Dvurechensky, P., Gasnikov, A., Stonyakin, F., Titov, A.: Generalized Mirror Prox: Solving Variational Inequalities with Monotone Operator, Inexact Oracle, and Unknown Hölder Parameters. arxiv:1806.05140.pdf (2018) · Zbl 1492.65181
[55] Nesterov, Y.; Pardalos, P. (ed.); Hearn, D. (ed.), Introductory lectures on convex optimization: a basic course (2004), Dordrecht · Zbl 1086.90045
[56] Watson, LT, Solving the nonlinear complementarity problem by a homotopy method, SIAM J. Control Optim., 17, 36-46 (1979) · Zbl 0407.90083
[57] Kannan, A.; Shanbhag, UV, Distributed computation of equilibria in monotone Nash games via iterative regularization techniques, SIAM J. Optim., 22, 1177-1205 (2012) · Zbl 1281.90072
[58] Allaz, B.; Vila, JL, Cournot competition, forward markets and efficiency, J. Econ. Theory, 59, 1-16 (1993) · Zbl 0802.90031
[59] Facchinei, F.; Kanzow, C., Generalized Nash equilibrium problems, 4OR, 5, 173-210 (2007) · Zbl 1211.91162
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.