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 (68)

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

This page was built for publication: Dual extrapolation and its applications to solving variational inequalities and related problems