The augmented Lagrangian method (ALM) is a benchmark for solving the convex minimization problem with linear constraints. We consider the special case where the objective is in form of the sum of m functions without coupled variables. For solving this separable convex programming model, it is usually required to decompose the ALM subproblem at each … Read more
In this paper we analyze the randomized block-coordinate descent (RBCD) methods for minimizing the sum of a smooth convex function and a block-separable convex function. In particular, we extend Nesterov’s technique (SIOPT 2012) for analyzing the RBCD method for minimizing a smooth convex function over a block-separable closed convex set to the aforementioned more general … Read more
We propose a new first-order augmented Lagrangian algorithm ALCC for solving convex conic programs of the form min{rho(x)+gamma(x): Ax-b in K, x in chi}, where rho and gamma are closed convex functions, and gamma has a Lipschitz continuous gradient, A is mxn real matrix, K is a closed convex cone, and chi is a “simple” … Read more
In this paper we present a variant of random coordinate descent method for solving linearly constrained convex optimization problems with composite objective function. If the smooth part has Lipschitz continuous gradient, then the method terminates with an ϵ-optimal solution in O(N2/ϵ) iterations, where N is the number of blocks. For the class of problems with … Read more
Inthispaper, weproposetwonewmultiple-setssplitfeasibilityproblem(MSFP)models, where the MSFP requires to find a point closest to the intersection of a family of closed convex sets in one space, such that its image under a linear transformation will be closest to the intersection of another family of closed convex sets in the image space. This problem arises in image restoration, … Read more
Recently, in [17] we have showed the first possibility of combining the Douglas-Rachford alternating direction method of multipliers (ADMM) with a Gaussian back substitution procedure for solving a convex minimization model with a general separable structure. This paper is a further study on theoretical aspects of this theme. We first derive a general algorithmic framework … Read more
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. ArticleDownload View PDF
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. ArticleDownload View PDF
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