Solving Variational Inequalities with Stochastic Mirror-Prox Algorithm

References

• Azuma, K. (1967). Weighted sums of certain dependent random variables. Tôhoku Math. J. 19, 357–367. MR0221571Google Scholar
• Ben-Tal, A., Nemirovski, A. (2005). Non-Euclidean restricted memory level method for large-scale convex optimization. Math. Progr. 102, 407–456. MR2136222Google Scholar
• Grigoriadis, M.D., Khachiyan, L.G. (1995). A sublinear-time randomized approximation algorithm for matrix games. OR Letters 18, 53–58. MR1361861Google Scholar
• Juditsky, A., Lan, G., Nemirovski, A., Shapiro, A. (2009) Stochastic Approximation approach to Stochastic Programming. SIAM J. Optim. 19, 1574–1609.Google Scholar
• Juditsky, A., Nemirovski, A. (2008). Large deviations of vector-valued martingales in 2-smooth normed spaces E-print: http://www.optimization-online.org/DB_HTML/2008/04/1947.htmlGoogle Scholar
• Juditsky, A., Kilinç Karzan, F., Nemirovski, A. (2010). L1 minimization via randomized first order algorithms. Submitted to Mathematical Programming E-print: http://www.optimization-online.org/DB_FILE/2010/05/2618.pdfGoogle Scholar
• Korpelevich, G. (1983). Extrapolation gradient methods and relation to Modified Lagrangeans” Ekonomika i Matematicheskie Metody 19, 694–703 (in Russian; English translation in Matekon). MR0711446Google Scholar
• Nemirovski, A., Yudin, D. (1983). Problem complexity and method efficiency in Optimization, J. Wiley & Sons. MR0702836Google Scholar
• Nemirovski, A. (2004). 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, 229–251. MR2112984Google Scholar
• Lu, Z., Nemirovski, A., Monteiro, R. (2007). Large-scale Semidefinite Programming via saddle point Mirror-Prox algorithm. Math. Progr. 109, 211–237. MR2295141Google Scholar
• Nemirovski, A., Onn, S., Rothblum, U. (2010). Accuracy certificates for computational problems with convex structure. Math. of Oper. Res. 35:1, 52–78. MR2676756Link, Google Scholar
• Nesterov, Yu. (2005). Smooth minimization of non-smooth functions. Math. Progr. 103, 127–152. MR2166537Google Scholar
• Nesterov, Yu. (2005). Excessive gap technique in nonsmooth convex minimization. SIAM J. Optim. 16, 235–249. MR2177777Google Scholar
• Nesterov, Yu. (2007). Dual extrapolation and its applications to solving variational inequalities and related problems. Math. Progr. 109, 319–344. MR2295146Google Scholar
• Rubinfeld, R. (2006). Sublinear time algorithms. In: Marta Sanz-Solé, Javier Soria, Juan Luis Varona, Joan Verdera, Eds. International Congress of Mathematicians, Madrid 2006, Vol. III, 1095–11110. European Mathematical Society Publishing House. MR2275720Google Scholar