On the Complexity of the Hybrid Proximal Extragradient Method for the Iterates and the Ergodic Mean
From MaRDI portal
Publication:3083307
DOI10.1137/090753127zbMath1230.90200OpenAlexW1966953121WikidataQ105584124 ScholiaQ105584124MaRDI QIDQ3083307
Renato D. C. Monteiro, Benar Fux Svaiter
Publication date: 21 March 2011
Published in: SIAM Journal on Optimization (Search for Journal in Brave)
Full work available at URL: https://semanticscholar.org/paper/1ce262efacfbe6194deb84d024c10c03082875ba
complexityvariational inequalitymaximal monotone operatorcomplementarity problemsextragradientKorpelevich and Newton methods
Numerical mathematical programming methods (65K05) Convex programming (90C25) Abstract computational complexity for mathematical programming problems (90C60) Variational and other types of inequalities involving nonlinear operators (general) (47J20) Numerical optimization and variational techniques (65K10) Monotone operators and generalizations (47H05) Complementarity and equilibrium problems and variational inequalities (finite dimensions) (aspects of mathematical programming) (90C33)
Related Items
On inexact stochastic splitting methods for a class of nonconvex composite optimization problems with relative error, New Primal-Dual Algorithms for a Class of Nonsmooth and Nonlinear Convex-Concave Minimax Problems, Local convergence of tensor methods, A Hybrid Proximal Extragradient Self-Concordant Primal Barrier Method for Monotone Variational Inequalities, Accelerating Block-Decomposition First-Order Methods for Solving Composite Saddle-Point and Two-Player Nash Equilibrium Problems, A Hybrid Proximal-Extragradient Algorithm with Inertial Effects, Iteration-complexity analysis of a generalized alternating direction method of multipliers, Convergence rates with inexact non-expansive operators, Variants of the A-HPE and large-step A-HPE algorithms for strongly convex problems with applications to accelerated high-order tensor methods, An \(O(s^r)\)-resolution ODE framework for understanding discrete-time algorithms and applications to the linear convergence of minimax problems, An Accelerated HPE-Type Algorithm for a Class of Composite Convex-Concave Saddle-Point Problems, Generalized mirror prox algorithm for monotone variational inequalities: Universality and inexact oracle, On the complexity of the projective splitting and Spingarn's methods for the sum of two maximal monotone operators, Bregman Proximal Point Algorithm Revisited: A New Inexact Version and Its Inertial Variant, Accelerated schemes for a class of variational inequalities, First-Order Methods for Problems with $O$(1) Functional Constraints Can Have Almost the Same Convergence Rate as for Unconstrained Problems, Simple and Optimal Methods for Stochastic Variational Inequalities, I: Operator Extrapolation, A projective splitting method for monotone inclusions: iteration-complexity and application to composite optimization, On Korpelevich's extragradient algorithm, A first-order block-decomposition method for solving two-easy-block structured semidefinite programs, On inexact relative-error hybrid proximal extragradient, forward-backward and Tseng's modified forward-backward methods with inertial effects, On the complexity of a hybrid proximal extragradient projective method for solving monotone inclusion problems, A unified single-loop alternating gradient projection algorithm for nonconvex-concave and convex-nonconcave minimax problems, Riemannian Hamiltonian Methods for Min-Max Optimization on Manifolds, An inexact Spingarn's partial inverse method with applications to operator splitting and composite optimization, Stochastic projective splitting, Principled analyses and design of first-order methods with inexact proximal operators, A Smooth Primal-Dual Optimization Framework for Nonsmooth Composite Convex Minimization, From Halpern's fixed-point iterations to Nesterov's accelerated interpretations for root-finding problems, An optimal method for stochastic composite optimization, On the computation of equilibria in monotone and potential stochastic hierarchical games, Improved Pointwise Iteration-Complexity of A Regularized ADMM and of a Regularized Non-Euclidean HPE Framework, Iteration-complexity of first-order penalty methods for convex programming, On FISTA with a relative error rule, Implementation of a block-decomposition algorithm for solving large-scale conic semidefinite programming problems, Unnamed Item, An extragradient-type algorithm for variational inequality on Hadamard manifolds, Complexity of first-order inexact Lagrangian and penalty methods for conic convex programming, A class of Fejér convergent algorithms, approximate resolvents and the hybrid proximal-extragradient method, Tikhonov-like methods with inexact minimization for solving linear ill-posed problems, Convergence Rate of $\mathcal{O}(1/k)$ for Optimistic Gradient and Extragradient Methods in Smooth Convex-Concave Saddle Point Problems, A proximal-Newton method for unconstrained convex optimization in Hilbert spaces, On the convergence rate of the scaled proximal decomposition on the graph of a maximal monotone operator (SPDG) algorithm, Maximal monotone inclusions and Fitzpatrick functions, A closed-loop supply chain equilibrium model with random and price-sensitive demand and return, Weak versus strong convergence of a regularized Newton dynamic for maximal monotone operators, An extragradient-based alternating direction method for convex minimization, Extragradient Method with Variance Reduction for Stochastic Variational Inequalities, Dynamic stochastic approximation for multi-stage stochastic optimization, An efficient algorithm for nonconvex-linear minimax optimization problem and its application in solving weighted maximin dispersion problem, Complexity of the relaxed Peaceman-Rachford splitting method for the sum of two maximal strongly monotone operators, A \(\mathcal O(1/k^{3/2})\) hybrid proximal extragradient primal-dual interior point method for nonlinear monotone mixed complementarity problems, Pointwise and ergodic convergence rates of a variable metric proximal alternating direction method of multipliers, Over relaxed hybrid proximal extragradient algorithm and its application to several operator splitting methods, A Majorized ADMM with Indefinite Proximal Terms for Linearly Constrained Convex Composite Optimization, An $\mathcal O(1/{k})$ Convergence Rate for the Variable Stepsize Bregman Operator Splitting Algorithm, Interior hybrid proximal extragradient methods for the linear monotone complementarity problem, Communication-efficient algorithms for decentralized and stochastic optimization, Non-stationary First-Order Primal-Dual Algorithms with Faster Convergence Rates, On the iteration-complexity of a non-Euclidean hybrid proximal extragradient framework and of a proximal ADMM, Iteration-complexity of a Rockafellar's proximal method of multipliers for convex programming based on second-order approximations, A partially inexact proximal alternating direction method of multipliers and its iteration-complexity analysis, Complexity of a Quadratic Penalty Accelerated Inexact Proximal Point Method for Solving Linearly Constrained Nonconvex Composite Programs, Iteration complexity of an inexact Douglas-Rachford method and of a Douglas-Rachford-Tseng's F-B four-operator splitting method for solving monotone inclusions, Stochastic relaxed inertial forward-backward-forward splitting for monotone inclusions in Hilbert spaces, An Accelerated Linearized Alternating Direction Method of Multipliers, A control-theoretic perspective on optimal high-order optimization, Regularized HPE-Type Methods for Solving Monotone Inclusions with Improved Pointwise Iteration-Complexity Bounds, A Proximal Bundle Variant with Optimal Iteration-Complexity for a Large Range of Prox Stepsizes, A partially inexact ADMM with o(1/n) asymptotic convergence rate, 𝒪(1/n) complexity, and immediate relative error tolerance, Higher-Order Methods for Convex-Concave Min-Max Optimization and Monotone Variational Inequalities, A variant of the hybrid proximal extragradient method for solving strongly monotone inclusions and its complexity analysis
