A proximal alternating linearization method for minimizing the sum of two convex functions

In this paper, we develop a novel alternating linearization method for solving convex minimization whose objective function is the sum of two separable functions. The motivation of the paper is to extend the recent work Goldfarb et al. (2013) to cope with more generic convex minimization. For the proposed method, both the separable objective functions and the auxiliary penalty terms are linearized. Provided that the separable objective functions belong to C 1,1(ℝ n ), we prove the O(1/∈) arithmetical complexity of the new method. Some preliminary numerical simulations involving image processing and compressive sensing are conducted.