On the convergence properties of non-Euclidean extragradient methods for variational inequalities with generalized monotone operators

详细信息    查看全文

• 作者：Cong D. Dang ; Guanghui Lan
• 关键词：Complexity ; Monotone variational inequality ; Pseudo ; monotone variational inequality ; Extragradient methods ; Non ; Euclidean methods ; Prox ; mapping
• 刊名：Computational Optimization and Applications
• 出版年：2015
• 出版时间：March 2015
• 年：2015
• 卷：60
• 期：2
• 页码：277-310
• 全文大小：337 KB
• 参考文献：1. Auslender, A, Teboulle, M (2005) Interior projection-like methods for monotone variational inequalities. Math. Progr. 104: pp. 39-68 CrossRef
  2. Auslender, A, Teboulle, M (2006) Interior gradient and proximal methods for convex and conic optimization. SIAM J. Optim. 16: pp. 697-725 CrossRef
  3. Bauschke, HH, Borwein, JM, Combettes, PL (2003) Bregman monotone optimization algorithms. SIAM J. Control Optim. 42: pp. 596-636 CrossRef
  4. Ben-Tal, A, Nemirovski, AS (2000) Lectures on Modern Convex Optimization: Analysis, Algorithms, Engineering Applications. SIAM, Philadelphia
  5. Bertsekas, D (1999) Nonlinear Programming. Athena Scientific, New York
  6. Bregman, LM (1967) The relaxation method of finding the common point convex sets and its application to the solution of problems in convex programming. USSR Comput. Math. Phys. 7: pp. 200-217 CrossRef
  7. Facchinei, F, Pang, J (2003) Finite-Dimensional Variational Inequalities and Complementarity Problems. Volumes I and II. Comprehensive Study in Mathematics. Springer-Verlag, New York
  8. Gafni, EM, Bertsekas, DP (1984) Two-metric projection methods for constrained optimization. SIAM J. Control Optim. 22: pp. 936-964 CrossRef
  9. Harker, PT, Pang, J (1990) A damped-Newton method for the linear complementarity problem. Computational solution of nonlinear systems of equations (Fort Collins, CO, 1988). American Mathematical Society, Providence
  10. Harker, PT, Pang, JS (1990) Finite-dimensional variational inequality and complementarity problems: a survey of theory, algorithms, and applications. Math. Progr. B 48: pp. 161-220 CrossRef
  11. Hearn, DW (1982) The gap function of a convex program. Oper. Res. Lett. 1: pp. 67-71 CrossRef
  12. Nedich, A, Koshal, J, Shanbhag, UV (2011) Multiuser optimization: distributed algorithms and error analysis. SIAM J. Optim. 21: pp. 1168-1199 CrossRef
  13. Kiwiel, KC (1997) Proximal minimization methods with generalized bregman functions. SIAM J. Controal Optim. 35: pp. 1142-1168 CrossRef
  14. Korpelevich, G (1976) The extragradient method for finding saddle points and other problems. Eknomika i Matematicheskie Metody 12: pp. 747-756
  15. Lan, G (2012) An optimal method for stochastic composite optimization. Math. Progr. 133: pp. 365-397 CrossRef
  16. Lan, G, Lu, Z, Monteiro, RDC (2011) Primal-dual first-order methods with $${\cal O}(1/\epsilon )$$ O ( 1 / ? ) iteration-complexity for cone programming. Math. Progr. 126: pp. 1-29 CrossRef
  17. Lan, G., Monteiro, R.D.C.: Iteration-complexity of first-order penalty methods for convex programming. Manuscript, School of Industrial and Systems Engineering, Georgia Institute of Technology, Atlanta, GA, USA, June 2008
  18. Lan, G., Monteiro, R.D.C.: Iteration-complexity of first-order augmented lagrangian methods for convex programming. Technical report, Department of Industrial and Systems Engineering, University of Florida, Gainesville, FL, USA, September 2013. Mathematical Programming (Under second-round review)
  19. Monteiro, R.D.C., Svaiter, B.F.: On the complexity of the hybrid proximal extragradient method for the iterates and the ergodic mean. Manuscript, School of ISyE, Georgia Tech, Atlanta, GA, USA, March 2009
  20. Monteiro, R.D.C., Svaiter, B.F.: Complexity of variants of tsengs modified f-b splitting and korpelevich’s methods for hemi-variational inequalities with applications to saddle-point and convex optimization problems. Manuscript, School of ISyE, Georgia Tech, Atlanta, GA, USA, June 2010
  21. Nemirovski, AS (2005) Prox-method with rate of convergence $$o(1/t)$$ o ( 1 / t ) for variational i
• 刊物类别：Mathematics and Statistics
• 刊物主题：Mathematics
  Optimization
  Operations Research and Mathematical Programming
  Operation Research and Decision Theory
  Statistics
  Convex and Discrete Geometry
  
• 出版者：Springer Netherlands
• ISSN：1573-2894

文摘

In this paper, we study a class of generalized monotone variational inequality (GMVI) problems whose operators are not necessarily monotone (e.g., pseudo-monotone). We present non-Euclidean extragradient (N-EG) methods for computing approximate strong solutions of these problems, and demonstrate how their iteration complexities depend on the global Lipschitz or H?lder continuity properties for their operators and the smoothness properties for the distance generating function used in the N-EG algorithms. We also introduce a variant of this algorithm by incorporating a simple line-search procedure to deal with problems with more general continuous operators. Numerical studies are conducted to illustrate the significant advantages of the developed algorithms over the existing ones for solving large-scale GMVI problems.