Goldstein stationarity in Lipschitz constrained optimization

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/\delta \epsilon ^3)\) $O(1/\delta {ϵ}^3)$ towards reaching a “Goldstein” stationary point, that is, a point where an average of gradients sampled at most distance \(\delta \) $\delta$ away has size at most \(\epsilon \) $ϵ$ . We generalize these prior techniques to handle functional constraints, proposing a subgradient-type method with similar \(O(1/\delta \epsilon ^3)\) $O(1/\delta {ϵ}^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.