A dual method for minimizing a nonsmooth objective over one smooth inequality constraint

• 成果类型: Article
• 署名作者: Shefi, Ron; Teboulle, Marc
• 署名单位: Tel Aviv University
• 刊物名称: MATHEMATICAL PROGRAMMING
• ISSN/ISSBN: 0025-5610
• DOI: 10.1007/s10107-015-0952-8
• 发表日期: 2016
• 页码: 137-164
• 关键词: 1st-order method; minimization; algorithm

摘要

We consider the class of nondifferentiable convex problems which minimizes a nonsmooth convex objective over a single smooth constraint. Exploiting the smoothness of the feasible set and using duality, we introduce a simple first order algorithm proven to globally converge to an optimal solution with a efficiency estimate. The performance of the algorithm is demonstrated by solving large instances of the convex sparse recovery problem.