Bingsheng He Recently, a worst-case O(1/t) convergence rate was established for the Douglas-Rachford alternating direction method of multipliers in an ergodic sense. This note proposes a novel approach to derive the same convergence rate while in a non-ergodic sense. Article Download View On non-ergodic convergence rate of Douglas-Rachford alternating direction method of multipliers
This note provides a simple proof on a O(1/k) convergence rate for the Douglas-Rachford operator splitting method where $k$ denotes the iteration counter. Article Download View On convergence rate of the Douglas-Rachford operator splitting method
This paper takes a uniform look at the customized applications of proximal point algorithm (PPA) to two classes of problems: the linearly constrained convex minimization problem with a generic or separable objective function and a saddle-point problem. We model these two classes of problems uniformly by a mixed variational inequality, and show how PPA with … Read more
Recently, we have proposed to combine the alternating direction method (ADM) with a Gaussian back substitution procedure for solving the convex minimization model with linear constraints and a general separable objective function, i.e., the objective function is the sum of many functions without coupled variables. In this paper, we further study this topic and show … Read more
The old alternating direction method (ADM) has found many new applications recently, and its empirical efficiency has been well illustrated in various fields. However, the estimate of ADM’s convergence rate remains a theoretical challenge for a few decades. In this note, we provide a uniform proof to show the O(1/t) convergence rate for both the … Read more
The alternating direction method (ADM) is classical for solving a linearly constrained separable convex programming problem (primal problem), and it is well known that ADM is essentially the application of a concrete form of the proximal point algorithm (PPA) (more precisely, the Douglas-Rachford splitting method) to the corresponding dual problem. This paper shows that an … Read more
Recently, Nemirovski’s analysis indicates that the extragradient method has the $O(1/t)$ convergence rate for variational inequalities with Lipschitz continuous monotone operators. For the same problems, in the last decades, we have developed a class of Fej\’er monotone projection and contraction methods. Until now, only convergence results are available to these projection and contraction methods, though … Read more
We consider the linearly constrained separable convex programming whose objective function is separable into m individual convex functions without crossed variables. The alternating direction method (ADM) has been well studied in the literature for the special case m=2. But the convergence of extending ADM to the general case m>=3 is still open. In this paper, … Read more
The proximal point algorithm (PPA) is classical, and it is implicit in the sense that the resulting proximal subproblems may be as difficult as the original problem. In this paper, we show that with appropriate choices of proximal parameters, the application of PPA to the linearly constrained convex programming can result in easy proximal subproblems. … Read more
Recently, some attractive primal-dual algorithms have been proposed for solving a saddle-point problem, with particular applications in the area of total variation (TV) image restoration. This paper focuses on the convergence analysis of existing primal-dual algorithms and shows that the involved parameters of those primal-dual algorithms (including the step sizes) can be significantly enlarged if … Read more