Sensitivity Analysis of the Proximal-Based Parallel Decomposition Methods

The proximal-based parallel decomposition methods were recently proposed to solve structured convex optimization problems. These algorithms are eligible for parallel computation and can be used efficiently for solving large-scale separable problems. In this paper, compared with the previous theoretical results, we show that the range of the involved parameters can be enlarged while the convergence can be still established. Preliminary numerical tests on stable principal component pursuit problem testify to the advantages of the enlargement. 1. Introduction Consider the constrained convex optimization problems with separable objective functions in the following form: where , , , , and , are two nonempty, closed, and convex sets and , are convex functions. Problem of this type arises from a number of fields such as signal processing, compressed sensing, machine learning, and semidefinite programming (see, e.g., [1–7] and references cited therein). To solve (1), the classical alternating direction method generates the new iterate via the following scheme: where is the Lagrange multiplier associated with the linear constraint and is a penalty parameter for the violation of the linear constraint. At each iteration, ADM essentially splits the subproblem of the augmented Lagrangian method into two subproblems in Gauss-Seidel fashion. The subproblems can be solved in consecutive order, which makes ADM possible to exploit the individual structure of and . The decomposed subproblems in (2) are often easy when and in (1) are both identity matrices and the resolvent operators of and have closed-form solutions or can be efficiently solved up to a high precision. Here, the resolvent operator of a function (say, ) is defined by where and . However, in some cases, both and are not identity matrices; the two subproblems in ADM (2) are difficult to solve because the evaluation of the following minimization style could be costly, where is a given nonidentity matrix, for example, or . For the purpose of parallel and easy computing, the first parallel decomposition method [8] (abbreviated as FPDM) generates the new iterative as follows: where the parameters , are required to satisfy and . Here, denotes the largest eigenvalue of matrix . It is easy to verify that the proximal-based decomposition method proposed in [9] is a special case of the FPDM. When (4) is easy to evaluate for and , the second parallel decomposition method [8] (abbreviated as SPDM) can be used, which generates the new iterative as follows: where the parameters , are required to satisfy and . Note that