A coordinate gradient descent method for nonsmooth separable minimization

• 成果类型: Article
• 署名作者: Tseng, Paul; Yun, Sangwoon
• 署名单位: University of Washington; University of Washington Seattle
• 刊物名称: MATHEMATICAL PROGRAMMING
• ISSN/ISSBN: 0025-5610
• DOI: 10.1007/s10107-007-0170-0
• 发表日期: 2009
• 页码: 387-423
• 关键词: linear convergence; convex function; ascent methods; algorithm; regression; robust; SUM

摘要

We consider the problem of minimizing the sum of a smooth function and a separable convex function. This problem includes as special cases bound-constrained optimization and smooth optimization with l(1)-regularization. We propose a (block) coordinate gradient descent method for solving this class of nonsmooth separable problems. We establish global convergence and, under a local Lipschitzian error bound assumption, linear convergence for this method. The local Lipschitzian error bound holds under assumptions analogous to those for constrained smooth optimization, e.g., the convex function is polyhedral and the smooth function is (nonconvex) quadratic or is the composition of a strongly convex function with a linear mapping. We report numerical experience with solving the l(1)-regularization of unconstrained optimization problems from More et al. in ACM Trans. Math. Softw. 7, 17-41, 1981 and from the CUTEr set (Gould and Orban in ACM Trans. Math. Softw. 29, 373-394, 2003). Comparison with L-BFGS-B and MINOS, applied to a reformulation of the l(1)-regularized problem as a bound-constrained optimization problem, is also reported.