Goldstein Stationarity in Lipschitz Constrained Optimization
Fuente:
arXiv
Saved in:
| Main Authors: | , |
|---|---|
| Format: | Preprint |
| Published: |
2023
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866909287210549248 |
|---|---|
| author | Grimmer, Benjamin Jia, Zhichao |
| author_facet | Grimmer, Benjamin Jia, Zhichao |
| contents | We prove the first convergence guarantees for a subgradient method minimizing a generic Lipschitz function over generic Lipschitz inequality constraints. No smoothness or convexity (or weak convexity) assumptions are made. Instead, we utilize a sequence of recent advances in Lipschitz unconstrained minimization, which showed convergence rates of $O(1/δε^3)$ towards reaching a "Goldstein" stationary point, that is, a point where an average of gradients sampled at most distance $δ$ away has size at most $ε$. We generalize these prior techniques to handle functional constraints, proposing a subgradient-type method with similar $O(1/δε^3)$ guarantees on reaching a Goldstein Fritz-John or Goldstein KKT stationary point, depending on whether a certain Goldstein-style generalization of constraint qualification holds. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2310_03690 |
| institution | arXiv |
| publishDate | 2023 |
| record_format | arxiv |
| spellingShingle | Goldstein Stationarity in Lipschitz Constrained Optimization Grimmer, Benjamin Jia, Zhichao Optimization and Control We prove the first convergence guarantees for a subgradient method minimizing a generic Lipschitz function over generic Lipschitz inequality constraints. No smoothness or convexity (or weak convexity) assumptions are made. Instead, we utilize a sequence of recent advances in Lipschitz unconstrained minimization, which showed convergence rates of $O(1/δε^3)$ towards reaching a "Goldstein" stationary point, that is, a point where an average of gradients sampled at most distance $δ$ away has size at most $ε$. We generalize these prior techniques to handle functional constraints, proposing a subgradient-type method with similar $O(1/δε^3)$ guarantees on reaching a Goldstein Fritz-John or Goldstein KKT stationary point, depending on whether a certain Goldstein-style generalization of constraint qualification holds. |
| title | Goldstein Stationarity in Lipschitz Constrained Optimization |
| topic | Optimization and Control |
| url | https://arxiv.org/abs/2310.03690 |