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/δε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.