EUVIMEDEUVIMED entdecken
Crossref

The Cost of Nonconvexity in Deterministic Nonsmooth Optimization

Siyu Kong, A. S. Lewis

Mathematics of Operations Research · 2024-11 · 49 (4) · 2385-2401

DOI: 10.1287/moor.2022.0289 ↗

Kurz gefasst

Fachartikel in der Zeitschrift Mathematics of Operations Research, 2024-11. Verfasst von Siyu Kong und 1 weiteren Autor:innen. Die Arbeit wurde bisher 9-mal zitiert (Crossref) und nennt 15 Literaturangaben.

AbstractBibliografische AngabenZitierenVerwandte Studien

Abstract (Originalsprache)

We study the impact of nonconvexity on the complexity of nonsmooth optimization, emphasizing objectives such as piecewise linear functions, which may not be weakly convex. We focus on a dimension-independent analysis, slightly modifying a 2020 black-box algorithm of Zhang-Lin-Jegelka-Sra-Jadbabaie that approximates an ϵ-stationary point of any directionally differentiable Lipschitz objective using [Formula: see text] calls to a specialized subgradient oracle and a randomized line search. Seeking by contrast a deterministic method, we present a simple black-box version that achieves [Formula: see text] for any difference-of-convex objective and [Formula: see text] for the weakly convex case. Our complexity bound depends on a natural nonconvexity modulus that is related, intriguingly, to the negative part of directional second derivatives of the objective, understood in the distributional sense. Funding: This work was supported by the National Science Foundation [Grant DMS-2006990].

Zitieren

APA

Kong, S., & Lewis, A. S. (2024). The Cost of Nonconvexity in Deterministic Nonsmooth Optimization. Mathematics of Operations Research, 49(4), 2385-2401. https://doi.org/10.1287/moor.2022.0289

Vancouver

Kong S, Lewis AS. The Cost of Nonconvexity in Deterministic Nonsmooth Optimization. Mathematics of Operations Research. 2024;49(4):2385-2401. doi:10.1287/moor.2022.0289

BibTeX
@article{Kong2024,
  author = {Kong, Siyu and Lewis, A. S.},
  title = {The Cost of Nonconvexity in Deterministic Nonsmooth Optimization},
  journal = {Mathematics of Operations Research},
  year = {2024},
  volume = {49},
  number = {4},
  pages = {2385--2401},
  doi = {10.1287/moor.2022.0289}
}
Kostenlos starten →