no. 16 · Tuesday 17 November 2026
Deterministic Oracle Complexity for Goldstein Stationarity in Nonsmooth Nonconvex Optimization with Constraints
Abstract
We consider the deterministic oracle complexity of finding a $(δ,ε)$-Goldstein stationary point of a Lipschitz function under constraints. Our main result concerns products of convex bodies. Each block contains an inner ball and lies in a concentric outer ball. The inner radii have a common positive lower bound, and each outer radius is at most a fixed multiple of the corresponding inner radius. This class includes common constraints such as balls and boxes. On each prescribed feasible set of dimension $d$ in this class, every deterministic algorithm using a local oracle needs $\exp(Ω(d))$ objective-oracle calls in the worst case at fixed, sufficiently small accuracies $δ$ and $ε$. The objective Lipschitz and initial objective-value gap bounds are fixed, and each constructed function has a global minimizer in the interior of the feasible set. For broader classes of constraints, supplementary results show that every deterministic algorithm needs $Ω(ε^{-2})$ objective-oracle calls in the worst case when $d\gtrsimε^{-2}$ and $δ\lesssimε$. The constants depend on the interior-ball radius and, for inequalities, the local Lipschitz and Slater bounds. These supplementary results cover closed sets that are star-shaped with respect to a ball and convex coercive inequalities with a Slater point, and hold even for convex objectives.
- comments
- 29 pages, no figures. Substantially revised, with a new exponential lower bound for set-constrained Goldstein stationarity, revised results for inequality constraints, and comparisons of constrained stationarity criteria. References updated
- fields
- Optimization and Control