Anytime-Feasible Gradient Descent for Constrained Optimization Under Gradient Uncertainty
Abstract
Constrained optimization is central to many engineering systems in which decisions must satisfy strict safety and operational requirements, especially in real-time settings with limited computational budgets. In such scenarios, optimization algorithms are often terminated before full convergence, making *anytime feasibility* essential for safe deployment. Existing methods that guarantee feasibility at every iterate typically rely on exact gradient information, an assumption that is often violated in practice due to measurement noise, stochastic approximations, or model mismatch. We develop an anytime-feasible first-order method for nonlinear constrained optimization under norm-bounded errors in the objective and constraint gradients. The method computes a robust search direction by solving a second-order cone program and selects a step size through safeguarded backtracking. Assuming exact function evaluations and a strictly feasible initialization, the method preserves strict feasibility and guarantees sufficient objective decrease whenever the computed search direction is nonzero. We establish a uniform positive lower bound on the accepted step sizes, an O(1/K) bound on the average squared search direction norm, and convergence of the search directions to zero. We also show that a zero search direction at a strictly feasible point certifies approximate first-order stationarity. We validate the proposed method on a multi-agent navigation task in cluttered environments and show that it maintains collision-free trajectories despite noisy gradient information.
Related
- Randomized and Oracle-Based Feasible Directions Methods for Nonsmooth Nonconvex Constrained Optimization
- Can Acceleration in Gradient-Norm Minimization Be Anytime? Sharp Last-Iterate Limits in Smooth Convex Optimization
- A Stochastic Proximal-Gradient Method for Regularized Generally Constrained Continuous Optimization
- A Unified Efficient Gradient-Based Heuristic For Box-Constrained Expectation-Related and Risk-Averse Stochastic Optimization Problems
- A switching proximal gradient method for constrained difference-of-convex optimization problems
BibTeX
@misc{sharifi2026anytimefeasible,
title = {{Anytime-Feasible Gradient Descent for Constrained Optimization Under Gradient Uncertainty}},
author = {Sina Sharifi and Jiarui Wang and Mahyar Fazlyab},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2609.23848},
eprint = {2609.23848},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.23848},
}
RIS
TY - UNPB
TI - Anytime-Feasible Gradient Descent for Constrained Optimization Under Gradient Uncertainty
AU - Sina Sharifi
AU - Jiarui Wang
AU - Mahyar Fazlyab
PY - 2026
DA - 2026/09/20
PB - arXiv
DO - 10.48550/arxiv.2609.23848
UR - https://arxiv.org/abs/2609.23848
AB - Constrained optimization is central to many engineering systems in which decisions must satisfy strict safety and operational requirements, especially in real-time settings with limited computational budgets. In such scenarios, optimization algorithms are often terminated before full convergence, making *anytime feasibility* essential for safe deployment. Existing methods that guarantee feasibility at every iterate typically rely on exact gradient information, an assumption that is often violated in practice due to measurement noise, stochastic approximations, or model mismatch. We develop an anytime-feasible first-order method for nonlinear constrained optimization under norm-bounded errors in the objective and constraint gradients. The method computes a robust search direction by solving a second-order cone program and selects a step size through safeguarded backtracking. Assuming exact function evaluations and a strictly feasible initialization, the method preserves strict feasibility and guarantees sufficient objective decrease whenever the computed search direction is nonzero. We establish a uniform positive lower bound on the accepted step sizes, an O(1/K) bound on the average squared search direction norm, and convergence of the search directions to zero. We also show that a zero search direction at a strictly feasible point certifies approximate first-order stationarity. We validate the proposed method on a multi-agent navigation task in cluttered environments and show that it maintains collision-free trajectories despite noisy gradient information.
ER -