An improved algorithm for the - minimization problem

• 成果类型: Article
• 署名作者: Ge, Dongdong; He, Rongchuan; He, Simai
• 署名单位: Shanghai University of Finance & Economics; City University of Hong Kong
• 刊物名称: MATHEMATICAL PROGRAMMING
• ISSN/ISSBN: 0025-5610
• DOI: 10.1007/s10107-016-1107-2
• 发表日期: 2017
• 页码: 131-158
• 关键词: sparse; complexity

摘要

In this paper we consider a class of non-Lipschitz and non-convex minimization problems which generalize the - minimization problem. We propose an iterative algorithm that decides the next iteration based on the local convexity/concavity/sparsity of its current position. We show that our algorithm finds an -KKT point within iterations from certain initial points. The same result is also applied to the problem with general linear constraints under mild conditions.