ergodic convergence – Optimization Online

An accelerated non-Euclidean hybrid proximal extragradient-type Algorithm for convex-concave saddle-point Problems

Published: 2015/09/18

Convex Optimization accelerated gradient method, bregman distances, complexity, convex optimization, ergodic convergence, hybrid proximal extragradient method, inexact proximal method, maximal monotone operator, saddle point problem

This paper describes an accelerated HPE-type method based on general Bregman distances for solving monotone saddle-point (SP) problems. The algorithm is a special instance of a non-Euclidean hybrid proximal extragradient framework introduced by Svaiter and Solodov [28] where the prox sub-inclusions are solved using an accelerated gradient method. It generalizes the accelerated HPE algorithm presented … Read more

An O(1/k) Convergence Rate for the Variable Stepsize Bregman Operator Splitting Algorithm

Published: 2015/04/23, Updated: 2015/09/30

William W. Hager

Maryam Yashtini

Hongchao Zhang

Nonsmooth Optimization bosvs, convex optimization, ergodic convergence, nonsmooth optimization, saddle point problem, variational inequality

An earlier paper proved the convergence of a variable stepsize Bregman operator splitting algorithm (BOSVS) for minimizing $\phi(Bu)+H(u)$ where $H$ and $\phi$ are convex functions, and $\phi$ is possibly nonsmooth. The algorithm was shown to be relatively efficient when applied to partially parallel magnetic resonance image reconstruction problems. In this paper, the convergence rate of … Read more

On the ergodic convergence rates of a first-order primal-dual algorithm

Published: 2014/09/09, Updated: 2014/11/09

Antonin Chambolle

Thomas Pock

Convex and Nonsmooth Optimization convergence rate, ergodic convergence, first-order methods, primal-dual algorithms, saddle point problem

We revisit the proofs of convergence for a first order primal-dual algorithm for convex optimization which we have studied a few years ago. In particular, we prove rates of convergence for a more general version, with simpler proofs and more complete results. Article Download View On the ergodic convergence rates of a first-order primal-dual algorithm

An Accelerated Hybrid Proximal Extragradient Method for Convex Optimization and its Implications to Second-Order Methods

Published: 2011/05/11, Updated: 2012/05/26

Renato D.C. Monteiro

Benar Fux Svaiter

Convex and Nonsmooth Optimization, Convex Optimization, Linear, Cone and Semidefinite Programming accelerated gradient, accelerated newton, complexity, convex optimization, ergodic convergence, extragradient, hybrid, maximal monotone operator, proximal point algorithm, variational inequality

This paper presents an accelerated variant of the hybrid proximal extragradient (HPE) method for convex optimization, referred to as the accelerated HPE (A-HPE) method. Iteration-complexity results are established for the A-HPE method, as well as a special version of it, where a large stepsize condition is imposed. Two specific implementations of the A-HPE method are … Read more