<p>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.</p>

错误:搜索内容不能为空,请输入英文关键词
错误:关键词超出字数限制,请精简
高级检索

Lipschitz minimization and the Goldstein modulus

  • Siyu Kong,
  • A. S. Lewis

摘要

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.