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. The problem is posed in ℝd, where d denotes the dimension; constraints are specified either by a closed feasible set or by a single explicit inequality. For closed feasible sets that are star-shaped with respect to an interior ball, including all convex bodies, we use a resisting-oracle construction to show that every deterministic algorithm needs Ω(ε−2) objective-oracle calls in the worst case when d≳ε−2 and δ≲ε. For explicit inequalities satisfying uniform Goldstein constraint qualification and strict feasibility, finding Goldstein KKT stationary points requires exponentially many oracle calls in d in the worst case, even at fixed stationarity accuracy. This exponential dependence holds under dimension-independent constraint regularity and strict-feasibility bounds, with a sufficiently small neighborhood radius and complementary slackness error. The result covers common constraints such as ball and box constraints and also allows nonconvex feasible regions. For convex coercive constraints with a Slater point, the resisting-oracle argument also gives an Ω(ε−2) oracle-call bound in the same dimension and radius regime while allowing a larger complementary slackness error. These results hold for all deterministic algorithms using a local oracle, whether or not the returned point was queried. Each constructed objective has a strictly feasible global minimizer; the lower bounds therefore concern the information required to find stationary points, not their existence.
Related
- Exponential Deterministic Query Complexity of Goldstein Stationarity
- A sequential quadratic programming method for optimization with expectation objective functions, deterministic inequality constraints and robust subproblems
- Optimal Deterministic First-Order Oracle Complexity for Nonconvex-Concave Minimax Optimization
- Near-Optimal Deterministic Exact-Value Complexity for Smooth Convex Optimization
- Augmented Lagrangian methods with telescopic subproblems for MPCCs and cardinality constraints with general constraints: constraint-preserving swaps and B-stationarity
BibTeX
@misc{ding2026deterministic,
title = {{Deterministic Oracle Complexity for Goldstein Stationarity in Nonsmooth Nonconvex Optimization with Constraints}},
author = {Yixi Ding and Ya-xiang Yuan},
howpublished = {arXiv},
year = {2026},
month = nov,
doi = {10.48550/arxiv.2611.06739},
eprint = {2611.06739},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2611.06739},
}
RIS
TY - UNPB
TI - Deterministic Oracle Complexity for Goldstein Stationarity in Nonsmooth Nonconvex Optimization with Constraints
AU - Yixi Ding
AU - Ya-xiang Yuan
PY - 2026
DA - 2026/11/04
PB - arXiv
DO - 10.48550/arxiv.2611.06739
UR - https://arxiv.org/abs/2611.06739
AB - We consider the deterministic oracle complexity of finding a (δ,ε)-Goldstein stationary point of a Lipschitz function under constraints. The problem is posed in ℝ^d, where d denotes the dimension; constraints are specified either by a closed feasible set or by a single explicit inequality. For closed feasible sets that are star-shaped with respect to an interior ball, including all convex bodies, we use a resisting-oracle construction to show that every deterministic algorithm needs Ω(ε^−2) objective-oracle calls in the worst case when d≳ε^−2 and δ≲ε. For explicit inequalities satisfying uniform Goldstein constraint qualification and strict feasibility, finding Goldstein KKT stationary points requires exponentially many oracle calls in d in the worst case, even at fixed stationarity accuracy. This exponential dependence holds under dimension-independent constraint regularity and strict-feasibility bounds, with a sufficiently small neighborhood radius and complementary slackness error. The result covers common constraints such as ball and box constraints and also allows nonconvex feasible regions. For convex coercive constraints with a Slater point, the resisting-oracle argument also gives an Ω(ε^−2) oracle-call bound in the same dimension and radius regime while allowing a larger complementary slackness error. These results hold for all deterministic algorithms using a local oracle, whether or not the returned point was queried. Each constructed objective has a strictly feasible global minimizer; the lower bounds therefore concern the information required to find stationary points, not their existence.
ER -