Lipschitz minimization and the Goldstein modulus

• 成果类型: Article; Early Access
• 署名作者: Kong, Siyu; Lewis, A. S.
• 署名单位: Cornell University
• 刊物名称: MATHEMATICAL PROGRAMMING
• ISSN/ISSBN: 0025-5610
• DOI: 10.1007/s10107-025-02262-9
• 发表日期: 2025
• 关键词: Optimization; CONVERGENCE

摘要

Goldstein's 1977 idealized iteration for minimizing a Lipschitz objective fixes a distance - the step size - and relies on a certain approximate subgradient. That Goldstein subgradient is the shortest convex combination of objective subgradients at points within that distance of the current iterate. A recent implementable Goldstein-style algorithm allows a remarkable complexity analysis (Zhang et al. 2020), and a more sophisticated variant (Davis and Jiang, 2022) leverages typical objective geometry to force near-linear convergence. To explore such methods, we introduce a new modulus, based on Goldstein subgradients, that quantifies the extent to which points fail to be approximately stationary. We relate near-linear convergence of Goldstein-style methods to linear growth of this modulus at minimizers. We illustrate the idea computationally with a simple heuristic for Lipschitz minimization.