A coordinate descent homotopy method for linearly constrained nonsmooth convex minimization. (3rd March 2016)

• Record Type: Journal Article
• Authors: Jung, Y.M.; Yun, S.
• Is Part Of: Optimization methods and software. Volume 31:Number 2(2016)
• Page Start: 342
• Page End: 358
• Publication Date: 2016-03-03
• Subjects: homotopy method -- coordinate descent method -- linearly constrained nonsmooth convex minimization; 49M27 -- 65K05 -- 90C06 -- 90C25 -- 90C30; Mathematical optimization -- Periodicals; Algorithms -- Periodicals; 519.7
• DOI: 10.1080/10556788.2015.1088851
• Languages: English
• ISSNs: 1055-6788

Abstract

Abstract : A problem in optimization, with a wide range of applications, entails finding a solution of a linear equation with various minimization properties. Such applications include compressed sensing, which requires an efficient method to find a minimal norm solution. We propose a coordinate descent homotopy method to solve the linearly constrained convex minimization problem where P is proper, convex and lower semicontinuous. A well-known special case is the basis pursuit problem . The greedy-type coordinate descent method is applied to solve the regularized linear least squares problem, which arises as a sequence of subproblems for the proposed method, and we show global linear convergence. We report numerical results for solving large-scale basis pursuit problem. Comparison with Bregman iterative algorithm [W. Yin, S. Osher, D. Goldfarb, and J. Darbon, Bregman iterative algorithms for -minimization with applications to compressed sensing, SIAM J. Image Sci. 1 (2008), pp. 143–168] and linearized Bregman iterative algorithm [J.-F. Cai, S. Osher, and Z. Shen, Linearized Bregman iterations for compressed sensing, Math. Comput. 78 (2009), pp. 1515–1536] suggests that the proposed method can be used as an efficient method for minimization problem.