Randomized and Oracle-Based Feasible Directions Methods for Nonsmooth Nonconvex Constrained Optimization
Abstract
Minimizing nonsmooth nonconvex objectives over general convex sets using no derivatives of the objective, together with structural access to the constraint set, poses a fundamental geometric difficulty: at boundary points, the feasible direction cone may fail to be closed, preventing the construction of finite sets of search directions that capture all feasible descent directions. We develop a feasible-directions framework for problems structured as the difference between a continuously differentiable function and a convex function over a closed convex set, and access the objective without knowledge of its decomposition, through exact line searches along feasible segments. To address the geometric obstruction, we introduce η-feasible directions, which remain uniformly separated from the boundary of the feasible direction cone, enabling finite-direction search even in the presence of nonlinear constraints. We present two algorithmic realizations of this framework. The first assumes access to an η-direction oracle and extends feasible-directions methods from linear to general convex constraints. The second replaces the oracle by a noise-augmented randomization scheme that constructs spanning directions from the affine-hull inner normal and almost surely avoids nonsmooth boundary points when initialized outside that set. Under curvature bounds and Lipschitz continuity of the smooth component's gradient, we jointly control the spanning coefficients and feasible step lengths of the oracle construction. This yields finite-time approximate d-stationarity along every unit feasible direction admitting a prescribed positive step length. For both methods, we also establish a rate in the proximal directional minimization (PDM) measure, assuming uniformly bounded direction-set sizes. Randomized exploration ensures that, almost surely, every accumulation point is d-stationary.
Related
- The Complexity of Finding Stationary Points in Nonsmooth Nonconvex Optimization
- Proximal Limited-Memory Quasi-Newton Methods for Nonsmooth Nonconvex Optimization
- Variable Bregman Majorization-Minimization algorithms for nonconvex nonsmooth optimization, with application to Poisson imaging
- A sequential regularized piecewise affine algorithm for nonconvex nonsmooth multicomposite optimization in RNN training
- The Exponential Price of Determinism in Nonsmooth Nonconvex Optimization
BibTeX
@misc{greenstein2026randomized,
title = {{Randomized and Oracle-Based Feasible Directions Methods for Nonsmooth Nonconvex Constrained Optimization}},
author = {Dan Greenstein and Nadav Hallak},
howpublished = {arXiv},
year = {2026},
month = nov,
doi = {10.48550/arxiv.2611.07691},
eprint = {2611.07691},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2611.07691},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - Randomized and Oracle-Based Feasible Directions Methods for Nonsmooth Nonconvex Constrained Optimization
AU - Dan Greenstein
AU - Nadav Hallak
PY - 2026
DA - 2026/11/05
PB - arXiv
DO - 10.48550/arxiv.2611.07691
UR - https://arxiv.org/abs/2611.07691
AB - Minimizing nonsmooth nonconvex objectives over general convex sets using no derivatives of the objective, together with structural access to the constraint set, poses a fundamental geometric difficulty: at boundary points, the feasible direction cone may fail to be closed, preventing the construction of finite sets of search directions that capture all feasible descent directions. We develop a feasible-directions framework for problems structured as the difference between a continuously differentiable function and a convex function over a closed convex set, and access the objective without knowledge of its decomposition, through exact line searches along feasible segments. To address the geometric obstruction, we introduce η-feasible directions, which remain uniformly separated from the boundary of the feasible direction cone, enabling finite-direction search even in the presence of nonlinear constraints. We present two algorithmic realizations of this framework. The first assumes access to an η-direction oracle and extends feasible-directions methods from linear to general convex constraints. The second replaces the oracle by a noise-augmented randomization scheme that constructs spanning directions from the affine-hull inner normal and almost surely avoids nonsmooth boundary points when initialized outside that set. Under curvature bounds and Lipschitz continuity of the smooth component's gradient, we jointly control the spanning coefficients and feasible step lengths of the oracle construction. This yields finite-time approximate d-stationarity along every unit feasible direction admitting a prescribed positive step length. For both methods, we also establish a rate in the proximal directional minimization (PDM) measure, assuming uniformly bounded direction-set sizes. Randomized exploration ensures that, almost surely, every accumulation point is d-stationary.
ER -