A Superlinearly Convergent Subgradient Method for Sharp Semismooth Problems

• 成果类型: Article
• 署名作者: Charisopoulos, Vasileios; Davis, Damek
• 署名单位: Cornell University
• 刊物名称: MATHEMATICS OF OPERATIONS RESEARCH
• ISSN/ISSBN: 0364-765X
• DOI: 10.1287/moor.2023.1390
• 发表日期: 2024
• 关键词: alternating projections; set; optimization; algorithm; rates

摘要

Subgradient methods comprise a fundamental class of nonsmooth optimization algorithms. Classical results show that certain subgradient methods converge sublinearly for general Lipschitz convex functions and converge linearly for convex functions that grow sharply away from solutions. Recent work has moreover extended these results to certain nonconvex problems. In this work, we seek to improve the complexity of these algorithms by asking the following question. Is it possible to design a superlinearly convergent subgradient method? We provide a positive answer to this question for a broad class of sharp semi smooth functions.