Fast alternating linearization methods for minimizing the sum of two convex functions

• 成果类型: Article
• 署名作者: Goldfarb, Donald; Ma, Shiqian; Scheinberg, Katya
• 署名单位: Columbia University; University of Minnesota System; University of Minnesota Twin Cities; Lehigh University
• 刊物名称: MATHEMATICAL PROGRAMMING
• ISSN/ISSBN: 0025-5610
• DOI: 10.1007/s10107-012-0530-2
• 发表日期: 2013
• 页码: 349-382
• 关键词: splitting algorithm; inverse; DECOMPOSITION; selection; RECOVERY; MODEL

摘要

We present in this paper alternating linearization algorithms based on an alternating direction augmented Lagrangian approach for minimizing the sum of two convex functions. Our basic methods require at most iterations to obtain an -optimal solution, while our accelerated (i.e., fast) versions of them require at most iterations, with little change in the computational effort required at each iteration. For both types of methods, we present one algorithm that requires both functions to be smooth with Lipschitz continuous gradients and one algorithm that needs only one of the functions to be so. Algorithms in this paper are Gauss-Seidel type methods, in contrast to the ones proposed by Goldfarb and Ma in (Fast multiple splitting algorithms for convex optimization, Columbia University, 2009) where the algorithms are Jacobi type methods. Numerical results are reported to support our theoretical conclusions and demonstrate the practical potential of our algorithms.