A Superlinearly Convergent Subgradient Method for Sharp Semismooth Problems
A Superlinearly Convergent Subgradient Method for Sharp Semismooth Problems
复制标题
DOI：
10.1287/moor.2023.1390
复制
发表时间：
2022-01
影响因子：
1.7
通讯作者：
Vasileios Charisopoulos;Damek Davis
中科院分区：
文献类型：
--
作者：
Vasileios Charisopoulos;Damek Davis
次梯度法是一类基本的非光滑优化算法。经典的结果表明，某些次梯度方法对一般的Lipschitz凸函数是次线性收敛的，而对远离解急剧增长的凸函数是线性收敛的。最近的工作，而且这些结果扩展到某些非凸问题。在这项工作中，我们试图通过提出以下问题来提高这些算法的复杂性。是否有可能设计一个超线性收敛的次梯度法？我们提供了一个肯定的答案，这个问题的一个广泛的一类尖锐的半光滑函数。资金来源：D.戴维斯是由数学科学司[格兰特2047637]和阿尔弗雷德P斯隆基金会。
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 semismooth functions. Funding: The research of D. Davis was supported by the Division of Mathematical Sciences [Grant 2047637] and the Alfred P. Sloan Foundation.