Dual extrapolation and its applications to solving variational inequalities and related problems

DOI10.1007/s10107-006-0034-zzbMath1167.90014OpenAlexW2081316950MaRDI QIDQ868471

Yu. E. Nesterov

Publication date: 5 March 2007

Published in: Mathematical Programming. Series A. Series B (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s10107-006-0034-z

zbMATH Keywords

variational inequalitiesconvex optimizationmonotone operatorscomplexity theorynon-smooth optimizationoptimal methods

Mathematics Subject Classification ID

Convex programming (90C25) Minimax problems in mathematical programming (90C47) Variational inequalities (49J40)

Related Items

Accelerated Bregman Primal-Dual Methods Applied to Optimal Transport and Wasserstein Barycenter Problems, An adaptive accelerated first-order method for convex optimization, An adaptive analog of Nesterov's method for variational inequalities with a strongly monotone operator, New Primal-Dual Algorithms for a Class of Nonsmooth and Nonlinear Convex-Concave Minimax Problems, A Hybrid Proximal Extragradient Self-Concordant Primal Barrier Method for Monotone Variational Inequalities, New First-Order Algorithms for Stochastic Variational Inequalities, Accelerating Block-Decomposition First-Order Methods for Solving Composite Saddle-Point and Two-Player Nash Equilibrium Problems, A Novel Algorithm with Self-adaptive Technique for Solving Variational Inequalities in Banach Spaces, Cubic regularized Newton method for the saddle point models: a global and local convergence analysis, On lower iteration complexity bounds for the convex concave saddle point problems, Proportional-integral projected gradient method for conic optimization, Generalized mirror prox algorithm for monotone variational inequalities: Universality and inexact oracle, On the iteration complexity of some projection methods for monotone linear variational inequalities, Physics-informed distribution transformers via molecular dynamics and deep neural networks, Sparse non Gaussian component analysis by semidefinite programming, Two Steps at a Time---Taking GAN Training in Stride with Tseng's Method, A new method for solving monotone generalized variational inequalities, Two fast variance-reduced proximal gradient algorithms for SMVIPs -- stochastic mixed variational inequality problems with suitable applications to stochastic network games and traffic assignment problems, Adaptive two-stage Bregman method for variational inequalities, Potential Function-Based Framework for Minimizing Gradients in Convex and Min-Max Optimization, Accelerated schemes for a class of variational inequalities, Simple and Optimal Methods for Stochastic Variational Inequalities, I: Operator Extrapolation, Unifying mirror descent and dual averaging, A unified analysis of variational inequality methods: variance reduction, sampling, quantization, and coordinate descent, Cyclic Coordinate Dual Averaging with Extrapolation, A unified single-loop alternating gradient projection algorithm for nonconvex-concave and convex-nonconcave minimax problems, Accelerated variance-reduced methods for saddle-point problems, Linear Convergence of Proximal Gradient Algorithm with Extrapolation for a Class of Nonconvex Nonsmooth Minimization Problems, Optimal algorithms for differentially private stochastic monotone variational inequalities and saddle-point problems, Optimal analysis of method with batching for monotone stochastic finite-sum variational inequalities, Unnamed Item, No-regret dynamics in the Fenchel game: a unified framework for algorithmic convex optimization, Variable sample-size operator extrapolation algorithm for stochastic mixed variational inequalities, Bregman-Golden ratio algorithms for variational inequalities, Smooth monotone stochastic variational inequalities and saddle point problems: a survey, Primal-Dual First-Order Methods for Affinely Constrained Multi-block Saddle Point Problems, First-order methods for convex optimization, A Smooth Primal-Dual Optimization Framework for Nonsmooth Composite Convex Minimization, Convergence of the modified extragradient method for variational inequalities with non-Lipschitz operators, Barrier subgradient method, Iterative methods for solving monotone equilibrium problems via dual gap functions, Iteration-complexity of first-order penalty methods for convex programming, Golden ratio algorithms for variational inequalities, Learning in games with continuous action sets and unknown payoff functions, Complexity of first-order inexact Lagrangian and penalty methods for conic convex programming, Dual extragradient algorithms extended to equilibrium problems, The Approximate Duality Gap Technique: A Unified Theory of First-Order Methods, Dual subgradient algorithms for large-scale nonsmooth learning problems, Forward-reflected-backward method with variance reduction, Primal-dual methods for solving infinite-dimensional games, A proximal difference-of-convex algorithm with extrapolation, A version of the mirror descent method to solve variational inequalities, On the convergence of the iterates of proximal gradient algorithm with extrapolation for convex nonsmooth minimization problems, Self-concordant barriers for convex approximations of structured convex sets, Metastability of the proximal point algorithm with multi-parameters, Variance-based single-call proximal extragradient algorithms for stochastic mixed variational inequalities, Self-concordant inclusions: a unified framework for path-following generalized Newton-type algorithms, A Subgradient Method for Free Material Design, Convergence of two-stage method with Bregman divergence for solving variational inequalities, Bregman extragradient method with monotone rule of step adjustment, Solving variational inequalities with Stochastic Mirror-Prox algorithm, Stochastic relaxed inertial forward-backward-forward splitting for monotone inclusions in Hilbert spaces, An adaptive proximal method for variational inequalities, Regularized HPE-Type Methods for Solving Monotone Inclusions with Improved Pointwise Iteration-Complexity Bounds, On the convergence properties of non-Euclidean extragradient methods for variational inequalities with generalized monotone operators, Convergence of the method of extrapolation from the past for variational inequalities in uniformly convex Banach spaces, Learning in nonatomic games. I: Finite action spaces and population games, A semi-definite programming approach for robust tracking

Cites Work

• Smooth minimization of non-smooth functions
• Information-based complexity of linear operator equations
• Introductory lectures on convex optimization. A basic course.
• Prox-Method with Rate of Convergence O(1/t) for Variational Inequalities with Lipschitz Continuous Monotone Operators and Smooth Convex-Concave Saddle Point Problems
• Homogeneous Analytic Center Cutting Plane Methods for Convex Problems and Variational Inequalities
• Excessive Gap Technique in Nonsmooth Convex Minimization
• Unnamed Item